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.

Sign up for GitHub

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

Jump to bottom

BooleanOps panic in Snake::into_ring #1189

Closed
donkeyteethUX opened this issue May 31, 2024 · 1 comment
Closed

BooleanOps panic in Snake::into_ring #1189

donkeyteethUX opened this issue May 31, 2024 · 1 comment

Comments

@donkeyteethUX
Copy link

Backtrace:

thread 'test::reproduce_crash' panicked at /Systems/extlib/rust/geo-0.28.0/src/algorithm/bool_ops/assembly.rs:397:22:
internal error: entered unreachable code
stack backtrace:
   0: rust_begin_unwind
             at /rustc/82e1608dfa6e0b5569232559e3d385fea5a93112/library/std/src/panicking.rs:645:5
   1: core::panicking::panic_fmt
             at /rustc/82e1608dfa6e0b5569232559e3d385fea5a93112/library/core/src/panicking.rs:72:14
   2: core::panicking::panic
             at /rustc/82e1608dfa6e0b5569232559e3d385fea5a93112/library/core/src/panicking.rs:127:5
   3: geo::algorithm::bool_ops::assembly::Snake<T>::into_ring
   4: geo::algorithm::bool_ops::assembly::rings_from_snakes
             at /Systems/extlib/rust/geo-0.28.0/src/algorithm/bool_ops/assembly.rs:314:27
   5: geo::algorithm::bool_ops::assembly::RegionAssembly<T>::finish
             at /Systems/extlib/rust/geo-0.28.0/src/algorithm/bool_ops/assembly.rs:157:39
   6: <geo::algorithm::bool_ops::spec::BoolOp<T> as geo::algorithm::bool_ops::spec::Spec<T>>::finish
             at /Systems/extlib/rust/geo-0.28.0/src/algorithm/bool_ops/spec.rs:71:9
   7: geo::algorithm::bool_ops::op::Proc<T,S>::sweep
             at /Systems/extlib/rust/geo-0.28.0/src/algorithm/bool_ops/op.rs:208:9
   8: <geo_types::geometry::multi_polygon::MultiPolygon<T> as geo::algorithm::bool_ops::BooleanOps>::boolean_op
             at /Systems/extlib/rust/geo-0.28.0/src/algorithm/bool_ops/mod.rs:94:9
   9: geo::algorithm::bool_ops::BooleanOps::union
             at /Systems/extlib/rust/geo-0.28.0/src/algorithm/bool_ops/mod.rs:33:9
  10: my_lib::test::reproduce_crash
             at ./src/lib.rs:399:9
  11: my_lib::test::reproduce_crash::{{closure}}
             at ./src/lib.rs:364:40
  12: core::ops::function::FnOnce::call_once
             at /rustc/82e1608dfa6e0b5569232559e3d385fea5a93112/library/core/src/ops/function.rs:250:5
  13: core::ops::function::FnOnce::call_once
             at /rustc/82e1608dfa6e0b5569232559e3d385fea5a93112/library/core/src/ops/function.rs:250:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

Reproducible with:

#[test]
fn reproduce_crash() {
    let mutipolygon = MultiPolygon(vec![Polygon::new(
        LineString(vec![
            coord! { x: -842.8114919816321, y: -1593.246948876771 },
            coord! { x: -250.74147790864794, y: -1277.405012942043 },
            coord! { x: -107.7221679586994, y: -1437.4340368172966 },
            coord! { x: 548.266741952783, y: -851.1711267623472 },
            coord! { x: 1324.5108343844536, y: -437.08084844385627 },
            coord! { x: 1223.4931768687463, y: -247.7154757616648 },
            coord! { x: 1411.99111985414, y: -79.25324884855956 },
            coord! { x: 721.4329328584276, y: 693.4350869619186 },
            coord! { x: 383.16901237055976, y: 1327.5368365314368 },
            coord! { x: 228.479378920974, y: 1245.0170801910524 },
            coord! { x: 79.25324884855956, y: 1411.99111985414 },
            coord! { x: -605.2045801730624, y: 800.285292836034 },
            coord! { x: -1784.1533139955259, y: 171.37073609852212 },
            coord! { x: -842.8114919816321, y: -1593.246948876771 },
        ]),
        vec![],
    )]);

    let p = Polygon::new(
        LineString(vec![
            coord! { x: -842.8114919816321, y: -1593.246948876771 },
            coord! { x: -1784.1533139955259, y: 171.37073609852212 },
            coord! { x: 383.16901237055976, y: 1327.5368365314368 },
            coord! { x: 1324.5108343844536, y: -437.08084844385627 },
            coord! { x: -842.8114919816321, y: -1593.246948876771 },
        ]),
        vec![],
    );

    mutipolygon.union(&p.into());
}
@michaelkirk michaelkirk mentioned this issue Oct 24, 2024
Merged
2 tasks
michaelkirk added a commit that referenced this issue Oct 28, 2024
@michaelkirk
Fix "panic" in BoolOps by introducing i_overlay
4915dfc 
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
@michaelkirk @urschrei
Fix "panic" in BoolOps by introducing i_overlay
15c3362 
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
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@michaelkirk @donkeyteethUX