半平面交与多边形核判定

可视化演示

半平面交计算多个半平面的公共区域，可用于多边形核判定与可视化裁剪。本文详解有向直线的半平面表示、极角排序增量法... 切换模式查看不同维度。

半平面概念

想象展厅里的第一面墙：它是一堵无限延伸的直墙，探照灯站在墙的某一侧，灯光只能照亮这堵墙的其中一半世界。这一半，在数学里就叫“半平面”。我们不需要真的把墙画出来，只需要给它一个方向——一条有向直线，箭头指向被照亮的那一侧，就能完整描述“允许站立的位置”。这就是半平面表示的核心：用一条直线的方向，定义“哪一边是亮的”。

具体来说，一条直线可以写成 \( ax + by + c = 0 \)。向量 \((a, b)\) 就是这条直线的法向量，它垂直指向墙的一侧。我们约定：法向量指向的那一侧就是“照亮的一侧”，也就是半平面。因此一个半平面可以写成关于 \( x, y \) 的一个不等式：

\[

H = \{(x, y) \mid ax + by + c \ge 0\}

\]

这里的 “\(\ge 0\)“ 表示包含边界本身——就像你站在墙根的线上也算在展厅内。如果换成 ”\(>0\)“，那就是不包含边界的”开半平面”。多数算法默认使用闭半平面，因为边界交点的计算更整齐。

1. 直线方程：\( ax + by + c = 0 \) 是一条无限长直线，所有满足等式的点 \((x,y)\) 都落在墙上。

$$ax + by + c = 0$$

2. 法向量方向：\((a,b)\) 是直线的法向量，它垂直指向被照亮的一侧，所以它决定了“哪边是亮的”。

$$\vec{n} = (a,b) \quad \text{垂直于直线}$$

3. 不等式范围：把等式改为 \(\ge 0\)，意味着我们把墙的一侧连同墙本身一起包含进来，形成一个闭半平面。

$$H = \{(x,y) \mid ax + by + c \ge 0\}$$

回到展厅：每面墙都不再是“一堵实物”，而是一道有方向的光束指令。当你把所有墙的“照亮侧”叠加在一起时，公共亮区就在这些指令中浮现——这就是半平面交的起点。理解到这里，你已经掌握了第一个工具：用不等式描述几何区域。

多边形核定义

现在展厅不再是空旷的矩形，而是一个不规则的多边形房间，比如一个五角形展厅。你想找一个位置，从这个位置看向任意一面墙时，视线都不会被另一面墙挡住——换句话说，这个位置能“同时看到所有墙”。所有满足这个条件的位置组成的区域，就叫多边形的核。

核的数学定义非常优雅：把多边形的每条边都看成一面有方向的墙，法向量指向多边形内部，那么核就是所有这些半平面的交集。如果这个交集不是空的，我们就说这个多边形是星形的——像一颗星星，从核里任意一点都能“看到”整个多边形的轮廓。

\[

K(P) = \bigcap_{i=0}^{n-1} H_i

\]

其中 \(H_i\) 是第 \(i\) 条边对应的内部半平面。

1. 每条边的半平面：将多边形的每条边视为有向直线，左侧（内法向量侧）形成半平面 \(H_i\)。

$$H_i = \{(x,y) \mid a_i x + b_i y + c_i \ge 0\}$$

2. 交集运算：把 \(n\) 个半平面做交集，交集里的点必须同时满足所有不等式。

$$K(P) = H_0 \cap H_1 \cap \cdots \cap H_{n-1} = \bigcap_{i=0}^{n-1} H_i$$

3. 星形判定：若 \(K(P) \neq \varnothing\)，则多边形为星形，核中任意点都满足全局可见性。

$$K(P) \neq \varnothing \iff P \text{ 是星形多边形}$$

用射灯的语言来说：核就是那个“万能观赏位”。你不需要移动到房间的每个角落去试验，只需要求解这个交集——一次几何计算，就回答了“是否存在这样的位置”。这也解释了为什么核判定在游戏关卡设计、监控摄像头布点中如此重要：它直接告诉你，一个区域是否有一个“全览视角”。

极角排序增量法

终于到了核心算法：怎么高效地求出这些半平面的交集？如果盲目地把半平面两两求交，复杂度会爆炸。聪明的做法是像整理书架一样，先把所有墙按“朝向”排好队，再一面一面地“砌”进去。这个方法叫“极角排序增量法”。

