Delaunay Triangulations-Height Interpolation

(delaunay 三角剖分 高度插值)

1）三角剖分
2）将每个样品点提升到正确的高度（对应三角地图）

地面上的是等高线

问题：
1）我们如何对样本点集进行三角剖分？
2）哪种三角测量最适合我们的目的，即近似地形？

9.1 Triangulations of Planar Point Sets

（平面点集的三角剖分）

P 的一个三角剖分，定义为“以 P 为顶点集的一个极大平面子区域划分

连接P的凸包边界上的两个连续点的任何段是任何三角剖分中的边

同一点集的三角剖分含同样数目的三角形，具体数目取决于点集的规模及其 凸包的规模。

Theorem 9.1

Let P be a set of n points in the plane, not all collinear, and let k denote the number of points in P that lie on the boundary of the convex hull of P. Then any triangulation of P has 2n−2−k triangles and 3n−3−k edges.

设 P 为由平面上不全部共线的任意 n 个点组成的一个集合，落在 P 的凸包边界上点的个数记作 k。 则 P 的任何一个三角剖分必然由 2n - 2 – k 个三角形组成，而且共有 3n - 3 – k 条边。

边翻转操作

Observation 9.3

Let T be a triangulation with an illegal edge e. Let T be the triangulation obtained from T by flipping e. Then A(T) > A(T).

设 e 为三角剖分 T 中的一条非法边。在 T 中对 e 进行边翻转操作之后，设新的三角剖分为 T '。则必有 A(T ') > A(T)。
其中A（T）表示T的角度测量

In other words, an edge is illegal if we can locally increase the smallest angle by flipping that edge.

Criterion:
to check whether a given edge is legal

Lemma9.4

Letedge pipj beincidenttotriangles pipjpk and pipjpl,andletC be the circle through pi, pj, and pk. The edge pipj is illegal if and only if the point pl lies in the interior of C. Furthermore, if the points pi, pj, pk, pl form a convex quadrilateral and do not lie on a common circle, then exactly one of pi p j and pk pl is an illegal edge.

设三角形pipjpk和pipjpl之间的公共边为pipj，令C为由点pi、pj和pk确定的圆。pipj是一条非法边，当且仅当点pl落在C的内部。而且，只要点pi、pj、pk和pl构成一个凸的四边形 1，并且不共圆，则在pipj和pkpl二者当中有且仅有一条非法边。

根据Thales定理找出非法边

当所有四个点都在一个圆圈上时，两者都有
并且是合法的。
请注意，非法边缘的两个三角形必须形成凸四边形，因此始终可以翻转非法边缘。
将合法三角剖分定义为不包含任何非法边缘的三角剖分。

Algorithm LEGALTRIANGULATION(T)

该算法中的每一轮迭代之后，T的 角度向量都会有所增长。对于任一集合P，可能的三角剖分只有有限个，因此这样一个单调变化的过 程必然会终止。一旦算法终止，得到的结果必然是一个合法三角剖分。

9.2 The Delaunay Triangulation

Vor§的对偶图
若两个单元之间公用一条边，则在这两个单元各自对应的节点 之间，联接一条弧(arc)。
在G的所有有界面与Vor§中的所有顶点之间，存在一个 一一对应关系。

Theorem 9.5

The Delaunay graph of a planar point set is a plane graph.

任何平面点集的 Delaunay 图都是一个平面图。

Theorem 9.6

Let P be a set of points in the plane.

• (i) Three points pi , p j , pk ∈ P are vertices of the same face of the Delaunay
  graph of P if and only if the circle through pi, pj, pk contains no point of
  P in its interior.
• (ii) Two points pi, pj ∈ P form an edge of the Delaunay graph of P if and only
  if there is a closed disc C that contains pi and p j on its boundary and does not contain any other point of P.

(i) 三个点 pi, pj, pk ∈ P 同为某张面的顶点，当且仅当 pi, pj, pk 外接圆的内部不含 P 中的任何点;
(ii) 两个点 pi, pj ∈ P 同时与某条边相关联，当且仅当存在一个闭圆盘 C，除了 pi 和 pj 落在其边界上
之外，该圆盘不包含 P 中其它的任何点

Theorem 9.7

