kd-tree-rs

Crates.io	kd-tree-rs
lib.rs	kd-tree-rs
version	0.1.0
source	src
created_at	2023-05-19 19:36:29.259822
updated_at	2023-05-19 19:36:29.259822
description	A Rust implementation of a k-d tree.
homepage	https://github.com/AlexanderDefuria/kd-tree-rs
repository	https://github.com/AlexanderDefuria/kd-tree-rs
max_upload_size
id	869068
size	32,432

Alexander De Furia (AlexanderDefuria)

documentation

README

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)`
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.