计算几何
挖坑 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。 |