旋转卡壳法求凸包直径并绘图的python代码

以下是旋转卡壳法求凸包直径并绘图的Python代码：

import math
import matplotlib.pyplot as plt

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

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

# 计算凸包直径
def diameter(points):
    n = len(points)
    if n < 2:
        return 0, []
    if n == 2:
        return distance(points[0], points[1]), [points[0], points[1]]

    # 找到最左边和最右边的点
    left = min(points, key=lambda x: x[0])
    right = max(points, key=lambda x: x[0])

    # 找到以左右两个点为端点的最远的直线
    max_distance = 0
    max_points = []
    i, j = points.index(left), points.index(right)
    l, r = (i + 1) % n, (j + 1) % n
    while i != j or l != r:
        d1 = distance(points[i], points[l])
        d2 = distance(points[j], points[r])
        if d1 > max_distance:
            max_distance = d1
            max_points = [points[i], points[l]]
        if d2 > max_distance:
            max_distance = d2
            max_points = [points[j], points[r]]
        if cross_product(points[i], points[l], points[j]) < 0:
            i = (i - 1) % n
        else:
            l = (l + 1) % n
        if cross_product(points[j], points[r], points[i]) < 0:
            j = (j + 1) % n
        else:
            r = (r - 1) % n

    return max_distance, max_points

# 绘制凸包和直径
def plot(points, diameter_points):
    x = [p[0] for p in points]
    y = [p[1] for p in points]
    plt.plot(x, y, 'bo')
    for i in range(len(points)):
        plt.text(points[i][0], points[i][1], str(i))
    plt.plot([p[0] for p in diameter_points], [p[1] for p in diameter_points], 'r-')
    plt.show()

if __name__ == '__main__':
    points = [(0, 0), (1, 2), (3, 3), (2, 1), (1, 1), (2, 2)]
    d, dp = diameter(points)
    print('直径长度：', d)
    print('直径端点：', dp)
    plot(points, dp)

在这个示例中，我们定义了一个点集，计算它的凸包直径，并绘制了凸包和直径。你可以根据自己的需要修改点集，测试代码的正确性。