第一步，把每个半平面的法向量 \((a,b)\) 按角度排序。法向量的角度就是探照灯的光轴方向，我们用 \(\text{atan2}(b, a)\) 来计算。排序之后，所有墙按方向绕了一圈，就像时针扫过表盘。第二步，维护一个双端队列（deque），队列里保存的是“当前仍然有效的边界半平面”以及它们两两之间的交点。每加入一面新墙，我们检查队列头部和尾部的交点是否还落在新墙的照亮侧——如果不在，说明这个交点已经被新墙淘汰，就把它从队列里弹出。最后，队列里剩下的就是所有半平面的交集边界。

\[

\theta_i = \text{atan2}(b_i, a_i) \quad \text{排序后：} \theta_0 \le \theta_1 \le \cdots \le \theta_{n-1}

\]

新半平面加入时，若队尾交点 \(q\) 满足 \(a_k q_x + b_k q_y + c_k < 0\)，则弹出队尾。

1. 极角计算：每个半平面的法向量都有一个极角，用 \(\text{atan2}\) 计算，它的值域是 \((-π, π]\)。

$$\theta_i = \text{atan2}(b_i, a_i)$$

2. 排序保证：排序后墙面按角度依次排列，增量插入时保证处理的顺序是“绕一圈”的完整性。

$$\theta_0 \le \theta_1 \le \cdots \le \theta_{n-1}$$

3. 淘汰条件：新墙加入时，若队列末尾的交点已经落入新墙的“暗侧”（不等式小于零），说明这个交点不再属于公共区域。

$$a_k q_x + b_k q_y + c_k < 0 \Rightarrow \text{弹出队尾}$$

这个算法的妙处在于：每面墙只需要入队一次、出队一次，总共 O(n) 次操作。排序是唯一的“大开销”，这让整个算法达到 O(n log n)。队列就像一条传送带，墙体按角度有序流过，不符合条件的交点自动掉落，留下的就是核的轮廓。

复杂度分析

我们常说半平面交是 O(n log n) 的算法，这个复杂度从何而来？把它拆开看，只有两步：排序和扫描。

排序阶段，我们把 n 个半平面按法向量极角排序，最好的通用比较排序是 O(n log n)。这也是整个算法的瓶颈，因为后面的扫描过程是线性的。扫描阶段，我们用一个双端队列依次处理排好序的半平面：每个半平面最多被加入队列一次，也最多被弹出一次，所以均摊下来每个元素的操作是常数时间的，总共 O(n)。两部分相加，整体复杂度就是 O(n log n)。空间上，我们只需要存储排序后的数组和双端队列，都是 O(n)。

\[

T(n) = O(n \log n) + O(n) = O(n \log n), \quad S(n) = O(n)

\]

1. 排序开销：对 n 个半平面按极角排序，比较排序的下界是 n log n。

$$O(n \log n)$$

2. 线性扫描：双端队列中每个半平面最多入队、出队一次，均摊 O(1)，总耗时 O(n)。

$$O(n)$$

3. 合并结论：总复杂度取最大的量级，因此 \(O(n \log n)\) 主导了算法。

$$T(n) = O(n \log n)$$

如果你面对的是十万条边的复杂多边形，排序的 n log n 和暴力两两求交的 n² 之间，差距是巨大的——前者在眨眼间完成，后者可能要跑到地老天荒。这就是算法设计的价值：把看似不可能的任务，压缩到可接受的时间窗口内。

关键实现细节

理论讲得再漂亮，落地写代码时总有细节绊脚。半平面交实现中有三个关键细节：求交点、判左右、处理退化。

首先是求交点。两个半平面的边界直线 \(L_1, L_2\) 相交，我们需要精确算出入射点。最稳健的方法是用参数化直线和叉积。设直线 \(L_1\) 过点 \(P_0\)、方向向量 \(d_1\)，直线 \(L_2\) 过点 \(Q_0\)、方向向量 \(d_2\)，则交点参数可由两个叉积的比值给出：

\[

t = \frac{\text{cross}(P_0 - Q_0, d_2)}{\text{cross}(d_2, d_1)}

\]

