VecSet may cause panics #1104
Comments
|
#976 may be an example of this. |
|
That's an intriguing possibility. If I get this right, you're saying that you can insert I'm not familiar with Martinez-Rueda, can you share your sample implementation that exhibits the problem? My impression is that for non- |
|
Yes, that's my hypothesis. Here's my implementation: https://github.com/andriyDev/polygon_clipping_rs and this branch being the most up-to-date (but broken) https://github.com/andriyDev/polygon_clipping_rs/tree/new-impl-2 The line that would regularly "trip" is https://github.com/andriyDev/polygon_clipping_rs/blob/new-impl-2/src/lib.rs#L984, which is the search for the "right" event, which seems to be the same error as in #976. I think the reason this happens is that computing the intersection of two lines can break ordering. For example, one of the ordering criteria in Martinez-Rueda is whether a line is vertical or not. A previously non-vertical line can be split into a non-vertical line and vertical line due to floating point errors if the intersection point is close enough to an endpoint. I believe you are correct in that equality and ordering tests are fine for the same |
|
To be clear, my version still uses a VecSet (of my own). I got the idea to use a node set through the original implementation here http://www4.ujaen.es/~fmartin/bool_op.html (or at least this looks like the original author). |
This is awful / great job figuring out that this could be an issue |
|
I created https://github.com/andriyDev/stable_node_set_rs just for this (just coming back to this after a break). Not sure of its performance implications exactly, but it could be a fine starting point for seeing if it works at all. I did an initial attempt at using this in place of the VecSet, but it got stuck on an infinite loop somewhere I believe. I haven't dug in very deep though. |
|
anyone having an idea why the RegionAssembly is crashing? |
…eo library - panix possibly related to georust/geo#1104, georust/geo#1174 or similar
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 |
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
I tried writing my own implementation of Martinez-Rueda polygon clipping, and also used my own VecSet. This can be problematic since floating point issues can make the position in the VecSet somewhat not ordered (binary search can fail because floating point errors tell it to search in the wrong half).
The original algorithm from the paper cheats. Instead of using a VecSet, they use C++s
std::set, which is a binary search tree with pointer stability. In other words, when you insert a value, it returns an iterator to the node in the binary search tree. This iterator is not invalidated unless the value is removed, so they just store this iterator with the edge. Once the edge has to be removed from the active set, they go into the edge, find the iterator, and remove that iterator. No lookup, so no way for floating point errors to make this fail.This won't solve all the panics, but it could solve a good chunk of them.
The text was updated successfully, but these errors were encountered: