Function choose_subtree

nodedb-spatial/src/rtree/insert.rs:54–79

R*-tree ChooseSubtree: navigate to the best leaf for this entry.

(
    tree: &RTree,
    node_idx: usize,
    entry_bbox: &BoundingBox,
    target_level: u32,
)

/// R*-tree ChooseSubtree: navigate to the best leaf for this entry.
fn choose_subtree(
    tree: &RTree,
    node_idx: usize,
    entry_bbox: &BoundingBox,
    target_level: u32,
) -> usize {
    let node = &tree.nodes[node_idx];
    if node.level == target_level {
        return node_idx;
    }

    match &node.kind {
        NodeKind::Leaf { .. } => node_idx,
        NodeKind::Internal { children } => {
            if children.is_empty() {
                return node_idx;
            }
            let best = if tree.nodes[children[0].node_idx].is_leaf() {
                choose_least_overlap(children, entry_bbox)
            } else {
                choose_least_enlargement(children, entry_bbox)
            };
            choose_subtree(tree, children[best].node_idx, entry_bbox, target_level)
        }
    }
}

fn choose_least_enlargement(children: &[ChildRef], entry_bbox: &BoundingBox) -> usize {
    let mut best = 0;