其中 \(\text{cross}(u, v) = u_x v_y - u_y v_x\)。第二个细节是“点在直线的哪一侧”：用叉积 \(s = \text{cross}(d, p - P_0)\)，正数表示点在左（内部），负数表示在右（外部）。第三个细节是退化的处理：当两条直线的方向向量平行时，叉积分母接近零，这时需要特殊处理——比如直接跳过相同的半平面，或者用不等式判断谁更严格。

1. 参数化：把每条直线写成“起点 + 方向 × 参数”的形式，交点就是两条参数直线相等的点。

$$L_1(t) = P_0 + t \cdot d_1, \quad L_2(u) = Q_0 + u \cdot d_2$$

2. 叉积求参：利用二维叉积的性质，交点参数 \(t\) 等于两个叉积的比值，分母不为零时有效。

$$t = \frac{\text{cross}(P_0 - Q_0, d_2)}{\text{cross}(d_2, d_1)}$$

3. 侧向判定：计算 \(s = \text{cross}(d_1, p - P_0)\)，\(s > 0\) 表示点在直线左侧（内部），\(s < 0\) 在右侧。

$$s = \text{cross}(d_1, p - P_0)$$

这些细节决定了算法的鲁棒性。如果忽略平行退化，程序会在除零时崩溃；如果忽略浮点误差，边界判断会抖动。好的实现就像一位细心的工匠，既懂原理，也懂得在微小的误差面前保持清醒。

工程应用场景

理论总归要落地。半平面交在实际工程中有一大批应用场景，这里举三个典型的。

第一个是可视化裁剪。在游戏引擎或地理信息系统中，摄像机有一个视锥体，场景里的物体只有在视锥体内才需要被渲染。视锥体在二维平面上可以被表示为若干个半平面的交集——一个矩形视口就是四个半平面。用半平面交判断一个多边形是否与视锥相交，可以快速剔除视野外的物体，节省大量渲染计算。第二个是核判定应用。在建筑设计中，判断一个房间是否“无死角”（任意位置都能看到安全出口），本质就是计算多边形的核是否覆盖出口位置。第三个是导航安全区域。机器人或自动驾驶车辆在规划路径时，需要计算可行走区域，这个区域常常被描述为多个障碍物的半平面约束的交集。

\[

p \text{ 可见} \iff \forall i,\; n_i \cdot p + c_i \ge 0

\]

其中 \(n_i, c_i\) 是第 \(i\) 个裁剪半平面的法向量和常数项。

1. 可见性判定：一个点 \(p\) 可见，当且仅当它满足所有裁剪半平面的不等式。

$$\forall i,\; n_i \cdot p + c_i \ge 0$$

2. 视锥建模：视锥体的每个侧面都对应一个半平面，六个面构成六半平面交集。

$$V = \bigcap_{i=1}^{6} H_i$$

3. 快速剔除：若物体包围盒与 \(V\) 无交集，则跳过该物体的渲染。

$$\text{BBox} \cap V = \varnothing \Rightarrow \text{cull}$$

回到射灯的比喻：视锥裁剪就是剧场里只亮一盏追光灯，灯光外的区域自动“隐身”。半平面交让这种隐身判断变得既科学又高效——每条光束都是一条不等式，而“是否被照亮”就是一次代入计算。

常见陷阱处理

写半平面交代码时，最让人头疼的不是主流程，而是一堆“刁钻”的边界情况。这里把最常见的陷阱集中处理。

第一个陷阱是平行退化。当两条直线的方向向量平行时，叉积分母为零，交点公式失效。此时需要判断这两条平行线是否冗余：如果它们方向相同，保留更严格的那个（即约束更强的半平面）；如果方向相反，则交集必为空，可以提前退出。第二个陷阱是重复半平面。输入中可能存在完全相同的半平面，如果不先去重，排序后相邻的重复项会导致队列中产生长度为 0 的边，破坏交点计算。第三个陷阱是浮点误差。几何计算中，叉积的结果可能非常接近零但并不精确等于零，因此判断“是否平行”和“点在不在边界上”时，需要使用一个极小阈值 \(\varepsilon\) 来容忍误差。

\[

|\text{cross}(d_1, d_2)| < \varepsilon \Rightarrow \text{判定为平行}

\]

\[

s = \text{cross}(d_1, p - P_0), \quad |s| \le \varepsilon \Rightarrow p \text{ 在边界上}

\]

