Midpoint has 2 redundant distance computation, which are expensive

[abstractqqq]

Current Impl of midpoint is very redundant

fn midpoint<P: Point>(a: &P, b: &P) -> P {
    let d = a.distance(b);
    a.move_towards(b, d / 2.0)
}

  fn move_towards(&self, other: &Self, d: f64) -> Self {
      let mut result = self.clone();

      let distance = self.distance(other);

      // Don't want to get a NaN in the division below
      if distance == 0.0 {
          return result;
      }

      let scale = d / self.distance(other);

      for i in 0..D {
          result[i] += scale * (other[i] - self[i]);
      }

      result
  }

Note that mathematically, the code below is equivalent. You can see it by substituting the symbols.

fn midpoint<P: Point>(a: &P, b: &P) -> P {
    let new_point = a.clone();
    for i in 0..D {
        new_point[i] += 0.5 * (b[i] - a[i]);
    }
   new_point
}

This has huge performance implications when dealing with a big tree construction.

[grantslatton]

Fixed by d2b88e3

[abstractqqq]

Fixed by d2b88e3

That was quick! Thanks for the response.

Btw, I would love to contribute to this repo but I am still going through the code and the theory about ball trees, etc, etc. I am afraid I might not go with your design in the end.

[grantslatton]

@abstractqqq The code is hopefully small and easy to understand (and I'm sure you can paste the whole thing into ChatGPT to get more explanation)

That said, Rust has got a lot of new features since I first wrote this in 2018, and I have learned a lot about writing libraries and high-perf code since then, so I would probably write it differently too :)

Feel free to link me to any repo you make, or if you want to contribute to this one.