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 |

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.

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

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.

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

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