计算几何

挖坑 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)	。