geo
geo copied to clipboard
Published
20 hours ago •
georust
georust
BUG: Polygon intersection and union operations raise panic for certain case
Hello, I have two polygons:
[src/utils/bbox.rs:209] &polygon_x = Polygon {
exterior: LineString(
[
Coordinate {
x: 8055.658,
y: 7977.5537,
},
Coordinate {
x: 8010.734,
y: 7999.9697,
},
Coordinate {
x: 8032.9717,
y: 8044.537,
},
Coordinate {
x: 8077.896,
y: 8022.121,
},
Coordinate {
x: 8055.658,
y: 7977.5537,
},
],
),
interiors: [],
}
[src/utils/bbox.rs:209] &polygon_y = Polygon {
exterior: LineString(
[
Coordinate {
x: 8055.805,
y: 7977.847,
},
Coordinate {
x: 8010.871,
y: 8000.2676,
},
Coordinate {
x: 8033.105,
y: 8044.8286,
},
Coordinate {
x: 8078.039,
y: 8022.408,
},
Coordinate {
x: 8055.805,
y: 7977.847,
},
],
),
interiors: [],
}
Trying to calculate intersection or union over them like:
let _u = polygon_x.union(&polygon_y).unsigned_area();
It causes the error to happen:
called `Option::unwrap()` on a `None` value
thread 'utils::bbox::polygons::fails' panicked at 'called `Option::unwrap()` on a `None` value', /home/ivan/.cargo/registry/src/github.com-1ecc6299db9ec823/geo-0.22.1/src/algorithm/bool_ops/rings.rs:79:21
stack backtrace:
0: rust_begin_unwind
at /rustc/9a7b7d5e50ab0b59c6d349bbf005680a7c880e98/library/std/src/panicking.rs:584:5
1: core::panicking::panic_fmt
at /rustc/9a7b7d5e50ab0b59c6d349bbf005680a7c880e98/library/core/src/panicking.rs:142:14
2: core::panicking::panic
at /rustc/9a7b7d5e50ab0b59c6d349bbf005680a7c880e98/library/core/src/panicking.rs:48:5
3: core::option::Option<T>::unwrap
at /home/ivan/.cargo/registry/src/github.com-1ecc6299db9ec823/geo-0.22.1/src/algorithm/bool_ops/rings.rs:79:21
4: geo::algorithm::bool_ops::rings::Rings<T>::finish
at /home/ivan/.cargo/registry/src/github.com-1ecc6299db9ec823/geo-0.22.1/src/algorithm/bool_ops/rings.rs:79:21
5: geo::algorithm::bool_ops::op::Op<T>::sweep
at /home/ivan/.cargo/registry/src/github.com-1ecc6299db9ec823/geo-0.22.1/src/algorithm/bool_ops/op.rs:171:9
6: <geo_types::geometry::polygon::Polygon<T> as geo::algorithm::bool_ops::BooleanOps>::boolean_op
at /home/ivan/.cargo/registry/src/github.com-1ecc6299db9ec823/geo-0.22.1/src/algorithm/bool_ops/mod.rs:57:21
7: geo::algorithm::bool_ops::BooleanOps::union
at /home/ivan/.cargo/registry/src/github.com-1ecc6299db9ec823/geo-0.22.1/src/algorithm/bool_ops/mod.rs:32:9
Meanwhile:
let _u = dbg!(polygon_x.union(&polygon_x).unsigned_area()); <- works
let _u = dbg!(polygon_y.union(&polygon_y).unsigned_area()); <- works
let _i = dbg!(polygon_y.intersection(&polygon_x).unsigned_area()); <- works (X.Y)
let _i = dbg!(polygon_x.intersection(&polygon_y).unsigned_area()); <- error (Y.X)
The bug is connected with f32 precision, f64 works well. But I think that the behavior is incorrect, though.
Also encountered this! f64 seems more stable but it crashes with this large polygon as well:
use geo::{BooleanOps, Coordinate, LineString, MultiPolygon, Polygon};
fn main() {
let a = MultiPolygon::new(vec![Polygon::new(
LineString::new(vec![
Coordinate {
x: 256.0,
y: -256.0,
},
Coordinate {
x: -256.0,
y: -256.0,
},
Coordinate {
x: -256.0,
y: 256.0,
},
Coordinate { x: 256.0, y: 256.0 },
Coordinate {
x: 256.0,
y: -256.0,
},
]),
vec![
LineString::new(vec![
Coordinate {
x: 21.427018453144548,
y: 100.2247496417564,
},
Coordinate {
x: 22.170654296875,
y: 97.449462890625,
},
Coordinate {
x: 21.255590787413905,
y: 95.86452640008609,
},
Coordinate {
x: 22.170654296875,
y: 92.449462890625,
},
Coordinate {
x: 21.255635468249327,
y: 90.86460378956318,
},
Coordinate {
x: 22.170654296875,
y: 87.44970703125,
},
Coordinate {
x: 21.255590787413905,
y: 85.86477054071109,
},
Coordinate {
x: 22.170654296875,
y: 82.44970703125,
},
Coordinate {
x: 21.255590787413905,
y: 80.86477054071109,
},
Coordinate {
x: 22.170654296875,
y: 77.44970703125,
},
Coordinate {
x: 21.255635468249327,
y: 75.86484793018818,
},
Coordinate {
x: 22.170654296875,
y: 72.449951171875,
},
Coordinate {
x: 21.255590787413905,
y: 70.86501468133609,
},
Coordinate {
x: 22.170654296875,
y: 67.449951171875,
},
Coordinate {
x: 21.255590787413905,
y: 65.86501468133609,
},
Coordinate {
x: 22.170654296875,
y: 62.449951171875,
},
Coordinate {
x: 21.255635468249327,
y: 60.865092070813176,
},
Coordinate {
x: 22.170654296875,
y: 57.4501953125,
},
Coordinate {
x: 20.964468977514716,
y: 55.3610210560243,
},
Coordinate {
x: 21.7110595703125,
y: 52.57470703125,
},
Coordinate {
x: 6.7110595703125036,
y: 26.593944917716843,
},
Coordinate {
x: 4.94307055353958,
y: 26.120213688445443,
},
Coordinate {
x: 3.1754150390625036,
y: 23.058544527091843,
},
Coordinate {
x: 1.4077371841677144,
y: 22.584896673394404,
},
Coordinate {
x: -0.36010742187499645,
y: 19.522899995841843,
},
Coordinate {
x: -2.127952027917708,
y: 19.04920746130898,
},
Coordinate {
x: -3.8956298828124964,
y: 15.987499605216843,
},
Coordinate {
x: -5.663474488855209,
y: 15.513807070683983,
},
Coordinate {
x: -7.4311523437499964,
y: 12.452099214591843,
},
Coordinate {
x: -9.199141360522919,
y: 11.978367985320444,
},
Coordinate {
x: -10.966796874999996,
y: 8.916698823966843,
},
Coordinate {
x: -12.734474729894785,
y: 8.443050970269406,
},
Coordinate {
x: -14.502319335937496,
y: 5.381054292716843,
},
Coordinate {
x: -29.502319335937507,
y: 1.36181640625,
},
Coordinate {
x: -44.502319335937514,
y: 5.381054292716847,
},
Coordinate {
x: -55.48308144947066,
y: 16.361816406249996,
},
Coordinate {
x: -59.5023193359375,
y: 31.361816406250004,
},
Coordinate {
x: -55.48308144947066,
y: 46.36181640625,
},
Coordinate {
x: -51.94760366936858,
y: 49.89729418635208,
},
Coordinate {
x: -51.94755898853316,
y: 49.8974609375,
},
Coordinate {
x: -40.96679687499999,
y: 60.87822305103316,
},
Coordinate {
x: -40.96646337270415,
y: 60.878312412704005,
},
Coordinate {
x: -37.43115234374999,
y: 64.41362344165816,
},
Coordinate {
x: -37.43098559260209,
y: 64.41366812249358,
},
Coordinate {
x: -37.25638533366225,
y: 64.58826838143341,
},
Coordinate {
x: -37.15947272204719,
y: 64.949951171875,
},
Coordinate {
x: -37.829345703125,
y: 67.449951171875,
},
Coordinate {
x: -37.15947272204719,
y: 69.949951171875,
},
Coordinate {
x: -37.829345703125,
y: 72.449951171875,
},
Coordinate {
x: -37.159505430688846,
y: 74.9498291015625,
},
Coordinate {
x: -37.829345703125,
y: 77.44970703125,
},
Coordinate {
x: -37.15947272204719,
y: 79.94970703125,
},
Coordinate {
x: -37.829345703125,
y: 82.44970703125,
},
Coordinate {
x: -37.15947272204719,
y: 84.94970703125,
},
Coordinate {
x: -37.829345703125,
y: 87.44970703125,
},
Coordinate {
x: -37.6218793727004,
y: 88.22398191725448,
},
Coordinate {
x: -43.845336914062514,
y: 89.89155233959184,
},
Coordinate {
x: -54.82609902759566,
y: 100.872314453125,
},
Coordinate {
x: -58.8453369140625,
y: 115.872314453125,
},
Coordinate {
x: -54.82609902759566,
y: 130.872314453125,
},
Coordinate {
x: -43.84533691406249,
y: 141.85307656665816,
},
Coordinate {
x: -28.845336914062496,
y: 145.872314453125,
},
Coordinate {
x: -26.345275878906246,
y: 145.20242511772636,
},
Coordinate {
x: -23.845214843749996,
y: 145.872314453125,
},
Coordinate {
x: -21.345153808593746,
y: 145.20242511772636,
},
Coordinate {
x: -18.845092773437496,
y: 145.872314453125,
},
Coordinate {
x: -16.345092773437496,
y: 145.20244147204718,
},
Coordinate {
x: -13.845092773437498,
y: 145.872314453125,
},
Coordinate {
x: -11.345092773437498,
y: 145.20244147204718,
},
Coordinate {
x: -8.845092773437498,
y: 145.872314453125,
},
Coordinate {
x: -7.241160801189184,
y: 145.4425421764466,
},
Coordinate {
x: -4.753417968749998,
y: 146.109130859375,
},
Coordinate {
x: -3.857349940998309,
y: 145.86903015497558,
},
Coordinate {
x: -3.8450927734374982,
y: 145.872314453125,
},
Coordinate {
x: -2.5414695567288628,
y: 145.52300966497347,
},
Coordinate {
x: -0.04333496093749816,
y: 146.1923828125,
},
Coordinate {
x: 14.956665039062504,
y: 142.17314492603316,
},
Coordinate {
x: 14.96700942550945,
y: 142.16280053958621,
},
Coordinate {
x: 15.549804687500004,
y: 142.00664101978316,
},
Coordinate {
x: 26.53056680103316,
y: 131.02587890625,
},
Coordinate {
x: 30.5498046875,
y: 116.02587890625,
},
Coordinate {
x: 21.427018453144548,
y: 100.2247496417564,
},
]),
LineString::new(vec![
Coordinate {
x: 15.9573974609375,
y: 218.888916015625,
},
Coordinate {
x: 11.93815957447066,
y: 233.888916015625,
},
Coordinate {
x: 0.9573974609375036,
y: 244.86967812915816,
},
Coordinate {
x: -14.042602539062498,
y: 248.888916015625,
},
Coordinate {
x: -29.042602539062493,
y: 244.86967812915816,
},
Coordinate {
x: -32.57795824885207,
y: 241.3343224193686,
},
Coordinate {
x: -32.57812499999999,
y: 241.33427773853316,
},
Coordinate {
x: -36.11348070978957,
y: 237.7989220287436,
},
Coordinate {
x: -36.11364746093749,
y: 237.79887734790816,
},
Coordinate {
x: -39.64895848989165,
y: 234.26356631895402,
},
Coordinate {
x: -39.64929199218749,
y: 234.26347695728316,
},
Coordinate {
x: -50.63005410572066,
y: 223.28271484375,
},
Coordinate {
x: -50.63009878655608,
y: 223.28254809260207,
},
Coordinate {
x: -54.16557656665816,
y: 219.7470703125,
},
Coordinate {
x: -58.184814453125,
y: 204.7470703125,
},
Coordinate {
x: -54.16557656665816,
y: 189.7470703125,
},
Coordinate {
x: -43.184814453125014,
y: 178.76630819896684,
},
Coordinate {
x: -28.184814453125007,
y: 174.7470703125,
},
Coordinate {
x: -13.184814453124996,
y: 178.76630819896684,
},
Coordinate {
x: -11.416969847082285,
y: 181.8283048765194,
},
Coordinate {
x: -9.649291992187496,
y: 182.30195273021684,
},
Coordinate {
x: -7.88163647771042,
y: 185.36362189157043,
},
Coordinate {
x: -6.1136474609374964,
y: 185.83735312084184,
},
Coordinate {
x: -4.345969606042708,
y: 188.89906097693398,
},
Coordinate {
x: -2.5781249999999964,
y: 189.37275351146684,
},
Coordinate {
x: -0.8104471451052081,
y: 192.43446136755898,
},
Coordinate {
x: 0.9573974609375036,
y: 192.90815390209184,
},
Coordinate {
x: 15.9573974609375,
y: 218.888916015625,
},
]),
],
)]);
let b = Polygon::new(
LineString::new(vec![
Coordinate {
x: 19.492919921875,
y: 222.424560546875,
},
Coordinate {
x: 15.47368203540816,
y: 237.424560546875,
},
Coordinate {
x: 4.4929199218750036,
y: 248.40532266040816,
},
Coordinate {
x: -10.507080078124998,
y: 252.424560546875,
},
Coordinate {
x: -25.507080078124993,
y: 248.40532266040816,
},
Coordinate {
x: -36.48784219165816,
y: 237.424560546875,
},
Coordinate {
x: -40.507080078125,
y: 222.424560546875,
},
Coordinate {
x: -36.48784219165816,
y: 207.424560546875,
},
Coordinate {
x: -25.507080078125014,
y: 196.44379843334184,
},
Coordinate {
x: -10.507080078125005,
y: 192.424560546875,
},
Coordinate {
x: 4.4929199218750036,
y: 196.44379843334184,
},
Coordinate {
x: 19.492919921875,
y: 222.424560546875,
},
]),
vec![],
);
a.difference(&MultiPolygon::new(vec![b]));
}
I added the above test case here: https://github.com/rmanoka/geo/tree/fix/issue-885 . However, something complicated is happening with the code-gen. The test case panics or not depending on if certain trace macros are enabled at run-time !!!
$ export RUST_LOG=
$ cargo test -- issue_885 # test fails
$ export RUST_LOG=geo::algorithm::sweep::iter=trace
$ cargo test -- issue_885 # test succeeds!!!
The only trace macro in there is:
trace!(
"cb: {seg:?} {ty:?} (crossable = {cross:?})",
cross = seg.cross().line()
);
Could anyone check they encounter this too?
EDIT: The tree has changed; please check-out this commit if testing the issue.
It looks like the issue may be with incorrect usage of UnsafeCell; for safety, I've moved to using RefCell instead.
The issue with the first test-case was indeed a fp precision issue; have fixed it but the larger test-case is yet to be resolved.