docvortex_core/
row_geometry.rs

1//! 保序行框聚合与最大下边界查询，返回来源位置以共享 Python 原坐标。
2
3pub struct RowGeometry {
4    boxes: Vec<[f64; 4]>,
5    size: usize,
6    tree: Vec<[usize; 4]>,
7}
8
9impl RowGeometry {
10    /// 拒绝非有限几何，平局选较早来源，避免改变负零及原坐标身份。
11    pub fn new(boxes: Vec<[f64; 4]>) -> Option<Self> {
12        if boxes.iter().flatten().any(|x| !x.is_finite()) {
13            return None;
14        }
15        let size = boxes.len().max(1).next_power_of_two();
16        let mut result = Self {
17            boxes,
18            size,
19            tree: vec![[usize::MAX; 4]; size * 2],
20        };
21        for i in 0..result.boxes.len() {
22            result.tree[size + i] = [i; 4];
23        }
24        for i in (1..size).rev() {
25            result.tree[i] = result.combine(result.tree[i * 2], result.tree[i * 2 + 1]);
26        }
27        Some(result)
28    }
29
30    /// 合并保序区间的极值来源，严格比较使相等值始终保留左侧对象。
31    fn combine(&self, a: [usize; 4], b: [usize; 4]) -> [usize; 4] {
32        let mut output = a;
33        for k in 0..4 {
34            if a[k] == usize::MAX {
35                output[k] = b[k];
36            } else if b[k] != usize::MAX {
37                let better = if k < 2 {
38                    self.boxes[b[k]][k] < self.boxes[a[k]][k]
39                } else {
40                    self.boxes[b[k]][k] > self.boxes[a[k]][k]
41                };
42                if better {
43                    output[k] = b[k];
44                }
45            }
46        }
47        output
48    }
49
50    /// 使用左右独立累计器，查询树拆分不能改变原始行的比较顺序。
51    pub fn union_indices(&self, start: usize, end: usize) -> Option<[usize; 4]> {
52        if start >= end || end > self.boxes.len() {
53            return None;
54        }
55        let (mut l, mut r) = (self.size + start, self.size + end);
56        let (mut left, mut right) = ([usize::MAX; 4], [usize::MAX; 4]);
57        while l < r {
58            if l % 2 == 1 {
59                left = self.combine(left, self.tree[l]);
60                l += 1;
61            }
62            if r % 2 == 1 {
63                r -= 1;
64                right = self.combine(self.tree[r], right);
65            }
66            l /= 2;
67            r /= 2;
68        }
69        Some(self.combine(left, right))
70    }
71
72    /// 找到原顺序中首个下边界严格超过表底的行，不要求边界单调。
73    pub fn first_after(&self, bottom: f64) -> usize {
74        if self.boxes.is_empty() {
75            return 0;
76        }
77        let mut node = 1;
78        let source = self.tree[node][3];
79        if self.boxes[source][3] <= bottom {
80            return self.boxes.len();
81        }
82        while node < self.size {
83            let left = self.tree[node * 2][3];
84            node = if left != usize::MAX && self.boxes[left][3] > bottom {
85                node * 2
86            } else {
87                node * 2 + 1
88            };
89        }
90        (node - self.size).min(self.boxes.len())
91    }
92}
docvortex_core/row_geometry.rs

docvortex_core/
row_geometry.rs
