Existing test case with wrong result

[bluenote10]

While preparing a fix for #110 I noticed that there is currently a test case, which tests for a wrong intersection result (input left, output right):

Also notice that the result polygon ring isn't closed. There is a similar problem when computing the union:

My solution for #110 works in all other tests but "breaks" this case, but it also doesn't fix it. I'll try and see if I can fix both. But maybe this is because the case is also affected by output edge connecting logic, and requires @rowanwins's fixes in #113.

[rowanwins]

Hi @bluenote10

Feel free to put the PR in even if it breaks a test case, we might be able to help debug what's going on. Also worth noting that in my #113 PR I fixed a few test cases which were incorrect so it maybe that your PR isn't actually breaking anything.

Anyway put in the PR and then someone can review.

Cheers

[bluenote10]

I think this problem is caused by an inconsistency of compare_segments and segment_intersection:

• From the image it looks like the lower left point of the blue rectangle falls exactly on top of the diagonal yellow line. However in compare_segments when computing the signedArea of this point w.r.t. the yellow segment, we don't get a zero. Rather the result is that the point is slightly to the lower left of the yellow line. Thus, in the sweep line the blue segment is inserted at the bottom below the yellow segment.
• This would be fine if the intersection check with its upper neighbor would properly subdivide both segments -- just a very tiny one for the first part of the blue segment. However, the intersection check returns exactly the starting point of the blue segment, so there is nothing we can divide here. From here on the algorithm is bound to fail, because it didn't detect that the blue segment went on top of the yellow one.

I think the solution to this issue is to make the two consistent: The intersection check must return a non-endpoint if and only if the signedArea is non-zero. Since signedArea is based on robust predicate's orient2d it should probably considered "ground truth" for the check, and we may have to adapt the intersection logic.

To verify the hypothesis I have moved the vertical segment a little bit to the left here so that segment comparison and intersection check are consistent, and then it works fine:

In conclusion, this is different to #110 which deals with the case where the endpoint falls exactly on the other segment (i.e., signedArea is also zero there), and probably it is best to have two separate PRs, with a temporary adaption of the test case result.

[rowanwins]

Wow good digging @bluenote10 - looking forward to checking out the PR!

[bluenote10]

@w8r In case you are interested, I have PR for this in Rust here: 21re/rust-geo-booleanop#13

[rowanwins]

More very thorough work thanks @bluenote10 - I hope you are finding computational geometry an enjoyable rabbit hole because you are very good at it!

[bluenote10]

@rowanwins Haha thanks! Yes, indeed quite a rabbit hole, but an enjoyable one. No talent really, just a fondness for tedious debugging ;).