Struct Quadtree 

pub struct Quadtree { /* private fields */ }

An axis-aligned 2D spatial partitioning tree.

Contract

• Insertions that fall entirely outside bounds are silently dropped.
• retrieve returns ALL rects in leaf nodes that overlap the query rect; callers must perform their own exact AABB test on the returned set.
• Maximum recursion depth is capped at max_depth (default 5) to bound memory usage even with degenerate inputs (all rects at one point).

Implementations

impl Quadtree

pub fn new(bounds: Rect) -> Self

Create a new root QuadTree node covering the given bounds.

Default capacity per leaf is 10 rects, maximum depth is 5 levels.

pub fn insert(&mut self, rect: Rect)

Insert a rect into the tree.

The rect is dropped if it does not intersect this node’s bounds. If this is an interior node (already subdivided), the rect is propagated to all overlapping children. Otherwise it is stored in this leaf; if the leaf is now over capacity and below max depth, the node is subdivided and existing rects redistributed.

pub fn retrieve(&self, rect: Rect, out: &mut Vec<Rect>)

Collect all candidate rects that may overlap rect into out.

This is a broad-phase query: returned rects are candidates from overlapping leaf nodes. Callers MUST perform their own exact intersection test on results. The out vec is appended to — it is never cleared.