search

mapbox / delaunator

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

Fix a halfedges race condition #12

Closed mourner closed 7 years ago

mourner commented 7 years ago

Closes #11. cc @redblobgames

Not the most elegant fix but should do the trick. The bug was in the way I tracked halfedge ids associated with convex hull's edges — when an opposing edge of a flipped quad also belonged to the convex hull (usually in the very beginning of a triangulation), flipping would invalidate the associated adjacent edge id of that edge.

redblobgames commented 7 years ago

Great — thank you! I've been trying lots of random point sets and the opposite-edge test is now passing with all of them.