search

mapbox / earcut.hpp

Fast, header-only polygon triangulation
ISC License
858 stars 133 forks source link

Endless loop in the filterPoints function #92

Closed shlem closed 2 years ago

shlem commented 3 years ago

Hi You wrote an excellent library. It is very easy to use and fast. I included it to my project to triangulate ESRI geo shape files and everything worked well till I found a problematic file. After a few hours of debugging I found and fixed (hope!) the problem. With the following integer data (one outer polygon with one hole).

878 412 878 413 878 412 879 412 878 412 879 412 880 412 879 412 880 412 879 412 879 413 880 413 880 412 880 413 879 413 878 413 878 412 878 413 879 413 879 412 878 412 879 412 878 412 879 412 879 413 878 413 878 412 878 413

the filterPoints function goes to endless loop. It seems to me that it is not good idea to call this function and don't get result, because the first node can be removed and disconnected from the linked list.

I know that this is a very degenerated case, but I got it when render a small polygon in a big zoom

My fix as follows:

  1. Comment two lines in eliminateHole() function //!! filterPoints(outerNode, outerNode->next); //!! filterPoints(b, b->next);

  2. Add one line in Earcut::operator() function after optional call to eliminateHoles() function outerNode = filterPoints( outerNode ); //!! filter the entire polygon

mrgreywater commented 3 years ago

The issue should be resolved with the current version. Could you please check again?