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

[svenboulanger]

I'm working on my own implementation of the Martinez paper, and I started there from the original implementation in C++ that they published (I need integer coordinates). Since I was having the same issue: here's what I tracked what was going wrong:

When the status line reaches point (120, 210), the line segments starting at (120,210) are incorrectly inserted between segment (111,228)-(129,192) and (80,300)-(115,96). This causes the segments to have the wrong neighbors.

So what likely needs work, is the segment comparer. I noticed that you're using a comparer somewhat similar to the C++ version so I'm guessing that's also going to apply here. When I made sure the segment comparer ordered them correctly for this one use case, the correct result was being computed.

[w8r]

Thank you so much ! I will try that

On Fri, 19 May 2023 at 22:25, Sven @.***> wrote:

I'm working on my own implementation of the Martinez paper, and I started there from the original implementation in C++ that they published (I need integer coordinates). Since I was having the same issue: here's what I tracked what was going wrong:

When the status line reaches point (120, 210), the line segments starting at (120,210) are incorrectly inserted between segment (111,228)-(129,192) and (80,300)-(115,96). This causes the segments to have the wrong neighbors.

So what likely needs work, is the segment comparer. I noticed that you're using a comparer somewhat similar to the C++ version so I'm guessing that's also going to apply here. When I made sure the segment comparer ordered them correctly for this one use case, the correct result was being computed.

— Reply to this email directly, view it on GitHub https://github.com/w8r/martinez/issues/110#issuecomment-1555198208, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAAGSBFCZSHJ4FRJTFJKU2DXG7JKXANCNFSM4KAIIFEQ . You are receiving this because you were assigned.Message ID: @.***>