Panic in BooleanOps::union for Polygon<f32> #1103

nebocco · 2023-10-29T13:30:43Z

When I executed the following code, a panic occurred. I believe it is related to issue #976; however, a different error message was displayed, saying assembly segments must be eulierian. What does "segments are eulerian" mean?

(by the way, there seems to be a typo in this error message).

use geo::{BooleanOps, Coord, LineString, MultiPolygon, Polygon};

fn main() {
    let polygons = [
        Polygon::<f32>::new(
            LineString::from(vec![
                Coord {
                    x: 3.34936523437500000000,
                    y: -55.80126953125000000000,
                },
                Coord {
                    x: 171.22442626953125000000,
                    y: -300.00000000000000000000,
                },
                Coord {
                    x: 291.84164428710937500000,
                    y: -300.00000000000000000000,
                },
                Coord {
                    x: 46.65063476562500000000,
                    y: -30.80126953125000000000,
                },
                Coord {
                    x: 3.34936523437500000000,
                    y: -55.80126953125000000000,
                },
            ]),
            Vec::new(),
        ),
        Polygon::<f32>::new(
            LineString::from(vec![
                Coord {
                    x: 46.65063476562500000000,
                    y: -30.80126953125000000000,
                },
                Coord {
                    x: 291.84164428710937500000,
                    y: -300.00000000000000000000,
                },
                Coord {
                    x: 300.00000000000000000000,
                    y: -228.34002685546875000000,
                },
                Coord {
                    x: -3.34936523437500000000,
                    y: 55.80126953125000000000,
                },
                Coord {
                    x: 46.65063476562500000000,
                    y: -30.80126953125000000000,
                },
            ]),
            Vec::new(),
        ),
        Polygon::<f32>::new(
            LineString::from(vec![
                Coord {
                    x: -46.65063476562500000000,
                    y: 30.80126953125000000000,
                },
                Coord {
                    x: 195.83728027343750000000,
                    y: -300.00000000000000000000,
                },
                Coord {
                    x: 300.00000000000000000000,
                    y: -228.34002685546875000000,
                },
                Coord {
                    x: -3.34936523437500000000,
                    y: 55.80126953125000000000,
                },
                Coord {
                    x: -46.65063476562500000000,
                    y: 30.80126953125000000000,
                },
            ]),
            Vec::new(),
        ),
        Polygon::<f32>::new(
            LineString::from(vec![
                Coord {
                    x: 3.34936523437500000000,
                    y: -55.80126953125000000000,
                },
                Coord {
                    x: 171.22442626953125000000,
                    y: -300.00000000000000000000,
                },
                Coord {
                    x: 195.83728027343750000000,
                    y: -300.00000000000000000000,
                },
                Coord {
                    x: -46.65063476562500000000,
                    y: 30.80126953125000000000,
                },
                Coord {
                    x: 3.34936523437500000000,
                    y: -55.80126953125000000000,
                },
            ]),
            Vec::new(),
        ),
    ];

    let mut multi = MultiPolygon::new(Vec::new());
    for poly in polygons {
        multi = multi.union(&MultiPolygon::new(vec![poly]));
    }
}

% RUST_BACKTRACE=1 cargo run
   Compiling geom_check v0.1.0 (/home/user/Rust/geom_check)
    Finished dev [unoptimized + debuginfo] target(s) in 0.43s
     Running `target/debug/geom_check`
thread 'main' panicked at /home/user/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.26.0/src/algorithm/bool_ops/assembly.rs:45:13:
assembly segments must be eulierian
stack backtrace:
   0: rust_begin_unwind
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library/std/src/panicking.rs:595:5
   1: core::panicking::panic_fmt
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library/core/src/panicking.rs:67:14
   2: geo::algorithm::bool_ops::assembly::RegionAssembly<T>::finish
             at /home/user/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.26.0/src/algorithm/bool_ops/assembly.rs:45:13
   3: <geo::algorithm::bool_ops::spec::BoolOp<T> as geo::algorithm::bool_ops::spec::Spec<T>>::finish
             at /home/user/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.26.0/src/algorithm/bool_ops/spec.rs:52:9
   4: geo::algorithm::bool_ops::op::Proc<T,S>::sweep
             at /home/user/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.26.0/src/algorithm/bool_ops/op.rs:172:9
   5: <geo_types::geometry::multi_polygon::MultiPolygon<T> as geo::algorithm::bool_ops::BooleanOps>::boolean_op
             at /home/user/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.26.0/src/algorithm/bool_ops/mod.rs:94:9
   6: geo::algorithm::bool_ops::BooleanOps::union
             at /home/user/.cargo/registry/src/index.crates.io-6f17d22bba15001f/geo-0.26.0/src/algorithm/bool_ops/mod.rs:33:9
   7: geom_check::main
             at ./src/main.rs:109:17
   8: core::ops::function::FnOnce::call_once
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library/core/src/ops/function.rs:250:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

