KdTree::remove() fails in some circumstances

[abey79]

I have been able to narrow down a case where remove() incorrectly fails to remove an item, returning 0:

#[test]
    fn test_kiddo_bug() {
        let pts = vec![
            [19.2023, 7.1812],
            [7.6427, 22.5779],
            [26.6314, 34.8920],
            [36.7890, 27.2663],
            [28.3226, 8.5047],
            [5.3914, 28.1360],
            [5.0978, 3.6814],
            [0.5114, 11.6552],
            [4.7981, 21.6210],
            [29.0030, 9.6799],
            [35.5580, 1.8891],
            [3.9160, 25.5702],
            [22.2497, 31.6140],
            [30.7110, 36.7514],
            [0.2828, 12.4298],
            [20.0206, 3.0635],
            [30.6153, 2.8582],
            [23.7179, 6.2048],
            [13.0438, 4.2319],
            [4.6433, 30.9660],
            [5.0588, 5.2028],
            [19.2023, 23.7406],
            [37.3171, 32.7523],
            [12.6957, 15.7080],
            [15.6001, 14.3995],
            [36.0203, 21.0366],
            [6.3956, 2.7644],
            [3.1719, 8.7039],
            [0.9159, 12.2299],
            [23.8157, 14.0699],
            [27.7757, 7.3597],
            [28.4198, 31.3427],
            [2.3290, 6.2364],
            [10.1126, 7.7009],
        ];

        let mut tree = KdTree::<f64, 2>::new();

        for (i, pt) in pts.iter().enumerate() {
            tree.add(pt, i);
        }

        assert_eq!(tree.remove(&pts[0], 0), 1);
    }

This test fails as tree.remove(&pts[0], 0) return 0. Commenting out any of the points in the input array makes the test pass. Removing any/all of the points except 0 works. Removing index 0 fails in all circumstances.

Also, this failing case appears to be sensitive to the specific order of the input points. I can't reproduce the fail by moving points around.

kiddo 2.0.0-beta.5
Toolchain: nightly-2023-03-03
macOS Ventura 13.2.1 on MBP M1 Max

[sdd]

Thanks for this report too. This is a strange one! Looks like I'll have to break out the debugger for this one...

[sdd]

Confirmed, I see the same behaviour. Looking into it now

[sdd]

Fixed! Released as https://crates.io/crates/kiddo/2.0.0-beta.7.

Thanks a lot for the example, it was invaluable in tracking down the problem!

Please do let me know how you get on if you continue to use the v2 beta, especially if you experience any more issues - happy to help.

[abey79]

Great, thanks!

[wentasah]

It seems there is more problems with point removals. See #28.