Struct space_partitioning::QuadTree

pub struct QuadTree<ElementId = u32> where
    ElementId: ElementIdType,  { /* fields omitted */ }

A QuadTree implementation as described in Efficient Quadtrees.

Remarks

This tree uses integral coordinates only in order to speed up box-box intersection tests.

Implementations

impl<ElementId> QuadTree<ElementId> where
    ElementId: ElementIdType, 

pub fn default() -> Self

pub fn new(
    root_rect: QuadRect,
    max_depth: u32,
    max_num_elements: u32,
    smallest_cell_size: u32
) -> Self

pub fn insert(
    &mut self,
    element: QuadTreeElement<ElementId>
) -> Result<(), InsertError>

pub fn remove(&mut self, element: &QuadTreeElement<ElementId>) -> bool

Removes the specified element.

Remarks

The element is located using its bounding box and identified using the ID. Because of that, the bounding box of the element must not change until is was removed from the tree.

Arguments

• [element] - The element to remove.

pub fn visit_leaves<F>(&self, visit: F) where
    F: FnMut(NodeInfo), 

pub fn cleanup(&mut self) -> bool

Prunes unused child nodes from the tree.

Remarks

The tree is never pruned automatically for performance reasons. Call this method after all elements were removed or updated.

pub fn intersect_aabb(&self, rect: &AABB) -> HashSet<ElementId>

Returns the set of IDs that occupy space within the specified bounding box.

Arguments

• [rect] - The rectangle to test for.

pub fn intersect_aabb_fn<F>(&self, rect: &AABB, candidate_fn: F) where
    F: FnMut(ElementId), 

Calls a function for each ID that occupies space within the specified bounding box. The function may be called multiple times for the same ID.

Arguments

• [rect] - The rectangle to test for.
• [candidate_fn] - The function called for each candidate element’s ID.

pub fn intersect_generic<T>(&self, element: &T) -> HashSet<ElementId> where
    T: IntersectsWith<AABB>, 

Returns the set of IDs that occupy space within the specified bounding box.

Arguments

• [element] - The element to test for.

pub fn intersect_generic_fn<T, F>(&self, element: &T, candidate_fn: F) where
    T: IntersectsWith<AABB>,
    F: FnMut(ElementId), 

Calls a function for each ID that occupies space within the specified bounding box. The function may be called multiple times for the same ID.

Arguments

• [element] - The element to test for.
• [candidate_fn] - The function called for each candidate element’s ID.