Stack overflow for some big polygons

[amandasaurus]

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)

[bluenote10]

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.

[TilBlechschmidt]

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 }]

[TilBlechschmidt]

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);
    }
}

[TilBlechschmidt]

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 😄

[bluenote10]

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?).

[TilBlechschmidt]

Do you have a working version of the crate with the non-recursive implementation somewhere? If so I could give it a try.

[bluenote10]

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...

[daef]

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...