queryIds method

List<int> queryIds(Rect rect)

Query the QuadTree for objects that intersect with the given rect. Returns a list of object identifiers.

This method is two times faster than queryMap and query. And should be used when you need only object identifiers.

Implementation

List<int> queryIds(ui.Rect rect) {
  //if (rect.isEmpty) return const [];

  final root = _root;
  if (root == null) return const [];

  // 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) {
    if (root._subdivided) {
      final results = Uint32List(_length);
      for (var i = 0, j = 0; i < _nextObjectId; i++) {
        if (_id2node[i] != 0) results[j++] = i;
      }
      return results;
    } else {
      return root._ids.toList(growable: false);
    }
  }

  // Visit all suitable nodes in the QuadTree and collect objects.
  final objects = _objects;
  final results = Uint32List(_length);
  final queue = Queue<QuadTree$Node>()..add(root);
  var offset = 0;
  var count = 0;
  while (queue.isNotEmpty) {
    final node = queue.removeFirst();
    if (!_overlaps(node.boundary, rect)) continue;
    if (node.subdivided) {
      queue
        ..add(node._northWest!)
        ..add(node._northEast!)
        ..add(node._southWest!)
        ..add(node._southEast!);
    } else {
      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))
          results[count++] = id;
      }
    }
  }
  return results.sublist(0, count);
}