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

[trehn]

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]

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

[mourner]

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

[Roughsketch]

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:

delaunator-rs/src/lib.rs

Lines 230 to 235 in 82ddbdb

	let mut e = hull.start;
	loop {
	if hull.tri[e] == bl {
	hull.tri[e] = a;
	break;
	}

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]

@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!