search

jhasse / poly2tri

2D constrained Delaunay triangulation library
BSD 3-Clause "New" or "Revised" License
429 stars 89 forks source link

Crash with a simple polygon #11

Open wonder-sk opened 4 years ago

wonder-sk commented 4 years ago

https://github.com/jhasse/poly2tri/commit/e0ba327ed83f3e32933cf6cc4f61fabc50191711 caused a regression - this simple polygon will now crash during triangulation:

0 0 -5 -3e-10 -10 -2e-10 -10 -4 0 -4

From what I understand, Edge maintains invariant that p1.y < p2.y and in case p1.y == p2.y then p1.x < p2.x. However if the 1e10 tolerance is used for comparison of Y coordinates, this invariant is broken for the second edge and the subsequent code crashes later during triangulation.

I would therefore suggest rolling back that commit...

jhasse commented 4 years ago

We should add a test case for that polygon.