docvortex_core/
table_merge.rs

1//! 自有表格候选的网格扩展、共享成员与动态合并；只在最终边界导出保留结果。
2use crate::geometry::{rotate, Box4, Size};
3use std::collections::{HashMap, HashSet};
4use std::hash::{BuildHasherDefault, Hasher};
5use std::sync::Arc;
6
7/// 来源 ID 由解析器生成；用整数混合避免对大量行号执行通用字符串哈希。
8#[derive(Default)]
9pub struct IdHasher(u64);
10impl Hasher for IdHasher {
11    /// 返回当前混合值，集合仍通过整数相等判定处理哈希碰撞。
12    fn finish(&self) -> u64 {
13        self.0
14    }
15    /// 保留 Hasher 的字节入口，实际成员键走专用整数方法。
16    fn write(&mut self, bytes: &[u8]) {
17        for b in bytes {
18            self.0 = (self.0 ^ u64::from(*b)).wrapping_mul(0x100000001b3);
19        }
20    }
21    /// 混合高低位，避免稀疏行号与负数集中到同一桶。
22    fn write_u64(&mut self, value: u64) {
23        let mut v = value.wrapping_add(0x9e3779b97f4a7c15);
24        v = (v ^ (v >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
25        v = (v ^ (v >> 27)).wrapping_mul(0x94d049bb133111eb);
26        self.0 = v ^ (v >> 31);
27    }
28    /// 有符号 ID 按位无损转换，不把负来源号当作数组下标。
29    fn write_i64(&mut self, value: i64) {
30        self.write_u64(value as u64);
31    }
32}
33pub type Ids = HashSet<i64, BuildHasherDefault<IdHasher>>;
34pub type Row = (f64, Vec<(i64, Box4)>);
35
36/// 有限普通坐标准入，限制极值以避免面积运算溢出。
37pub fn valid(b: &Box4) -> bool {
38    b.iter().all(|v| v.is_finite() && v.abs() <= 1e150)
39}
40
41/// 按首见坐标合并，保留相等值及负零。
42fn union(mut a: Box4, b: Box4) -> Box4 {
43    for i in 0..4 {
44        if (i < 2 && b[i] < a[i]) || (i >= 2 && b[i] > a[i]) {
45            a[i] = b[i];
46        }
47    }
48    a
49}
50
51/// 复用原 Python 面积定义，仅网格面积将负宽高截为零。
52fn area(b: Box4) -> f64 {
53    (b[2] - b[0]).max(0.0) * (b[3] - b[1]).max(0.0)
54}
55
56/// 保持较小框面积作为分母，退化框返回零。
57fn overlap(a: Box4, b: Box4) -> f64 {
58    let intersection =
59        (a[2].min(b[2]) - a[0].max(b[0])).max(0.0) * (a[3].min(b[3]) - a[1].max(b[1])).max(0.0);
60    let denominator = ((a[2] - a[0]) * (a[3] - a[1])).min((b[2] - b[0]) * (b[3] - b[1]));
61    if denominator > 0.0 {
62        intersection / denominator
63    } else {
64        0.0
65    }
66}
67
68/// 从局部坐标回到页面坐标，保持减法顺序及非正交角的原样返回。
69fn inverse(b: Box4, size: Size, angle: i32) -> Box4 {
70    match angle {
71        270 => [b[1], size[1] - b[2], b[3], size[1] - b[0]],
72        90 => [size[0] - b[3], b[0], size[0] - b[1], b[2]],
73        180 => [
74            size[0] - b[2],
75            size[1] - b[3],
76            size[0] - b[0],
77            size[1] - b[1],
78        ],
79        _ => b,
80    }
81}
82
83#[derive(Clone)]
84pub struct Members {
85    base: Arc<Ids>,
86    added: Ids,
87    removed: Ids,
88}
89impl Members {
90    /// 普通已构造候选没有共享基底，后续可精确转换到首个网格基底。
91    pub fn plain(added: Ids) -> Self {
92        Self {
93            base: Arc::new(Ids::default()),
94            added,
95            removed: Ids::default(),
96        }
97    }
98    /// 未扩展核心共享不可变成员，不在每个候选上复制完整集合。
99    pub fn new(base: Arc<Ids>, excluded: Ids) -> Self {
100        let removed = excluded.into_iter().filter(|v| base.contains(v)).collect();
101        Self {
102            base,
103            added: Ids::default(),
104            removed,
105        }
106    }
107    /// 查询当前可见成员，包括共享基底上的删改差集。
108    fn contains(&self, value: &i64) -> bool {
109        self.added.contains(value) || (self.base.contains(value) && !self.removed.contains(value))
110    }
111    /// 仅在跨基底合并或最终输出时枚举实际成员。
112    pub fn values(&self) -> impl Iterator<Item = i64> + '_ {
113        self.base
114            .iter()
115            .filter(|v| !self.removed.contains(v))
116            .chain(&self.added)
117            .copied()
118    }
119    /// 网格扩展先并入基底，再排除注释，和共享 Python 集合的构造顺序相同。
120    fn expand(&mut self, base: Arc<Ids>, excluded: &Ids) {
121        let added = self.values().filter(|v| !base.contains(v)).collect();
122        self.base = base;
123        self.added = added;
124        self.removed = Ids::default();
125        for id in excluded {
126            self.added.remove(id);
127            if self.base.contains(id) {
128                self.removed.insert(*id);
129            }
130        }
131    }
132    /// 优先统一共享基底，后续同网格候选只合并差集。
133    fn merge(&mut self, other: &Self) {
134        if !Arc::ptr_eq(&self.base, &other.base) && self.base.is_empty() && !other.base.is_empty() {
135            let visible: Ids = self.values().collect();
136            self.removed = other.base.difference(&visible).copied().collect();
137            self.added = visible.difference(&other.base).copied().collect();
138            self.base = other.base.clone();
139        }
140        if Arc::ptr_eq(&self.base, &other.base) {
141            self.removed.retain(|v| other.removed.contains(v));
142            for id in &other.added {
143                if self.base.contains(id) {
144                    self.removed.remove(id);
145                } else {
146                    self.added.insert(*id);
147                }
148            }
149        } else {
150            for id in other.values() {
151                if self.base.contains(&id) {
152                    self.removed.remove(&id);
153                } else {
154                    self.added.insert(id);
155                }
156            }
157        }
158    }
159}
160
161pub struct Annotation {
162    pub kind: String,
163    pub bbox: Box4,
164    pub members: Ids,
165    pub rows: Vec<(i64, Box4)>,
166}
167pub struct Candidate {
168    pub bbox: Box4,
169    pub local: Box4,
170    pub core: Option<Box4>,
171    pub angle: i32,
172    pub score: f64,
173    pub members: Members,
174    pub annotations: Vec<Annotation>,
175}
176
177pub struct GridContext {
178    grids: Vec<Box4>,
179    rows: Vec<Row>,
180    size: Size,
181    angle: i32,
182    tolerance: f64,
183    cache: HashMap<[u64; 4], Arc<Ids>>,
184}
185impl GridContext {
186    /// 页面只准备一次网格及片段中心数据；拒绝特殊数值而不改变候选覆盖。
187    pub fn new(
188        grids: Vec<Box4>,
189        rows: Vec<Row>,
190        size: Size,
191        angle: i32,
192        height: f64,
193    ) -> Option<Self> {
194        if grids.iter().any(|b| !valid(b))
195            || rows
196                .iter()
197                .any(|r| !r.0.is_finite() || r.1.iter().any(|(_, b)| !valid(b)))
198            || size.iter().any(|v| !v.is_finite() || v.abs() > 1e100)
199            || !height.is_finite()
200        {
201            return None;
202        }
203        Some(Self {
204            grids,
205            rows,
206            size,
207            angle,
208            tolerance: 2.0_f64.max(height),
209            cache: HashMap::new(),
210        })
211    }
212    /// 扩展后才参与候选合并；首见并列网格及页面旋转往返均保持原顺序。
213    pub fn expand(&mut self, candidate: &mut Candidate) {
214        let Some(core) = candidate.core else {
215            return;
216        };
217        let core = rotate(core, self.size, self.angle);
218        let mut selected = None;
219        for grid in &self.grids {
220            let shorter = (core[2] - core[0]).min(grid[2] - grid[0]);
221            let share = if shorter > 0.0 {
222                (core[2].min(grid[2]) - core[0].max(grid[0])).max(0.0) / shorter
223            } else {
224                0.0
225            };
226            if share < 0.9
227                || core[3] < grid[1] - self.tolerance
228                || core[1] > grid[3] + self.tolerance
229            {
230                continue;
231            }
232            let score = (core[3].min(grid[3]) - core[1].max(grid[1]), area(*grid));
233            if selected
234                .as_ref()
235                .is_none_or(|(previous, _)| score > *previous)
236            {
237                selected = Some((score, *grid));
238            }
239        }
240        let Some((_, grid)) = selected else {
241            return;
242        };
243        let expanded = union(core, grid);
244        candidate.local = union(candidate.local, grid);
245        candidate.core = Some(inverse(expanded, self.size, self.angle));
246        candidate.bbox = inverse(candidate.local, self.size, self.angle);
247        let key = expanded.map(|v| if v == 0.0 { 0 } else { v.to_bits() });
248        let members = self.cache.get(&key).cloned().unwrap_or_else(|| {
249            let mut ids = Ids::default();
250            for (center, fragments) in &self.rows {
251                if *center < expanded[1] || *center > expanded[3] {
252                    continue;
253                }
254                for (id, b) in fragments {
255                    let x = (b[0] + b[2]) / 2.0;
256                    let y = (b[1] + b[3]) / 2.0;
257                    if expanded[0] <= x && x <= expanded[2] && expanded[1] <= y && y <= expanded[3]
258                    {
259                        ids.insert(*id);
260                    }
261                }
262            }
263            let members = Arc::new(ids);
264            // 页面级缓存有界，超出后继续精确计算，不减少候选或成员。
265            if self.cache.len() < 128 {
266                self.cache.insert(key, members.clone());
267            }
268            members
269        });
270        let excluded = candidate
271            .annotations
272            .iter()
273            .flat_map(|a| a.members.iter().copied())
274            .collect();
275        candidate.members.expand(members, &excluded);
276    }
277}
278
279/// 动态合并注释；表体优先，行框保留首次插入顺序，再计算注释并集。
280fn merge_annotations(target: &mut Candidate, annotations: Vec<Annotation>) {
281    for annotation in annotations {
282        if let Some(existing) = target
283            .annotations
284            .iter_mut()
285            .find(|a| a.kind == annotation.kind)
286        {
287            existing.bbox = union(existing.bbox, annotation.bbox);
288            existing.members.extend(annotation.members);
289            for (id, bbox) in annotation.rows {
290                if let Some((_, previous)) = existing.rows.iter_mut().find(|(v, _)| *v == id) {
291                    *previous = union(*previous, bbox);
292                } else {
293                    existing.rows.push((id, bbox));
294                }
295            }
296        } else {
297            target.annotations.push(annotation);
298        }
299    }
300    for annotation in &mut target.annotations {
301        annotation.members.retain(|id| !target.members.contains(id));
302        annotation
303            .rows
304            .retain(|(id, _)| annotation.members.contains(id));
305        if let Some((_, first)) = annotation.rows.first() {
306            annotation.bbox = annotation
307                .rows
308                .iter()
309                .skip(1)
310                .fold(*first, |b, (_, next)| union(b, *next));
311        }
312    }
313    target.annotations.retain(|a| !a.members.is_empty());
314}
315
316#[derive(Default)]
317pub struct Merger {
318    pub candidates: Vec<Candidate>,
319}
320impl Merger {
321    /// 调用方按分数稳定降序追加；始终与已经合并更新后的首个目标比较。
322    pub fn push(&mut self, candidate: Candidate) {
323        let Some(target) = self
324            .candidates
325            .iter_mut()
326            .find(|c| c.angle == candidate.angle && overlap(candidate.bbox, c.bbox) >= 0.2)
327        else {
328            self.candidates.push(candidate);
329            return;
330        };
331        target.bbox = union(target.bbox, candidate.bbox);
332        target.local = union(target.local, candidate.local);
333        target.core = match (target.core, candidate.core) {
334            (Some(a), Some(b)) => Some(union(a, b)),
335            (None, b) => b,
336            (a, None) => a,
337        };
338        target.members.merge(&candidate.members);
339        if candidate.score > target.score {
340            target.score = candidate.score;
341        }
342        merge_annotations(target, candidate.annotations);
343    }
344    /// 只在最终边界稳定按页面位置排序，不在中间阶段重排目标。
345    pub fn finish(mut self) -> Vec<Candidate> {
346        self.candidates.sort_by(|a, b| {
347            (a.bbox[1], a.bbox[0])
348                .partial_cmp(&(b.bbox[1], b.bbox[0]))
349                .unwrap()
350        });
351        self.candidates
352    }
353}
docvortex_core/table_merge.rs

docvortex_core/
table_merge.rs