The text was updated successfully, but these errors were encountered:

urschrei · 2023-10-30T14:21:10Z

@RobWalt Could you add this to your draft Bool ops PR as a test case?

RobWalt · 2023-10-31T20:46:17Z

@urschrei added a test for this in bd5f57a. I added both variations (f32 and f64) and they both succeeded.

wlinna · 2024-04-27T19:29:21Z

I get lots of panics with Polygon<f64>::union. It always seems to be one of these:

segment not found in active-vec-set: 2
assembly segments must be eulierian

What I'm doing is that I'm trying to turn a triangle mesh into a MultiPolygon by calling union sequentially.

I'm using geo 0.28.

I think turning boolean_op into a fallible function would be a good solution until all the issues have been ironed out. It seems that something like that has been attempted in at least two PRs before, and neither of them were merged

If I understand correctly, the first one was closed because the same author opened another PR with a different idea. But since that didn't pan out (?), why not reopen the first one? The panics are easy to hit and it'd be so much better if we could recover from errors.

EDIT: I've notice that there's also a Stitch PR and Spade Boolops PR

RobWalt · 2024-04-29T04:36:20Z

I think turning boolean_op into a fallible function would be a good solution until all the issues have been ironed out.

Yeah I thought so as well. The main problem with the current implementation, panicking implementation of boolops is, that it relies on an implementation of PartialOrd. Within this traits implementation there is panicking code. We don't really have control over this since partial_cmp has an un-generic function signature which doesn't allow falliability https://doc.rust-lang.org/stable/std/cmp/trait.PartialOrd.html#tymethod.partial_cmp . It might still be possible to fix this by rolling our own PartialOrd but no-one wanted to touch that can of worm yet I guess.

I'm still working on the alternative implementation of boolops which should work without panics but it'll still take a while since we're currently still stuck reviewing the stitch PR.

wlinna · 2024-04-29T17:08:09Z

Hmm.. but even if we those parts that depend on PartialOrd, wouldn't it help quite a lot of if code like this

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

and this

    pub fn index_of(&self, segment: &T) -> usize {
        self.data
            .binary_search(Active::active_ref(segment))
            .expect("segment not found in active-vec-set")
}

.. returned Errors or Options instead?

Btw, I switched to SpadeBoolops::union and so far it seems to work well enough.

RobWalt · 2024-05-15T05:51:37Z

Oh I just noticed I didn't press send here. Sorry for the wait.

Indeed I did try out to use errors in every scenario possible before. The thing is that during testing it didn't really make a difference since the panic in the PartialOrd was hit anyways.

michaelkirk · 2024-07-30T22:21:10Z

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.

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 · 2024-10-28T18:18:22Z

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.

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

urschrei mentioned this issue Dec 21, 2023

Panic in RegionAssembly reproducibly #1127

Closed

michaelkirk mentioned this issue Jan 29, 2024

Panic "assembly segments must be eulierian" when taking difference of two Multipolygons. 21re/rust-geo-booleanop#37

Open

michaelkirk closed this as completed Jul 30, 2024

michaelkirk mentioned this issue Oct 24, 2024

Back BooleanOps with i_overlay to avoid crashes from floating point collapse #1234

Merged

2 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Panic in BooleanOps::union for Polygon<f32> #1103

Panic in BooleanOps::union for Polygon<f32> #1103

nebocco commented Oct 29, 2023 •

edited

Loading

urschrei commented Oct 30, 2023

RobWalt commented Oct 31, 2023

wlinna commented Apr 27, 2024 •

edited

Loading

RobWalt commented Apr 29, 2024

wlinna commented Apr 29, 2024

RobWalt commented May 15, 2024

michaelkirk commented Jul 30, 2024

michaelkirk commented Oct 28, 2024

Panic in BooleanOps::union for Polygon<f32> #1103

Panic in BooleanOps::union for Polygon<f32> #1103

Comments

nebocco commented Oct 29, 2023 • edited Loading

urschrei commented Oct 30, 2023

RobWalt commented Oct 31, 2023

wlinna commented Apr 27, 2024 • edited Loading

RobWalt commented Apr 29, 2024

wlinna commented Apr 29, 2024

RobWalt commented May 15, 2024

michaelkirk commented Jul 30, 2024

michaelkirk commented Oct 28, 2024

nebocco commented Oct 29, 2023 •

edited

Loading

wlinna commented Apr 27, 2024 •

edited

Loading