CompressedQuadTree class

A space-partitioning data structure for efficient 2D spatial queries

Mathematical Foundations:

  1. Quadtree divides space into 4 quadrants (NW, NE, SW, SE)
  2. Uses recursive subdivision until capacity or depth limit reached
  3. Compression merges similar nodes to optimize memory usage

Performance Characteristics:

  • Insertion: O(log n) average case
  • Query: O(log n + k) where k is number of results
  • Memory: O(n) with compression

Constructors

CompressedQuadTree(Rectangle boundary)
Constructor initializes tree with given boundary.

Properties

boundary → Rectangle
The rectangular boundary within which the tree partitions particles.
final
hashCode → int
The hash code for this object.
no setterinherited
root → CompressedQuadTreeNode
Public accessor for root node (for debugging/inspection).
no setter
runtimeType → Type
A representation of the runtime type of the object.
no setterinherited

Methods

buildFromParticles(List particles, List<int> visibleParticles) → void
Bulk builds the tree from a list of particles. particles: Complete list of particle objects. visibleParticles: Indices of particles to include in tree.
clear() → void
Clears all particles from the tree.
findNearbyParticles(double x, double y, double searchRadius) → List<int>
Finds nearby particles using circular query. Convenience wrapper around queryCircle.
findNearbyParticlesToOutput(double x, double y, double searchRadius, List<int> output) → void
Finds nearby particles using circular query and fills the given list. output: List to fill with found particle indices.
getAllParticleIndices() → List<int>
Gets indices of all particles in the tree.
getStats() → Map<String, dynamic>
Gets comprehensive tree statistics including node counts, depth, and compression metrics.
insert(QuadTreeParticle particle) → bool
Inserts a particle into the tree. Returns true if insertion was successful.
needsRebalancing() → bool
Determines if tree needs rebalancing based on compression metrics.
noSuchMethod(Invocation invocation) → dynamic
Invoked when a nonexistent method or property is accessed.
inherited
optimize() → void
Optimizes memory usage by compressing similar nodes.
queryCircle(double centerX, double centerY, double radius) → List<int>
Queries particles within a circular area. Returns list of particle indices within the circle.
queryRange(Rectangle range) → List<int>
Queries particles within a rectangular range. Returns list of particle indices within the range.
rebalance() → void
Rebalances the tree structure.
rebuild(List particles, List<int> visibleParticles) → void
Rebuilds the entire tree from particle data.
toString() → String
A string representation of this object.
inherited

Operators

operator ==(Object other) → bool
The equality operator.
inherited