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 boundary: The rectangular area this tree will cover

Properties

boundary → Rectangle
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
getAllParticleIndices() → List<int>
Gets indices of all particles in the tree
getStats() → Map<String, dynamic>
Gets comprehensive tree statistics including:
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 area 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