search

mapbox / delaunator

An incredibly fast JavaScript library for Delaunay triangulation of 2D points
https://mapbox.github.io/delaunator/
ISC License
2.24k stars 139 forks source link

How to get hull's halfedges ? #75

Open w77 opened 2 years ago

w77 commented 2 years ago

How to get hull's halfedges ? Is there anything to get them directly or must I check all edges around hull's points ? I need this to close the triangulation on a sphere. The last triangles are made with a pole in sterographic projection connected to each hull's edge. This pole/point is removed before running delaunator then added after and so all new triangles with this new point.

hull give points but hulltri, hullhash, hullnext and hullprev are not related to hull's actual edges.

redblobgames commented 2 years ago

All the halfedges that don't have an opposite are on the hull. That doesn't put them in order. But if you find any one of these halfedges without an opposite, A→B, then there should be only one halfedge B→ that doesn't have an opposite, and that will be the next one in the hull. You can keep following the chain until you get back to A, I think.

Fil commented 2 years ago

For a spherical delaunay, you can also check https://github.com/Fil/d3-geo-voronoi (it uses delaunator internally, with the stereographic projection).

w77 commented 2 years ago

For a spherical delaunay, you can also check https://github.com/Fil/d3-geo-voronoi (it uses delaunator internally, with the stereographic projection).

Oui je connais mais je ne comprend pas leur code. Le miens est beaucoup plus simple et marche aussi bien, sauf pour la fin.