Polygon Triangulation

美术馆问题：
我们需要多少台摄像机才能保护特定的画廊，我们如何确定放置它们的位置？

3.1 Guarding and Triangulations

将画廊建模为多边形区域

simple polygons（简单多边形）

简单的多边形，由单个封闭的多边形链包围的区域，不与自身相交。不允许有孔的区域

一个简单多边形和一个可能的三角剖分

triangulation of the polygon（多边形的三角剖分）

A decomposition of a polygon into triangles by a maximal set of non-intersecting diagonals is called a triangulation of the polygon
即将多边形分解为多个三角形

如果多边形具有三个连续的共线顶点，则三角测量通常不是唯一的

Theorem 3.1

Every simple polygon admits a triangulation, and any triangulation of a simple polygon with n vertices consists of exactly n−2 triangles.

任何简单多边形都存在(至少)一个三角剖分;若其顶点数目为 n，则它的每个三角剖分都恰好包 含 n - 2 个三角形。

Theorem 3.2 (Art Gallery Theorem)

For a simple polygon with n vertices, n/3 cameras are occasionally necessary and always sufficient to have every point in the polygon visible from at
least one of the cameras.

（美术馆定理）包含 n 个顶点的任何简单多边形，只需(放置在适当位置的)⎣n/3⎦台摄像机就能保证:其中任何一点 都可见于至少一台摄像机。有的时候，的确需要这样多台摄像机

Theorem3.3

LetPbeasimplepolygonwithnvertices.Asetof n/3 camera positions in P such that any point inside P is visible from at least one of the cameras can be computed in O(nlogn) time.

任给一个包含 n 个顶点的简单多边形 P。总可以在 O(nlogn)时间内，在 P 中确定⎣n3⎦台摄像机的位置，
使得 P 中的任何一点都可见于其中的至少一台摄像机。

3.2 Partitioning a Polygon into Monotone Pieces

单调

图为y单调的多边形，但不是x单调的。
如果一个多边形既是x又是y单调，则为凸多边形。
x和y可以理解为 x方向和y方向

y单调，在y方向上移动，不会有折回的情况
x单调，在x方向上移动，不会有折回的情况。

---

为什么要做多边形做三角化？
是为了做局部处理。（着色、拉伸、切割……）

此图非y单调 在点v处 发生了折返，v点成为 拐点

策略：
将拐点对角化

点的高低比较：
先比y，再比x（x越小，越大）

start vertex
相邻顶点在其下方
end vertex
相邻顶点在其上方
regular vertex
相邻顶点一上一下
split vertex 分裂点 （从上往下看）
相邻顶点都在其下方，多边形内的夹角 大于 180
merge vertex 汇合点 （从上往下看）
相邻顶点都在其上方，多边形内的夹角 大于 180

split vertex和 merge vertex 都是拐点（turn vertex）

Lemma 3.4

A polygon is y-monotone if it has no split vertices or merge vertices.

一个多边形若既不含分裂顶点，也不含汇合顶点，则必然是 y-单调的。

证明如下

假设P不是y-单调。 我们必须证明P包含一个split或一个合并顶点。

• （a）中 q-r 是非连通，则必然存在一个 split vertex 在其上方
• （b）中 q-r '是非连通，则必然存在一个 merge vertex 在其下方

By adding a diagonal going upward from each split vertex and a diagonal going downward from each merge vertex.

Plane sweep method

主要思想：
从每个分割顶点添加一个向上的对角线，从每个合并顶点向下添加一个对角线

ej: immediately to the left of vi,
ek: immediately to the right of vi on the sweep line.

helper(ej):
is defined as the lowest vertex above the sweep line such that the horizontal segment connecting the vertex to ej lies inside P
在位于扫描线上方、通过一条完全落在P内部的水平线段 1与ej相联的 那些顶点中，高度最低的那个顶点

merge vertices vi
when we reach a vertex vm that replaces as the helper of , then this is the vertex we are looking for.

当扫描线向下移动的时候，helper（ej）= vi
vm 是扫描线向下移动过程中 触及的第一个点。
If the old helper was a merge vertex, we thus get rid of a split vertex and a merge vertex with the same diagonal.

一个分割结果如下：

Algorithm

Algorithm MAKEMONOTONE§

接下来分别对几个不同类型的点的处理的算法进行说明，特别值得注意的是对split vertex和merge vertex的处理

HANDLESPLITVERTEX(vi)

HANDLEMERGEVERTEX(vi)

Lemma 3.5

Algorithm MAKEMONOTONE adds a set of non-intersecting diag- onals that partitions P into monotone subpolygons.

通过引入一系列互不相交的对角线，算法 MAKEMONOTONE 能够将 P 划分为多个单调子多边形。

介于vm和vi之间水平梯形Q内部必空
vivm不会与P的任意一条边相交，也不会和之前添加的对角线相交。

Theorem 3.6

A simple polygon with n vertices can be partitioned into y- monotone polygons in O(n log n) time with an algorithm that uses O(n) storage.

使用 O(n)的存储空间，可以在 O(nlogn)时间内将包含 n 个顶点的任何简单多边形分解为多个 y-单调 的子块。

3.3 Triangulating a Monotone Polygon

(单调多边形的三角剖分)

单调多边形可以在线性时间内进行三角剖分
假设 P是严格y单调的
等价于 p是y单调的，并且不包含水平边

The greedy triangulation algorithm

算法按照y坐标的降序依次处理顶点
漏斗的一个边界由单个边缘的一部分组成，另一个边界是由反射顶点组成的链

将多边形按y坐标的降序分为两个链

考虑vj时，先将右侧链全部pop出，除最后一个点外，其他点都添加与vj的对角线，再将右链中最后一个push进栈，再把vjpush进栈

对于新加入的点uj，如果与当前栈顶异侧，则pop出栈中所有的点，除最后pop出的那个点外，都与新加入点添加对角线。然后将uj-1 和uj压入栈中。
如果与当前栈顶同侧，则首先将栈顶pop出来（这个栈顶必然与uj构成多边形P的边）。再不断检查剩下的栈顶，如果栈顶和uj连线完全处于p内部，则弹出该栈顶并构建对角线，如果不在p内部，则将最后弹出的那个栈顶压回s中，并将uj压回s中。

Theorem 3.7

A strictly y-monotone polygon with n vertices can be triangulated in linear time.

由 n 个顶点组成的任一严格 y-单调多边形，都可以在线性时间内被三角剖分。

General planar subdivision

在处理未封闭的多边形情况时，可以为其添加边框才处理。

Theorem 3.8

A simple polygon with n vertices can be triangulated in O(n log n) time with an algorithm that uses O(n) storage.

使用 O(n)的存储空间，可以在 O(nlogn)时间内对由 n 个顶点组成的任一简单多边形进行三角剖分。

Theorem 3.9

A planar subdivision with n vertices in total can be triangulated in O(nlogn) time with an algorithm that uses O(n) storage.

使用 O(n)存储空间，可以在 O(nlogn)时间内对包含 n 个顶点的任一平面子区域划分进行三角剖分。