Crash in Earcut::findHoleBridge about earcut.hpp HOT 11 CLOSED

I'll look into the issue, some vertex data to reproduce the crash would be perfect.

This is likely related to mapbox/earcut#87

from earcut.hpp.

Earcut::filterPoints may return nullptr in case it reduces the polygon into a point

Note that it should never return null — in the case of a point, it will return the pointer to that point's node. Also looks related to mapbox/earcut#83

from earcut.hpp.

Earcut::filterPoints may return nullptr in case it reduces the polygon into a point

Note that it can never return null — in the case of a point, it will return the pointer to that point's node. So the cause must be something else.

Not sure what you mean. As far as I understand it, the code from filterPoints below checks whether the current edge is degenerate, or the two adjacent edges are colinear, and in such case removes the middle node. After this elimination it checks if the current node is same node as next node, and returns nullptr;

If p == p->next, then isn't the polygon just a point?

        if (!p->steiner && (equals(p, p->next) || area(p->prev, p, p->next) == 0)) {
            removeNode(p);
            p = end = p->prev;

            if (p == p->next) return nullptr;
            again = true;

        } else {
            p = p->next;
        }

from earcut.hpp.

I'll look into the issue, some vertex data to reproduce the crash would be perfect.
This is likely related to mapbox/earcut#87

Looks like the same issue, I agree!

Below is one example polygon which causes the issue:

0:
    -32, 493
    -32, 444
    0, 440
    6, 487
1:
    -32, 501
    -13, 645
    -32, 648
2:
    -32, 493
    -32, 444
    0, 440
    6, 487
3:
    -32, 501
    -13, 645
    -32, 648
4:
    -32, 493
    -32, 444
    0, 440
    6, 487
5:
    -32, 501
    -13, 645
    -32, 648
6:
    -32, 493
    -32, 444
    0, 440
    6, 487
7:
    -32, 501
    -13, 645
    -32, 648
8:
    -32, 493
    -32, 444
    0, 440
    6, 487
9:
    -32, 501
    -13, 645
    -32, 648
10:
    -32, 493
    -32, 444
    0, 440
    6, 487
11:
    -32, 501
    -13, 645
    -32, 648

from earcut.hpp.

@huhtanen yeah my bad, I missed this line https://github.com/mapbox/earcut.hpp/blob/master/include/mapbox/earcut.hpp#L235

from earcut.hpp.

replacing return nullptr; with break; (or the equivalent return p;) should do the trick, but it's probably better to check the changes with a larger test set than we have hardcoded here.

from earcut.hpp.

replacing return nullptr; with break; (or the equivalent return p;) should do the trick, but it's probably better to check the changes with a larger test set than we have hardcoded here.

In that case should the below nullptr check be if (ear == ear->next), or should it simply be removed?

template <typename N>
void Earcut<N>::earcutLinked(Node* ear, int pass) {
    if (!ear) return;

eliminateHoles could also early exit by checking every iteration if p == p->next, instead for p == nullptr, but then again, it might not be common enough case to warrant for extra checks.

from earcut.hpp.

@huhtanen Neither. earcutLinked will not do anything if ear == ear->next anyway. But checking for a nullptr is required for code sanity reasons, even if it might never happen.

from earcut.hpp.

@mrgreywater are you looking into a fix? I guess always treating 1-point holes as if they were Steiner points (and never returning null in filterPoints) seems like a good solution.

from earcut.hpp.

I am, but I want to rewrite the test generating script first, to allow additional tests for earcut.hpp that aren't in earcut.js. I don't want to merge the fix without having a testcase that actually confirms it's working.

from earcut.hpp.

So I rewrote the tests to be auto registering, which allows custom (manually written) tests without risking them to be overwritten by the script.
Interestingly after I added the patch, the new test case also gave out some new undefined behaviour warnings which we will have to look into.

/home/travis/build/mrgreywater/earcut.hpp/include/mapbox/earcut.hpp:606:60: runtime error: division by zero
/home/travis/build/mrgreywater/earcut.hpp/include/mapbox/earcut.hpp:606:38: runtime error: value -nan is outside the range of representable values of type 'int'
/home/travis/build/mrgreywater/earcut.hpp/include/mapbox/earcut.hpp:607:60: runtime error: division by zero
/home/travis/build/mrgreywater/earcut.hpp/include/mapbox/earcut.hpp:607:38: runtime error: value -nan is outside the range of representable values of type 'int'
/home/travis/build/mrgreywater/earcut.hpp/include/mapbox/earcut.hpp:609:17: runtime error: left shift of negative value -2147483648
/home/travis/build/mrgreywater/earcut.hpp/include/mapbox/earcut.hpp:614:17: runtime error: left shift of negative value -2147483648

from earcut.hpp.