rust-geo-booleanop
rust-geo-booleanop copied to clipboard
21re
Stack overflow for some big polygons
I have a process which creates some polygons, and some of them are invalid and weird. But this library is unable to deal with them.
With this test:
#[test]
fn infinite_bad_geom() {
let orig = fixture_multi_polygon("orig.geojson");
let bad = fixture_multi_polygon("bad.geojson");
orig.union(&bad);
}
And these files:
bad.geojson.gz orig.geojson.gz
You get this following stack overflow:
thread 'infinite::infinite_bad_geom' has overflowed its stack
fatal runtime error: stack overflow
error: process didn't exit successfully: `/home/rory/code/rust/rust-geo-booleanop/target/debug/deps/geo_booleanop_tests-53da8e6c52baad74 'infinite::infinite_bad_geom' --nocapture` (signal: 6, SIGABRT: process abort signal)
It seems to be a problem of the tree implementation. I ran into the stack overflows as well when benchmarking various tree implementations as baselines for rust-array-stump. Since I would suggest to move to that data structure anyway for performance and algorithmic reasons (fixing #17), this issue could be resolved by that as well.
I can confirm this also happens when running a union operation on two polygons with 37 points each. Coordinates included below. I'm running the algorithm in WASM which is definitely more memory constrained than a bare-metal execution. However, it still takes the library a good 20 seconds to fill all the memory (which seems to cap out at about 4GB).
// LineString #1
[Coordinate { x: -3828.47325323343, y: 184.61849396854478 }, Coordinate { x: -3744.3282551942657, y: 844.4790610816565 }, Coordinate { x: -3528.0523052764856, y: 1465.4459224325428 }, Coordinate { x: -3211.7895846268275, y: 2030.7649845350663 }, Coordinate { x: -2808.101736837183, y: 2524.7914293026834 }, Coordinate { x: -2332.058397209177, y: 2934.6862809267104 }, Coordinate { x: -1800.3113258430094, y: 3250.404170670792 }, Coordinate { x: -1230.865112692322, y: 3465.209528149565 }, Coordinate { x: -642.3660652849201, y: 3575.86247638694 }, Coordinate { x: 2922.6159493795944, y: -140.9358037351325 }, Coordinate { x: 2902.3539727399443, y: 523.9595271467309 }, Coordinate { x: 2746.8317356173307, y: 1162.8554209895278 }, Coordinate { x: 2486.4321700624746, y: 1755.982571529817 }, Coordinate { x: 2132.1532698860715, y: 2286.5600564201627 }, Coordinate { x: 1697.7593650183412, y: 2740.3584543964375 }, Coordinate { x: 1198.8583733582022, y: 3105.776754884361 }, Coordinate { x: 652.7232383154001, y: 3374.378217175655 }, Coordinate { x: 77.6020031594331, y: 3541.143827016887 }, Coordinate { x: -3828.47325323343, y: 184.61849396854524 }, Coordinate { x: -3808.21127659378, y: -480.2768369133182 }, Coordinate { x: -3652.6890394711663, y: -1119.172730756115 }, Coordinate { x: -3392.2894739163103, y: -1712.2998812964045 }, Coordinate { x: -3038.010573739907, y: -2242.87736618675 }, Coordinate { x: -2603.616668872177, y: -2696.6757641630247 }, Coordinate { x: -2104.7156772120384, y: -3062.094064650948 }, Coordinate { x: -1558.580542169236, y: -3330.6955269422424 }, Coordinate { x: -983.4593070132689, y: -3497.461136783474 }, Coordinate { x: 2922.6159493795944, y: -140.93580373513205 }, Coordinate { x: 2838.47095134043, y: -800.7963708482438 }, Coordinate { x: 2622.19500142265, y: -1421.76323219913 }, Coordinate { x: 2305.932280772992, y: -1987.0822943016537 }, Coordinate { x: 1902.2444329833472, y: -2481.1087390692705 }, Coordinate { x: 1426.2010933553415, y: -2891.0035906932976 }, Coordinate { x: 894.4540219891734, y: -3206.7214804373793 }, Coordinate { x: 325.0078088384862, y: -3421.526837916152 }, Coordinate { x: -263.4912385689159, y: -3532.1797861535274 }, Coordinate { x: -3828.47325323343, y: 184.61849396854478 }]
// LineString #2
[Coordinate { x: -1176.424962399583, y: 3647.919372311033 }, Coordinate { x: -529.244043614958, y: 3801.7153640888973 }, Coordinate { x: 128.10290468648918, y: 3818.1506604836554 }, Coordinate { x: 768.6086578745783, y: 3721.40289264295 }, Coordinate { x: 1373.2052190509614, y: 3517.714393221754 }, Coordinate { x: 1924.566578897045, y: 3216.6633984372393 }, Coordinate { x: 2407.4235518692108, y: 2830.2932682989103 }, Coordinate { x: 2809.127657487675, y: 2373.079813988442 }, Coordinate { x: 3120.0756936799994, y: 1861.331318591357 }, Coordinate { x: 988.2062330241528, y: -3064.281000918514 }, Coordinate { x: 1603.3046575254384, y: -2811.001951445636 }, Coordinate { x: 2146.4043225685223, y: -2440.302769845651 }, Coordinate { x: 2609.711525971147, y: -1987.5841091694645 }, Coordinate { x: 2981.3977482224786, y: -1469.052182696947 }, Coordinate { x: 3252.9971689669933, y: -902.602886428241 }, Coordinate { x: 3419.1534551134396, y: -306.931145966288 }, Coordinate { x: 3478.0583144543484, y: 298.8250333825231 }, Coordinate { x: 3431.4455537922463, y: 895.8195511936171 }, Coordinate { x: -1176.4249623995825, y: 3647.919372311033 }, Coordinate { x: -1791.5233869008682, y: 3394.640322838155 }, Coordinate { x: -2334.623051943952, y: 3023.941141238169 }, Coordinate { x: -2797.930255346577, y: 2571.2224805619835 }, Coordinate { x: -3169.6164775979087, y: 2052.690554089466 }, Coordinate { x: -3441.215898342423, y: 1486.2412578207595 }, Coordinate { x: -3607.372184488869, y: 890.5695173588066 }, Coordinate { x: -3666.277043829778, y: 284.8133380099955 }, Coordinate { x: -3619.664283167676, y: -312.18117980109855 }, Coordinate { x: 988.2062330241532, y: -3064.281000918514 }, Coordinate { x: 341.02531423952814, y: -3218.0769926963785 }, Coordinate { x: -316.32163406191876, y: -3234.512289091137 }, Coordinate { x: -956.827387250008, y: -3137.7645212504312 }, Coordinate { x: -1561.4239484263912, y: -2934.0760218292353 }, Coordinate { x: -2112.7853082724746, y: -2633.0250270447204 }, Coordinate { x: -2595.6422812446403, y: -2246.6548969063915 }, Coordinate { x: -2997.3463868631047, y: -1789.441442595923 }, Coordinate { x: -3308.294423055429, y: -1277.6929471988385 }, Coordinate { x: -1176.424962399583, y: 3647.919372311033 }]
I've extracted the coordinates posted above into a bare-bones test (see below the fold) which creates two polygons and calls union on them and ran it on bare-metal with release mode. In about two minutes, the union function started hogging ALL THE MEMORY 🤣
At 64GB I had to call it as my poor laptop was beginning to struggle, mind you it pulls 100% CPU load all the time and basically allocates as fast as it can.
Funnily enough 80GB of used memory is still considered a medium memory pressure ... guess it has 300GB of disk space to swap into 🤷♂️
Test code
#[cfg(test)]
mod demo_tests {
use geo::{Coordinate, LineString, Polygon};
use geo_booleanop::boolean::BooleanOp;
#[test]
fn infinite_allocation() {
// LineString #1
let coordinates1 = vec![
Coordinate {
x: -3828.47325323343,
y: 184.61849396854478,
},
Coordinate {
x: -3744.3282551942657,
y: 844.4790610816565,
},
Coordinate {
x: -3528.0523052764856,
y: 1465.4459224325428,
},
Coordinate {
x: -3211.7895846268275,
y: 2030.7649845350663,
},
Coordinate {
x: -2808.101736837183,
y: 2524.7914293026834,
},
Coordinate {
x: -2332.058397209177,
y: 2934.6862809267104,
},
Coordinate {
x: -1800.3113258430094,
y: 3250.404170670792,
},
Coordinate {
x: -1230.865112692322,
y: 3465.209528149565,
},
Coordinate {
x: -642.3660652849201,
y: 3575.86247638694,
},
Coordinate {
x: 2922.6159493795944,
y: -140.9358037351325,
},
Coordinate {
x: 2902.3539727399443,
y: 523.9595271467309,
},
Coordinate {
x: 2746.8317356173307,
y: 1162.8554209895278,
},
Coordinate {
x: 2486.4321700624746,
y: 1755.982571529817,
},
Coordinate {
x: 2132.1532698860715,
y: 2286.5600564201627,
},
Coordinate {
x: 1697.7593650183412,
y: 2740.3584543964375,
},
Coordinate {
x: 1198.8583733582022,
y: 3105.776754884361,
},
Coordinate {
x: 652.7232383154001,
y: 3374.378217175655,
},
Coordinate {
x: 77.6020031594331,
y: 3541.143827016887,
},
Coordinate {
x: -3828.47325323343,
y: 184.61849396854524,
},
Coordinate {
x: -3808.21127659378,
y: -480.2768369133182,
},
Coordinate {
x: -3652.6890394711663,
y: -1119.172730756115,
},
Coordinate {
x: -3392.2894739163103,
y: -1712.2998812964045,
},
Coordinate {
x: -3038.010573739907,
y: -2242.87736618675,
},
Coordinate {
x: -2603.616668872177,
y: -2696.6757641630247,
},
Coordinate {
x: -2104.7156772120384,
y: -3062.094064650948,
},
Coordinate {
x: -1558.580542169236,
y: -3330.6955269422424,
},
Coordinate {
x: -983.4593070132689,
y: -3497.461136783474,
},
Coordinate {
x: 2922.6159493795944,
y: -140.93580373513205,
},
Coordinate {
x: 2838.47095134043,
y: -800.7963708482438,
},
Coordinate {
x: 2622.19500142265,
y: -1421.76323219913,
},
Coordinate {
x: 2305.932280772992,
y: -1987.0822943016537,
},
Coordinate {
x: 1902.2444329833472,
y: -2481.1087390692705,
},
Coordinate {
x: 1426.2010933553415,
y: -2891.0035906932976,
},
Coordinate {
x: 894.4540219891734,
y: -3206.7214804373793,
},
Coordinate {
x: 325.0078088384862,
y: -3421.526837916152,
},
Coordinate {
x: -263.4912385689159,
y: -3532.1797861535274,
},
Coordinate {
x: -3828.47325323343,
y: 184.61849396854478,
},
];
// LineString #2
let coordinates2 = vec![
Coordinate {
x: -1176.424962399583,
y: 3647.919372311033,
},
Coordinate {
x: -529.244043614958,
y: 3801.7153640888973,
},
Coordinate {
x: 128.10290468648918,
y: 3818.1506604836554,
},
Coordinate {
x: 768.6086578745783,
y: 3721.40289264295,
},
Coordinate {
x: 1373.2052190509614,
y: 3517.714393221754,
},
Coordinate {
x: 1924.566578897045,
y: 3216.6633984372393,
},
Coordinate {
x: 2407.4235518692108,
y: 2830.2932682989103,
},
Coordinate {
x: 2809.127657487675,
y: 2373.079813988442,
},
Coordinate {
x: 3120.0756936799994,
y: 1861.331318591357,
},
Coordinate {
x: 988.2062330241528,
y: -3064.281000918514,
},
Coordinate {
x: 1603.3046575254384,
y: -2811.001951445636,
},
Coordinate {
x: 2146.4043225685223,
y: -2440.302769845651,
},
Coordinate {
x: 2609.711525971147,
y: -1987.5841091694645,
},
Coordinate {
x: 2981.3977482224786,
y: -1469.052182696947,
},
Coordinate {
x: 3252.9971689669933,
y: -902.602886428241,
},
Coordinate {
x: 3419.1534551134396,
y: -306.931145966288,
},
Coordinate {
x: 3478.0583144543484,
y: 298.8250333825231,
},
Coordinate {
x: 3431.4455537922463,
y: 895.8195511936171,
},
Coordinate {
x: -1176.4249623995825,
y: 3647.919372311033,
},
Coordinate {
x: -1791.5233869008682,
y: 3394.640322838155,
},
Coordinate {
x: -2334.623051943952,
y: 3023.941141238169,
},
Coordinate {
x: -2797.930255346577,
y: 2571.2224805619835,
},
Coordinate {
x: -3169.6164775979087,
y: 2052.690554089466,
},
Coordinate {
x: -3441.215898342423,
y: 1486.2412578207595,
},
Coordinate {
x: -3607.372184488869,
y: 890.5695173588066,
},
Coordinate {
x: -3666.277043829778,
y: 284.8133380099955,
},
Coordinate {
x: -3619.664283167676,
y: -312.18117980109855,
},
Coordinate {
x: 988.2062330241532,
y: -3064.281000918514,
},
Coordinate {
x: 341.02531423952814,
y: -3218.0769926963785,
},
Coordinate {
x: -316.32163406191876,
y: -3234.512289091137,
},
Coordinate {
x: -956.827387250008,
y: -3137.7645212504312,
},
Coordinate {
x: -1561.4239484263912,
y: -2934.0760218292353,
},
Coordinate {
x: -2112.7853082724746,
y: -2633.0250270447204,
},
Coordinate {
x: -2595.6422812446403,
y: -2246.6548969063915,
},
Coordinate {
x: -2997.3463868631047,
y: -1789.441442595923,
},
Coordinate {
x: -3308.294423055429,
y: -1277.6929471988385,
},
Coordinate {
x: -1176.424962399583,
y: 3647.919372311033,
},
];
let line1 = LineString(coordinates1);
let line2 = LineString(coordinates2);
let polygon1 = Polygon::new(line1, vec![]);
let polygon2 = Polygon::new(line2, vec![]);
println!("Running union");
let union = polygon1.union(&polygon2);
panic!("union result {:?}", union);
}
}
Throwing the polygons into Desmos revealed a nasty bug in my polygon generation logic and it seems like the resulting shapes are overlapping themselves in unexpected ways. I'll definitely fix those issues and with a "proper" polygon it will likely work. Regardless, I'd expect the library to not allocate infinite memory either way 😄
Would be interesting to try this with the array-stump implementation (non-recursive) instead of the splay tree (recursive), to see if this data really just requires a huge stack (unlikely, right?).
Do you have a working version of the crate with the non-recursive implementation somewhere? If so I could give it a try.
I only have this old branch, but I cannot remember if it is in a usable state (or how much of the order-fixing-logic went into that branch). IIRC @daef also had a branch that was more up-to-date.
If the recursion depth turns out to be a true problem it would make sense to switch to the array-stump implementation even without the order-fixing-stuff it was primarily designed for...
Afair it was working pretty neat when I stopped working on it the last time..:
https://github.com/daef/rust-geo-booleanop/commits/feature/specialized_data_structure_for_sweep_line
Since I'm currently up to something completely different I don't feel like debugging this for now, but someone interested could easily try this problem against that branch in no time...
