计算几何
挖坑 MuJoCo 的时候发现， 它会用一个 qhull 的库来计算三角网格的凸包。 再挖一层发现，它和一本经典的教材《Computational Geometry in C》有很密切的关系。 出于好奇，想看看所谓的计算几何都在算些啥，所以决定 2025 年啃一遍这本书。
翻译过程中，我们仍然保持原著中的 C 代码。我还会根据个人的使用习惯，在XiaoTuMathBox中用 C++ 再实现一遍。
前言.Preface。
封面图像是一个分布在球面上的螺旋曲线，它是一个 5,000 个点的凸包。它是通过运行本书附带的 spiral.c 和 chull.c 代码生成的。
spiral 5000 -r1OOO | chull
第一章.多边形的三角分割(Polygon Triangulation)
|
1.1 艺术画廊定理 (Art Gallery Theorems) |
本节定义了多边形，从 Klee 提出的多边形覆盖问题，讨论了数学家们如何形式化的描述问题，提出假设并严格证明。 通过 Fisk 的充分性证明引出了多边形的三角分割问题。 |
|
1.2 三角分割理论 (Triangulation: Theory) |
本节我们将证明每个多边形都可以进行三角分割，还会介绍一些三角分割的基本性质。 |
|
1.3 多边形的面积 (Area of Polygon) |
本节我们将要研究如何计算一个多边形的面积。虽然这个问题本身就很有趣，但是我们的目标是为计算半平面的包含关系、线段的交点、可见性关系做一些准备工作， 为最终在1.6.5 节中引出三角分割算法打基础。 |
|
1.4 实现的问题 (Implementation Issues) |
本节用双向循环链表表示多边形，并提供了计算多边形面积的 C 程序。 我们用 C++ 实现了一遍 Polygon.hpp。 |
|
1.5 线段相交 (Segment Intersection) |
本节重申了多边形对角线的定义，并给出判定两个线段是否相交的实现。 参考 Euclidean2.hpp 中的函数 Intersect。 |
|
1.6 三角分割实现 (Triangulation: Implementation) |
本节先介绍了如何判定一条线段是多边形的对角线，然后基于双耳定理实现了复杂度为 \(O(n^2)\) 的三角分割算法。 参考 Polygon.hpp 中的成员函数 Diagnal 和 Triangulate。 |
第二章.多边形分割(Polygon Partitioning)
在本章中，我们将探讨其他类型的多边形分割。分割单调(monotone)多边形(2.1节)、梯形(trapezoids)(2.2节)、"单调山(monotone mountains)"(2.3节)以及凸(convex)多边形(2.5节)。 我们的主要目的是加速上一章中介绍的三角剖分算法，但这些分割方法本身也具有广泛的应用和研究价值。 凸多边形分割的一个应用是字符识别: 光学扫描的字符可以表示为多边形(有时带有多边形孔洞)，并被分割成多个凸多边形，然后将分割后的结构与形状数据库进行匹配，从而识别字符(Feng & Pavlidis 1975)。 此外，由于许多计算在凸多边形上更容易，例如，计算与障碍物或光线的交点；计算到直线的距离；判断一个点是否在多边形内部。所以这些应用的第一步通常都是，将复杂形状分割成凸多边形。
本章没有实现什么算法，但是有些练习里会建议读者自行实现。
|
2.1 单调多边形分割 (Monotone Partitioning) |
本节介绍了单调多边形的概念，并简单概述了一种对单调多边形进行三角分割的贪心算法，其时间复杂度为 \(O(n)\)。 |
|
2.2 梯形化 (Trapezoidalization) |
本节介绍一种基于平面扫描的方法将多边形梯形化，以便快速的将多边形分割成单调多边形。配合上一些特殊的数据结构，其时间复杂度为 \(O(n\log n)\)。 |
|
2.3 单调山分割 (Partition into Monotone Mountains) |
上节中描述的算法有一个更简单的变体。其思路仍然是从 \(P\) 的梯形化开始，将之分割成若干个更容易进行三角分割的部分，称之为单调山 monotone mountains。 |
|
2.4 线性时间三角化 (Linear-Time Triangulation) |
本节介绍了三角化算法的发展过程，极简述了复杂度为 \(O(n)\) 但细节非常多的Chazelle's 算法，以及复杂度为 \(O(n \log^* n)\) 但实现简单的Seidel's算法。 |
|
2.5 凸分割 (Convex Partitioning) |
所谓的凸分割是将多边形分割成若干个凸多边形，而不局限于三角形。本节介绍凸分割问题，简要讨论如何将多边形分割成尽可能少的凸块。 |
第三章.二维凸包(Convex Hulls in Two Dimensions)
凸包是计算几何中最常见的结构。它本身就很有用，在很多情况下可以作为工具来构建其他结构。从纯数学的角度看来，它也是一个简洁优美的对象，扮演着核心角色。 它也是计算几何研究中的成功应用的案例。计算几何领域最早的论文就涉及凸包的计算，我们将在3.5节中讨论。之后，关于凸包的研究层出不穷，为大多数自然问题(natural problems)找到了最优算法。 本章我们将探讨其中一小部分工作，并在练习(3.9节)中补充一些材料。在继续探讨几何之前，我们先举几个应用的例子:
- 避障 Collision avoidance。如果包裹机器人的凸包能够避开障碍物，那么机器人本身也能避开障碍物。 由于规划凸机器人避开障碍物的路径比非凸机器人的要容易得多，因此凸包常用于路径规划。这将在8.4节中讨论。
- Fitting ranges with a line. Finding a straight line that fits between a collection of data ranges maps to finding the convex region common to a collection of half-planes (O'Rourke 1981).
- 最小包围盒子 Smallest box。对于能够包含一个多边形的最小面积盒子，至少有一条边与该多边形的凸包齐平。 因此在最小包围盒子算法的第一步就是计算凸包(Toussaint 1983b)。类似地，在空间中寻找包围物体的最小三维盒子也需要物体的凸包(O'Rourke 1985a)。
- 形状分析 Shape analysis。为了进行模式匹配，我们会通过"凸差数 Convex Deficiency Tree(CDT)"对形状进行分类。CDT 的结构依赖于凸包的计算。 这将在练习 3.2.3[2] 中进行探讨。
凸包很重要，所以我们不仅要给出严谨的定义，更要有直观透彻的理解。平面上一个点集的凸包，可以想象成在每个点上顶一个钉子，然后用橡皮筋围着这些钉子，自然绷直之后的形状。 三维空间中点集的凸包边界，可以想象成用保鲜膜紧紧包裹住这些点所形成的形状。本章将给出凸和凸包的详细定义，并致力于构建凸包的算法。
|
3.1 凸和凸包的定义 (Definitions of Convexity and Convex Hulls) |
本节罗列了一系列关于凸和凸包的概念定义，并简单讨论了凸包算法的输出形式，以及极点(extreme points)的概念。 |
|
3.2 极点的朴素算法 (Naive Algorithms for Extreme Points) |
本节介绍了两个速度很慢的算法，用于求取非极点(nonextreme points) 和极边(extreme edges)。它们将作为后续更快算法的参照。 |
|
3.3 包装礼物算法 (Gift Wrapping) |
本节介绍的包装礼物(gift wrapping)算法，相比于上一节要快一点，而且输出的凸包顶点是排序的。 |
|
3.4 快速凸包算法 (QuickHull) |
本节介绍了一个类似快排的递归算法 QuickHull，在最好的情况其时间复杂度是 \(O(n \log n)\)。但最坏情况下，其复杂度仍然是二次的。 |
|
3.5 Graham 算法 (Graham's Algorithm) |
Graham 算法十分简洁，通过栈结构和排序，实现了复杂度为 \(O(n\log n)\) 的凸包算法。实际上 \(O(n \log n)\) 的复杂度源自于快排的复杂度， 扫描过程的复杂度只有 \(O(n)\)。 |
|
3.6 下界 (Lower Bound) |
本文通过问题规约的方法，讨论了凸包算法的下界 \(\Omega(n \log n)\)。 |
|
3.7 增量算法 (Incremental Algorithm) |
本文介绍的增量算法可以方便的扩展到更高维的空间中。在最坏的情况下它的复杂度是 \(O(n^2)\) 的，但经过排序并合理安排搜索策略之后， 其复杂度可以达到 \(O(n \log n)\)。 |
|
3.8 分治 (Divide and Conquer) |
分治是一种常用的算法思想。本文介绍的分治算法，是目前已知唯一能够扩展到三维并达到渐近最优 \(O(n \log n)\) 时间复杂度的技术。 |
|
3.9 附加练习 (Additional Exercises) |
本节就是一些思考题，没有什么算法要介绍的。 |
第四章.三维凸包(Convex Hulls in Three Dimensions)
本章关注构建三维空间点集凸包的算法(第4.2节)。我们还将涉及一些相关问题，多面体的性质(第4.1节)、如何表示多面体(第4.4节)，还会简单探索一下更高维度的多面体(第4.6节)。 最后，将通过一系列练习来探讨几个相关主题(第4.7节)。本章的核心内容是全书中最复杂的代码实现：通过增量算法(Incremental Algorithm)构建三维凸包的代码(第4.3节)。
|
4.1 多面体 (Polyhedra) |
本节给出了多面体的严格定义。证明了三维空间中只有 5 种正多面体，它们被称为柏拉图多面体。著名的欧拉公式描述了零亏格多面体的点、边、面的关系。 |
|
4.2 凸包算法 (Hull Algorithms) |
本节将简单提一下三维空间中的包装礼物算法Gift Wrapping，并概述三维分治算法Divide and Conquer的总体思想。 重点在于介绍本章关注的三维增量算法Incremental Algorithm的框架。 |