Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Canonical segment orientation for robust intersections #23

Open
nick-parker opened this issue Apr 29, 2020 · 6 comments
Open

Canonical segment orientation for robust intersections #23

nick-parker opened this issue Apr 29, 2020 · 6 comments

Comments

@nick-parker
Copy link

Currently, this test fails:

    #[test]
    fn test_intersection_order() {
        for _ in 0..1000 {
            let a1 = random_coord();
            let a2 = random_coord();
            let b1 = random_coord();
            let b2 = random_coord();
            let p1234 = intersection(a1, a2, b1, b2); 
            assert_eq!(p1234, intersection(a2, a1, b1, b2));
            assert_eq!(p1234, intersection(a1, a2, b2, b1));
            assert_eq!(p1234, intersection(a2, a1, b2, b1));
            assert_eq!(p1234, intersection(b1, b2, a1, a2));
            assert_eq!(p1234, intersection(b1, b2, a2, a1));
            assert_eq!(p1234, intersection(b2, b1, a1, a2));
            assert_eq!(p1234, intersection(b2, b1, a2, a1));
        }
    }
}

The accumulation of floating point errors in intersection depends on the order of its arguments, when all 8 permutations ought to be the exact same intersection.

If we change the intersection function to enforce a canonical orientation for the two line segments before performing its calculations, this test will pass and naive equality checks on intersection results will be reliable.

We perform most of the comparisons necessary to enforce such a convention already in constructing the intersection bounding box. See this commit in my fork:
nick-parker@ae3159f

Would this sort of robustness be helpful? I haven't dug into the main library enough to know yet, and my branch breaks a bunch of tests right now because it changes the orientation of eg some Overlap results.

@nick-parker
Copy link
Author

Just pushed an updated version that maintains the old Overlap orientation conventions, if that matters.

https://github.com/nick-parker/rust-geo-booleanop/tree/robust-intersection

I believe the only failing tests now are due to the floating point differences this change is meant to fix.

@bluenote10
Copy link
Contributor

Yeah interesting idea. I would definitely have to think / experiment a lot more to come to a final conclusion but my immediate thoughts are:

  • The algorithm should already call intersection in a semi-canonical way. Basically the relation between the 1 and 2 points is given by the event ordering, 1 being the start event, 2 being the end event -- or put differently: it is always a1 < a2 and b1 < b2. If I remember correctly the current implementation of intersection does not yet exploit that, i.e., we actually could save some of the checks we have to do for the bounding boxes. This was an optimization I had in the back of my mind -- the blocker being that currently the test cases below are "generic", i.e., they don't satisfy that pattern and need to be adjusted first.
  • This reduces the canonicalization to being symmetric in the segments a vs b which is indeed something that may be important for overall robustness (but actually there should also be enough context for this at the call site to make the call canonic, e.g., by using always a for the segment lower in the sweep line).
  • When I added all the if needed for the bounding boxes I was surprised that it causes more performance impact then I expected. So we have to be a bit careful with more conditions.

@nick-parker
Copy link
Author

Maybe it would make sense to have a minimally checked 'naked' intersection function, and then a fully checked second function that calls the naked version after canonicalization?

That would let us optimize the call sites where we know certain conditions are guaranteed, but also encourage us to think about those guarantees and give us an escape hatch if there are any sites where we can't provide them.

@bluenote10
Copy link
Contributor

There are only two callsites:

I'm wondering if we can actually come up a test case that fails because of this inconsistency.

A first question to investigate would be: Is it possible to get different result types LineIntersection::None / LineIntersection::Point / LineIntersection::Overlap by swapping segments?

@nick-parker
Copy link
Author

Hi there, sorry I've been distracted by other projects. Still can't quite jump into this one like I want, but I poked around my test here a bit more, and you can definitely get different result types.

The easiest case is if the two segments share an endpoint. That's order-dependent every time. However if the midpoint of one segment is an endpoint of another, it only sometimes differs depending on the specific random coordinates.

I haven't poked around yet, but I bet you can also get it to flip between a point intersection and an overlap intersection.

@nick-parker
Copy link
Author

nick-parker commented May 17, 2020

I rebased this onto #24 because the outdated geo_types had been bugging me, and I plotted all the generic_test_cases which you can see in the attached pdf.

I'm not sure which if any tests are supposed to fail, but issue103 was marked that flipping ba causes it to fail, and in the attached pdf you can see that they match perfectly now.

test_cases.pdf

Rebased branch: https://github.com/nick-parker/rust-geo-booleanop/tree/robust-intersection

Edit: Ahhh dang, I just realized the python plot script just plots, it doesn't execute the actual operations. Are these geojson files updated when I run the tests or what?

Edit2: Nevermind, noticed the /tests/README. I haven't fixed issue103 SwapResult. Also I ran the benchmarks and this is around 20% slower :(

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants