A few test cases with bad triangulations

[mourner]

Processed ~5 million polygons from a Mapbox Terrain subset and found just 79 cases with deviations that are not fixed by filtering out collinear points (fix-alt branch): https://gist.github.com/mourner/738f8ff6c7dae5a1144e (for reference, it's 159 on master without filtering).

edit: it's down to 4 failing cases with the latest patches.

This is a great set of cases to investigate and fix remaining Earcut issues. A lot of them seem to be about rings sharing a point (edges touching by an endpoint).

I'll look into them in the next few days but any help is appreciated too. cc @hjanetzek @mrgreywater

The biggest failing sample looks like this (it's a hole on the left):

[mourner]

The script I used to test polygons in vector tiles: https://github.com/mapbox/earcut-reduce
It's very fast – takes 23 seconds to process 5 million polygons in a sample tileset (it's using all available CPU cores) .

[hjanetzek]

@mourner that's a good regression test-suite! Currently busy getting things finished before vacation, but I'll get back to it. Could you extract the failing polygons - or failing tiles? I don't have the full mapbox tileset here :)

The above polygon should be handled by case 3 in Eberly's algorithm.

[mourner]

@hjanetzek the failing polygons are extracted in the gist I linked above.

[mourner]

Yeah, it finds a bad connection that's equal to an edge in this particular case:

[mourner]

@hjanetzek @flippmoke @jakepruitt fixing the 3rd Eberly algorithm case with cf5f2f1 brings us down from 79 to 28 failures, without collinear filtering. \o/

Updated the gist with new failures, looking further...

[mrgreywater]

The simplest broken testpolygon (without collinear points) that I was able to create is this one:
[ [ [18,0], [18,12], [0,12], [2,8], [4,0] ], [ [3,5], [8,10], [8,5] ], [ [12,2], [12,4], [14,4] ] ]

Notice there are no connections to [8,10] and [8,5] whatsoever.

I might look into it over the weekend, when I have more time.

[mourner]

The latest commit fixes cureLocalIntersections routine for edges with shared endpoints, and that brings the amount of failures down to 12! 😍 @mrgreywater fixes you test case above too. Updated the gist.

[mourner]

Reduced test case for a part of the remaining problems:

[[[440,4152],[440,4208],[296,4192],[368,4192],[400,4200],[400,4176],[368,4192],[296,4192],[264,4200],[288,4160],[296,4192]]]

[mourner]

Fixed the case above with d13c8dc and it's down to 4 bad cases! 🚀

[mourner]

Damn, this one is tough:

[
[[4224,1776],[4224,2064],[4200,2088],[4184,2080],[4168,2112],[4136,2104],[4136,2072],[4072,2096],[4072,2128],[4032,2160],[4032,2184],[4064,2184],[4064,2200],[4040,2208],[4040,2240],[3992,2280],[3936,2280],[3928,2336],[3888,2376],[3880,2408],[3864,2408],[3864,2432],[3888,2440],[3920,2440],[3968,2408],[3976,2464],[3960,2472],[3960,2496],[3976,2496],[3976,2528],[4000,2528],[4024,2488],[4064,2504],[4056,2536],[4032,2536],[4032,2576],[4056,2584],[4056,2624],[4024,2656],[3944,2672],[3888,2736],[3848,2712],[3840,2768],[3800,2800],[3784,2960],[3744,2976],[3760,3000],[3744,3048],[3768,3144],[3760,3200],[3768,3240],[3792,3256],[3784,3320],[3752,3328],[3688,3248],[3672,3200],[3632,3168],[3632,3104],[3600,3024],[3608,2944],[3648,2864],[3648,2832],[3624,2808],[3632,2728],[3648,2728],[3688,2672],[3672,2560],[3728,2528],[3728,2496],[3712,2496],[3704,2464],[3704,2288],[3728,2168],[3744,2128],[3768,2120],[3768,2088],[3792,2088],[3816,2064],[3840,2064],[3848,2080],[3888,2072],[3920,2024],[3968,2032],[3968,2016],[4000,2008],[4032,1968],[4008,1928],[4096,1896],[4096,1792],[4120,1752],[4144,1744],[4152,1680],[4224,1624],[4224,1776]],
[[3816,2616],[3800,2624],[3808,2656],[3840,2632],[3840,2616],[3816,2616]],
[[3728,2632],[3760,2632],[3752,2592],[3728,2632]],
[[3968,2552],[3960,2568],[3936,2600],[3952,2624],[3992,2600],[3992,2560],[4008,2560],[4008,2544],[3968,2552]],
[[3768,2472],[3752,2520],[3768,2552],[3752,2592],[3768,2568],[3816,2568],[3840,2552],[3832,2488],[3808,2464],[3768,2472]],
]

Basically the bug seems to sometimes happen when a hole bridge routine takes a segment that was previously another hole connection, takes the wrong of the two matching segments, and hole elimination rewires the polygon in some invalid way. I've been trying to fix this with locallyInside checks when looking for the closest left segment, but while it fixes this case, it breaks hundreds of others.

[mrgreywater]

Great progress so far!
Went ahead and reduced the testcase above, might make debugging easier:

[[[11,10],[0,10],[0,0],[11,0]],[[7,6],[7,9],[10,9]],[[7,5],[10,2],[10,5]],[[6,9],[1,4],[1,9]],[[1,1],[1,4],[4,1]]]

[mourner]

@mrgreywater thanks for reducing, this is indeed much easier to reason about!

[mourner]

It looks like all 4 remaining problems have the same look like the above reduced case. However I'm out of ideas for fixing them for now — I thought the most promising fix would be to just check if the node found by the findHoleBridge routine is in the same spot as the P point from the Eberly algorithm, and if it is, use P as the connection instead. And while if fixes this particular case, it fails on a lot of other cases (the amount of failures on the 5 million test set jumps to 600+).