旋转卡壳算法详解（Rust语言实现凸包直径与最远点对）

前置知识：凸包（Convex Hull）

旋转卡壳算法作用于凸包。因此，我们首先需要将任意点集转换为凸包。在 Rust 中，我们可以使用 Andrew's monotone chain 算法来构建凸包。

定义点结构

#[derive(Debug, Clone, Copy, PartialEq)]struct Point {    x: f64,    y: f64,}impl Point {    fn new(x: f64, y: f64) -> Self {        Point { x, y }    }    // 计算叉积：(b - a) × (c - a)    fn cross(&self, b: &Point, c: &Point) -> f64 {        (b.x - self.x) * (c.y - self.y) - (b.y - self.y) * (c.x - self.x)    }    // 计算两点间距离的平方（避免开方提高性能）    fn dist_sq(&self, other: &Point) -> f64 {        let dx = self.x - other.x;        let dy = self.y - other.y;        dx * dx + dy * dy    }}

构建凸包

fn convex_hull(mut points: Vec<Point>) -> Vec<Point> {    if points.len() <= 1 {        return points;    }    // 按 x 升序，x 相同则按 y 升序    points.sort_by(|a, b| a.x.partial_cmp(&b.x).unwrap()        .then_with(|| a.y.partial_cmp(&b.y).unwrap()));    // 去重    points.dedup();    let n = points.len();    let mut hull = Vec::with_capacity(n);    // 下凸壳    for i in 0..n {        while hull.len() >= 2 &&               hull[hull.len() - 2].cross(&hull[hull.len() - 1], &points[i]) <= 0.0 {            hull.pop();        }        hull.push(points[i]);    }    // 上凸壳    let lower_len = hull.len();    for i in (0..=n-2).rev() {        while hull.len() > lower_len &&               hull[hull.len() - 2].cross(&hull[hull.len() - 1], &points[i]) <= 0.0 {            hull.pop();        }        hull.push(points[i]);    }    // 移除最后一个重复点（首尾相同）    if hull.len() > 1 {        hull.pop();    }    hull}

实现旋转卡壳算法

有了凸包后，我们就可以应用旋转卡壳算法来找最远点对（即凸包的直径）。核心思想是：对于凸包上的每一条边，找到离它最远的点，然后利用单调性避免重复计算。

fn rotating_calipers_diameter(hull: &[Point]) -> f64 {    let n = hull.len();    if n == 1 {        return 0.0;    }    if n == 2 {        return hull[0].dist_sq(&hull[1]).sqrt();    }    let mut max_dist_sq = 0.0;    let mut j = 1; // 最远点的索引    for i in 0..n {        // 找到下一个点 j，使得三角形面积最大（即距离最远）        // 利用叉积比较高度        let next_i = (i + 1) % n;        while (hull[next_i].x - hull[i].x) * (hull[(j + 1) % n].y - hull[j].y)            - (hull[next_i].y - hull[i].y) * (hull[(j + 1) % n].x - hull[j].x)            > 0.0 {            j = (j + 1) % n;        }        // 更新最大距离        max_dist_sq = max_dist_sq.max(hull[i].dist_sq(&hull[j]));    }    max_dist_sq.sqrt()}

上面的代码中，我们通过比较向量叉积的符号来判断是否应继续移动指针 j。这种方法的时间复杂度为 O(n)，非常高效。

完整示例与测试

fn main() {    let points = vec![        Point::new(0.0, 0.0),        Point::new(1.0, 0.0),        Point::new(1.0, 1.0),        Point::new(0.0, 1.0),        Point::new(0.5, 0.5),    ];    let hull = convex_hull(points);    println!("凸包点数: {}", hull.len());    let diameter = rotating_calipers_diameter(&hull);    println!("凸包直径: {:.4}", diameter);}

运行上述代码，你会得到正方形的对角线长度 √2 ≈ 1.4142，验证了算法的正确性。

总结

通过本文，你学会了如何在 Rust 中实现 旋转卡壳算法 来求解凸包的直径。这项技术广泛应用于计算机图形学、机器人路径规划和地理信息系统等领域。掌握 Rust凸包算法 和 Rust计算几何 的基础，将为你在高性能系统编程中处理空间数据打下坚实基础。

希望这篇 Rust编程教程 对你有所帮助！你可以尝试扩展该算法，用于计算凸包的宽度、最小包围矩形等更复杂的几何问题。