Hole connection bug

[mourner]

Test case:

[
[[1920,552],[1904,616],[1912,664],[1984,672],[2008,712],[1944,720],[1904,760],[1896,800],[1856,760],[1824,768],[1824,832],[1864,864],[1888,864],[1904,936],[1936,944],[1936,1064],[1936,1112],[1872,1136],[1856,1160],[1840,1144],[1792,1152],[1784,1112],[1752,1096],[1608,1096],[1600,1064],[1640,1040],[1664,992],[1640,968],[1568,1024],[1560,1056],[1480,1048],[1440,1072],[1440,1032],[1400,1032],[1400,1088],[1336,1136],[1320,1136],[1264,1072],[1232,1080],[1240,1104],[1200,1096],[1232,1048],[1272,1032],[1272,1000],[1232,1024],[1176,1024],[1176,1000],[1248,952],[1344,944],[1352,904],[1424,880],[1448,848],[1496,840],[1512,800],[1568,760],[1616,752],[1640,640],[1680,600],[1736,592],[1776,560],[1776,536],[1840,464],[1848,400],[1888,328],[1952,264],[2000,240],[2040,240],[2040,264],[1968,376],[1912,424],[1936,512],[1920,528],[1880,528],[1872,552],[1920,552]],
[[1608,800],[1576,848],[1520,840],[1512,872],[1456,904],[1440,952],[1528,936],[1552,912],[1584,912],[1608,880],[1664,864],[1680,816],[1656,776],[1608,800]],
[[1720,792],[1736,792],[1720,780],[1720,792]],
[[1656,728],[1670,752],[1672,728],[1656,728]],
[[1712,680],[1696,720],[1720,728],[1736,704],[1736,680],[1712,680]],
[[1968,712],[2000,712],[1968,688],[1968,712]]
]

It looks like this happens when a hole connects to outer polygon, then another hole connects to that hole through the same vertice, but since there are two vertices after eliminating the hole, one of the two connections leads to a broken outline. Should be fixable with some more checks in the findHoleBridge routine.

cc @flippmoke @hjanetzek @jakepruitt

[hjanetzek]

Not sure if this is the solution or just removes the trigger:

            list = getLeftmost(list);
            while (equals(list, list->next) && list != list->next) { removeNode(list->next); }
            while (equals(list, list->prev) && list != list->next) { removeNode(list->prev); }
            if (list == list->next) list->steiner = true;
            queue.push_back(list);

This still finds the same bridge-node in the outer ring, so I guess the problem lies somewhere in not filtering enough points after the split.

[mourner]

Interesting, I didn't think it would be related to filtering.

[hjanetzek]

Another observation: the overlapping triangle is inserted after the first 'fallback' split, where the chosen diagonal is the same as the bridge for the left hole (cyan line). When duplicates are filtered out in advance no extra passes are needed.

I think in general it would make sense to filter out duplicate consecutive points since most predicates depend on the signedness of the triangle's area which seems hard to always get right with 0 area triangles.

[mourner]

@hjanetzek filtering was there earlier, the reason it was dropped recently is discussed in #41. Do you think we should bring it back? Or could we fix it with a more targeted filtering, like in the split routine? https://github.com/mapbox/earcut/blob/master/src/earcut.js#L238-L240

[hjanetzek]

@mourner in my opinion it would be better to filter out duplicate points and colinear segments in advance and have an extra mode to skip filtering.
In this particular case the wrong triangulation seem to be caused by locallyInside returning true for zero area triangles around a. If one allows duplicate consecutive points, locallyInside would have to search for the next and previous different points. Colinear segments also need some special handling for locallyInside I guess.

One way to fix this triangulation is to ensure that p is reflex. (also I cannot directly see how locallyInside should guarantee that p is reflex which is required in Eberly's algorithm)

            if ((tan < tanMin || (tan === tanMin && p.x > m.x)) &&
                area(p.prev, p, p.next) > 0 &&
                locallyInside(p, hole)) {
                m = p;
                tanMin = tan;
            }

[mourner]

@hjanetzek interesting! The area(p.prev, p, p.next) > 0 condition causes a spectacular fail in the touching-holes case, however replacing > with !== fixes the current issue while not introducing failures. Not sure if it's right though.

I tried your suggestion to not consider duplicate vertices in locallyInside check and it also fixes the issue: 736de1a

Should we do one of these, revert the point filtering change, or try to figure out a more sophisticated fix? I'm not sure.

[hjanetzek]

@mourner reflex is said to be required by Eberly and seems to make sense for a valid connection. I guess checking != there just causes to pick a lucly splitPolygon fallback.

But the zero area case in locallyInside should certainly be avoided :)

[mourner]

@hjanetzek want to show the proposed fix (reflex angle check + locallyInside fix) in a PR?

[mourner]

BTW, if we bring back duplicate/collinear point filtering prior to hole elimination and trinagulation, together with the reflex check, the touching holes case still fails hard. Or is this related to an edge locallyInside case?

[hjanetzek]

@mourner I'm not sure what the best solution for this issue is.
The reflex property for findHoleBridge case 6 should already be ensured by minimizing the angle I think. But for degenerate Polygons one cannot tell.
I would add this test-case and the area != 0 fix + a note that it should be > 0

That touching-holes fails with filtering in advance is rather a problem in splitEarcut: It causes to pick a split that cannot be successful. You can test it by dumping the rings after the split

[[3761, 2053], [3694, 2061], [3708, 2079], [3712, 2079], [3714, 2076], [3719, 2079], [3722, 2079], [3718, 2088], [3723, 2089], [3738, 2081], [3745, 2095], [3761, 2099], [3777, 2082], [3774, 2071], [3748, 2088], [3749, 2062], [3738, 2081], [3723, 2089], [3734, 2075], [3730, 2068], [3717, 2065], [3708, 2079], [3694, 2061], [3794, 2035], [3773, 2067]]

[[3812, 2123], [3784, 2123], [3708, 2139], [3694, 2061], [3712, 2109], [3715, 2125], [3723, 2128], [3740, 2124], [3752, 2109], [3740, 2102], [3780, 2106], [3788, 2114], [3797, 2101], [3787, 2096], [3740, 2102], [3712, 2109], [3694, 2061], [3706, 2091], [3712, 2097], [3719, 2094], [3721, 2102], [3734, 2099], [3732, 2091], [3719, 2094], [3712, 2097], [3721, 2080], [3719, 2079], [3712, 2079], [3706, 2091], [3694, 2061], [3753, 2061], [3753, 2071], [3756, 2075], [3773, 2067],  [3794, 2035]]

[mourner]

@hjanetzek it's hard to choose which option is the best fix because we can't make a decision based on one failing test (which can be affected by a lot of things). So I made three branches fix-locally-inside, fix-alt and fix-alt-2 which we're going to run on a bunch of Mapbox Streets vector tiles and see how the number of failures with each compares to master.

[mourner]

@hjanetzek we ran some samples on 4 branches and looks like we have a winner here — https://gist.github.com/jakepruitt/5d8a834e6054d5f4265e

While exploring the results, I suddenly discovered a bug in the current earcut master — it doesn't filter out the last point if it's equal to the first one when making an initial linked list. Fixing it fixes the issue above too.