Struct QuadTree2D 

pub struct QuadTree2D { /* private fields */ }

A 2D quadtree broad-phase acceleration structure, interface-compatible with SpatialHashGrid2D.

Bodies are inserted by their world-space axis-aligned bounding box. A node subdivides into four children once its entry count exceeds the capacity and its depth is below the maximum; an entry whose box straddles a split boundary stays in the parent node, so no body is ever duplicated and every query visits each body exactly once.

Unlike the uniform grid, the quadtree concentrates resolution where bodies are dense, which makes it the better structure for scenes with strongly clustered content. A body larger than the root region is still inserted and still returned by every query overlapping it — it simply resides at the root and is confirmed by its exact box test.

Implementations

impl QuadTree2D

Implements construction, insertion, subdivision, and querying for QuadTree2D.

pub fn create( bounds_min: Vector2D, bounds_max: Vector2D, capacity: usize, max_depth: usize, ) -> QuadTree2D

Creates a new 2D quadtree rooted at the given region.

The root region is normalized so the first corner is always the minimum, and a zero-width or zero-height region is widened by EPSILON so subdivision always makes progress. A capacity below one is raised to one, and a depth above [SPATIAL_MAX_DEPTH_2D] is clamped.

Arguments

• Vector2D - One corner of the root region.
• Vector2D - The opposite corner of the root region.
• usize - The number of entries a node may hold before subdividing.
• usize - The deepest subdivision level a node may reach.

Returns

• QuadTree2D - The new empty quadtree.

pub fn with_default_size() -> QuadTree2D

Creates a new 2D quadtree with the default capacity, depth, and a root region centred on the world origin.

Returns

• QuadTree2D - The new empty quadtree.

pub fn with_half_extent(half_extent: f64) -> QuadTree2D

Creates a new 2D quadtree over a square region of the given half-extent, using the default capacity and depth.

Arguments

• f64 - The half-extent of the root region in world units.

Returns

• QuadTree2D - The new empty quadtree.

pub fn len(&self) -> usize

Returns the number of bodies currently stored in the tree.

Returns

• usize - The number of inserted bodies.

pub fn is_empty(&self) -> bool

Reports whether the tree holds no bodies.

Returns

• bool - true when no body is stored.

pub fn bounds(&self) -> (Vector2D, Vector2D)

Returns the region covered by the root node.

Returns

• (Vector2D, Vector2D) - The minimum and maximum corners of the root region.

pub fn insert(&mut self, index: usize, min: Vector2D, max: Vector2D)

Inserts a body index together with its exact bounding box.

The entry descends into the child region that fully contains it. An entry that straddles a split boundary, or that is larger than the node it lands in, stays in the current node and marks that node loose — that is the standard quadtree invariant, and it is what guarantees a body is stored exactly once, so queries never need dedup beyond the caller’s scratch set.

Arguments

• usize - The body index to insert.
• Vector2D - The minimum corner of the bounding box.
• Vector2D - The maximum corner of the bounding box.

pub fn query(&self, min: Vector2D, max: Vector2D) -> Vec<usize>

Returns all body indices whose exact bounding box overlaps the query box.

Each candidate index appears at most once.

Arguments

• Vector2D - The minimum corner of the query box.
• Vector2D - The maximum corner of the query box.

Returns

• Vec<usize> - The list of candidate body indices.

pub fn query_into( &self, min: Vector2D, max: Vector2D, out: &mut Vec<usize>, seen: &mut HashSet<usize>, )

Appends all candidate body indices overlapping the query box into out, deduplicating via the caller-provided seen set.

Both out and seen are cleared first, so the caller can reuse the same buffers across all queries in a step without any per-query allocation.

Nodes are pruned by region overlap, then every entry that survives pruning is confirmed with an exact box-vs-box test. A node holding a body larger than its own region is marked loose and skips the region prune entirely, which is what keeps such a body — including one larger than the whole root region — returned by every query that overlaps it. The traversal uses an explicit stack, so no recursion is involved.

Arguments

• Vector2D - The minimum corner of the query box.
• Vector2D - The maximum corner of the query box.
• &mut Vec<usize> - The output buffer, cleared then filled with candidates.
• &mut HashSet<usize> - The dedup scratch set, cleared then reused.

pub fn clear(&mut self)

Removes every entry and child node, keeping only the empty root so the same tree can be reused for a fresh insertion pass.

pub fn boxes_overlap( a_min: Vector2D, a_max: Vector2D, b_min: Vector2D, b_max: Vector2D, ) -> bool

Reports whether two axis-aligned boxes overlap.

Touching edges count as overlapping, matching the inclusive cell semantics of SpatialHashGrid2D::query.

Arguments

• Vector2D - The minimum corner of the first box.
• Vector2D - The maximum corner of the first box.
• Vector2D - The minimum corner of the second box.
• Vector2D - The maximum corner of the second box.

Returns

• bool - true when the two boxes share at least one point.

impl QuadTree2D

pub fn get_nodes(&self) -> &QuadTreeNodeList2D

pub fn get_mut_nodes(&mut self) -> &mut QuadTreeNodeList2D

pub fn set_nodes(&mut self, val: QuadTreeNodeList2D) -> &mut Self

pub fn get_capacity(&self) -> usize

pub fn get_mut_capacity(&mut self) -> &mut usize

pub fn set_capacity(&mut self, val: usize) -> &mut Self

pub fn get_max_depth(&self) -> usize

pub fn get_mut_max_depth(&mut self) -> &mut usize

pub fn set_max_depth(&mut self, val: usize) -> &mut Self

pub fn get_count(&self) -> usize

pub fn get_mut_count(&mut self) -> &mut usize

Trait Implementations

impl Clone for QuadTree2D

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for QuadTree2D

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for QuadTree2D

Default-construction for QuadTree2D.

fn default() -> QuadTree2D

Constructs a default QuadTree2D value.

Returns

• QuadTree2D - A default-constructed instance with the documented initial state.

impl PartialEq for QuadTree2D

fn eq(&self, other: &Self) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl StructuralPartialEq for QuadTree2D