Running convex hull on LineString causes a panic

[frewsxcv]

Discovered while fuzzing.

Add this to src/algorithm/convex_hull/test.rs:

#[test]
fn test_foo() {
    let line_string = LineString(
        vec![
            Coordinate { x: -26711958.00000000000000000000000000000000, y: 0.00000000000000000000000000002010f32 },
            Coordinate { x: 0.00000268524786406487692147493362, y: -26711958.00000000000000000000000000000000 },
            Coordinate { x: -26711958.00000000000000000000000000000000, y: -26711958.00000000000000000000000000000000 },
            Coordinate { x: -9624178056385058486995749175296.00000000000000000000000000000000, y: -9624201630438540972264655945728.00000000000000000000000000000000 },
        ],
    );
    let res = line_string.convex_hull();
}

Run RUST_BACKTRACE=1 cargo test test_foo:

running 1 test
test algorithm::convex_hull::test::test_foo ... FAILED

failures:

---- algorithm::convex_hull::test::test_foo stdout ----
thread 'algorithm::convex_hull::test::test_foo' panicked at 'called `Option::unwrap()` on a `None` value', geo/src/algorithm/convex_hull/qhull.rs:103:30
stack backtrace:
   0: rust_begin_unwind
             at /rustc/25c8c53dd994acb3f4f7c02fe6bb46076393f8b0/library/std/src/panicking.rs:483
   1: core::panicking::panic_fmt
             at /rustc/25c8c53dd994acb3f4f7c02fe6bb46076393f8b0/library/core/src/panicking.rs:85
   2: core::panicking::panic
             at /rustc/25c8c53dd994acb3f4f7c02fe6bb46076393f8b0/library/core/src/panicking.rs:50
   3: core::option::Option<T>::unwrap
             at /Users/coreyf/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/library/core/src/option.rs:383
   4: geo::algorithm::convex_hull::qhull::hull_set::{{closure}}
             at ./src/algorithm/convex_hull/qhull.rs:103
   5: core::ops::function::impls::<impl core::ops::function::FnOnce<A> for &mut F>::call_once
             at /Users/coreyf/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/library/core/src/ops/function.rs:280
   6: core::cmp::max_by
             at /Users/coreyf/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/library/core/src/cmp.rs:1011
   7: core::iter::traits::iterator::Iterator::max_by::fold::{{closure}}
             at /Users/coreyf/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/library/core/src/iter/traits/iterator.rs:2557
   8: <core::iter::adapters::Enumerate<I> as core::iter::traits::iterator::Iterator>::fold::enumerate::{{closure}}
             at /Users/coreyf/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/library/core/src/iter/adapters/mod.rs:1434
   9: core::iter::adapters::map_fold::{{closure}}
             at /Users/coreyf/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/library/core/src/iter/adapters/mod.rs:905
  10: core::iter::traits::iterator::Iterator::fold
             at /Users/coreyf/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/library/core/src/iter/traits/iterator.rs:2023
  11: <core::iter::adapters::Map<I,F> as core::iter::traits::iterator::Iterator>::fold
             at /Users/coreyf/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/library/core/src/iter/adapters/mod.rs:945
  12: <core::iter::adapters::Enumerate<I> as core::iter::traits::iterator::Iterator>::fold
             at /Users/coreyf/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/library/core/src/iter/adapters/mod.rs:1441
  13: core::iter::traits::iterator::Iterator::fold_first
             at /Users/coreyf/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/library/core/src/iter/traits/iterator.rs:2064
  14: core::iter::traits::iterator::Iterator::max_by
             at /Users/coreyf/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/library/core/src/iter/traits/iterator.rs:2560
  15: geo::algorithm::convex_hull::qhull::hull_set
             at ./src/algorithm/convex_hull/qhull.rs:91
  16: geo::algorithm::convex_hull::qhull::quick_hull
             at ./src/algorithm/convex_hull/qhull.rs:58
  17: <geo_types::line_string::LineString<T> as geo::algorithm::convex_hull::ConvexHull>::convex_hull
             at ./src/algorithm/convex_hull/mod.rs:76
  18: geo::algorithm::convex_hull::test::test_foo
             at ./src/algorithm/convex_hull/test.rs:93
  19: geo::algorithm::convex_hull::test::test_foo::{{closure}}
             at ./src/algorithm/convex_hull/test.rs:84
  20: core::ops::function::FnOnce::call_once
             at /Users/coreyf/.rustup/toolchains/nightly-x86_64-apple-darwin/lib/rustlib/src/rust/library/core/src/ops/function.rs:227
  21: core::ops::function::FnOnce::call_once
             at /rustc/25c8c53dd994acb3f4f7c02fe6bb46076393f8b0/library/core/src/ops/function.rs:227
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.


failures:
    algorithm::convex_hull::test::test_foo

[rmanoka]

The calculation at: https://github.com/georust/geo/blob/master/geo/src/algorithm/convex_hull/qhull.rs#L98 seems to overflow and produce nan for the input. What would be a good fix here?

[urschrei]

My initial impulse would be to ask "What happens to GEOS for this input ?". But in general, we should perhaps switch to returning a Result, check for None on line 101, and return early with an Err if we overflow?

[frewsxcv]

My initial impulse would be to ask "What happens to GEOS for this input ?"

this is what gdal gives back:

POLYGON ((
    -9.624178E+3 -9.6242016E+3,
    -26711958 0.0,0.0000026852479 -26711958,
    -9.624178E+3 -9.6242016E+3
))

[urschrei]

I wonder whether GDAL / GEOS has any notion of f32…

Do we get the same failure on f64 input?

[frewsxcv]

using f64, gdal returns:

POLYGON ((
    -9.62417805638506E+3 -9.62420163043854E+3,
    -26711958 0.0,0.000002685247864 -26711958,
    -9.62417805638506E+3 -9.62420163043854E+3
))

[frewsxcv]

and the original geo panic here disappears with f64

[rmanoka]

Once we make the Kernel trait public, users can implement HasKernel for arbit. / higher precision data-types, and the accuracy / range should improve. That's a great benefit of the way geo-types structs are generics.