查找最大间隔数与python重叠的点的最有效方法

import math

# 定义点类
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

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

# 判断三个点的方向关系
def orientation(p, q, r):
    val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)
    if val == 0:
        return 0  # 三点共线
    elif val > 0:
        return 1  # 逆时针方向
    else:
        return 2  # 顺时针方向

# 寻找最左下角的点
def find_leftmost_lowest(points):
    min_index = 0
    n = len(points)
    for i in range(1, n):
        if points[i].y < points[min_index].y or (points[i].y == points[min_index].y and points[i].x < points[min_index].x):
            min_index = i
    return min_index

# 按极角排序
def compare(p1, p2):
    o = orientation(p0, p1, p2)
    if o == 0:
        if distance(p0, p2) >= distance(p0, p1):
            return -1
        else:
            return 1
    elif o == 2:
        return -1
    else:
        return 1

# 计算凸包
def convex_hull(points):
    n = len(points)
    if n < 3:
        return []

    # 寻找最左下角的点，并将其放在列表的第一个位置
    min_index = find_leftmost_lowest(points)
    points[0], points[min_index] = points[min_index], points[0]

    global p0
    p0 = points[0]

    # 按极角排序（逆时针方向）
    points = sorted(points, key=lambda point: compare(point, p0))

    # 构建凸包
    stack = [points[0], points[1], points[2]]
    for i in range(3, n):
        while len(stack) > 1 and orientation(stack[-2], stack[-1], points[i]) != 1:
            stack.pop()
        stack.append(points[i])

    return stack

# 查找最大间隔数与Python重叠的点的最有效方法
def find_max_overlap(points):
    # 计算凸包
    convex_points = convex_hull(points)

    # 计算凸包上相邻两点之间的间隔数，并找到最大的间隔数
    max_overlap = 0
    n = len(convex_points)
    for i in range(n):
        overlap = distance(convex_points[i], convex_points[(i + 1) % n])
        if overlap > max_overlap:
            max_overlap = overlap

    return max_overlap

# 测试
points = [Point(1, 1), Point(2, 3), Point(4, 2), Point(3, 5), Point(5, 4), Point(6, 6)]
max_overlap = find_max_overlap(points)
print("最大间隔数与Python重叠的点的最有效方法为:", max_overlap)