1. 平行判定：当叉积绝对值小于阈值 \(\varepsilon\) 时，认为两条直线平行。

$$|\text{cross}(d_1, d_2)| < \varepsilon$$

2. 边界容忍：点在直线上的判定也采用阈值，避免浮点噪声导致误判。

$$|s| \le \varepsilon$$

3. 去重与剪枝：排序前去重相同的半平面；发现反向平行时直接判定交集为空，提前终止。

$$\text{重复项} \to \text{去重}, \quad \text{反向平行} \to \text{返回空集}$$

这些细节才是工程实现与玩具代码的分水岭。正如探照灯也需要校准焦距，几何算法同样需要一套“误差处理机制”，才能在真实世界的噪声中稳定工作。

AI 应用场景

Python 演示

import math class Point:    def __init__(self, x, y):        self.x = x        self.y = y     def __sub__(self, o):        return Point(self.x - o.x, self.y - o.y) class Line:    # 半平面: 点 p 满足 cross(dir, p - p0) >= 0 的一侧    def __init__(self, p0, p1):        self.p0 = p0        self.dir = p1 - p0  # 方向向量        self.ang = math.atan2(self.dir.y, self.dir.x)     def side(self, p):        return cross(self.dir, p - self.p0) def cross(u, v):    return u.x * v.y - u.y * v.x def intersect(l1, l2):    # 两直线交点 (l1 参数 t, l2 参数 u)    d1, d2 = l1.dir, l2.dir    denom = cross(d2, d1)    t = cross(l1.p0 - l2.p0, d2) / denom    return Point(l1.p0.x + t * d1.x, l1.p0.y + t * d1.y) def half_plane_intersection(lines):    # 1. 极角排序 + 去除平行冗余    lines.sort(key=lambda l: l.ang)    unique = []    for l in lines:        if not unique or abs(l.ang - unique[-1].ang) > 1e-9:            unique.append(l)        else:            # 同向平行: 保留更严格(起点在对方内部)的那条            if unique[-1].side(l.p0) < -1e-9:                unique[-1] = l     # 2. 双端队列维护    dq = []    for l in unique:        while len(dq) >= 2 and dq[-1][0].side(dq[-1][1]) < -1e-9:            dq.pop()        while len(dq) >= 2 and dq[0][0].side(dq[0][1]) < -1e-9:            dq.pop(0)        if dq:            dq.append((l, intersect(dq[-1][0], l)))        else:            dq.append((l, None))     # 3. 收尾: 首尾相交验证    n = len(dq)    if n >= 3:        head = dq[0][0]        if head.side(dq[-1][1]) < -1e-9:            return []        dq.append((head, intersect(dq[-1][0], head)))        dq = dq[:-1]  # 去掉多出的边界     return [pt for (_, pt) in dq if pt is not None] if __name__ == "__main__":    # 正五边形作为输入的"墙"    N = 5    poly = []    for i in range(N):        ang = -math.pi/2 + i * 2 * math.pi / N        poly.append(Point(10 * math.cos(ang), 10 * math.sin(ang)))     # 每条边 -> 内法向量侧的半平面    lines = []    for i in range(N):        p0 = poly[i]        p1 = poly[(i + 1) % N]        # 保证内部在左侧: 逆时针顶点顺序        lines.append(Line(p0, p1))     core_pts = half_plane_intersection(lines)    if core_pts:        print("多边形核的顶点坐标:")        for pt in core_pts:            print("  ({:.4f}, {:.4f})".format(pt.x, pt.y))        print("核存在，顶点数 =", len(core_pts))    else:        print("核为空: 该多边形不是星形多边形")

1. lines.sort(key=lambda l: l.ang)对所有半平面按法向量极角排序，这是 O(n log n) 复杂度的来源。
2. if abs(l.ang - unique[-1].ang) > 1e-9用阈值去重平行且角度相同的半平面。
3. if unique[-1].side(l.p0) < -1e-9同向平行时比较起点，保留约束更严格的半平面。
4. while ... dq[-1][0].side(dq[-1][1]) < -1e-9新墙加入后，不断从队尾弹出被淘汰的交点。
5. while ... dq[0][0].side(dq[0][1]) < -1e-9循环结束时，还要检查队首交点的合法性。
6. intersect(l1, l2)利用叉积求两直线交点，分母为叉积，正是正文中的参数化公式。

常见误区

面试题