(children: &[ChildRef], entry_bbox: &BoundingBox)
| 95 | } |
| 96 | |
| 97 | fn choose_least_overlap(children: &[ChildRef], entry_bbox: &BoundingBox) -> usize { |
| 98 | let mut best = 0; |
| 99 | let mut best_oi = f64::INFINITY; |
| 100 | let mut best_enlarge = f64::INFINITY; |
| 101 | let mut best_area = f64::INFINITY; |
| 102 | for (i, child) in children.iter().enumerate() { |
| 103 | let enlarged = child.bbox.union(entry_bbox); |
| 104 | let mut before = 0.0_f64; |
| 105 | let mut after = 0.0_f64; |
| 106 | for (j, other) in children.iter().enumerate() { |
| 107 | if j != i { |
| 108 | before += child.bbox.overlap_area(&other.bbox); |
| 109 | after += enlarged.overlap_area(&other.bbox); |
| 110 | } |
| 111 | } |
| 112 | let oi = after - before; |
| 113 | let enlarge = child.bbox.enlargement(entry_bbox); |
| 114 | let area = child.bbox.area(); |
| 115 | if oi < best_oi |
| 116 | || (oi == best_oi && enlarge < best_enlarge) |
| 117 | || (oi == best_oi && enlarge == best_enlarge && area < best_area) |
| 118 | { |
| 119 | best = i; |
| 120 | best_oi = oi; |
| 121 | best_enlarge = enlarge; |
| 122 | best_area = area; |
| 123 | } |
| 124 | } |
| 125 | best |
| 126 | } |
| 127 | |
| 128 | /// R*-tree overflow: forced reinsert first, then split on second overflow. |
| 129 | fn treat_overflow(tree: &mut RTree, node_idx: usize, reinserted_levels: &mut Vec<u32>) { |
no test coverage detected