Qutee is a simple implementation of a quadtree. Qutee allows you to choose which primitive number type should be used for coordinates. Items of the quadtree do not require any trait bounds.
A boundary can be constructed with Boundary::new or Boundary::between_points.
Boundary::new takes a Point as its first argument, followed by a width and height.
Boundary::between_points takes two Point Objects.
A point in 2D space.
A point can be constructed with Point::new. This function takes an x and y argument.
Most functions do not directly require a Point but take impl Into<Point> as an argument.
This allows for a tuple to be used as a point where the first item is x and the second `y'.
QuadTree provides the actual quadtree implementation. QuadTree has two required and one optional generic parameter.
The first two arguments are the coordinate and item type. The third parameter defines how the max capacity for each level is determined.
By default, this argument is set to DynCapacity. You can change this to ConstCapacity if you know the size at compile time.
To create a QuadTree you can use one of three methods
- new_with_capacity takes a
Boundaryand parameter of typeCapacity. - new_with_dyn_cap takes a
Boundaryand a capacity of type usize. This function is only available if the capacity is dynamic. - new_with_const_cap takes a
Boundary. This function is only available if the capacity is known at compile time.
An item can be inserted using the insert function. This function requires for item to implement AsPoint.
If your item does not implement AsPoint, you can use insert_at. The first parameter is the point, and the second is the item.
query takes a Boundary and returns an Iterator of type Query
iter returns an Iterator of type Iter containing all items in the tree.
use qutee::*;
// Create a new quadtree where the area's top left corner is at -10, -10, with a width and height of 20.
let mut tree = QuadTree::new_with_dyn_cap(Boundary::new((-10., -10.), 20., 20.), 5);
assert!(tree.insert_at((0.5, 0.1), "A").is_ok());
assert!(tree.insert_at((-1., 1.), "B").is_ok());
// This point is outside the tree
assert_eq!(tree.insert_at((10.1, 5.), "C"), Err(QuadTreeError::OutOfBounds));
// Search elements inside a boundary. A boundary can also be defined as an area between two points.
let mut query = tree.query(Boundary::between_points((0.,0.),(1.,1.)));
assert_eq!(query.next(), Some(&"A"));
assert!(query.next().is_none());
// Get an iterator over all items
let mut iter = tree.iter();
assert_eq!(iter.next(), Some(&"A"));
assert_eq!(iter.next(), Some(&"B"));
assert!(iter.next().is_none());