mourner / delaunator-rs

Fast 2D Delaunay triangulation in Rust. A port of Delaunator.
https://docs.rs/delaunator
ISC License
207 stars 28 forks source link

Crash: index out of bounds: the len is 14 but the index is 18446744073709551615 #8

Closed trehn closed 3 years ago

trehn commented 5 years ago

I'm trying to triangulate a detailed map of the world. On several "chunks" (think islands on the map) of my data, delaunator crashes. Here is one example:

extern crate delaunator;

use delaunator::{Point, triangulate};

fn main() {
    let points = vec!(
        Point { x: 11.484139442443848, y: 65.20500183105469 },
        Point { x: 11.484139442443848, y: 65.2066421508789 },
        Point { x: 11.484999656677246, y: 65.20708465576172 },
        Point { x: 11.491666793823242, y: 65.20708465576172 },
        Point { x: 11.492444038391113, y: 65.2066650390625 },
        Point { x: 11.492500305175781, y: 65.20580291748047 },
        Point { x: 11.491639137268066, y: 65.20541381835938 },
        Point { x: 11.489860534667969, y: 65.20541381835938 },
        Point { x: 11.488332748413086, y: 65.20622253417969 },
        Point { x: 11.487471580505371, y: 65.2058334350586 },
        Point { x: 11.487388610839844, y: 65.20500183105469 },
        Point { x: 11.486528396606445, y: 65.20455932617188 },
        Point { x: 11.484916687011719, y: 65.20458221435547 },
        Point { x: 11.484139442443848, y: 65.20500183105469 },
    );
    let result = triangulate(&points).expect("No triangulation exists.");
    println!("{:?}", result.triangles);
}

When I run this code, delaunator panics:

> rustc -V
rustc 1.30.1 (1433507eb 2018-11-07)
> RUST_BACKTRACE=1 cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s                                                                                 
     Running `target/debug/tmprusttest`
thread 'main' panicked at 'index out of bounds: the len is 14 but the index is 18446744073709551615', libcore/slice/mod.rs:2046:10
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
   1: std::sys_common::backtrace::print
             at libstd/sys_common/backtrace.rs:71
             at libstd/sys_common/backtrace.rs:59
   2: std::panicking::default_hook::{{closure}}
             at libstd/panicking.rs:211
   3: std::panicking::default_hook
             at libstd/panicking.rs:227
   4: std::panicking::rust_panic_with_hook
             at libstd/panicking.rs:477
   5: std::panicking::continue_panic_fmt
             at libstd/panicking.rs:391
   6: rust_begin_unwind
             at libstd/panicking.rs:326
   7: core::panicking::panic_fmt
             at libcore/panicking.rs:77
   8: core::panicking::panic_bounds_check
             at libcore/panicking.rs:59
   9: <usize as core::slice::SliceIndex<[T]>>::index
             at libcore/slice/mod.rs:2046
  10: core::slice::<impl core::ops::index::Index<I> for [T]>::index
             at libcore/slice/mod.rs:1914
  11: <alloc::vec::Vec<T> as core::ops::index::Index<I>>::index
             at liballoc/vec.rs:1725
  12: delaunator::Triangulation::legalize
             at /home/trehn/.cargo/registry/src/github.com-1ecc6299db9ec823/delaunator-0.2.0/src/lib.rs:232
  13: delaunator::triangulate
             at /home/trehn/.cargo/registry/src/github.com-1ecc6299db9ec823/delaunator-0.2.0/src/lib.rs:484
  14: tmprusttest::main
             at src/main.rs:27
  15: std::rt::lang_start::{{closure}}
             at libstd/rt.rs:74
  16: std::panicking::try::do_call
             at libstd/rt.rs:59
             at libstd/panicking.rs:310
  17: __rust_maybe_catch_panic
             at libpanic_unwind/lib.rs:103
  18: std::rt::lang_start_internal
             at libstd/panicking.rs:289
             at libstd/panic.rs:392
             at libstd/rt.rs:58
  19: std::rt::lang_start
             at libstd/rt.rs:74
  20: main
  21: __libc_start_main
  22: _start

Any idea what's going on here?

mourner commented 5 years ago

Interesting! Might be a bug — will look at it next week.

mourner commented 5 years ago

The reference implementation (Delaunator in JavaScript) works fine on that input, so must be something off in the port.

Roughsketch commented 5 years ago

I've been getting the same issue while trying out this library. It makes it impossible to use for my purpose since it involves lots of calls with moving points. It seems I can only loop a few thousand times on average before it hits this and crashes.

From what I can tell the cause is on line 232: https://github.com/mourner/delaunator-rs/blob/82ddbdb33651139414f2fe581f67dc12522dec32/src/lib.rs#L230-L235

e at this point will be -1, or EMPTY, and instead of handling the empty value it instead tries to index into the slice. I do not know enough about the algorithm to know what is causing this, so I'm not sure if a simple empty check would suffice.

andreesteve commented 3 years ago

@mourner - whenever you get some time, do you think you could do a package release on crates.io with this fix? I use this crate on my library and I'd love to be able to reference the package version with this fix. Let me know if I can help in any way. Thank you!