【算法】Graham 凸包扫描算法 ( 凸包概念 | 常用的凸包算法 | 角排序 | 叉积 | Python 代码示例 )

import tkinter as tk    # 导入 Tkinter 模块
import random           # 导入 random 模块用于生成随机数
import math             # 导入 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)

# 通过计算叉乘计算 3 点方向
#   如果叉乘结果 = 0 , 则说明 p1/p2/p3 共线
#   如果叉乘结果 > 0 , 则为顺时针方向
#   如果叉乘结果 < 0 , 则为逆时针方向
def cross_product(p1, p2, p3):
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x)

# 求点集的极角
def polar_angle(p0, p):
    return math.atan2(p.y - p0.y, p.x - p0.x)

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

# 角排序函数
def angle_sort(points):
    # 点集个数必须大于 3 个
    if len(points) < 2:
        return points

    # 找到最左下方的点作为起始点
    # p0 点作为极坐标的原点
    p0 = min(points, key=lambda p: (p.y, p.x))
    # 按照极角和距离的平方排序
    # 先按照极角进行排序 如果极角相同 则按照 p0 点到该点的距离排序
    sorted_points = sorted(points, key=lambda p: (polar_angle(p0, p), distance_squared(p0, p)))
    # 返回按照极角进行排序的 Point 集合
    return [p0] + sorted_points[1:]

# Graham 扫描法找凸包
def graham_scan(points):
    if len(points) < 3:
        return points

    # 进行角排序
    sorted_points = angle_sort(points)
    # 栈数据结构
    stack = []
    for p in sorted_points:
        # 如果栈中的元素大于 2 个开始执行循环, 计算 p 点 在 栈顶两个元素(倒数第二个在前,倒数第一个再后)组成的向量的左侧还是右侧
        while len(stack) >= 2 and cross_product(stack[-2], stack[-1], p) <= 0:
            # 如果 p 点在栈顶两个元素组成的向量的左侧 则说明该点是凸边中的点 , 栈顶元素不是凸边中的点 , 将栈顶出栈 , 将本元素入栈
            stack.pop()
        # 向栈中添加新元素
        stack.append(p)
    return stack

# 生成随机点集
# 界面为 800x600 , x 方向上在 50 ~ 750 之间生成点, y 方向上在 50 ~ 550 之间生成点
def generate_points(num_points):
    points = []
    for _ in range(num_points):
        x = random.randint(50, 750)  # 生成 x 坐标范围在 50 到 750 之间的随机数
        y = random.randint(50, 550)  # 生成 y 坐标范围在 50 到 550 之间的随机数
        points.append(Point(x, y))
    return points

# 在画布上绘制点
def draw_points(canvas, points):
    for point in points:
        canvas.create_oval(point.x - 2, point.y - 2, point.x + 2, point.y + 2, fill="blue")  # 绘制圆点

# 在画布上绘制凸包
def draw_convex_hull(canvas, convex_hull):
    for i in range(len(convex_hull)):
        p1 = convex_hull[i]
        p2 = convex_hull[(i + 1) % len(convex_hull)]
        canvas.create_line(p1.x, p1.y, p2.x, p2.y, fill="red")  # 绘制凸包的边

# 主函数
def main():
    num_points = 100                       # 点的数量设置为 200 个
    points = generate_points(num_points)    # 生成随机点集
    convex_hull = graham_scan(points)  # 使用 Graham 扫描法找凸包

    root = tk.Tk()  # 创建 Tkinter 窗口
    root.title("Graham Scan Convex Hull")  # 设置窗口标题
    canvas = tk.Canvas(root, width=800, height=600, bg="white")  # 创建画布
    canvas.pack()  # 将画布放置在窗口中央

    draw_points(canvas, points)  # 绘制点集
    draw_convex_hull(canvas, convex_hull)  # 绘制凸包

    root.mainloop()  # 进入 Tkinter 主循环

if __name__ == "__main__":
    main()  # 调用主函数