计算几何

破除误解：计算几何不是欧几里得几何的数字化#

欧几里得几何研究的是什么图形存在（直线的平行关系、圆的性质）。计算几何研究的是如何高效计算几何对象的属性和关系：

• 不只是"凸包存在"，而是"如何在 $O(n \log n)$ 时间内找到 $n$ 个点的凸包"
• 不只是"两条线段可能相交"，而是"如何在 $O((n + k) \log n)$ 时间内找到 $n$ 条线段中所有的 $k$ 个交点"

更微妙的是，计算几何必须处理数值精度和退化情况（Degeneracy）：现实中的点可能完全共线，三个圆可能交于同一点，这些"退化"情形往往使简单算法失效，需要特别处理——这在纯粹数学的几何学里不是问题，但在工程实现中是核心挑战。

另一条分界线是组合复杂度：同一几何对象集合随参数连续移动时，组合结构（哪些三角形相邻、哪些边相交）只在临界事件处跳变。算法设计经常把连续几何还原为这些离散事件的排序与维护——扫描线、随机增量、运动规划中的路线图，背后都是"连续→组合"的翻译。懂欧氏几何不等于会做这步翻译。

现场：1970 年代的学科建立#

计算几何作为独立研究领域，通常以 1975 年迈克尔·沙莫斯（Michael Ian Shamos）在卡内基梅隆大学的博士论文为奠基，该论文系统地研究了几何问题的计算复杂度，引入了"扫描线"等核心算法技术，并建立了几何问题下界分析的框架。

1985 年，沙莫斯与弗朗哥·普雷帕拉塔（Franco Preparata）合著了《计算几何：导论》（Computational Geometry: An Introduction），成为该领域的第一本权威教材。这本书把散落在各处的几何算法研究统一到一个系统性框架中，被认为是计算几何成为独立学科的标志性时刻。

此后几十年，随机增量构造、切分树与持久化搜索结构相继进入主流工具箱；CGAL 等库把教科书算法落成可链接的几何内核。学科的自我认同不再只是"几个漂亮的最优算法"，而是一套处理退化、精度与大数据的工程方法论。

核心问题一：凸包（Convex Hull）#

问题：给定平面上 $n$ 个点，找到包含所有这些点的最小凸多边形——即"橡皮筋套住所有点"后的形状。

凸包是计算几何最基础的问题之一，也是许多更复杂问题的子步骤。

格雷厄姆扫描（Graham Scan，1972）：罗纳德·格雷厄姆（Ronald Graham）提出的 $O(n \log n)$ 算法。 1. 选取最低点 $p_0$ 作为起点 2. 按照与 $p_0$ 的极角排序其余所有点 3. 依次加入点，维护一个栈（逆时针的"左转"允许，"右转"弹出栈顶）

直觉：想象你按角度顺序绕最低点扫过所有点，凸包的边是在扫过时需要保留的边。

$O(n \log n)$ 是最优的吗？ 沙莫斯证明了凸包问题的下界是 $\Omega(n \log n)$（通过规约自排序问题），格雷厄姆扫描达到了这个下界——它是最优算法。

但这个"最优"有个漏洞：下界是针对最坏输入的。如果凸包实际只有 $h$ 个顶点而 $h \ll n$（比如一万个点挤在圆周附近，凸包只有十几个点），$O(n \log n)$ 里的排序开销就是冤枉的。输出敏感（output-sensitive）算法追求的正是让代价随输出规模收缩。最早的礼物包扎法（Jarvis march，1973）每绕出一条边要扫描全部点，代价 $O(nh)$——$h$ 小时已经优于排序类算法。1986 年，Kirkpatrick 与 Seidel 用"先剪枝、后分治"的策略（他们称之为 marriage-before-conquest）做到 $O(n \log h)$，并证明这在输出敏感意义下也是最优的。

三维与高维凸包的复杂度曲线更陡：三维已可做到接近最优的期望时间，但常数与实现难度显著上升；更高维则迅速逼近输出规模本身的瓶颈。平面凸包之所以成为入门案例，正因为它把下界、构造与输出敏感三条线索收在同一页里。

Chan 算法（Chan's Algorithm，Timothy Chan，1996）：提问是否可以不知道最终凸包顶点数 $h$ 就达到 $O(n \log h)$ 时间？Timothy Chan 给出了肯定答案，这个输出敏感的算法在 $h \ll n$ 时远快于 $O(n \log n)$。他的构造异常简洁：把格雷厄姆扫描与礼物包扎嵌套起来，对 $h$ 做逐次加倍的猜测，猜过头就推倒重来——浪费的部分被几何级数吸收，总开销仍是 $O(n \log h)$。

核心问题二：Voronoi 图（Voronoi Diagram）#

问题：给定平面上 $n$ 个点（"站点"，sites），把平面分割成 $n$ 个区域，每个区域包含所有离对应站点最近的点。

Voronoi 图（以俄罗斯数学家格奥尔基·沃罗诺伊 Georgy Voronoy 命名，实际上更早的相关工作可追溯到笛卡尔）是 GIS、城市规划、生物学等领域最常用的空间分析工具之一：

