query method

QuadTree$QueryResult query(Rect rect)

Query the QuadTree for objects that intersect with the given rect. Returns a buffer of object data.

Implementation

QuadTree$QueryResult query(ui.Rect rect) {
  //if (rect.isEmpty) return QuadTree$QueryResult._(Float32List(0));

  final root = _root;
  if (root == null || isEmpty) return QuadTree$QueryResult._(Float32List(0));

  const sizePerObject = QuadTree$QueryResult.sizePerObject; // id + 4 floats
  final objects = _objects;
  var offset = 0;

  // If the query rectangle fully contains the QuadTree boundary.
  // Return all objects in the QuadTree.
  if (rect.left <= boundary.left &&
      rect.top <= boundary.top &&
      rect.right >= boundary.right &&
      rect.bottom >= boundary.bottom) {
    final results = Float32List(_length * sizePerObject);
    final ids = Uint32List.sublistView(results);

    if (root._subdivided) {
      for (var i = 0, j = 0; i < _nextObjectId; i++) {
        if (_id2node[i] == 0) continue;
        offset = i * _objectSize;
        ids[j + 0] = i;
        results[j + 1] = objects[offset + 0];
        results[j + 2] = objects[offset + 1];
        results[j + 3] = objects[offset + 2];
        results[j + 4] = objects[offset + 3];
        j += sizePerObject;
      }
    } else {
      final rootIds = root._ids;
      var j = 0;
      for (final id in rootIds) {
        offset = id * _objectSize;
        ids[j + 0] = id;
        results[j + 1] = objects[offset + 0];
        results[j + 2] = objects[offset + 1];
        results[j + 3] = objects[offset + 2];
        results[j + 4] = objects[offset + 3];
        j += sizePerObject;
      }
    }
    return QuadTree$QueryResult._(results);
  }

  final subdivided = Queue<QuadTree$Node>()..add(root);
  final leafs = <QuadTree$Node>[];

  // Find all leaf nodes from the subdivided nodes
  while (subdivided.isNotEmpty) {
    final node = subdivided.removeFirst();
    if (node.isEmpty) continue;
    if (!_overlaps(node.boundary, rect)) continue;
    if (node.subdivided) {
      subdivided
        ..add(node._northWest!)
        ..add(node._northEast!)
        ..add(node._southWest!)
        ..add(node._southEast!);
    } else {
      leafs.add(node);
    }
  }

  // Find all objects in the leaf nodes
  // hat intersect with the query rectangle
  /* var j = 0;
  for (var i = 0; i < leafs.length; i++) {
    final node = leafs[i];
    if (!_overlaps(node.boundary, rect)) continue;
    if (i != j) leafs[j] = leafs[i];
    j++;
  }
  leafs.length = j; */

  // No leaf nodes found
  if (leafs.isEmpty) return QuadTree$QueryResult._(Float32List(0));

  // Calculate the maximum possible length of the results
  final length = leafs.fold<int>(0, (sum, node) => sum + node.length);

  // Fill the results with the objects from the leaf nodes
  final results = Float32List(length * sizePerObject);
  final ids = Uint32List.sublistView(results);
  var $length = 0;
  for (final node in leafs) {
    for (final id in node._ids) {
      offset = id * _objectSize;
      final left = objects[offset + 0],
          top = objects[offset + 1],
          width = objects[offset + 2],
          height = objects[offset + 3];
      if (!_overlapsLTWH(rect, left, top, width, height)) continue;
      ids[$length + 0] = id;
      results[$length + 1] = left;
      results[$length + 2] = top;
      results[$length + 3] = width;
      results[$length + 4] = height;
      $length += sizePerObject;
    }
  }

  // No objects found
  if ($length == 0) return QuadTree$QueryResult._(Float32List(0));

  // Resize the results to the actual length
  return QuadTree$QueryResult._(results.sublist(0, $length));
}