2.2 梯形化
Trapezoidalization
我们发现单调多边形有可能被快速地三角分割，那么，如何将多边形快速的分割成单调多边形，就成了一个有趣的问题。我们将通过另一种中间的结构——梯形，来实现单调多边形的分割，这种方法本身就很有意思， 并且会在 7.11 节中用到。 Chazelle & Incerpi(1984)以及 Fournier & Montuno(1984) 引入了这种分割方法，用作三角分割的关键步骤。与之前讨论的分割方法不同，它不会将分割线段限制为对角线。
经过每个顶点画一条水平线，就可以对一个多边形进行水平梯形化horizontal trapezoidation。更准确的说，经过每个顶点 \(v\) 的最长水平线段 \(s\)， 满足 \(s \subset P\) 并且 \(s \cap \partial P = v\)。\(s\) 相当于从顶点 \(v\) 出发向左或向右看的一条水平视线。\(s\) 可能位于 \(v\) 的一侧，也可能 \(s = v\)。 为方便表述，我们先只考虑任意两个顶点都不在同一条水平线上的情况。图 2.3 给出一个水平梯形化的例子。
梯形是只有两条边平行的四边形。三角形可以看作是退化的梯形，其中一条平行边的长度为零。我们称水平线经过的顶点为其支撑顶点supporting vertices。
假设 \(P\) 是一个任意两个顶点都不位于同一水平线上的多边形。那么在水平梯形化中，每个梯形恰好有两个支撑顶点，分别位于其上下两边。 梯形分割与单调多边形之间存在联系，如果一个支撑顶点位于梯形上边或下边内，那么它是一个内部尖点interior cusp。如果将每个内部支撑顶点 \(v\) 都与其所支撑的梯形的另一个顶点相连， 向下连接被称为"向下尖点"，向上连接为"向上尖点"，那么这些对角线将 \(P\) 分割成关于垂直方向的单调多边形。这由引理 2.1.1 得出，因为每个内部尖点都被这些对角线移除。 例如，图 2.3 中的向下尖点 \(v_6\) 会被对角线 \(v_6v_4\) 消除。连接向下尖点 \(v_{12}\) 就可以消除向上尖点 \(v_{15}\)，等等。
现在，我们发现通过梯形化可以直接得到单调分割monotone partition，那么我们接下来重点关注，如何通过多边形的每个顶点绘制水平线。
2.2.1. 扫平面(Plane Sweep)
我们用于一种基于"平面扫描Plane Sweep" 或者"扫描线Sweep line" 的技术实现梯形化。该技术在许多几何算法中都非常有用(Nievergelt & Preparata 1982)。 其主要思想是用一条直线扫描一个平面，沿该直线维护某种数据结构。扫描过程中会遇到一些离散的“事件”，此时会处理这些事件并更新数据结构。 我们将用水平线 \(L\) 扫描多边形，每遇到一个顶点就会触发一个事件。这需要对顶点按 y 坐标进行排序，对于一般的多边形，需要 \(O(n \log n)\) 的时间复杂度。
这个处理过程，需要沿着 \(L\) 找到每个顶点 \(v\) 紧邻的左侧和右侧的边。为了高效地完成此操作，我们要一直维护排序列表 \(\mathcal{L}\) 记录 \(L\) 先后穿过的边。 如图 2.4 所示，当前扫描线依次穿过的边集合为，\(\mathcal{L} = (e_{19}, e_{18}, e_{17}, e_6, e_8, e_{10})\)。
假设列表 \(\mathcal{L}\) 已知，该如何确定图中 \(e_{17}\) 和 \(e_6\) 之间的那个顶点 \(v\)呢? 假设 \(e_i\) 是指向多边形一条边的指针，我们可以很容易地从中获取其端点的坐标。 假设 \(v\) 的纵坐标为 \(y\)，扫描线 \(L\) 上的所有点纵坐标也都是 \(y\)。已知 \(e_i\) 的端点和 \(y\)，我们可以计算 \(L\) 与 \(e_i\) 的交点的 x 坐标。 因此，我们可以通过计算高度为 \(y\) 的直线 \(L\) 穿过每条边的 x 坐标，来确定 \(v\) 在列表中的位置。
如果从左到右依次搜索，所需时间与列表 \(\mathcal{L}\) 的长度成正比，即 \(O(n)\)。但如果我们将列表存储在一个高效的数据结构中，例如平衡树，则搜索时间仅需\(O(\log n)\)。 由于每次事件发生都需要进行一次搜索，因此整个平面扫描的总复杂度为 \(O(n\log n)\)。
接下来需要证明，我们总是可以维护这个数据结构，并且时间复杂度是 \(O(n \log n)\)。只要数据结构支持 \(O(\log n)\) 时间复杂度的插入和删除操作，那么这一点就很容易实现， 例如平衡树、2-3树或红黑树就支持这种操作。现在，我们假设有一条向下的扫描线，来详细研究一下每次事件的更新过程。
假设在扫描线 \(L\) 上 \(v\) 位于边 \(a\) 和 \(b\) 之间，并且 \(v\) 是边 \(c\) 和 \(d\)公共点。如图 2.5 所示，扫描线 \(L\) 会遇到三种可能的事件类型。
- \(c\) 在 \(L\) 的上面， \(d\) 在下面。那么就将 \(c\) 从 \(\mathcal{L}\) 中删除，同时插入 \(d\): $$ (\cdots, a, c, b, \cdots) \Rightarrow (\cdots, a, d, b, \cdots) $$
- \(c\) 和 \(d\) 都在 \(L\) 的上面，那么将他们都从 \(\mathcal{L}\) 中删除: $$ (\cdots, a, c, d, b, \cdots) \Rightarrow (\cdots, a, b, \cdots) $$
- \(c\) 和 \(d\) 都在 \(L\) 的下面，那么将他们都添加到 \(\mathcal{L}\) 中: $$ (\cdots, a, b, \cdots) \Rightarrow (\cdots, a, c, d, b, \cdots) $$
回到图 2.4，一开始扫描线 \(L\) 位于多边形的上方，穿越边列表 \(\mathcal{L}\) 就是空的。然后随着 \(L\) 经过每个事件顶点，列表依次如下，其中最后一组列表对应的就是图中 \(L\) 的位置。
$$ \begin{array}{c} (e_{12}, e_{11}) \\ (e_{15}, e_{14}, e_{12}, e_{11}) \\ (e_{15}, e_{14}, e_{12}, e_{6}, e_7, e_{11}) \\ (e_{15}, e_{14}, e_{13}, e_{6}, e_7, e_{10}) \\ (e_{16}, e_{14}, e_{13}, e_{6}, e_7, e_{10}) \\ (e_{16}, e_{6}, e_7, e_{10}) \\ (e_{16}, e_{6}, e_8, e_{10}) \\ (e_{19}, e_{18}, e_{16}, e_6, e_8, e_{10}) \\ (e_{19}, e_{18}, e_{17}, e_6, e_8, e_{10}) \end{array} $$2.2.2. \(O(n \log n)\) 的三角分割(Triangulation in \(O(n\log n)\))
省略其余(主要是数据结构)细节，我们在算法 2.1 中总结了复杂度为 \(O(n \log n)\) 的多边形三角分割的算法。
 |
2.2.3. 练习
- 关于唯一方向单调Monotone with respect to a unique direction。一个多边形能否只关于一个方向单调？
- 内部尖点Interior cusps。构造一个非严格单调的多边形，该多边形没有内部尖点，从而表明引理 2.1.1 不能扩展为“没有内部尖点意味着严格单调性”。
- 水平线上有多个顶点Several vertices on a horizontal。将梯形分割算法扩展到水平线上可能有多个顶点的多边形。
- 对带孔多边形进行扫描Sweeping a polygon with holes。设计一个算法，利用平面扫描对带孔多边形(外层多边形 \(P\) 包含多个多边形孔洞)进行三角分割。 对角线应将 P 内部除每个孔洞外的部分分割开来。将算法复杂度表示为顶点总数 \(n\) 的函数。