insert method

bool insert(QuadTreeParticle particle)

Inserts a particle into the tree with path compression optimization Returns true if insertion was successful

Implementation

bool insert(QuadTreeParticle particle) {
  // First check if particle is within this node's boundary
  if (!boundary.contains(particle.x, particle.y)) return false;

  // If we have capacity and this is a leaf node, store here
  if (particles.length < maxParticles && isLeaf) {
    particles.add(particle);
    return true;
  }

  // At capacity but not at max depth - consider subdivision
  if (isLeaf && depth < maxDepth) {
    // Temporary collection of all particles including new one
    final List<QuadTreeParticle> allParticles = [...particles, particle];

    // Group particles by which quadrant they would fall into
    final Map<Quadrant, List<QuadTreeParticle>> groups = {};
    for (final p in allParticles) {
      final Quadrant quad = _getQuadrant(p.x, p.y);
      groups.putIfAbsent(quad, () => []).add(p);
    }

    // Find the quadrant with most particles (dominant quadrant)
    var maxCount = 0;
    Quadrant? dominantQuad;
    for (final entry in groups.entries) {
      if (entry.value.length > maxCount) {
        maxCount = entry.value.length;
        dominantQuad = entry.key;
      }
    }

    // If all particles are in one quadrant, use path compression
    if (dominantQuad != null && maxCount == allParticles.length) {
      // Create compressed child node
      final Rectangle childBoundary = getChildBoundary(dominantQuad);
      final CompressedPath childPath =
          compressedPath?.extend(dominantQuad) ??
          CompressedPath([dominantQuad], depth + 1);

      children[dominantQuad] = CompressedQuadTreeNode(
        childBoundary,
        depth + 1,
        childPath,
      );

      // Move all particles to the compressed child
      for (final p in allParticles) {
        children[dominantQuad]!.insert(p);
      }
      particles.clear();
      return true;
    } else {
      // Normal subdivision if particles are distributed
      _subdivideNormal();
    }
  }

  // Try to insert into appropriate child if not leaf
  if (!isLeaf) {
    final Quadrant targetQuadrant = _getQuadrant(particle.x, particle.y);
    return children[targetQuadrant]?.insert(particle) ?? false;
  }

  // Fallback: store in current node if max depth reached
  particles.add(particle);
  return true;
}