• 给定城市中所有医院位置，Voronoi 图告诉你地图上每个位置最近的医院
• 细胞生物学中，组织中细胞的分布近似遵循 Voronoi 图结构
• 机器人运动规划中，Voronoi 图是绕开障碍物的"安全通道"

Fortune 算法（Steven Fortune，1987）：用扫描线（sweep line）技术在 $O(n \log n)$ 时间和 $O(n)$ 空间内构造 $n$ 个点的 Voronoi 图，是该问题的最优算法。

扫描线技术是计算几何最强大的工具之一：用一条从上到下（或从左到右）移动的假想线，将二维问题分解为一系列随扫描线推进而演化的一维问题，并用平衡二叉树维护当前扫描线上的结构。

对偶性：Voronoi 图与 Delaunay 三角剖分（Delaunay Triangulation）互为对偶结构——Delaunay 三角剖分是把 $n$ 个点连成三角形的方法，使得每个三角形的外接圆内没有其他点。在几何插值、有限元网格生成等应用中，Delaunay 三角剖分是最高质量的三角网格。"最高质量"有精确含义：在所有可能的三角剖分中，Delaunay 剖分最大化了最小内角——它系统性地避开瘦长三角形，而瘦长三角形正是有限元计算中数值误差的温床。Voronoi 图管"谁离谁最近"，它的对偶就管"怎么把点连成最好的网"。

构造 Voronoi 还有一条优美的抬升路径：把每个站点抬到三维抛物面上，取下凸包再投影回平面，即可恢复最近邻划分的对偶信息。许多最优算法的直觉来自这种维度技巧——把距离比较变成半空间支撑关系，从而借用凸包与排列工具。GIS 服务区、气象插值、蜂窝基站规划，用的都是同一份最近邻证书。

核心问题三：线段相交（Line Segment Intersection）#

问题：给定 $n$ 条线段，找出所有 $k$ 对相交点。

暴力算法：检查所有 $\binom{n}{2}$ 对线段是否相交，时间 $O(n^2)$。

本特利-奥特曼算法（Bentley-Ottmann Algorithm，1979）：扫描线算法，时间 $O((n+k) \log n)$。关键思想：线段按 $x$ 坐标排序，扫描线从左到右移动，维护当前线段的竖向顺序，只有相邻线段才可能相交。当检测到相邻线段相交时，交换它们在扫描线上的顺序，并检测新的相邻对。

当 $k = O(n)$ 时（相交点不多），这比暴力算法快得多；当 $k = O(n^2)$ 时，算法退化回暴力速度，但无法更好（因为输出本身就有 $\Omega(n^2)$ 大小）。

线段相交是地图叠置、CAD 布尔运算与布线短路检测的日常原语。输出敏感界说明：算法快不快，常常取决于到底有多少交点，而不是输入规模单独说了算。 工程上还会先用包围盒做粗滤，把显然不相交的对丢掉，再把幸存候选送进扫描线——理论最优与实践加速在这里叠用。

核心问题四：最近点对（Closest Pair）#

问题：给定 $n$ 个点，找距离最近的两个点。

分治算法（沙莫斯，1975）在 $O(n \log n)$ 时间内解决：将点集按 $x$ 坐标分两半，递归求各半的最近点对距离 $d$，然后在中间宽度 $2d$ 的带状区域内寻找跨两半的最近点对（关键观察：这个带状区域内每个点只需要检查有限个邻居，使得合并步骤是 $O(n)$）。

带状区域里"每个点只看常数个邻居"来自鸽笼论证：把条带按当前最小距离划成格子，同一格与邻格里不可能塞下太多过近的点，于是按纵坐标扫过时比较次数被钉死。这个论证把二维几何约束变成计数引理，是计算几何证明里反复出现的套路。教学上分治版本仍是理解"几何为何能低于平方级"的最佳入口。

空间数据结构：范围查询与 kd 树#

计算几何不只研究算法，也研究支持几何查询的数据结构。

kd 树（k-dimensional tree，1975，Jon Bentley）：用于高效查找 $k$ 维空间中的近邻点。 - 交替按各维度的中位数分割空间，构建二叉树 - 最近邻查询平均 $O(\log n)$，最坏 $O(\sqrt{n})$（高维时退化） - 广泛用于机器学习中的 k 近邻算法、碰撞检测、点云处理

R 树（R-tree，1984，安东宁·古特曼 Antonin Guttman）：用于存储和查询矩形/几何对象（如地图中的街道、建筑），支持范围查询（"找出这个矩形框内所有对象"），是 GIS 数据库的核心空间索引结构。

维数灾难：kd 树在低维好用，维数升高时剪枝失效——高维空间中"最近邻"与"最远邻"的距离趋于接近，几乎每个节点都得访问，查询退化到接近线性扫描。实践中维数超过一二十，精确最近邻索引往往不如暴力。于是高维场景转向近似最近邻（允许返回"差不多最近"的点）：局部敏感哈希（LSH）这类方法用一点点误差换回亚线性查询——这是"输出要求放松一点，复杂度量级就改变"的又一例。

