VecSet may cause panics

[andriyDev]

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.

[andriyDev]

#976 may be an example of this.

[lnicola]

That's an intriguing possibility. If I get this right, you're saying that you can insert x into VecSet, then search for it and not find it because it's not sorted properly?

I'm not familiar with Martinez-Rueda, can you share your sample implementation that exhibits the problem? My impression is that for non-NaN floats, equality and ordering tests should work. So if we recompute x somehow, that might cause problems, but if we use the same x, it should be the same as keeping track of an iterator.

[andriyDev]

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 x, but since we insert computed xs from line intersections they can actually subtly break the ordering. I imagine these subtle breakages don't impact that algorithm significantly, since they problem come from "small" lines which will be resolved quickly, but they do break the ordering enough that removing the corresponding right point may fail. I am very not certain of this though, and I might be totally wrong :P

[andriyDev]

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).

[urschrei]

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.

This is awful / great job figuring out that this could be an issue

[andriyDev]

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.

[frehberg]

anyone having an idea why the RegionAssembly is crashing?
Please see the regression test in #1126