Function nearest

nodedb-spatial/src/rtree/search.rs:49–103

Nearest-neighbor search via priority queue (min-heap).

(
    nodes: &[Node],
    root: usize,
    query_lng: f64,
    query_lat: f64,
    k: usize,
    is_empty: bool,
)

/// Nearest-neighbor search via priority queue (min-heap).
pub(crate) fn nearest(
    nodes: &[Node],
    root: usize,
    query_lng: f64,
    query_lat: f64,
    k: usize,
    is_empty: bool,
) -> Vec<NnResult> {
    if k == 0 || is_empty {
        return Vec::new();
    }

    let mut heap: BinaryHeap<HeapItem> = BinaryHeap::new();
    let mut results: Vec<NnResult> = Vec::with_capacity(k);

    heap.push(HeapItem {
        dist: min_dist_point_bbox(query_lng, query_lat, &nodes[root].bbox),
        node_idx: root,
    });

    while let Some(item) = heap.pop() {
        if results.len() >= k && item.dist > results[k - 1].distance {
            continue;
        }
        let node = &nodes[item.node_idx];
        match &node.kind {
            NodeKind::Internal { children } => {
                for child in children {
                    let d = min_dist_point_bbox(query_lng, query_lat, &child.bbox);
                    if results.len() < k || d <= results[results.len() - 1].distance {
                        heap.push(HeapItem {
                            dist: d,
                            node_idx: child.node_idx,
                        });
                    }
                }
            }
            NodeKind::Leaf { entries } => {
                for entry in entries {
                    let d = min_dist_point_bbox(query_lng, query_lat, &entry.bbox);
                    if results.len() < k || d < results[results.len() - 1].distance {
                        let nn = NnResult {
                            entry_id: entry.id,
                            bbox: entry.bbox,
                            distance: d,
                        };
                        insert_sorted(&mut results, nn, k);
                    }
                }
            }
        }
    }

    results
}

/// Min-heap item for NN traversal.
#[derive(Debug)]