pub enum KdNode<T: KDT> {
Empty,
Node {
point: Point<T>,
dim: Dim,
left: Box<KdNode<T>>,
right: Box<KdNode<T>>,
},
}
Variants§
Implementations§
Source§impl<T: KDT + Mul<Output = T> + Sub<Output = T> + Add<Output = T> + Debug> KdNode<T>
impl<T: KDT + Mul<Output = T> + Sub<Output = T> + Add<Output = T> + Debug> KdNode<T>
Sourcepub fn new() -> Self
pub fn new() -> Self
Create a new empty tree
Examples found in repository?
7fn main() {
8 let mut node: KdNode<i32> = KdNode::new();
9 assert_eq!(node, Empty);
10
11 // Tree Root
12 node.insert(1, 1);
13 node.insert(2, 2);
14 node.insert(2, -12);
15
16 println!("{:?}", node);
17 println!("{:?}", node.nearest_neighbor_x_y(1, 1, 1.0));
18 println!("{:?}", node.nearest_neighbor(Point{x: 1, y: 1}, 1.0));
19}
Sourcepub fn insert(&mut self, x: T, y: T) -> &Self
pub fn insert(&mut self, x: T, y: T) -> &Self
Insert a new item into the tree
This should used sparingly as it can unbalance the tree and reduce performance. If there is a large change to the dataset it is better to create a new tree. This effect has not been tested though and could be totally fine in terms of performance for a large number of inserts. A good rule of thumb may be if the tree size is going to increase by more than 10% it may be better to create a new tree.
Examples found in repository?
7fn main() {
8 let mut node: KdNode<i32> = KdNode::new();
9 assert_eq!(node, Empty);
10
11 // Tree Root
12 node.insert(1, 1);
13 node.insert(2, 2);
14 node.insert(2, -12);
15
16 println!("{:?}", node);
17 println!("{:?}", node.nearest_neighbor_x_y(1, 1, 1.0));
18 println!("{:?}", node.nearest_neighbor(Point{x: 1, y: 1}, 1.0));
19}
Sourcepub fn insert_point(&mut self, item: Point<T>) -> &Self
pub fn insert_point(&mut self, item: Point<T>) -> &Self
Insert a new item into the tree
This is the same as insert
but takes a Point
instead of x
and y
Sourcepub fn nearest_neighbor<'a>(
&self,
origin: Point<T>,
radius: f64,
) -> Vec<Point<T>>
pub fn nearest_neighbor<'a>( &self, origin: Point<T>, radius: f64, ) -> Vec<Point<T>>
Find the nearest neighbors to the origin point
This will return a vector of points that are within the radius of the origin point. The radius is inclusive so if a point is exactly on the radius it will be included.
Examples found in repository?
7fn main() {
8 let mut node: KdNode<i32> = KdNode::new();
9 assert_eq!(node, Empty);
10
11 // Tree Root
12 node.insert(1, 1);
13 node.insert(2, 2);
14 node.insert(2, -12);
15
16 println!("{:?}", node);
17 println!("{:?}", node.nearest_neighbor_x_y(1, 1, 1.0));
18 println!("{:?}", node.nearest_neighbor(Point{x: 1, y: 1}, 1.0));
19}
More examples
6fn main() {
7 let points: Vec<Point<i32>> = vec![
8 Point { x: 1, y: 8 },
9 Point { x: 2, y: 2 },
10 Point { x: 3, y: 6 },
11 Point { x: 4, y: 9 },
12 Point { x: 7, y: 3 },
13 Point { x: 8, y: 8 },
14 Point { x: 9, y: 1 },
15 Point { x: 9, y: 9 },
16 ];
17
18 let node: KdNode<i32> = KdNode::build(points);
19
20 let radius: f64 = 1.5;
21 let origin: Point<i32> = Point { x: 8, y: 8 };
22 let nearest = node.nearest_neighbor(origin, radius);
23 assert_eq!(
24 nearest,
25 vec![Point { x: 8, y: 8 }, Point { x: 9, y: 9 }]
26 );
27 println!("Neighbours within 1.5 units of (1,1): {:?}", nearest);
28}
Sourcepub fn nearest_neighbor_x_y<'a>(&self, x: T, y: T, radius: f64) -> Vec<Point<T>>
pub fn nearest_neighbor_x_y<'a>(&self, x: T, y: T, radius: f64) -> Vec<Point<T>>
Insert a new item into the tree
This is the same as insert
but takes a Point
instead of x
and y
Examples found in repository?
7fn main() {
8 let mut node: KdNode<i32> = KdNode::new();
9 assert_eq!(node, Empty);
10
11 // Tree Root
12 node.insert(1, 1);
13 node.insert(2, 2);
14 node.insert(2, -12);
15
16 println!("{:?}", node);
17 println!("{:?}", node.nearest_neighbor_x_y(1, 1, 1.0));
18 println!("{:?}", node.nearest_neighbor(Point{x: 1, y: 1}, 1.0));
19}
Sourcepub fn n_nearest_neighbor<'a>(
&self,
origin: Point<T>,
max: usize,
) -> Vec<Point<T>>
pub fn n_nearest_neighbor<'a>( &self, origin: Point<T>, max: usize, ) -> Vec<Point<T>>
Find the nearest neighbors to the origin point
This will return a vector of points that are within the radius of the origin point.
This is the same as nearest_neighbor
but will only return the max
number of points.
Sourcepub fn build(points: Vec<Point<T>>) -> Self
pub fn build(points: Vec<Point<T>>) -> Self
Examples found in repository?
6fn main() {
7 let points: Vec<Point<i32>> = vec![
8 Point { x: 1, y: 8 },
9 Point { x: 2, y: 2 },
10 Point { x: 3, y: 6 },
11 Point { x: 4, y: 9 },
12 Point { x: 7, y: 3 },
13 Point { x: 8, y: 8 },
14 Point { x: 9, y: 1 },
15 Point { x: 9, y: 9 },
16 ];
17
18 let node: KdNode<i32> = KdNode::build(points);
19
20 let radius: f64 = 1.5;
21 let origin: Point<i32> = Point { x: 8, y: 8 };
22 let nearest = node.nearest_neighbor(origin, radius);
23 assert_eq!(
24 nearest,
25 vec![Point { x: 8, y: 8 }, Point { x: 9, y: 9 }]
26 );
27 println!("Neighbours within 1.5 units of (1,1): {:?}", nearest);
28}