knn method

List<T> knn(double x, double y, int k, { bool predicate(T item)?, double? maxDistance, })

K-nearest neighbors search.

For a given (x, y) location, returns k nearest items, sorted by distance to their bounding boxes.

Use maxDistance to filter by distance as well. Use predicate function to filter by item properties.

Implementation

List<T> knn(double x, double y, int k,
    {bool Function(T item)? predicate, double? maxDistance}) {
  final List<T> result = [];
  if (k <= 0) return result;

  _RBushNode<T> node = data;
  final queue = TinyQueue<_KnnElement<T>>([]);

  while (true) {
    if (node.leaf) {
      for (final child in node.leafChildren) {
        final dist = toBBox(child).distanceSq(x, y);
        if (maxDistance == null || dist <= maxDistance * maxDistance) {
          queue.push(_KnnElement(item: child, dist: dist));
        }
      }
    } else {
      for (final child in node.children) {
        final dist = child.distanceSq(x, y);
        if (maxDistance == null || dist <= maxDistance * maxDistance) {
          queue.push(_KnnElement(node: child, dist: dist));
        }
      }
    }

    while (queue.isNotEmpty && queue.peek().item != null) {
      T candidate = queue.pop().item!;
      if (predicate == null || predicate(candidate)) {
        result.add(candidate);
      }
      if (k > 0 && result.length == k) return result;
    }

    if (queue.isEmpty) break;
    if (queue.peek().node == null) break;
    node = queue.pop().node!;
  }

  return result;
}