# [−][src]Crate vpsearch

A relatively simple and readable Rust implementation of Vantage Point tree search algorithm.

The VP tree algorithm doesn't need to know coordinates of items, only distances between them. It can efficiently search multi-dimensional spaces and abstract things as long as you can define similarity between them (e.g. points, colors, and even images).

This algorithm does not work with squared distances. When implementing Euclidean distance, you MUST use `sqrt()`. You really really can't use that optimization. There's no way around it. Vantage Point trees require metric spaces.

```#[derive(Copy, Clone)]
struct Point {
x: f32, y: f32,
}

impl vpsearch::MetricSpace for Point {
type UserData = ();
type Distance = f32;

fn distance(&self, other: &Self, _: &Self::UserData) -> Self::Distance {
let dx = self.x - other.x;
let dy = self.y - other.y;
(dx*dx + dy*dy).sqrt() // sqrt is required
}
}

fn main() {
let points = vec![Point{x:2.0,y:3.0}, Point{x:0.0,y:1.0}, Point{x:4.0,y:5.0}];
let vp = vpsearch::Tree::new(&points);
let (index, _) = vp.find_nearest(&Point{x:1.0,y:2.0});
println!("The nearest point is at ({}, {})", points[index].x, points[index].y);
}```
```#[derive(Clone)]

type UserData = ();
type Distance = f64;

fn distance(&self, other: &Self, _: &Self::UserData) -> Self::Distance {
let dist_squared = self.0.iter().copied().zip(other.0.iter().copied())
.map(|(a, b)| {
(a as i32 - b as i32).pow(2) as u32
}).sum::<u32>();

(dist_squared as f64).sqrt() // sqrt is required
}
}

fn main() {