第 33 章计算几何 (Computational Geometry)

核心结论

叉积作为基本工具：二维叉积 \(\mathbf{p}_1 \times \mathbf{p}_2 = x_1 y_2 - x_2 y_1\) 给出有向面积，正负决定「顺/逆时针」——这是计算几何一切判定问题的基础，无需除法或三角函数。
线段相交判定：两线段 \(p_1 p_2\) 与 \(p_3 p_4\) 相交当且仅当「互相跨立」或「端点在另一线段上」；通过 4 次叉积判断 + 端点共线检查，\(O(1)\) 完成。
扫描线算法 (Line-Sweep)：从左向右移动虚拟扫描线，事件点（端点）排序 \(O(n \lg n)\)，扫描线状态用红黑树维护「相交顺序」——判断 n 条线段是否有交 \(O(n \lg n)\)。
凸包 (Convex Hull)：极角扫描的两类算法——Graham 扫描 \(O(n \lg n)\)（排序 + 栈）、Jarvis 步进 \(O(nh)\)（包装，h 为凸包顶点数）；h 小时 Jarvis 更快。
最近点对 (Closest Pair)：分治法——按 x 排序 + 递归，按 y 排序合并带状区域；总时间 \(O(n \lg n)\)。
几何问题的典型应用：凸包不仅是几何对象，还用于最远点对（必在凸包上）、碰撞检测、VLSI 设计、机器人运动规划等。

本章主旨

本章聚焦二维计算几何的四个基本算法：线段相交判定（叉积）、线段集合是否有交（扫描线）、凸包（Graham/Jarvis）、最近点对（分治）。所有算法都避免除法和三角函数，改用整数运算（叉积），保证数值稳定性。共同的设计哲学是：把几何判定化归为代数符号判定（叉积正负），再用成熟的离散算法（排序、栈、递归）求解。这是计算几何区别于纯数值几何的标志——精确、稳健、可证。

一、核心概念

本章围绕 5 个核心概念展开：先建立叉积作为基本工具，再分别解决线段相交判定、扫描线多线段相交、凸包、最近点对。

概念	定义 + 重要性	实现提示
叉积 (Cross Product)	二维叉积 \(\mathbf{p}_1 \times \mathbf{p}_2 = x_1 y_2 - x_2 y_1\) 等于有向平行四边形面积；正负给出「顺/逆时针」相对方向，0 表示共线。	§33.1；避免除法和三角函数，数值稳定；定义 DIRECTION(pi, pj, pk) 返回 \((pk - pi) \times (pj - pi)\)。
线段相交判定	两线段相交 \(\Leftrightarrow\) 互相跨立（端点叉积符号相反）或端点共线落在另一线段上。	§33.1；SEGMENTS-INTERSECT 调用 4 次 DIRECTION + ON-SEGMENT；\(O(1)\)。
扫描线 (Line-Sweep)	从左向右移动垂直线；事件点为 2n 个端点（左/右）；扫描线状态用红黑树维护「与扫描线相交的线段按 y 排序」。	§33.2；ANY-SEGMENTS-INTERSECT 总时间 \(O(n \lg n)\)（排序 + 2n 次红黑树操作）。
凸包 (Convex Hull)	包含给定点集的最小凸多边形 \(\mathrm{CH}(Q)\)；Graham 扫描用栈维护逆时针顶点，Jarvis 步进用「包装」找每一步极角最小顶点。	§33.3；Graham \(O(n \lg n)\)，Jarvis \(O(nh)\)；Theorem 33.1 证明 Graham 正确性。
最近点对 (Closest Pair)	n 个点的最近两点距离；分治——按 x 排序 + 递归两侧 + 合并带状区。	§33.4；先按 x 排序 \(O(n \lg n)\)；每层 merge \(O(n)\)；总 \(O(n \lg n)\)。

概念

定义 + 重要性

实现提示

叉积 (Cross Product)

二维叉积 \(\mathbf{p}_1 \times \mathbf{p}_2 = x_1 y_2 - x_2 y_1\) 等于有向平行四边形面积；正负给出「顺/逆时针」相对方向，0 表示共线。

§33.1；避免除法和三角函数，数值稳定；定义 DIRECTION(pi, pj, pk) 返回 \((pk - pi) \times (pj - pi)\)。

线段相交判定

两线段相交 \(\Leftrightarrow\) 互相跨立（端点叉积符号相反）或端点共线落在另一线段上。

§33.1；SEGMENTS-INTERSECT 调用 4 次 DIRECTION + ON-SEGMENT；\(O(1)\)。

扫描线 (Line-Sweep)

