Not the right intersection

[jonathanlurie]

Hello,
I have a case where I intersect 2 convex polygons and the result of the intersection is not correct. Here is a piece of code:

var poly1 = [[175, 105],
                [130, 60],
                [210, 45],
                [215, 65]];

    var poly2 = [[256, 106],
                [207.14285714285714, 57.14285714285714],
                [215, 0],
                [256, 0]];

var intersection = greinerHormann.intersection(poly1, poly2);
/*
gives:
[208.78107457898957, 45.22854851643946],
[210, 45],
[215, 65],
[175, 105], <-- should not be here, belongs to poly1 only
[130, 60], <-- should not be here, belongs to poly1 only
[208.78107457898957, 45.22854851643946]

While it should give:
[207.14285714285714, 57.14285714285714],
[208.78107457898957, 45.22854851643945],
[210, 45],
[215, 65]

I am not sure what's going wrong, and if I use .intersection(poly2, poly1) instead of .intersection(poly1, poly2), it gives me two points of poly2 that should not be there either.

To get the proper result I used PolyBool js, which is 2.5x slower...
Cheers.
Jo.

[w8r]

Unfortunately, Greiner-Hormann algorithm cannot handle degenerate cases, e.g. when intersections are falling on the edges of the polygon, or vertices coincide.

I changed a point in your polygon slightly to get the correct shape, that's the technique that is suggested to treat cases like that with this algorithm.

[256, 106] → [256, 106.00001]
https://codepen.io/w8r/pen/aawKrE