用Rust实现凸包算法（从零开始掌握计算几何中的Andrew算法）

为什么选择 Andrew 算法？

Andrew 算法是 Graham 扫描法的一种变体，它通过分别构建凸包的上半部分和下半部分，时间复杂度为 O(n log n)，易于理解和实现，非常适合初学者学习 计算几何 的入门。

准备工作：创建 Rust 项目

首先，确保你已安装 Rust（可通过 rustup 安装）。然后在终端中运行：

cargo new convex_hull_tutorialcd convex_hull_tutorial

步骤一：定义点结构

我们先定义一个二维点的结构体，并实现必要的比较方法：

#[derive(Debug, Clone, Copy)]struct Point {    x: i32,    y: i32,}impl PartialEq for Point {    fn eq(&self, other: &Self) -> bool {        self.x == other.x && self.y == other.y    }}impl Eq for Point {}impl PartialOrd for Point {    fn partial_cmp(&self, other: &Self) -> Option {        Some(self.cmp(other))    }}impl Ord for Point {    fn cmp(&self, other: &Self) -> std::cmp::Ordering {        match self.x.cmp(&other.x) {            std::cmp::Ordering::Equal => self.y.cmp(&other.y),            other => other,        }    }}

这里我们让 Point 可以按 x 坐标排序，x 相同时按 y 排序，这是 Andrew 算法的前提。

步骤二：实现叉积函数

叉积用于判断三个点的转向（左转、右转或共线）：

fn cross(o: &Point, a: &Point, b: &Point) -> i32 {    (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)}

- 如果结果 > 0：左转（逆时针）
- 如果结果 < 0：右转（顺时针）
- 如果结果 = 0：三点共线

步骤三：实现 Andrew 凸包算法

fn convex_hull(mut points: Vec) -> Vec {    if points.len() <= 1 {        return points;    }    // 按 x（然后 y）排序    points.sort();    // 去重    points.dedup();    let n = points.len();    let mut hull = Vec::with_capacity(n);    // 构建下凸壳    for i in 0..n {        while hull.len() >= 2 {            let last = hull.len() - 1;            if cross(&hull[last - 1], &hull[last], &points[i]) <= 0 {                hull.pop();            } else {                break;            }        }        hull.push(points[i]);    }    // 构建上凸壳    let lower_len = hull.len();    for i in (0..=n - 2).rev() {        while hull.len() > lower_len {            let last = hull.len() - 1;            if cross(&hull[last - 1], &hull[last], &points[i]) <= 0 {                hull.pop();            } else {                break;            }        }        hull.push(points[i]);    }    // 移除最后一个重复点（起点）    if !hull.is_empty() {        hull.pop();    }    hull}

步骤四：测试我们的算法

在 main.rs 中添加主函数进行测试：

fn main() {    let points = vec![        Point { x: 0, y: 0 },        Point { x: 1, y: 1 },        Point { x: 2, y: 2 },        Point { x: 0, y: 2 },        Point { x: 2, y: 0 },        Point { x: 1, y: 0 },    ];    let hull = convex_hull(points);    println!("凸包顶点: {:?}", hull);}

运行程序：

cargo run

你应该看到输出类似：

凸包顶点: [Point { x: 0, y: 0 }, Point { x: 2, y: 0 }, Point { x: 2, y: 2 }, Point { x: 0, y: 2 }]

总结

恭喜你！你已经成功用 Rust 实现了凸包算法。通过本教程，你不仅掌握了 Rust编程教程 中的重要实践，也深入理解了 计算几何 的核心思想。Andrew 算法简洁高效，是解决凸包问题的理想选择。

希望这篇关于 Rust凸包算法 和 Andrew算法 的教程对你有帮助！你可以尝试扩展功能，比如处理浮点坐标、可视化结果等。