Let P be a set of points in the plane, and let T be a triangulation of P. Then T is a Delaunay triangulation of P if and only if the circumcircle of any triangle of T does not contain a point of P in its interior.

设 P 为平面上的任一点集，而 T 为 P 的任一三角剖分。则 T 是 P 的 Delaunay 三角剖分，当且仅当在 T 中每个三角形的外接圆的内部，都不包含 P 中的任何点。

Theorem 9.8

Let P be a set of points in the plane. A triangulation T of P is legal if and only if T is a Delaunay triangulation of P.

设 P 为平面上的任一点集。则 T 是 P 的一个合法三角剖分，当且仅当 T 是 P 的 Delaunay 三角剖分。
(普通的三角剖分不一定是合法的)

Theorem 9.9

Let P be a set of points in the plane. Any angle-optimal trian- gulation of P is a Delaunay triangulation of P. Furthermore, any Delaunay triangulation of P maximizes the minimum angle over all triangulations of P.

设 P 为任一平面点集。P 的任一角度最优的三角剖分，必是 P 的一个 Delaunay 三角剖分。此外，在 P 的所有三角剖分中，Delaunay 三角剖分使最小角达到最大。

9.3 Computing the Delaunay Triangulation

采用随机增量式算法来直接计算Delaunay三角剖分。

足够大的包围三角形
需要引入两个辅助点p-1 和p-2，它们与P中的最高 点联合构成的三角形，将包含所有的点。
选择的p-1 和p-2 必须相距足够远，才不致于对P的Delaunay三角剖分 中的任何三角形有所影响。尤其必须保证的一点是，它们不能落在P中任何三点的外接圆内。

Algorithm of Randomized incremental:
（随机增量算）
it adds the points in random order and it maintains a Delaunay triangulation of the current point set.

引入点pr时可能的两种情况:pr落在某个三角形内部(左)，pr恰好落在某条 边上(右)

考虑引入点pr时的情况。首先，要在当前的三角剖分中，确定 pr落在哪个三角形内(具体方法稍后将介绍)。然后，将pr与该三角形的三个顶点分别联接起来，生 成三条边。
倘若pr碰巧落在三角剖分的某条边e上，就需要找到与e关联的那两个三角形，然后将pr 与对顶的那两个顶点分别联接起来，生成两条边。

在引入点 pr 之后，原 来的某些边可能不再合法。为消除这些不合法性，需要针对每一条可能的非法边，调用一次子函数 LEGALIZEEDGE
这个子函数通过边翻转操作，将所有的非法边转换为合法边。

Algorithm DELAUNAYTRIANGULATION§

算法实现分别讨论了新添加点pr出现在三角形中的两种位置情况，并且对剖分形成的三角形都进行了LEGALIZEEDGE。
执行LEGALIZEEDGE之后的三角形并不能保证也是合法的，所有LEGALIZEEDGE内部还会再次调用LEGALIZEEDGE。

LEGALIZEEDGE(pr, pi pj,T)

新生出的每一条边，都必然与pr相关联

Lemma 9.10

Every new edge created in DELAUNAYTRIANGULATION or in LEGALIZEEDGE during the insertion of pr is an edge of the Delaunay graph of {p−2, p−1, p0,…, pr}.

无论是由算法 DELAUNAYTRIANGULATION 生成的边，还是在插入点 pr 的过程中生成的边，都是Ω ∪ {p1, …, pr}的 Delaunay 三角剖分中的边。

9.4 The Analysis

Lemma 9.11

The expected number of triangles created by algorithm DELAU- NAYTRIANGULATION is at most 9n + 1.

由算法 DELAUNAYTRIANGULATION 生成的三角形，总数目的期望值不超过 9n + 1

Theorem 9.12

The Delaunay triangulation of a set P of n points in the plane can be computed in O(nlogn) expected time, using O(n) expected storage.

任意给定由平面上 n 个点组成的一个集合 P，我们都可以使用 O(n)的期望空间，在 O(nlogn)的期望时 间内构造出 P 的 Delaunay 三角剖分。

将P中位于给定三角形Δ的外接圆中的点的子集表示为K（Δ）

Lemma 9.13

其中的求和范围，覆盖由算法生成的所有 Delaunay 三角形Δ.