Struct Tree 

pub struct Tree<Item: MetricSpace<Impl> + Clone, Impl = (), Ownership = Owned<()>> { /* private fields */ }

The VP-Tree.

Implementations

impl<Item: MetricSpace<Impl, UserData = ()> + Clone, Impl> Tree<Item, Impl, Owned<()>>

pub fn new(items: &[Item]) -> Self

Creates a new tree from items. Maximum number of items is 2^31.

See Tree::new_with_user_data_owned.

Examples found in repository

examples/orphan_rule.rs (line 17)

fn main() {
    let source_data = vec![vec![0; 64], vec![5; 64], vec![10; 64]];
    let vp = vpsearch::Tree::new(&source_data);
    let (index, dist) = vp.find_nearest(&vec![6; 64]);
    println!("The element at {index} is the nearest, off by {dist}");
}

examples/points.rs (line 22)

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);
}

examples/newtype_ref.rs (line 20)

fn main() {
    let source_data = [[0; 64], [5; 64], [10; 64]];
    let reference_data: Vec<_> = source_data.iter().map(LotsaDimensions).collect();
    let vp = vpsearch::Tree::new(&reference_data);
    let (index, dist) = vp.find_nearest(&LotsaDimensions(&[6; 64]));
    println!("The element at {index} is the nearest, off by {dist}");
}

examples/radius_nn.rs (line 88)

fn main() {
    let points = vec![
        PointN::new([2.0, 3.0]),
        PointN::new([0.0, 1.0]),
        PointN::new([4.0, 5.0]),
    ];
    let tree = vpsearch::Tree::new(&points);

    // Search with a distance of 0, expect no points to be returned
    let expected = HashSet::new();
    let actual = tree.find_nearest_custom(
        &PointN::new([1.0, 2.0]),
        &(),
        RadiusBasedNeighborhood::new(0.0f32),
    );
    assert_eq!(actual, expected);

    // Search with a distance of 100, expect all points to be returned
    let expected = [0, 1, 2].iter().copied().collect::<HashSet<usize>>();
    let actual = tree.find_nearest_custom(
        &PointN::new([1.0, 2.0]),
        &(),
        RadiusBasedNeighborhood::new(100.0f32),
    );
    assert_eq!(actual, expected);
}

examples/knn.rs (line 133)

fn main() {
    let points = vec![
        PointN::new([2.0, 3.0]),
        PointN::new([0.0, 1.0]),
        PointN::new([4.0, 5.0]),
    ];
    let tree = vpsearch::Tree::new(&points);

    // Search with a neigboord size of 1, expect a single points to be returned
    let actual = tree.find_nearest_custom(
        &PointN::new([1.0, 2.0]),
        &(),
        CountBasedNeighborhood::new(1),
    );
    assert_eq!(actual.len(), 1);

    // Search with a neigboord size of 2, expect a two points to be returned
    let expected = [0, 1].iter().copied().collect::<HashSet<usize>>();
    let actual = tree.find_nearest_custom(
        &PointN::new([1.0, 2.0]),
        &(),
        CountBasedNeighborhood::new(2),
    );
    assert_eq!(actual, expected);

    // Search with a neigboord size of 10, expect all points to be returned
    let expected = [0, 1, 2].iter().copied().collect::<HashSet<usize>>();
    let actual = tree.find_nearest_custom(
        &PointN::new([1.0, 2.0]),
        &(),
        CountBasedNeighborhood::new(10),
    );
    assert_eq!(actual, expected);
}

impl<U, Impl, Item: MetricSpace<Impl, UserData = U> + Clone> Tree<Item, Impl, Owned<U>>

pub fn find_nearest(&self, needle: &Item) -> (usize, Item::Distance)

Finds item closest to the given needle (that can be any item) and returns index of the item in items array from new().

Returns the index of the nearest item (index from the items slice passed to new()) found and the distance from the nearest item.

Examples found in repository

examples/orphan_rule.rs (line 18)

fn main() {
    let source_data = vec![vec![0; 64], vec![5; 64], vec![10; 64]];
    let vp = vpsearch::Tree::new(&source_data);
    let (index, dist) = vp.find_nearest(&vec![6; 64]);
    println!("The element at {index} is the nearest, off by {dist}");
}