从左向右移动垂直线；事件点为 2n 个端点（左/右）；扫描线状态用红黑树维护「与扫描线相交的线段按 y 排序」。

§33.2；ANY-SEGMENTS-INTERSECT 总时间 \(O(n \lg n)\)（排序 + 2n 次红黑树操作）。

凸包 (Convex Hull)

包含给定点集的最小凸多边形 \(\mathrm{CH}(Q)\)；Graham 扫描用栈维护逆时针顶点，Jarvis 步进用「包装」找每一步极角最小顶点。

§33.3；Graham \(O(n \lg n)\)，Jarvis \(O(nh)\)；Theorem 33.1 证明 Graham 正确性。

最近点对 (Closest Pair)

n 个点的最近两点距离；分治——按 x 排序 + 递归两侧 + 合并带状区。

§33.4；先按 x 排序 \(O(n \lg n)\)；每层 merge \(O(n)\)；总 \(O(n \lg n)\)。

二、详细笔记

2.1 叉积与方向判定

What：二维叉积 \(\mathbf{p}_1 \times \mathbf{p}_2 = x_1 y_2 - x_2 y_1\) 表示原点、\(\mathbf{p}_1\)、\(\mathbf{p}_2\) 构成的有向平行四边形面积。

Why：叉积的符号直接给出「相对方向」——为所有几何判定（左/右转、跨立、共线）提供基础；只用加减乘，无需除法和三角函数，对浮点误差更稳健。

How：

DIRECTION(pi, pj, pk)	含义
\(> 0\)	\(pk\) 在 \(pi \to pj\) 的顺时针一侧
\(< 0\)	\(pk\) 在 \(pi \to pj\) 的逆时针一侧
\(= 0\)	三点共线

DIRECTION(pi, pj, pk)

含义

\(> 0\)

\(pk\) 在 \(pi \to pj\) 的 顺时针 一侧

\(< 0\)

\(pk\) 在 \(pi \to pj\) 的 逆时针 一侧

\(= 0\)

三点共线

判断连续折线 \(p_0 p_1 p_2\) 是否左转：DIRECTION(\(p_0\), \(p_2\), \(p_1\)) \(< 0\)。

When：所有几何判定问题——共线、转向、相交、跨立；尤其在计算几何底层作为基本运算。

Example：判断 \(p_0 = (0,0), p_1 = (1,0), p_2 = (1,1)\) 是否左转：\(\mathbf{p}_1 - \mathbf{p}_0 = (1,0), \mathbf{p}_2 - \mathbf{p}_0 = (1,1)\)；叉积 \(= 1 \cdot 1 - 0 \cdot 1 = 1 > 0\)，故 DIRECTION = 正 → \(p_2\) 在 clockwise 一侧 → 折线是「右转」。

2.2 线段相交判定 (SEGMENTS-INTERSECT)

What：判定两条线段 \(p_1 p_2\) 与 \(p_3 p_4\) 是否相交；两线段相交当且仅当「互相跨立」或「端点在另一线段上」。

Why：跨立条件等价于「线段 1 的两端在线段 2 所在直线的两侧」——这是几何相交判定的核心抽象，避免了除法和浮点误差。

How：

条件	叉积表述
跨立一	DIRECTION(\(p_3\), \(p_4\), \(p_1\)) 与 DIRECTION(\(p_3\), \(p_4\), \(p_2\)) 符号相反
跨立二	DIRECTION(\(p_1\), \(p_2\), \(p_3\)) 与 DIRECTION(\(p_1\), \(p_2\), \(p_4\)) 符号相反
端点共线	若 \(d_k = 0\) 且该端点位于另一线段上（ON-SEGMENT 用坐标范围判定）

条件

叉积表述

跨立一

DIRECTION(\(p_3\), \(p_4\), \(p_1\)) 与 DIRECTION(\(p_3\), \(p_4\), \(p_2\)) 符号相反

跨立二

DIRECTION(\(p_1\), \(p_2\), \(p_3\)) 与 DIRECTION(\(p_1\), \(p_2\), \(p_4\)) 符号相反

端点共线

若 \(d_k = 0\) 且该端点位于另一线段上（ON-SEGMENT 用坐标范围判定）

ON-SEGMENT(pi, pj, pk)：要求 \(\min(x_i, x_j) \leq x_k \leq \max(x_i, x_j)\) 且 \(y\) 同理（已假设共线）。

When：所有需要线段相交的算法——扫描线、凸包、几何查询、CAD 系统。

Example：\(p_1=(0,0), p_2=(2,2), p_3=(2,0), p_4=(0,2)\)：两条对角线相交。DIRECTION 各值依次：late 译 (3,4)→1 正、(3,4)→2 负、(1,2)→3 正、(1,2)→4 负，符号交错 → 跨立成立 → 返回 TRUE。

2.3 扫描线算法 (ANY-SEGMENTS-INTERSECT)

What：判断 n 条线段集合中是否有任意两条相交；按 x 排序所有 2n 个端点作为事件点，扫描线状态维护「与扫描线相交的线段按 y 排序」。

Why：朴素枚举所有线段对是 \(O(n^2)\)；扫描线把「几何相交」化归为「状态相邻事件」——两线段在相交点附近必然在某条扫描线上相邻，只需检查相邻对。

How：

步骤	操作	复杂度
排序	事件点按 \((x, type, y)\) 排序（左端点先于右端点）	\(O(n \lg n)\)
处理左端点	INSERT 到扫描线状态；检查 ABOVE/BELOW 是否与新线段相交	红黑树操作 \(O(\lg n)\)
处理右端点	检查 ABOVE 与 BELOW 是否相交；然后 DELETE 当前线段	同上
返回	若任意检查返回 TRUE 则停止	总 \(O(n \lg n)\)

步骤

操作

复杂度

排序

事件点按 \((x, type, y)\) 排序（左端点先于右端点）

\(O(n \lg n)\)

处理左端点

INSERT 到扫描线状态；检查 ABOVE/BELOW 是否与新线段相交

红黑树操作 \(O(\lg n)\)

处理右端点

检查 ABOVE 与 BELOW 是否相交；然后 DELETE 当前线段

同上

若任意检查返回 TRUE 则停止

总 \(O(n \lg n)\)

正确性：设 \(p\) 是所有交点中最左（x 最小，y 平局最小），则交于此点的两条线段 \(a, b\) 在某条扫描线 \(\ell\) 上必然相邻；当扫描线到达端点事件时检测到这对相邻线段相交。

When：需要判断「是否存在交点」（不是枚举所有交点）；VLSI 布线检查、地图叠加分析、机器人路径冲突检测。

Example：4 条线段 \(\{a, b, c, d\}\) 形成一个交叉路口：扫描线从左向右依次处理各端点；当处理 d 的左端点时，状态中已有 b 与 d 相邻且相交，函数返回 TRUE。

2.4 凸包 — Graham 扫描

What：用栈结构维护当前凸包候选点；按极角排序后依次压栈，遇非左转则弹出栈顶，直到只剩凸包顶点（逆时针）。

Why：凸包是很多几何问题的预处理（最远点对必在凸包上）；Graham 扫描是凸包算法中最易于实现且稳定的，时间复杂 \(O(n \lg n)\)。

How：

步骤	操作
1	选 \(p_0\) 为 y 坐标最低的点（左平局最左）—— 必在凸包上
2	剩余点按极角（用叉积比较）逆时针排序；同角度只保留最远
3	初始化栈 \(S = (p_0, p_1, p_2)\)
4	for \(i = 3\) to \(m\): while TOP(NEXT-TO-TOP, TOP, \(p_i\)) 非左转: POP
5	PUSH \(p_i\)；返回 S

时间复杂度： * 极角排序：\(O(n \lg n)\) * while 循环：aggregate analysis — 每点最多 PUSH 1 次、POP 1 次，故总体 \(O(n)\) * 总：\(O(n \lg n)\)

正确性（Theorem 33.1）：循环不变式是「栈 S 自底向上恰好是 \(\mathrm{CH}(\{p_0, \ldots, p_{i-1}\})\) 的逆时针顶点」；初始化平凡成立；维护性通过分析非左转弹出点的几何意义证伪（Figure 33.8）。

When：所有需要凸包且 n 较大、h 不小的场景；h 极小时可改用 Jarvis 步进。

Example：12 个点的 Figure 33.6，Graham 扫描产生 6 个顶点（部分中间点被弹出）；运行过程 Figure 33.7(b)-(k) 显示每步栈状态。

2.5 凸包 — Jarvis 步进 / 最近点对

What：本节讨论两个与凸包/几何相关的问题——Jarvis 包装法与最近点对分治。

Jarvis 步进：从最低点开始，每一步选「使当前方向与剩余点夹角最小」的点——像用橡皮筋包装点集，时间 \(O(nh)\)。
最近点对：分治——按 x 排序 + 递归求左右两半最近距离 δ + 合并中间带状区内的最近对。

Why：两种算法各有适用场景。

Jarvis 在凸包顶点数 h 小时（\(h = o(\lg n)\)）比 Graham 更优。
最近点对经典分治展示「按 y 排序的合并 + 每点检查常数个邻居」的技巧。

How — Jarvis：

步骤	操作
1	从 \(p_0\)（最低点）开始，初始候选 = 任意点
2	对每个候选点，扫描所有点找极角最小（叉积最大）者
3	回到 \(p_0\) 时停止

每步扫描所有点 \(O(n)\)，共 \(h\) 步 → \(O(nh)\)。

How — 最近点对：

步骤	操作
1	按 x 排序递归两侧 → 左右最小距离 \(\delta_L, \delta_R\)，取 \(\delta = \min(\delta_L, \delta_R)\)
2	合并：取中线两侧各 δ 宽带，按 y 排序后每个点最多检查 7 个后续点
3	总时间 \(T(n) = 2T(n/2) + O(n)\) → \(O(n \lg n)\)

When：Jarvis 用于 h 小的稀疏凸包；最近点对用于碰撞检测、聚类、VLSI 设计规则检查。

Example：图 33.9 Jarvis 包装法产生右链与左链；最近点对的 7 点检查定理保证合并阶段每点只与常数个邻居比较。

三、关键图表

核心公式对照表

公式编号

内容

叉积

\(\mathbf{p}_1 \times \mathbf{p}_2 = x_1 y_2 - x_2 y_1 = -(\mathbf{p}_2 \times \mathbf{p}_1)\)

跨立条件

两线段相交 \(\Leftrightarrow\) (\(d_1 d_2 < 0\)) \(\wedge\) (\(d_3 d_4 < 0\))，或端点共线落在另一线段上

Graham 弹出条件

折线 NON-LEFT-TURN（叉积 \(\geq 0\)）时弹栈

扫描线主循环

排序 2n 事件点 → 每事件一次红黑树操作 → 总 \(O(n \lg n)\)

四、思维导图

mindmap
  root((第 33 章 计算几何))
    叉积基础
      有向面积
      顺逆时针
      共线判定
    线段相交
      跨立条件
      端点共线
      O(1)判定
    扫描线
      事件点排序
      红黑树状态
      O(nlgn)检测
    凸包
      Graham扫描
      Jarvis步进
      O(nlgn)与O(nh)
    最近点对
      分治策略
      合并带状区
      O(nlgn)

五、重点与易错点

叉积 \(x_1 y_2 - x_2 y_1\) 是核心运算——所有几何判定（左/右、共线、相交、凸包方向）都依赖它；熟记它比记任何具体算法更重要。
「顺/逆时针」的符号约定：原书中叉积 > 0 时 \(\mathbf{p}_1\) 在 \(\mathbf{p}_2\) 顺时针 一侧；与「平面几何」的逆时针为正相反——务必确认。
浮点误差陷阱：避免用「斜率比较」或「角度比较」——除法与三角函数对浮点误差敏感；叉积只用加减乘，稳健得多。
SEGMENTS-INTERSECT 必须同时检查「跨立」与「端点共线」两种情况；漏掉共线会导致端点恰好在另一线段上时返回 FALSE（Figure 33.3c vs 33.3d）。
ON-SEGMENT 必须同时检查 x 与 y 坐标范围；仅检查 x 是不够的（如退化线段共线于水平线时仍可能在 y 范围外）。
Graham 扫描的 while 条件是「非左转」（叉积 ≥ 0），不仅是「右转」（叉积 > 0）——排除共线点留在凸包上（避免三顶点共线）。
Jarvis 步进的复杂度是 \(O(nh)\)，h 可能为 n（所有点都在凸包上）此时为 \(O(n^2)\)；比 Graham 的 \(O(n \lg n)\) 差。
扫描线算法假设：没有垂直线段、没有三线共点；习题 33.2-8/9 给出去除这两个假设的方法。
凸包顶点数 h 与 n 是不同概念——h 可能远小于 n（点在凸包内）；最远点对必在凸包上是练习 33.3-3 的关键观察。
最近点对合并时每点检查「后续 7 个」点是经典结论——证明依赖几何：δ × 2δ 矩形最多容纳 8 个点（左下角 + 7 邻居），故每点只需与 7 个后续比较。
计算几何算法通常假设输入是「一般位置」（no three collinear, no two coincident）——实际工程中需显式处理退化情况。
扫描线状态中两线段在交点两侧顺序会反转（Figure 33.4b）——这是「先看到相交」的依据。

第 33 章 计算几何 (Computational Geometry)

核心结论

一、核心概念

二、详细笔记

2.1 叉积与方向判定

2.2 线段相交判定 (SEGMENTS-INTERSECT)

2.3 扫描线算法 (ANY-SEGMENTS-INTERSECT)

2.4 凸包 — Graham 扫描

2.5 凸包 — Jarvis 步进 / 最近点对

三、关键图表

四、思维导图

五、重点与易错点

第 33 章计算几何 (Computational Geometry)