KD Tree

Data structure for efficiently finding points in a k-dimensional space.

This is an under development implementation of a KD Tree in Rust. Below is a list of features that are currently implemented and features that are planned to be implemented.

• Build Tree
• Find All Points Within A Radius
• Find Nearest Neighbor
• Insert New Point
• Find N Nearest Neighbors
• Delete Point
• Re-Balance Tree
• Serialize Tree
• Publish Crate
• Add K dimensions (Currently only 2D)
• Add Examples

This was developed initially as a way to learn Rust and to implement a KD Tree for a boids simulation although the simulation is in progress. I plan to continue to work on this project as I learn more about Rust and as I have time.

Performance

The performance of the KD Tree is not yet optimized. I plan to optimize the performance once I have implemented all of the features. The current performance was taken from rustup run nightly cargo bench and is as follows:

Size	Build Tree O(n)	Find all points within a radius O(n log n)	Find nearest neighbor O(log n)	Insert O(1)
10000	5,798,8 84 ns	4,167,605 n s
10000	0.005799 s	0.004176 s
100000	89,055,903 ns	473,910,975 ns
100000	0.05799 s	0.4176 s

Usage - TODO

Publishing is a WIP

use kd_tree::KDTree;

fn main() {
    let mut node: KdNode<i32> = KdNode::new();
    // Tree Root
    node.insert(1, 1);
    node.insert(2, 2);
    node.insert(2, -12);

    assert_eq!(node.nearest_neighbor(Point{x: 1, y: 1}, 1.0), vec![Point{x: 1, y: 1}]);
}

Below is a diagram showing how the KD Tree is structured. The KD Tree is a binary tree where each node is a point in the k-dimensional space. Each alternating level of the tree is split by a different dimension. The root node is split by the first dimension, the children of the root node are split by the second dimension, this is typically the x and y dimensions in a 2D space. 3D space would be split by x, y, and z dimensions.

Contributing

Pull requests are welcome. For major changes, please open an issue first to discuss what you would like to change.

References

• KD Tree
• KD Tree Visualization
• KD Tree Nearest Neighbor
• Proof for neighborhood computation in expected logarithmic time - Martin Skrodzki
• Introduction to a KD Tree

License

MIT