add_constraint_and_split panics

[SethPipho]

I encountered a panic when using add_constraint_and_split. I was able to find a minimal example via fuzzing.

thread 'main' panicked at C:\Users\Seth.Pipho\.cargo\registry\src\index.crates.io-6f17d22bba15001f\spade-2.9.0\src\delaunay_core\triangulation_ext.rs:447:17:
Failed to locate position. This is a bug in spade.

use spade::{ConstrainedDelaunayTriangulation, Point2, Triangulation};

fn main() {
    let lines = vec![
        (
            Point2 {
                x: 0.9296344883099084,
                y: 0.03071359966930065,
            },
            Point2 {
                x: 0.26031306872107085,
                y: 0.34491289915959455,
            },
        ),
        (
            Point2 {
                x: 0.7384289920396423,
                y: 0.4981747664368982,
            },
            Point2 {
                x: 0.06543525273452533,
                y: 0.34139896206401854,
            },
        ),
        (
            Point2 {
                x: 0.9535295221136963,
                y: 0.9114305148801416,
            },
            Point2 {
                x: 0.8306091165247367,
                y: 0.08959389670590667,
            },
        ),
        (
            Point2 {
                x: 0.9081582053528728,
                y: 0.4974568601123005,
            },
            Point2 {
                x: 0.5138795569454557,
                y: 0.3186272217036502,
            },
        ),
    ];
    let mut cdt = ConstrainedDelaunayTriangulation::<Point2<f64>>::new();

    for (a, b) in lines.iter() {
        let a = cdt.insert(a.clone()).unwrap();
        let b = cdt.insert(b.clone()).unwrap();

        cdt.add_constraint_and_split(a, b, |v| v);
    }
}

[Stoeoef]

Ugh, that's the same as #98 , just the orientation is different. I somehow thought that this shouldn't be possible after changing the winding order.

In short, Spade tries to find the face where the target point (coloured in salmon in the image below) lies by "turning right" whenever it finds an edge that has the target point to its right.

Due to how the constraint edges overlap, this results in an endless loop which, luckily will be detected and panics.

The edges traversed are these:

1 -> 0
5 -> 0
5 -> 4
2 -> 4
2 -> 3
1 -> 3
1 -> 0
... repeats

I'm not sure what the best solution is yet but keep you updated. Thanks so much for the report!

(And I should probably create a fuzzer for CDTs to catch this myself!)

[Stoeoef]

Fixed in version 2.10.0 (just released). I have redesigned the locate-strategy this time completely - that should hopefully fix this kind of issue once and for all.

Thanks again for the report!

Feel free to roast the new version with your fuzzing setup :grin: