Stack overflow in add_to_bucket about kdtree-rs HOT 2 CLOSED

Hey i'm not actively working on this crate. Please reopen if you have can provide a case to reproduce or would like to submit a PR. Thanks.

from kdtree-rs.

I get the same error when I use this crate.

And I figured out the reason.

The avg will be equal to a, under the limit of f64's accuracy. As a result, the fn split() can't split this node successfully. In this situation, fn add_to_bucket() and fn split() will call each other infinitely.

    let a = 0.47945351705599926f64;
    let b = 0.47945351705599931f64;
    
    let avg = (a + b) / 2.0;

    println!("{:.20E}", a);
    println!("{:.20E}", b);
    println!("{:.20E}", avg);

And the resolution is extremely easy. Just modify fn belongs_in_left() like this

fn belongs_in_left(&self, point: &[A]) -> bool {
        // before
        // point[self.split_dimension.unwrap()] < self.split_value.unwrap()
        // after
        point[self.split_dimension.unwrap()] <= self.split_value.unwrap()
}

from kdtree-rs.