search

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

Fixes mourner/delaunator-rs#8 - panics index out of bounds #13

Closed andreesteve closed 3 years ago

andreesteve commented 3 years ago

I believe this fixes #8 I was able to narrow a repro with the following smaller set of points:

fn main() {
    let s = vec![
        Point { x: -0.2, y: -0.26 },
        Point { x: -0.5, y: -0.57 },
        Point { x: -0.06, y: 0.4 },
        Point { x: 0.0, y: 0.47 },
        Point { x: 0.6, y: 0.0 },
        Point { x: -0.9, y: -0.8 },
    ];

    triangulate(&s);
}

Which now passes. This error was happening on my 10M random point benchmark, which now passes consistently with this patch.

I haven't yet got a chance to validate the correctness of the generated triangulation. I'll do that next, but wanted to get the PR out for early review.

Comparing with the javascript implementation this seems to match the implementation there, so it gives me some hope this is the right fix.