examples/points.rs (line 24)

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);
}

examples/newtype_ref.rs (line 21)

fn main() {
    let source_data = [[0; 64], [5; 64], [10; 64]];
    let reference_data: Vec<_> = source_data.iter().map(LotsaDimensions).collect();
    let vp = vpsearch::Tree::new(&reference_data);
    let (index, dist) = vp.find_nearest(&LotsaDimensions(&[6; 64]));
    println!("The element at {index} is the nearest, off by {dist}");
}

impl<Item: MetricSpace<Impl> + Clone, Impl> Tree<Item, Impl, Owned<Item::UserData>>

pub fn new_with_user_data_owned( items: &[Item], user_data: Item::UserData, ) -> Self

Create a Vantage Point tree for fast nearest neighbor search.

• items — Array of items that will be searched.
• user_data — Reference to any object that is passed down to item.distance()

impl<Item: MetricSpace<Impl> + Clone, Impl> Tree<Item, Impl, ()>

pub fn new_with_user_data_ref( items: &[Item], user_data: &Item::UserData, ) -> Self

The tree doesn’t have to own the UserData. You can keep passing it to find_nearest().

pub fn find_nearest( &self, needle: &Item, user_data: &Item::UserData, ) -> (usize, Item::Distance)

impl<Item: MetricSpace<Impl> + Clone, Ownership, Impl> Tree<Item, Impl, Ownership>

pub fn find_nearest_custom<ReturnBy: BestCandidate<Item, Impl>>( &self, needle: &Item, user_data: &Item::UserData, best_candidate: ReturnBy, ) -> ReturnBy::Output

All the bells and whistles version. For best_candidate implement BestCandidate<Item, Impl> trait.

Examples found in repository

examples/radius_nn.rs (lines 92-96)

fn main() {
    let points = vec![
        PointN::new([2.0, 3.0]),
        PointN::new([0.0, 1.0]),
        PointN::new([4.0, 5.0]),
    ];
    let tree = vpsearch::Tree::new(&points);

    // Search with a distance of 0, expect no points to be returned
    let expected = HashSet::new();
    let actual = tree.find_nearest_custom(
        &PointN::new([1.0, 2.0]),
        &(),
        RadiusBasedNeighborhood::new(0.0f32),
    );
    assert_eq!(actual, expected);

    // Search with a distance of 100, expect all points to be returned
    let expected = [0, 1, 2].iter().copied().collect::<HashSet<usize>>();
    let actual = tree.find_nearest_custom(
        &PointN::new([1.0, 2.0]),
        &(),
        RadiusBasedNeighborhood::new(100.0f32),
    );
    assert_eq!(actual, expected);
}

examples/knn.rs (lines 136-140)

fn main() {
    let points = vec![
        PointN::new([2.0, 3.0]),
        PointN::new([0.0, 1.0]),
        PointN::new([4.0, 5.0]),
    ];
    let tree = vpsearch::Tree::new(&points);

    // Search with a neigboord size of 1, expect a single points to be returned
    let actual = tree.find_nearest_custom(
        &PointN::new([1.0, 2.0]),
        &(),
        CountBasedNeighborhood::new(1),
    );
    assert_eq!(actual.len(), 1);

    // Search with a neigboord size of 2, expect a two points to be returned
    let expected = [0, 1].iter().copied().collect::<HashSet<usize>>();
    let actual = tree.find_nearest_custom(
        &PointN::new([1.0, 2.0]),
        &(),
        CountBasedNeighborhood::new(2),
    );
    assert_eq!(actual, expected);

    // Search with a neigboord size of 10, expect all points to be returned
    let expected = [0, 1, 2].iter().copied().collect::<HashSet<usize>>();
    let actual = tree.find_nearest_custom(
        &PointN::new([1.0, 2.0]),
        &(),
        CountBasedNeighborhood::new(10),
    );
    assert_eq!(actual, expected);
}

Trait Implementations

impl<Item: Debug + Clone + MetricSpace<UserImpl>, UserImpl, Ownership> Debug for Tree<Item, UserImpl, Ownership>

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.