旋转卡壳算法详解（使用Python实现凸包直径与最远点对计算）

前置知识：凸包（Convex Hull）

在应用旋转卡壳之前，我们需要先获得点集的凸包。凸包可以理解为包裹所有点的最小凸多边形。常用的凸包算法有 Graham 扫描法、Andrew 算法等。本文将使用 Andrew 算法，因为它简洁且易于实现。

步骤一：构建凸包

首先，我们编写一个函数来计算给定点集的凸包：

def cross(o, a, b):    """计算向量 oa × ob 的叉积"""    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])def convex_hull(points):    """使用 Andrew 算法计算凸包"""    points = sorted(set(points))    if len(points) <= 1:        return points    # 构建下凸壳    lower = []    for p in points:        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:            lower.pop()        lower.append(p)    # 构建上凸壳    upper = []    for p in reversed(points):        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:            upper.pop()        upper.append(p)    # 去掉重复端点    return lower[:-1] + upper[:-1]

步骤二：实现旋转卡壳算法

有了凸包后，我们就可以在其上应用旋转卡壳算法来寻找最远点对。核心思想是：对于凸包上的每一条边，找到离该边最远的点（即“对踵点”），并更新最大距离。

import mathdef dist(p1, p2):    """计算两点间欧氏距离"""    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)def rotating_calipers(hull):    """旋转卡壳算法：返回凸包中最远点对的距离"""    n = len(hull)    if n == 1:        return 0    if n == 2:        return dist(hull[0], hull[1])    k = 1    res = 0    # 遍历每条边    for i in range(n):        j = (i + 1) % n        # 找到离边 (hull[i], hull[j]) 最远的点        while True:            next_k = (k + 1) % n            # 比较三角形面积（用叉积代替）            if cross(hull[i], hull[j], hull[next_k]) > cross(hull[i], hull[j], hull[k]):                k = next_k            else:                break        # 更新最大距离        res = max(res, dist(hull[i], hull[k]), dist(hull[j], hull[k]))    return res

完整示例：计算点集的直径

现在我们将上述函数组合起来，完成整个流程：

# 示例点集points = [(0, 0), (1, 1), (2, 0), (1, 2), (3, 3), (-1, 2)]# 1. 计算凸包hull = convex_hull(points)print("凸包顶点:", hull)# 2. 使用旋转卡壳算法计算直径diameter = rotating_calipers(hull)print("凸包直径（最远点对距离）:", diameter)

为什么旋转卡壳高效？

朴素方法需要检查所有点对，时间复杂度为 O(n²)。而旋转卡壳算法利用凸包的单调性，只需线性扫描（O(n)），前提是凸包已构建（构建凸包为 O(n log n)）。因此整体复杂度为 O(n log n)，非常适合处理大规模点集。

应用场景

• 地理信息系统（GIS）中计算区域最大跨度
• 计算机视觉中的形状分析
• 机器人路径规划中的障碍物包围盒计算
• 游戏开发中的碰撞检测优化

总结

通过本教程，你已经掌握了如何用 Python 实现旋转卡壳算法来求解凸包的直径。关键在于先构建凸包，再利用对踵点的性质线性扫描。这项技术是计算几何中的重要工具，也是面试和竞赛中的高频考点。

记住我们的四个核心关键词：旋转卡壳算法、凸包算法、Python几何计算 和 计算几何。掌握它们，你就能在几何问题中游刃有余！

动手试试吧！修改点集，观察结果变化，加深理解。