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

Panic in RegionAssembly reproducibly #1127

Closed
frehberg opened this issue Dec 21, 2023 · 6 comments
Closed

Panic in RegionAssembly reproducibly #1127

frehberg opened this issue Dec 21, 2023 · 6 comments

Comments

@frehberg
Copy link

frehberg commented Dec 21, 2023

Occasionally (1:8) I observe a panic condition. I managed to print out the data of RegionAssembly causing the panic, and using this data to create a regression test (see PR)

Code with regresssion test assembling 3668 segments/lines #1126

The panic occures in the the check in file assembly.rs

            debug_assert!(num_segments % 2 == 0, "assembly segments must be eulierian");

The execution path leading to this point of the RegionAssembly occures in the context of bop.sweep() in the following code

impl<T: GeoFloat> BooleanOps for MultiPolygon<T> {
    type Scalar = T;

    fn boolean_op(&self, other: &Self, op: OpType) -> MultiPolygon<Self::Scalar> {
        let spec = BoolOp::from(op);
        let mut bop = Proc::new(spec, self.coords_count() + other.coords_count());
        bop.add_multi_polygon(self, 0);
        bop.add_multi_polygon(other, 1);
        bop.sweep()
    }

Appreciating any hint why this crash occures and how to avoid the panic crash

Screenshot from 2023-12-21 11-30-58

@urschrei
Copy link
Member

#1102, #1103, and #1104 may be related here.

@frehberg frehberg changed the title Panic in RegionAssembly occasionally Panic in RegionAssembly reproducibly Jan 8, 2024
@frehberg
Copy link
Author

frehberg commented Jan 8, 2024

is the code of RegionAssembly crashing due to a bug in the algorithm, or due to bad input parameters? In case of the latter, how to prevent this?

@urschrei
Copy link
Member

urschrei commented Jan 8, 2024

It's crashing due to a bug, and a fix is unlikely in the short term.

@frehberg
Copy link
Author

frehberg commented Jan 9, 2024

hopefully this test #1126 can help you to reproduce the issue and fix the code

@michaelkirk
Copy link
Member

I believe this is a dupe of #913

That issue is still open - but let's try to focus any future discussion on this bug there. Note there may be other bugs with the boolean operations - this one in particular is about the "assembly segments must be eulierian", which I believe is caused by a collapse of floating point precision.

Feel free to re-open if I'm mistaken and this represents a different bug.

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
@michaelkirk
Copy link
Member

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 geo crate, otherwise we expect it to be part of the upcoming v0.29.0 release.

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
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants