python 旋转卡壳

旋转卡壳（Rotating Calipers）是计算几何中的一种常用算法，它可以求解凸包的直径，最小矩形等问题。

旋转卡壳的基本思想是，将凸包上的一条边作为旋转轴，将凸包沿着这个轴旋转，同时用两条平行线去“夹”住凸包，这样可以得到凸包在旋转过程中的最大宽度和最小高度，从而得到凸包的直径和最小矩形。

下面是一个 Python 实现旋转卡壳算法的示例代码：

import math

# 计算两点之间的距离
def distance(p1, p2):
    return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)

# 计算向量的叉积
def cross(p1, p2, p3):
    return (p2[0]-p1[0]) * (p3[1]-p2[1]) - (p2[1]-p1[1]) * (p3[0]-p2[0])

# 计算凸包上的直径
def convex_diameter(points):
    n = len(points)
    if n < 2:
        return 0
    if n == 2:
        return distance(points[0], points[1])
    # 找到最左边和最右边的点
    left = min(points, key=lambda x: x[0])
    right = max(points, key=lambda x: x[0])
    # 初始化旋转轴和最大宽度
    base = [1, 0]
    max_width = distance(left, right)
    # 旋转轴的初始方向是从左向右
    direction = 1
    i, j = points.index(left), points.index(right)
    while i != j:
        # 计算当前两条平行线的宽度
        width = cross(points[i], points[(i+direction)%n], points[j]) / distance(points[i], points[(i+direction)%n])
        if width > max_width:
            max_width = width
        # 计算旋转角度
        angle = math.acos((points[(i+direction)%n][0]-points[i][0])/distance(points[i], points[(i+direction)%n]))
        # 根据叉积判断旋转方向
        if cross(base, points[i], points[(i+direction)%n]) > 0:
            angle = -angle
        # 旋转旋转轴
        base = [math.cos(angle)*base[0]-math.sin(angle)*base[1], math.sin(angle)*base[0]+math.cos(angle)*base[1]]
        # 更新下一个点的下标
        i = (i+direction) % n
    return max_width

这里实现的是求凸包上的直径，输入参数 points 是一个二维点数组，例如 [[0,0], [1,1], [2,2], [2,0], [3,3], [4,4]]，返回的是凸包的直径。