QuadTree

Struct QuadTree 

Source
pub struct QuadTree<ElementId = u32>
where ElementId: ElementIdType,
{ /* private fields */ }
Expand description

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§

Source§

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

Source

pub fn default() -> Self

Source

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

Source

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

Source

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.
Source

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

Visits all leaf nodes in the tree, passing the node information to the provided closure.

Source

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.

Source

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

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

§Arguments
  • [rect] - The rectangle to test for.
Source

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.
Source

pub fn intersect_generic<T>(&self, element: &T) -> Vec<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.
Source

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.

Auto Trait Implementations§

§

impl<ElementId> Freeze for QuadTree<ElementId>

§

impl<ElementId> RefUnwindSafe for QuadTree<ElementId>
where ElementId: RefUnwindSafe,

§

impl<ElementId> Send for QuadTree<ElementId>
where ElementId: Send,

§

impl<ElementId> Sync for QuadTree<ElementId>
where ElementId: Sync,

§

impl<ElementId> Unpin for QuadTree<ElementId>
where ElementId: Unpin,

§

impl<ElementId> UnwindSafe for QuadTree<ElementId>
where ElementId: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.