knn method
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;
}