search

georust / geo

Geospatial primitives and algorithms for Rust
https://crates.io/crates/geo
Other
1.52k stars 196 forks source link

LineIntersection trait may return incorrect is_proper flag #664

Closed rmanoka closed 2 years ago

rmanoka commented 2 years ago

I'm looking to implement the Bentley-Ottman algorithm to fast compute all intersection of a set of lines. The LineIntersection trait is quite relevant as it tries to be very robust while calculating, and neatly flags all the edge-cases.

I notice however that the is_proper flag may sometimes be set incorrectly. The problem is that the calculations in proper_intersection may sometimes overflow, and returns one of the end points of the two lines. In this case, it shouldn't be flagged as a proper intersection, but the logic seems to always set it to true if proper_intersection is used.

In fact, the test test_central_endpoint_heuristic_failure_1 actually tests this case. The expected output is one of the end points of the inputs (line_1.start), but it expects is_proper to be true which seems incorrect. Since this comes from porting JTS code, I don't know if I'm missing something about the semantics.

michaelkirk commented 2 years ago

Thank you for catching this @rmanoka!

In fact, the test test_central_endpoint_heuristic_failure_1 actually tests this case. The expected output is one of the end points of the inputs (line_1.start), but it expects is_proper to be true which seems incorrect. Since this comes from porting JTS code, I don't know if I'm missing something about the semantics.

Upon review, JTS isn't testing for whether or not the intersection is "proper" or not. I guess I just added that additional check, and made an error with this one.

michaelkirk commented 2 years ago

The quickest hack I came up with looks like this: https://github.com/georust/geo/compare/mkirk/fix-proper-intersection-edge-case?expand=1

I'm going to follow up with JTS to see if this bug exists there, or if I mistranslated something...

michaelkirk commented 2 years ago

I've verified that JTS exhibits the same incorrect is_proper calculation as us here:

https://github.com/locationtech/jts/compare/master...michaelkirk:mkirk/fix-proper-intersection-edgecase?expand=1#diff-ff3a2a46ca692c71c2db5cdd3637bcb061803b8af8f693f5b15970bdf9c2a366R89

Next, I'll file a bug with the JTS folks.

rmanoka commented 2 years ago

Thanks for investigating this @michaelkirk ; as you've linked above, it does seem like JTS also misses this edge case. Your fix above looks good to me.

frewsxcv commented 2 years ago

What's the status of this ticket?

rmanoka commented 2 years ago

The reply in the mentioned issue sounds fair to me; it's a different semantics. The flag also seems to be used in our geo-rust code, so let's stick with what the experts did :). Let's link this discussion in the docs for future ref.