optimize method

void optimize()

Call this on the root to try merging all possible child nodes. Recursively merges subtrees that have fewer than capacity objects in total.

Implementation

void optimize() {
  final root = _root;
  if (root == null || !root._dirty) return;

  // Visit all nodes in the QuadTree and try to merge them.

  final queue = Queue<QuadTree$Node>()..add(root);
  late final toMerge = Queue<QuadTree$Node>();

  while (queue.isNotEmpty) {
    final node = queue.removeFirst();
    // Skip if not dirty
    if (!node._dirty) continue;
    // Leaf node - nothing to merge, just mark as not dirty
    if (node.leaf) {
      node._dirty = false;
      continue;
    }

    // If too many objects in the node, skip merging and just check children
    if (node.length > capacity) {
      node._dirty = false;
      queue
        ..add(node._northWest!)
        ..add(node._northEast!)
        ..add(node._southWest!)
        ..add(node._southEast!);
      continue;
    }

    // Get all leaf nodes
    toMerge
      ..add(node._northWest!)
      ..add(node._northEast!)
      ..add(node._southWest!)
      ..add(node._southEast!);

    while (toMerge.isNotEmpty) {
      final child = toMerge.removeFirst();
      if (child._subdivided) {
        // Add children to the queue for further merging
        toMerge
          ..add(child._northWest!)
          ..add(child._northEast!)
          ..add(child._southWest!)
          ..add(child._southEast!);
      } else {
        // Merge the child node with the parent node
        node._ids.addAll(child._ids);
        // Link the object id to the parent node
        for (final objectId in child._ids) _id2node[objectId] = node.id;
        child._ids.clear();
      }

      child
        .._length = 0
        .._dirty = false
        .._subdivided = false
        .._northWest = null
        .._northEast = null
        .._southWest = null
        .._southEast = null;
      _nodes[child.id] = null;

      // Resize recycled nodes array if needed
      if (_recycledNodesCount == _recycledNodes.length)
        _recycledNodes = _resizeUint32List(
          _recycledNodes,
          _recycledNodes.length << 1,
        );
      _recycledNodes[_recycledNodesCount++] = child.id;
    }

    // Reset the node to a leaf node with the merged objects
    node
      .._dirty = false
      .._length = node._ids.length
      .._subdivided = false
      .._northWest = null
      .._northEast = null
      .._southWest = null
      .._southEast = null;
  }
}