空间索引的选型还依赖查询形状：轴对齐范围适合 R 树与优先排队的分支限界；半径近邻常与球树或覆盖树搭配。没有一种结构在所有分布与所有维数上称王——基准测试必须写明数据维度、聚集程度与查询类型，否则"谁更快"没有意义。

数值鲁棒性：计算几何的实践挑战#

理论算法假设精确算术，但浮点运算有舍入误差。在计算几何中，这可能导致灾难性的错误：

退化情况（Degeneracy）：算法假设没有三点共线、没有四点共圆，但实际数据中这种情况频繁出现。处理退化情况往往使代码复杂度大幅增加。

一致性（Consistency）：浮点误差可能导致几何谓词的结果不一致（"点 $A$ 在直线 $BC$ 左边"和"点 $B$ 在直线 $CA$ 左边"在精确算术下同时成立，但浮点下可能矛盾），使得算法产生拓扑错误的结果。

工程上的主流解法不是"全程精确算术"，而是精确谓词 + 浮点过滤器：几何算法的命运只由少数几个谓词（predicate）的符号决定——最典型的是 orient2d（"点 $C$ 在有向直线 $AB$ 的左侧还是右侧"，一个行列式的符号）。1997 年，Jonathan Shewchuk 给出了至今仍广泛使用的方案：先用普通浮点算一遍并同时估计误差界；只有当结果可能翻号时，才升级到按需精度的展开式算术（expansion arithmetic）重算。绝大多数判断在过滤器阶段就结束，精确算术的高昂代价只在临界情形支付。CGAL 等主流计算几何库正是建立在这类过滤谓词之上。

解决方案包括：使用精确算术（速度慢）、符号微扰（symbolic perturbation，人为扰动点以消除退化情况）以及区间算术（以浮点区间代替单个浮点数）。

符号微扰的代价是语义：被扰动后的输入不再是用户给出的点集，地籍边界等应用不能接受"逻辑上消除共线"却改变面积符号的结果。鲁棒几何库因此常提供两种模式——谓词级精确保证拓扑决策自洽，构造级精确才保证输出坐标也是准确值；后者贵得多，只在布尔运算与几何排列等对顶点坐标敏感的场景启用。选型本身就是在正确性预算与性能预算之间划线。

应用领域#

运动规划把上述原语串成管道：先把障碍物膨胀成配置空间中的禁区，再用可视性图或 Voronoi 走廊提取候选路径，最后在离散路线上做曲率或动力学可行化。自动驾驶与仓储机器人并不每次从零发明几何，而是查询这些被索引好的交点、近邻与安全通道。

跨域连接#

• 计算机图形学：渲染与碰撞检测本质上是海量的求交与可见性判断，暴力两两比较不可行。空间划分把"与所有物体比较"换成"只与可能相交的少数物体比较"——图形的实时性不是靠算力堆出来的，是靠把几何关系预先组织好。
• 遥感与地理信息系统：地图查询的形态是范围与最近邻：框内有哪些对象、离我最近的是哪个。用矩形包围盒建树，可以在不看具体形状的前提下先排除整片区域，代价是包围盒越松、被误判为候选的对象越多，索引质量因此直接决定查询速度。
• 金属与合金：一批晶核同时开始、以相同速度向外生长，最终边界恰好落在相邻晶核的中垂面上——这就是最近邻划分的物理实现。同一套划分在城市服务半径、领地划分中反复出现，因为它的定义只用到"离谁最近"这一条。
• 数值方法：算法假设精确算术，浮点却会让几何判断自相矛盾：同一组点，"在左边"与"在右边"可能同时被判为真。错误在这里不是数值偏差，而是拓扑错乱，结构会直接失效。对策是精确谓词、区间算术或人为微扰，代价都是速度。
• 拓扑数据分析：把关注点从"距离多远"换成"哪些结构在多大尺度上一直存在"，几何就变成了拓扑。持续存在的特征被当作真信号，转瞬即逝的被当作噪声，这为高维点云提供了一种不依赖具体坐标的描述方式。

参考文献#

• Preparata, F. P. & Shamos, M. I. Computational Geometry: An Introduction. Springer (1985). （奠基性教材）
• Jarvis, R. A. On the Identification of the Convex Hull of a Finite Set of Points in the Plane. Information Processing Letters 2 (1973): 18–21. （礼物包扎法）
• Kirkpatrick, D. G. & Seidel, R. The Ultimate Planar Convex Hull Algorithm? SIAM Journal on Computing 15(1) (1986): 287–299.
• Fortune, S. A Sweepline Algorithm for Voronoi Diagrams. Algorithmica 2(1–4) (1987): 153–174. （Fortune 算法原始论文）
• Shewchuk, J. R. Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates. Discrete & Computational Geometry 18(3) (1997): 305–363. （精确谓词与浮点过滤器）
• de Berg, M., Cheong, O., van Kreveld, M. & Overmars, M. Computational Geometry: Algorithms and Applications. 3rd ed. Springer (2008). （最广泛使用的当代教材，可在作者网站免费获取）