search

mapbox / earcut

The fastest and smallest JavaScript polygon triangulation library for your WebGL apps
ISC License
2.21k stars 207 forks source link

infinite loop - polygon subtraction #142

Closed mataron closed 2 years ago

mataron commented 4 years ago

Hi,

I get an infinite loop when processing the following data: earcut([5.62675358811389, 31.94879819160804, -16.369709114391867, 28.341954255099814, -10.786562672455382, -1.2779295357476745, 10.819423740334923, 2.069348113719755, 3.220439475288522, 4.197526331591453, 5.024815373142793, 1.1716264034331543, 10.819423740334923, 2.069348113719755, 5.62675358811389, 31.94879819160804, -16.369709114391867, 28.341954255099814, -10.786562672455382, -1.2779295357476745, -6.833718161055838, -0.6655405509524673, -8.602352370111433, 2.142874784407777, -5.34630560403934, 6.768689248602321, -1.4053749889060216, 7.453573097663546], [4])

The "outer" polygon is a rectangle-like shape and the hole covers most of its area, but a small portion on one side. Therefore, it is more of a subtract operation, than an extract hole one.

I am not sure if this is the intended use of earcut, but is successfully handles numerous similar cases.

Any insights?

mourner commented 2 years ago

Apologies for not addressing this for so long — #157 appears to fix the infinite loop bug. The result is still one triangle off, but that could be fixed as a separate issue.