Function forced_reinsert

nodedb-spatial/src/rtree/insert.rs:143–168

Remove the farthest entries from node center and return for reinsertion.

(tree: &mut RTree, node_idx: usize)

/// Remove the farthest entries from node center and return for reinsertion.
fn forced_reinsert(tree: &mut RTree, node_idx: usize) -> Vec<RTreeEntry> {
    let reinsert_count = if tree.nodes[node_idx].is_leaf() {
        REINSERT_COUNT_LEAF
    } else {
        0
    };
    if reinsert_count == 0 {
        return Vec::new();
    }

    let center_lng = (tree.nodes[node_idx].bbox.min_lng + tree.nodes[node_idx].bbox.max_lng) / 2.0;
    let center_lat = (tree.nodes[node_idx].bbox.min_lat + tree.nodes[node_idx].bbox.max_lat) / 2.0;

    if let NodeKind::Leaf { entries } = &mut tree.nodes[node_idx].kind {
        entries.sort_by(|a, b| {
            let da = dist_sq_center(center_lng, center_lat, &a.bbox);
            let db = dist_sq_center(center_lng, center_lat, &b.bbox);
            db.partial_cmp(&da).unwrap_or(std::cmp::Ordering::Equal)
        });
        let removed: Vec<RTreeEntry> = entries.drain(..reinsert_count).collect();
        tree.nodes[node_idx].recompute_bbox();
        removed
    } else {
        Vec::new()
    }
}

fn dist_sq_center(lng: f64, lat: f64, bbox: &BoundingBox) -> f64 {
    let cx = (bbox.min_lng + bbox.max_lng) / 2.0;