[−][src]Crate ezquadtree
quadtree
Easy Quad Tree (ezquadtree)
This is the first Implementation of a quad tree I have made so there is some room for improvement.
A QuadTree uses the Hilbert curve and can be explained here
use ezquadtree::{Vector, QuadTree, Rectangle}; #[derive(Debug, Clone)] struct Foo { item: String, x: u32, y: u32, } impl Foo { fn new(x: u32, y: u32, item: &str) -> Self { Self { item: item.to_string(), x, y } } } impl Vector for Foo { fn as_point(&self) -> (u32, u32) { (self.x, self.y) } } impl PartialEq for Foo { fn eq(&self, other: &Foo) -> bool { self.x == other.x && self.y == other.y } } fn main() { let old = Foo::new(5, 5, "old"); let new = Foo::new(5, 5, "new"); let (w, h) = (40, 40); let bb = Rectangle::new(0, 0, w, h); let mut qt = QuadTree::new(bb, 4); qt.insert(&old); qt.insert(&new); let mut result = Vec::new(); qt.query(None, &mut |e| result.push(e.clone())); assert_eq!(result, vec![old.clone()]); assert_eq!(qt.len(), 1); let return_of_replace = qt.replace(&new); assert_eq!(Some(old.clone()), return_of_replace); assert_eq!(qt.len(), 1); qt.query(None, &mut |inner_item| { assert_eq!(inner_item, &new); }); }
Structs
QuadTree | A growable data structure type, with a look up complexity of O(log n). |
Rectangle | Rectangle is to represent a rectangular bounding box. |
Traits
Vector | A trait to describe Vector x and y to QuadTree. |