Panic in BooleanOps::union for Polygon<f32>

[nebocco]

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.

[urschrei]

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

[RobWalt]

@urschrei added a test for this in https://github.com/georust/geo/pull/1089/commits/bd5f57a8d0ee9a8a58079dc985f79645414e8283. I added both variations (f32 and f64) and they both succeeded.

[wlinna]

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

1. https://github.com/georust/geo/pull/1032
2. https://github.com/georust/geo/pull/1073

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]

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]

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]

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]

I believe this is a dupe of https://github.com/georust/geo/issues/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.