1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
// src/geom/simplify.rs
use geo::ConvexHull;
use geo::Simplify;
use geo_types::{Coord, LineString, Polygon};
use std::time::Instant;
/// 几何简化器
pub struct GeometrySimplifier;
impl GeometrySimplifier {
/// 使用凸包 + Douglas-Peucker 算法简化轮廓，筛选出四边形候选。
///
/// # 算法说明
/// 1. 将输入坐标点集构造为 LineString 并主动闭合。
/// 2. **新增**：对轮廓求凸包，消除锯齿噪声，使 D-P 更易收敛到 4 顶点。
/// 3. 以多档容差对凸包执行 Douglas-Peucker 简化，寻找恰好为 5 点的结果。
/// 4. 若多档容差均未能得到 5 点，则使用极值点法强制提取 4 个角点作为后备。
///
/// # 凸包预处理的必要性
/// 真实照片中文档边缘因透视变形、光照不均、纸张弯曲，Canny 产生带噪声的曲线段。
/// 直接对锯齿轮廓执行 D-P，容差小时点数过多，容差大时直接跳过 5 点跌至 3 点，
/// 无法在任何容差档位精确停在 5 点。凸包将轮廓预处理为凸多边形后，
/// D-P 的简化路径更平滑，能稳定收敛到 4 顶点（5 点闭合 LineString）。
///
/// # 闭合保证
/// 输入轮廓若首尾不同，此处主动闭合，确保 geo::Simplify 对闭合轮廓的正确处理。
pub fn simplify_to_quad(contour: Vec<Coord<f32>>) -> Option<LineString<f32>> {
let start = Instant::now();
if contour.len() < 4 {
log::debug!(
"[Geom::Simplify] - Contour too short (len={}), skipping.",
contour.len()
);
return None;
}
let original_len = contour.len();
// P1 修复：主动闭合轮廓，防止 ContourExtractor 输出未闭合时判断失效
let mut coords = contour;
if coords.first() != coords.last() {
if let Some(&first) = coords.first() {
coords.push(first);
}
}
let line_string = LineString::new(coords);
// 周长为零（退化轮廓）直接跳过
let perimeter = geo::EuclideanLength::euclidean_length(&line_string);
if perimeter < f32::EPSILON {
log::debug!(
"[Geom::Simplify] - Contour has zero perimeter (len={}), skipping.",
original_len
);
return None;
}
// ★ P0 修复：凸包预处理
// 对原始轮廓求凸包，将锯齿状噪声曲线转换为平滑凸多边形，
// 大幅提升后续 Douglas-Peucker 简化到恰好 4 顶点的成功率。
let polygon = Polygon::new(line_string.clone(), vec![]);
let hull: LineString<f32> = polygon.convex_hull().exterior().clone();
let hull_point_count = hull.0.len();
log::debug!(
"[Geom::Simplify] - Convex hull: original_len={}, hull_points={}, perimeter={:.1}",
original_len,
hull_point_count,
perimeter
);
// 凸包退化检查（少于 4 点无法构成四边形）
if hull_point_count < 5 {
log::debug!(
"[Geom::Simplify] - Hull degenerate (hull_points={} < 5), skipping.",
hull_point_count
);
return None;
}
let hull_perimeter = geo::EuclideanLength::euclidean_length(&hull);
// 多档容差依次尝试，从细粒度到粗粒度
let epsilon_ratios: &[f32] = &[0.01, 0.02, 0.03, 0.05, 0.08, 0.12, 0.20, 0.30, 0.40];
for &ratio in epsilon_ratios {
let epsilon = hull_perimeter * ratio;
let simplified = hull.simplify(&epsilon);
let simplified_len = simplified.0.len();
log::trace!(
"[Geom::Simplify] - DP trial: ratio={:.0}%, epsilon={:.1}, simplified_points={}",
ratio * 100.0,
epsilon,
simplified_len
);
if simplified_len == 5 {
log::debug!(
"[Geom::Simplify] - Found quad via convex-hull+DP at epsilon_ratio={:.0}%. \
original_len={}, hull_points={}, Elapsed: {}µs",
ratio * 100.0,
original_len,
hull_point_count,
start.elapsed().as_micros()
);
return Some(simplified);
}
}
log::debug!(
"[Geom::Simplify] - DP failed to find 5-point result for hull (hull_points={}). \
Falling back to extreme-point method. Elapsed: {}µs",
hull_point_count,
start.elapsed().as_micros()
);
// 后备策略：对凸包执行极值点法（比对原始轮廓更稳定，凸包已去除噪声）
let result = Self::extract_quad_by_extremes(&hull);
if result.is_some() {
log::debug!(
"[Geom::Simplify] - Extreme-point fallback SUCCEEDED (hull_points={}). Elapsed: {}µs",
hull_point_count,
start.elapsed().as_micros()
);
} else {
log::debug!(
"[Geom::Simplify] - Extreme-point fallback FAILED (hull_points={}). Elapsed: {}µs",
hull_point_count,
start.elapsed().as_micros()
);
}
result
}
/// 极值点法：从轮廓中提取 4 个角点，构造近似四边形。
///
/// # 算法说明
/// 分别找到使 (x+y)、(x-y)、(-x+y)、(-x-y) 最大的点，
/// 对应图像坐标系中的左上、右上、左下、右下四个极值方向。
/// 这 4 个点对于矩形轮廓能精确定位四个角，对透视变形矩形也有良好近似。
///
/// 返回的 LineString 包含 5 个点（4 顶点 + 重复起点），与 Douglas-Peucker 输出格式一致。
///
/// # P1 修复
/// 原退化检测使用 `f32::EPSILON` 精度判断 + 内层 `break` 导致计数不准确。
/// 改为基于欧氏距离的阈值判断（5px），更符合像素坐标的实际精度需求。
fn extract_quad_by_extremes(line_string: &LineString<f32>) -> Option<LineString<f32>> {
let pts = &line_string.0;
if pts.len() < 4 {
return None;
}
// 分别寻找 4 个极值方向的代表点：
// - min(x+y) → 左上角（图像坐标系 y 向下）
// - max(x-y) → 右上角
// - max(x+y) → 右下角
// - min(x-y) → 左下角
let tl = pts.iter().min_by(|a, b| {
(a.x + a.y)
.partial_cmp(&(b.x + b.y))
.unwrap_or(std::cmp::Ordering::Equal)
})?;
let tr = pts.iter().max_by(|a, b| {
(a.x - a.y)
.partial_cmp(&(b.x - b.y))
.unwrap_or(std::cmp::Ordering::Equal)
})?;
let br = pts.iter().max_by(|a, b| {
(a.x + a.y)
.partial_cmp(&(b.x + b.y))
.unwrap_or(std::cmp::Ordering::Equal)
})?;
let bl = pts.iter().min_by(|a, b| {
(a.x - a.y)
.partial_cmp(&(b.x - b.y))
.unwrap_or(std::cmp::Ordering::Equal)
})?;
log::debug!(
"[Geom::Simplify] - Extreme points: TL=({:.1},{:.1}), TR=({:.1},{:.1}), BR=({:.1},{:.1}), BL=({:.1},{:.1})",
tl.x, tl.y, tr.x, tr.y, br.x, br.y, bl.x, bl.y
);
// P1 修复：改用欧氏距离阈值判断重合，替代原来的 f32::EPSILON + break 逻辑。
// 原逻辑：内层 break 只跳出 j 循环，当 i=0 与 i=1 各有一个重合时，
// count 只被减 1 而非 2，导致退化四边形漏检。
// 新逻辑：任意两点距离 < 5px 即视为重合，直接拒绝。
let corners = [tl, tr, br, bl];
for i in 0..4 {
for j in (i + 1)..4 {
let dx = corners[i].x - corners[j].x;
let dy = corners[i].y - corners[j].y;
let dist = (dx * dx + dy * dy).sqrt();
if dist < 5.0 {
log::warn!(
"[Geom::Simplify] - Extreme-point fallback produced degenerate quad: \
corners[{}]=({:.1},{:.1}) and corners[{}]=({:.1},{:.1}) are too close (dist={:.1}px < 5px).",
i, corners[i].x, corners[i].y,
j, corners[j].x, corners[j].y,
dist
);
return None;
}
}
}
// 构造闭合 LineString（5 点，首尾相同）
let quad_coords = vec![*tl, *tr, *br, *bl, *tl];
Some(LineString::new(quad_coords))
}
}