Polygon subtraction creates degenerate result polygon

[BadIdeaException]

With the below polygons, subtracting S from T creates a degenerate result polygon: Instead of splitting the result into two polygons at vertex 3, it creates a single polygon with vertex 3 sitting on the edge connecting vertex 0 and 1.

I'm not sure if this is intended behavior? With other vertex-on-edge scenarios, result polygons always get split up correctly, so I think this is probably a bug.

var polybooljs = require("polybooljs")

const T = {
    inverted: false,
    regions: [[
        [ 3.1827730120236866, -14.647299060696893 ],
        [ 3.292779172743269, -14.709442780204576 ],
        [ 3.2790977409099513, -15.096879410975502 ]
    ]]
};
const S = {
    inverted: false,
    regions: [[
        [ 3.3984917402267456, -14.277922392125454 ],
        [ 3.3984917402267456, -14.919993494289331 ],
        [ 3.2411990917407074, -14.919993494289326 ]
    ]]
};
polybooljs.difference(T,S) // {   regions: [[
                           //         [ 3.1827730120236866, -14.647299060696893 ],
                           //         [ 3.2790977409099513, -15.096879410975502 ],
                           //         [ 3.2853440594539682, -14.919993494289328 ],
                           //         [ 3.2411990917407074, -14.919993494289326 ],
                           //         [ 3.292779172743269, -14.709442780204576]
                           //     ]],
                           //     inverted: false    }

Here is a graphical representation of T and S:

[velipso]

I haven't tried running your code, but just looking at the points, this jumps out to me:

        [ 3.3984917402267456, -14.919993494289331 ],
        [ 3.2411990917407074, -14.919993494289326 ]

Notice that the Y coordinates are nearly the same, but not exactly the same. This can cause issues with the floating point precision.

There is a PR here that aims to improve the epsilon logic. You could try applying that patch.

Alternatively, you could round your points before sending them to polybooljs so that they are guaranteed to be the same Y coordinate. For example:

polygon.regions.forEach((region) => {
  region.forEach((pt) => {
    pt[0] = Math.round(pt[0] * 1000) / 1000;
    pt[1] = Math.round(pt[1] * 1000) / 1000;
  });
});

I'm curious if that works for you.

[BadIdeaException]

Hey,

sorry it took so long to get back to you. I somehow missed the GitHub notification about your response, and then since then things have been pretty hectic in my personal life. Even so, I appreciate your super-quick response.

Regarding your suggestions:

• The PR does not solve my issue.
• Rounding the points does work with a factor of 1000. This is the lowest possible factor (that is a power of 10) with which this works, with 100 it doesn't. (Here's a link to the playground I've been using for this, btw.)
• I also tried manually changing the ...326 to ...331 on the last point, which - surprisingly - does not work.

So rounding the points does work. I am a little surprised that it should be necessary, though - after all, this is why we have epsilon logic in the first place, isn't it? The difference between those y-coordinates is ~5e-15, which seems small enough that it should get swallowed.

[mikhaelmartin]

i'm facing the same problem today. Showed by the demo screenshot below resulting a single polygon. It occurs sometimes when there are 2 point are sitting on edge or point of either polygons.

but it is not always the case. i move a point a bit and it give correct result, 2 polygons

I suspect the bug happens when the chainer choose a segment with overlapping points as a starting segment