geo
geo copied to clipboard
georust
Panic in BooleanOps::union for Polygon<f32>
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 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.
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
- https://github.com/georust/geo/pull/1032
- 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
I think turning
boolean_opinto 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.
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.
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.
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.
