Wrong result for two simple polygons

[abelramos]

These are my two simple polygons:

with coordinates:

[[115,96], [140,206], [120,210], [125,250], [80,300]]
[[111,228], [129,192], [309,282]]

And this is the resulting union:

There are no vertical edges, in fact, no two points share the same x-coordinate. I believe the issue here is with the otherInOut property not being correctly computed as these are the sweep events with otherInOut set to true after the subdivision step:

I also tried with the C++ code available online from the original paper, and the resulting union is the same.

[w8r]

Thanks for the detailed example and the C++ reference, I will try and figure it out

[jakeNiemiec]

@abelramos Until this gets fixed, I have found that adding very small (like 0.0005), pseudorandom values to the coordinates will prevent this. The problem occurs when a point falls exactly on another line. Our app has grid snapping, I can confirm that this happens all the time.

[bluenote10]

I have tested this case with polybooljs (another implementation of the Martinez algorithm) and there it seems to work:

Input:

Output:

So maybe it helps to have a look where the implementations differ.

[w8r]

It's not exactly the same algorithm, but thanks for the reference!

[bluenote10]

I also tried with the C++ code available online from the original paper...

It's not exactly the same algorithm

Ah interesting, I was wondering about that already. What is this implementation here actually based on? I've found three "original" versions of the Martinez algorithm:

• the 2008 paper, version cageo141 available as mirror on GitHub.
• the 2008 paper, version cageo144 available from the Martinez home page (first link).
• the 2013 paper, available from the Martinez home page (last link).

[w8r]

it's the last one

[abelramos]

@abelramos Until this gets fixed, I have found that adding very small (like 0.0005), pseudorandom values to the coordinates will prevent this. The problem occurs when a point falls exactly on another line. Our app has grid snapping, I can confirm that this happens all the time.

Exactly. I can also confirm it is not related to floating-point arithmetic and/or epsilon values, I tested the implementation with a type for rational numbers, and the issue remains.

[abelramos]

I have tested this case with polybooljs

Yes, I tried with that one too. It works. However, I believe this implementation is faster than the other one, that's why I'm interested in a fix for this one.

[daef]

afair the other one uses only linked lists (instead of a tree), plus solid improvements don't seem to get merged for... reasons

[w8r]

I would love to get some help here, I didn't have time to look at it recently

[bluenote10]

afair the other one uses only linked lists (instead of a tree)

Exactly, I came to the same conclusion here after reading the code a bit.

I would love to get some help here, I didn't have time to look at it recently

I'd like to have a look, but I don't have access to the paper :(.

[rowanwins]

@bluenote10 if you send me an email me at rowanwinsemius dot id dot au , then I can supply the paper