Split an overflowing node using the R*-tree axis split strategy.
(tree: &mut RTree, node_idx: usize)
| 7 | |
| 8 | /// Split an overflowing node using the R*-tree axis split strategy. |
| 9 | pub(crate) fn split_node(tree: &mut RTree, node_idx: usize) { |
| 10 | let is_root = node_idx == tree.root; |
| 11 | let level = tree.nodes[node_idx].level; |
| 12 | |
| 13 | let (sibling_idx, sibling_bbox) = match &mut tree.nodes[node_idx].kind { |
| 14 | NodeKind::Leaf { entries } => { |
| 15 | let all = std::mem::take(entries); |
| 16 | let (keep, split_off) = split_leaf_entries(all); |
| 17 | if let NodeKind::Leaf { entries } = &mut tree.nodes[node_idx].kind { |
| 18 | *entries = keep; |
| 19 | } |
| 20 | tree.nodes[node_idx].recompute_bbox(); |
| 21 | |
| 22 | let mut sibling = Node::new_leaf(); |
| 23 | if let NodeKind::Leaf { entries } = &mut sibling.kind { |
| 24 | *entries = split_off; |
| 25 | } |
| 26 | sibling.recompute_bbox(); |
| 27 | let bbox = sibling.bbox; |
| 28 | let idx = tree.nodes.len(); |
| 29 | tree.nodes.push(sibling); |
| 30 | (idx, bbox) |
| 31 | } |
| 32 | NodeKind::Internal { children } => { |
| 33 | let all = std::mem::take(children); |
| 34 | let (keep, split_off) = split_internal_children(all); |
| 35 | if let NodeKind::Internal { children } = &mut tree.nodes[node_idx].kind { |
| 36 | *children = keep; |
| 37 | } |
| 38 | tree.nodes[node_idx].recompute_bbox(); |
| 39 | |
| 40 | let mut sibling = Node::new_internal(level); |
| 41 | if let NodeKind::Internal { children } = &mut sibling.kind { |
| 42 | *children = split_off; |
| 43 | } |
| 44 | sibling.recompute_bbox(); |
| 45 | let bbox = sibling.bbox; |
| 46 | let idx = tree.nodes.len(); |
| 47 | tree.nodes.push(sibling); |
| 48 | (idx, bbox) |
| 49 | } |
| 50 | }; |
| 51 | |
| 52 | if is_root { |
| 53 | let old_root_bbox = tree.nodes[node_idx].bbox; |
| 54 | let mut new_root = Node::new_internal(level + 1); |
| 55 | if let NodeKind::Internal { children } = &mut new_root.kind { |
| 56 | children.push(ChildRef { |
| 57 | bbox: old_root_bbox, |
| 58 | node_idx, |
| 59 | }); |
| 60 | children.push(ChildRef { |
| 61 | bbox: sibling_bbox, |
| 62 | node_idx: sibling_idx, |
| 63 | }); |
| 64 | } |
| 65 | new_root.recompute_bbox(); |
| 66 | let new_root_idx = tree.nodes.len(); |
no test coverage detected