Crate kd_tree_rs

source ·
Expand description

KdTree

A simple k-d tree implementation in Rust.

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.

Usage

KdNode is the main data structure for the KD Tree. It is a generic struct that takes a type

Point which is a struct that contains the x and y coordinates of a point in 2D space.

The type of the x and y coordinates can be any type that can implement the KDT trait. This trait is implemented for all types that implement the following traits: PartialEq, PartialOrd, Into<f64>, Copy, Add, Sub, Mul.

extern crate kd_tree_rs;

use kd_tree_rs::KdNode;
use kd_tree_rs::KdNode::Empty;
use kd_tree_rs::point::Point;

fn main() {
   let mut node: KdNode<i32> = KdNode::new();

   node.insert(1, 1);
   node.insert(2, 2);

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

References

Re-exports

  • pub use crate::dim::Dim;
  • pub use crate::point::Point;
  • pub use crate::KdNode::Empty;
  • pub use crate::KdNode::Node;

Modules

Enums

Traits