VecSet may cause panics about geo HOT 7 OPEN

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

from geo.

#976 may be an example of this.

from geo.

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.

from geo.

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

from geo.

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

from geo.

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.

from geo.

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

from geo.