Wrong split dimension

[jeromerobert]

Using this code:

use std::{
    fs::File,
    io::{BufRead, BufReader},
};

fn main() {
    let f = File::open("pointcloud.dat").expect("Unable to open file");
    let br = BufReader::new(f);
    let mut coords = Vec::new();
    for line in br.lines() {
        let line = line.unwrap();
        let xyz = line
            .split(' ')
            .filter_map(|s| s.parse::<f64>().ok())
            .collect::<Vec<_>>();
        assert_eq!(xyz.len(), 3);
        coords.push(xyz.as_slice().try_into().unwrap());
    }
    let mut tree = kiddo::KdTree::<f64, 3>::new();
    tree.extend(coords.iter().enumerate().map(|(id, &pnt)| (pnt, id as u64)));
}

I get this error:

thread 'main' panicked at /home/robert/.cargo/registry/src/index.crates.io-6f17d22bba15001f/kiddo-4.2.0/src/float/construction.rs:223:25:
Too many items with the same position on one axis. Bucket size must be increased to at least 1 more than the number of items with the same position on one axis.
stack backtrace:
   0: rust_begin_unwind
             at /rustc/82e1608dfa6e0b5569232559e3d385fea5a93112/library/std/src/panicking.rs:645:5
   1: core::panicking::panic_fmt
             at /rustc/82e1608dfa6e0b5569232559e3d385fea5a93112/library/core/src/panicking.rs:72:14
   2: kiddo::float::construction::<impl kiddo::float::kdtree::KdTree<A,T,_,_,IDX>>::split
             at /home/robert/.cargo/registry/src/index.crates.io-6f17d22bba15001f/kiddo-4.2.0/src/float/construction.rs:223:25
   3: kiddo::float::construction::<impl kiddo::float::kdtree::KdTree<A,T,_,_,IDX>>::add
             at /home/robert/.cargo/registry/src/index.crates.io-6f17d22bba15001f/kiddo-4.2.0/src/float/construction.rs:56:28
   4: kiddo::float::construction::<impl core::iter::traits::collect::Extend<([A; K],T)> for kiddo::float::kdtree::KdTree<A,T,_,_,IDX>>::extend
             at /home/robert/.cargo/registry/src/index.crates.io-6f17d22bba15001f/kiddo-4.2.0/src/float/construction.rs:314:13
   5: test_kiddo::main
             at ./src/main.rs:20:5
   6: core::ops::function::FnOnce::call_once
             at /rustc/82e1608dfa6e0b5569232559e3d385fea5a93112/library/core/src/ops/function.rs:250:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

I'm aware that it's not very useful without the pointcloud.dat file, but I cannot share it. Fortunately the bug seems pretty clear.

Looking at the source code the split dimension is incremented without checking the shape of the nodes: split_dim = (split_dim + 1).rem(K);. My points are scattered all over the 3D space, but during the recursion kiddo create a node where all the points in node are on the Z=0 plane (IMHO this is fine). This node contains too many points and must be splitted. It should be splitted in the X or Y direction, but kiddo choose the Z direction (IMHO this THE bug).

Unfortunately the split_dim = (split_dim + 1).rem(K); snippet is used when creating the kd-tree (both mutable and immutable) but also in the queries. It makes the bug not that easy to fix for me.

[jeromerobert]

Sorry this is a duplicate of #78

[sdd]

This issue should be resolved in https://github.com/sdd/kiddo/pull/186 as part of the rewrite of the ImmutableKdTree, which was just released as Kiddo v5.0.0 🎉

https://crates.io/crates/kiddo/5.0.0

I know this issue was raised a while ago, and you have probably moved on, but if you do get chance to try v5 I'd love to hear any feedback. I'm closing this issue.