mark 增量式 Douglas-Peucker 算法

use egui::Pos2;

struct IncrementalSimplifier {
simplified: Vec<Pos2>, // 简化后的关键节点
buffer: Vec<Pos2>, // 缓存新增的临时点
epsilon: f32, // 误差阈值
buffer_limit: usize, // 缓存点数量上限
}

impl IncrementalSimplifier {
fn feed(&mut self, new_point: Pos2) {
self.buffer.push(new_point);

// 缓存点达到上限时触发局部简化
if self.buffer.len() >= self.buffer_limit {
self.simplify_buffer();
}
}

fn simplify_buffer(&mut self) {
if self.buffer.is_empty() {
return;
}
// 以简化集的最后一个点和缓存的第一个点为起点，局部应用Douglas-Peucker
let start = self.simplified.last().copied().unwrap_or(self.buffer[0]);
let mut local_points = vec![start];
local_points.extend(self.buffer.drain(..));

let local_simplified = douglas_peucker(&local_points, self.epsilon);
// 合并结果（排除重复的起点）
self.simplified.pop();
self.simplified.extend(local_simplified);
}
}

/// 计算点 p 到线段 (a, b) 的垂直距离
fn distance_point_to_segment(p: Pos2, a: Pos2, b: Pos2) -> f32 {
if a == b {
return (p - a).length(); // 线段为点时，直接返回两点距离
}

// 向量 AB 和 AP
let ab = b - a;
let ap = p - a;

// 计算 AP 在 AB 上的投影比例（ clamp 到 [0, 1] 确保在 segment 上）
let t = ap.dot(ab) / ab.dot(ab);
let t = t.clamp(0.0, 1.0);

// 投影点
let projection = a + ab * t;

// 点到投影点的距离
(p - projection).length()
}

/// Douglas-Peucker 算法简化点集
fn douglas_peucker(points: &[Pos2], epsilon: f32) -> Vec<Pos2> {
if points.len() <= 2 {
return points.to_vec(); // 少于 2 个点直接返回
}

let start = 0;
let end = points.len() - 1;
let a = points[start];
let b = points[end];

// 找到最远点
let mut max_dist = 0.0;
let mut max_idx = 0;
for (i, &p) in points.iter().enumerate().take(end).skip(start + 1) {
let dist = distance_point_to_segment(p, a, b);

// 递归简化
if max_dist > epsilon {
let mut left = douglas_peucker(&points[start..=max_idx], epsilon);
let mut right = douglas_peucker(&points[max_idx..=end], epsilon);
left.pop(); // 移除重复的 max_idx 点
left.extend(right);
left
} else {
vec![a, b] // 保留起点和终点
}
}

// 示例用法
fn main() {
// 原始点集（模拟一条曲线）
let original_points = vec![
Pos2::new(0.0, 0.0),
Pos2::new(1.0, 1.0),
Pos2::new(2.0, 0.5),
Pos2::new(3.0, 2.0),
Pos2::new(4.0, 2.0),
Pos2::new(5.0, 2.0),
Pos2::new(6.0, 2.0),
Pos2::new(7.0, 1.0),
Pos2::new(8.0, 1.0),
Pos2::new(9.0, 1.0),
Pos2::new(10.0, 1.0),
Pos2::new(11.0, 3.0),
Pos2::new(12.0, 3.0),
Pos2::new(13.0, 3.0),
Pos2::new(14.0, 3.0),
];

// 简化（阈值 ε=0.5）
let simplified = douglas_peucker(&original_points, 0.5);

println!("原始点集: {:?}", original_points);
println!("简化后: {:?}", simplified);
}