半平面交算法详解（Python实现计算几何中的凸多边形求交）

半平面交的目标

给定 N 个半平面，我们希望找到它们的交集区域。如果交集非空且有界，结果将是一个凸多边形。这就是为什么半平面交算法常用于求解多个约束条件下的可行区域。

算法思路（增量法）

最直观的方法是增量构造法：从第一个半平面开始，依次与当前交集区域求交，逐步缩小可行区域。

具体步骤如下：

1. 初始化交集为一个足够大的“包围盒”（如一个大正方形）。
2. 对每个半平面，用其边界直线去切割当前的多边形。
3. 保留位于半平面内部的顶点，并计算新产生的交点。
4. 更新多边形顶点列表。
5. 重复直到所有半平面处理完毕。

Python 实现

下面是一个完整的 Python 实现，包含向量运算、线段与直线求交、以及核心的裁剪函数。

import mathclass Point:    def __init__(self, x, y):        self.x = x        self.y = y        def __sub__(self, other):        return Point(self.x - other.x, self.y - other.y)        def __add__(self, other):        return Point(self.x + other.x, self.y + other.y)        def __mul__(self, scalar):        return Point(self.x * scalar, self.y * scalar)def cross(o, a, b):    """计算向量 OA × OB 的叉积"""    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)def line_intersection(p1, p2, q1, q2):    """求直线 p1p2 与 q1q2 的交点"""    A1 = p2.y - p1.y    B1 = p1.x - p2.x    C1 = A1 * p1.x + B1 * p1.y    A2 = q2.y - q1.y    B2 = q1.x - q2.x    C2 = A2 * q1.x + B2 * q1.y    det = A1 * B2 - A2 * B1    if abs(det) < 1e-10:        return None  # 平行或重合        x = (B2 * C1 - B1 * C2) / det    y = (A1 * C2 - A2 * C1) / det    return Point(x, y)def inside_halfplane(p, a, b):    """判断点 p 是否在有向直线 ab 的左侧（含边界）"""    return cross(a, b, p) >= -1e-10def clip_polygon(poly, a, b):    """用有向直线 ab 裁剪多边形 poly（保留左侧）"""    if not poly:        return []        new_poly = []    n = len(poly)        for i in range(n):        current = poly[i]        prev = poly[(i - 1) % n]                curr_in = inside_halfplane(current, a, b)        prev_in = inside_halfplane(prev, a, b)                if curr_in:            if not prev_in:                # 进入：添加交点                inter = line_intersection(prev, current, a, b)                if inter:                    new_poly.append(inter)            new_poly.append(current)        elif prev_in:            # 离开：添加交点            inter = line_intersection(prev, current, a, b)            if inter:                new_poly.append(inter)        return new_polydef halfplane_intersection(halfplanes):    """    半平面交主函数    halfplanes: 列表，每个元素为 (Point a, Point b)，表示有向直线 ab 的左侧为半平面    返回交集多边形的顶点列表（逆时针顺序）    """    # 初始化为一个大正方形（假设坐标范围在 [-1e5, 1e5] 内）    INF = 1e5    poly = [        Point(-INF, -INF),        Point(INF, -INF),        Point(INF, INF),        Point(-INF, INF)    ]        for a, b in halfplanes:        poly = clip_polygon(poly, a, b)        if not poly:            break  # 交集为空        return poly# 示例：求三个半平面的交集if __name__ == "__main__":    # 定义三个半平面（用有向线段表示）    hps = [        (Point(0, 0), Point(1, 0)),   # y >= 0        (Point(0, 0), Point(0, 1)),   # x >= 0        (Point(2, 0), Point(0, 2))    # x + y <= 2    ]        result = halfplane_intersection(hps)    print("交集多边形顶点：")    for p in result:        print(f"({p.x:.2f}, {p.y:.2f})")

代码说明

• Point 类用于表示二维点，并支持基本运算。
• cross 函数计算叉积，用于判断点在直线的哪一侧。
• line_intersection 计算两条直线的交点。
• clip_polygon 是 Sutherland-Hodgman 裁剪算法的核心，用于用一条直线裁剪多边形。
• halfplane_intersection 主函数，依次应用每个半平面进行裁剪。

应用场景

- 机器人路径规划中的可行区域计算
- 计算多个不等式约束下的解空间
- 计算 Voronoi 图的边界
- 游戏开发中的视野裁剪

总结

通过本教程，你已经掌握了使用 Python 实现半平面交算法 的完整流程。该算法虽然涉及一些几何知识，但通过增量裁剪的思想，可以清晰地构建出交集区域。记住，关键在于理解“保留半平面内侧”的裁剪逻辑。

希望这篇关于凸多边形求交和计算几何的教程对你有所帮助！动手试试修改示例中的半平面，观察输出结果的变化吧。