Panic in polygon difference #913
Comments
|
I ran into the same issue doing a union: The panic is the same: |
|
I’m out of action (🤒) rn, but we might try testing these errors against HEAD to see whether the recent fixes are relevant here? |
|
The HEAD version does indeed fix this issue. Thanks and hope you feel better! |
|
After returning to my original code using the HEAD version, I found a different example of the same issue. This one fails non-deterministically so you might have to do Example code is really long, click here to see it |
|
Unfortunately, my application also still produces panics when using the latest commit of this library. results in the output: |
|
I'm not very familiar with the bool ops implementation yet, but I did want to try to help solve this issue. To start with, I reproduced a similar error with simpler (triangular) inputs: here's what those look like rendered (poly1 on the left): This crossing looks interesting: To be clear, I have no idea if that's the point causing our slip-up, but it just looks topologically interesting to have a vertex of poly2 which appears to be on the crossing point into poly1. |
dabreegster
added a commit
to a-b-street/abstreet
that referenced
this issue
Nov 10, 2022
|
I have a reproducible crash with |
|
I thought I left a response on this long ago, sorry for letting the thread drop. Unfortunately I didn't take very good notes either, but as I recall the root of the issue was a lack of available precision. A little more specifically: With B.O. we maintain an invariant of visiting intersections and vertices in a certain order - (the "sweep" is monotonic). We can robustly compute when there is an intersection, but we also need to store the actual (X,Y) value of that intersection so we can order it WRT to our other crossings, to maintain the invariant that we're sweeping monotonically. However, because our floating point representation is finite, the number that we store may entail some error. IIRC, this panic is happening when we have two very close intersections, such that the amount of error in the f64 representation of the intersection is enough to break the monotonicity of the sweep. Like if we are trying to visit numbers in increasing order and we have: If we were trying to visit them monotonically, we might get it wrong. Anyway, not sure if this is helpful to anyone or if I'm even remembering the issue correctly, but I wanted to record my discoveries in case it's helpful for someone down the line. |
Looking at my debug branch a bit, I think this might be related to our usage of |
|
Implemented all the listed failed cases in this issue as test cases for a new implementation of the algo here a6184b1 and all the tests succeed. |
This was referenced Jul 30, 2024
2 tasks
michaelkirk
added a commit
that referenced
this issue
Oct 28, 2024
We've had several reports of crashes in our BooleanOps implementation over the years. Some of them have been addressed, but there remains a long tail of crashes. FIXES #913, #948, #976, #1053, #1064, #1103, #1104, #1127, #1174, #1189, 1193 The root of the issue (as I understand it) is that floating point rounding errors break the invariants of our sweep line algorithm. After a couple years, it seems like a "simple" resolution is not in sight. In the meanwhile, the i_overlay crate appeared. It uses a strategy that maps floating point geometries to a scaled fixed point grid, which nicely avoids the kind of problems we were having. Related changes included: Included are some tests that cover all reports in the issue tracker of the existing BoolOps panic'ing JTS supports Bops between all geometry types. We support a more limited set: 1. Two 2-Dimensional geometries `boolean_op`. 2. A 1-Dimenstinoal geometry with a 2-D geometry, which we call `clip`. So this maps JTS's Line x Poly intersection tests to our Clip method. - rm unused sweep code now that old boolops is gone I marked a couple fields as `allow(unused)` because they are used for printing debug repr in tests. Speed up benches by only benching local boolop impl by default
|
I just merged #1234 which replaces our BoolOps implementation with one backed by the i_overlay crate. This should resolve the issue you're seeing. Let us know if it recurs. You can use it now if you use the unreleased |
urschrei
pushed a commit
to urschrei/geo
that referenced
this issue
Nov 6, 2024
We've had several reports of crashes in our BooleanOps implementation over the years. Some of them have been addressed, but there remains a long tail of crashes. FIXES georust#913, georust#948, georust#976, georust#1053, georust#1064, georust#1103, georust#1104, georust#1127, georust#1174, georust#1189, 1193 The root of the issue (as I understand it) is that floating point rounding errors break the invariants of our sweep line algorithm. After a couple years, it seems like a "simple" resolution is not in sight. In the meanwhile, the i_overlay crate appeared. It uses a strategy that maps floating point geometries to a scaled fixed point grid, which nicely avoids the kind of problems we were having. Related changes included: Included are some tests that cover all reports in the issue tracker of the existing BoolOps panic'ing JTS supports Bops between all geometry types. We support a more limited set: 1. Two 2-Dimensional geometries `boolean_op`. 2. A 1-Dimenstinoal geometry with a 2-D geometry, which we call `clip`. So this maps JTS's Line x Poly intersection tests to our Clip method. - rm unused sweep code now that old boolops is gone I marked a couple fields as `allow(unused)` because they are used for printing debug repr in tests. Speed up benches by only benching local boolop impl by default
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I get a panic when executing the following code:
The panic looks like this:
I use version 0.23.0 of the geo library with rustc 1.64.0.
I use the intersection and following difference because I need the boolean operation A & ~B which is not directly present in the included boolean operations as far as I could see.
The text was updated successfully, but these errors were encountered: