研究生课程 · 计算几何
计算几何
让计算机"看见"形状：一切从叉积出发——它一举回答"在左边还是右边""相交还是分开""顺时针还是逆时针"。计算机图形学、游戏碰撞、GPS 地图、机器人路径，底层全是这一章的算法。
1 向量叉积与定向
概念cross(P1, P2, P3)
叉积：P1P2 × P1P3 = (x₂−x₁)(y₃−y₁) − (y₂−y₁)(x₃−x₁)（二维仿"z 分量"）。
定向判定：> 0 左转（逆时针）、< 0 右转（顺时针）、= 0 共线。绝对值 = 三角形面积的 2 倍。
一切几何关系都可用符号判定：鲁棒性警告——整数坐标用整型算叉积无误差；浮点坐标要小心"几乎共线"的退化情形（ε 容差或精确谓词）。
定向判定：> 0 左转（逆时针）、< 0 右转（顺时针）、= 0 共线。绝对值 = 三角形面积的 2 倍。
一切几何关系都可用符号判定：鲁棒性警告——整数坐标用整型算叉积无误差；浮点坐标要小心"几乎共线"的退化情形（ε 容差或精确谓词）。
2 线段相交判定
算法两次跨立 + 一次共线检查
线段 p1p2 与 p3p4 相交 ⇔：
① 相互跨立：cross(p1,p2,p3)·cross(p1,p2,p4) ≤ 0 且 cross(p3,p4,p1)·cross(p3,p4,p2) ≤ 0；
② 共线特例（乘积为 0）时还要判定包围盒重叠。复杂度 O(1)。扫描线（Bentley-Ottmann）把"n 条线段的所有交点"降到 O((n+k)log n)——VLSI 设计检查的地基。
① 相互跨立：cross(p1,p2,p3)·cross(p1,p2,p4) ≤ 0 且 cross(p3,p4,p1)·cross(p3,p4,p2) ≤ 0；
② 共线特例（乘积为 0）时还要判定包围盒重叠。复杂度 O(1)。扫描线（Bentley-Ottmann）把"n 条线段的所有交点"降到 O((n+k)log n)——VLSI 设计检查的地基。
3 多边形：面积、凸性与点包含
算法鞋带公式与射线法
面积（鞋带公式）：A = ½|Σ(xᵢyᵢ₊₁ − xᵢ₊₁yᵢ)|——顶点按序带符号求和。
凸性判定：沿顶点走一圈，叉积符号一致（全 ≥0 或全 ≤0）⇔ 凸多边形。
点在多边形内（射线法）：从该点向右发一条射线，与边界相交奇数次 ⇔ 在内部，O(n)；凸多边形可用二分 O(log n)。
凸性判定：沿顶点走一圈，叉积符号一致（全 ≥0 或全 ≤0）⇔ 凸多边形。
点在多边形内（射线法）：从该点向右发一条射线，与边界相交奇数次 ⇔ 在内部，O(n)；凸多边形可用二分 O(log n)。
随堂检测基础
4 凸包：Graham 扫描
算法栈里的左转筛选
Graham 扫描 O(n log n)：① 选 y 最小点 p₀；② 其余按极角排序；③ 依次入栈，若新点使栈顶两 点与其构成右转则弹栈——栈中剩下的就是凸包顶点。
Jarvis 步进（礼物包装）O(nh)，h 为包上点数；Andrew 单调链（按 x 排序扫两遍）实现最简单、竞赛常用。
下界 Ω(n log n)（排序可归约到凸包）。应用：碰撞检测的包围盒、直径旋转卡壳 O(n)。
Jarvis 步进（礼物包装）O(nh)，h 为包上点数；Andrew 单调链（按 x 排序扫两遍）实现最简单、竞赛常用。
下界 Ω(n log n)（排序可归约到凸包）。应用：碰撞检测的包围盒、直径旋转卡壳 O(n)。
5 最近点对
算法分治的经典 O(n log n)
① 按 x 排序，中线分左右两半递归求最小距离 d；② 只需检查中线带宽 2d 内的点；③ 带内点按 y 排序后，每个点只需与后续至多 7 个点比较（鸽笼原理保证）。T(n) = 2T(n/2) + O(n) ⇒ O(n log n)。
朴素 O(n²) 在 n = 10⁶ 时不可行，分治可解——又一个"指数变多项式"的范例。
朴素 O(n²) 在 n = 10⁶ 时不可行，分治可解——又一个"指数变多项式"的范例。
6 Voronoi 图与 Delaunay 三角剖分
概念影响范围与最优三角化
Voronoi 图：平面上每格归最近的站点——"邮局辖区划分"。n 个站点 O(n log n)（Fortune 算法）。对偶图就是 Delaunay 三角剖分（每个三角形外接圆内无其他点 ⇔ 最大化最小角，避免瘦三角）。
应用：最近邻查询、基站覆盖、地图着色（四色定理的平面图背景）、有限元网格生成、凸包的对偶（升一维的 Delaunay = 降维的凸包——SVD/凸包理论的又一次相遇）。
应用：最近邻查询、基站覆盖、地图着色（四色定理的平面图背景）、有限元网格生成、凸包的对偶（升一维的 Delaunay = 降维的凸包——SVD/凸包理论的又一次相遇）。