xA H ( A, B, C , D) xB xC xD yA yB yC yD
2 2 xA y A 1 2 2 xB y B 1
x y x y
2 C 2 D
2 C 2 D
1 1
.
0, point D is inside the circumcirc le of ABC H ( A, B, C , D ) 0, point D is outsidethe triangle 0, co - circular
5.4 Constrained Delaunay triangulation
5.5 Triangulation from contour data
5.6 Delaunay triangulations via Voronoi diagrams
建立TIN的算法多种多样
Delaunay三角网或其他三角网 静态或动态方法 无约束或有约束的方法 直接或间接方法
(b) Voronoi diagram of the set
(c) Dual relationship
(d) Triangulation of the set

Voronoi图最早由俄罗斯数学家Voronoi于1908年提出， 平面上一个点集P的Voronoi图是对平面的一个划分， 每个分区表示一些点的轨迹，这些点到P的一个元素比 到其它元素更近
(b) Subsequent triangles formed near the boundary
一旦提取出数据区域的凸闭包，就可以从其中的一条边 开始逐层构建三角网
随着数据点分布密度的不同， 边界收缩后一个完整的区域 可能会分解成若干个相互独 立的子区域 当数据量较大时如何提高顶 点选择的效率是该方法的关 键
插入约束线段ab 提取ab的影响多边形并把所有顶点都与a相连 进行 LOP 交换优化三角形 带约束的三角网

Three approaches to form triangulation from contour data :
等高线离散点直接生成TIN方法 将等高线作为特征线的方法 自动增加特征点及优化TIN的方法
每个点都有一个Thiessen 多边形或Voronoi区域（凸多边形） 所有这些Thiessen多边形的集合（没有缝隙和重叠）完整覆盖 整个区域
分治算法Divided-Conquer 增长法Incremental

1 2 3 4 3 7 1 2
4
5
6
5 6
Insertion of a point into an existing Voronoi diagram
(a) Data with a feature line (b) Point densification (c) Triangulation result
将特征线作为约束

To treat each feature line as a constraint means the predefined lines are not to be crossed by any triangle edges 这是最严密的解 带约束条件的三角网仍然满足Delaunay法则，但 其局部等角特性有较小的改变
(b) Point D used to form the triangle

由两相邻三角形构成的凸四边形中，交换此四边形的 两条对角线，不会增加这两个三角形六个内角总和的 最小值 最小角将最大化而最大角将最小化，因此又称MAXMIN angle principle 局部最优方法LOP （Local Optimization Procedure）， 交换凸四边形的对角线，可获得等角性最好的三角网
(a) A set of random (b) Minimum bounding rectangle points
(c) Imaginary boundary box
Delaunay三角形连网可以从任意虚拟边界点开始 凸多边形意味着任意线段上的所有点都将落入其中
插入法生成Delaunay三角网
如果发现另外一个点落在分裂三角形的外接圆内，则要
用另外一条对角线来替换这条公共边 新的三角形外边还要记入堆栈供后续检测使用
A A D

D
B (a) C B
C
(b)
边AC被BD替换
三角形ABC保持不变

Ridge lines are the connected lines of local maxima (points) and the valley lines are the local minima These lines are so special that they should not be broken by any triangle edges

数据逐点插入法
保证相邻的数据点渐次插入，并通过搜寻加入点的 影响三角网（Influence Triangulation），现存的三角 网在局部范围内得到动态更新
Dynamic Delaunay triangulation by the insertion of points into the initial coarse triangles
5.1 Triangulated irregular network formation:Principles 5.2 Vector-based static Delaunay triangulation
5.3 Vector-based dynamic Delaunay triangulation


A
Minimum
A
D
D
Maximum Maximum
C B B C
Minimum
(a) Before swapping the diagonal
(b) After swapping the diagonal
Local Optimization Procedure
考虑所有点，在构网过程 中没有点的增加或删除
(d) 考虑山谷后的等高线
最简单的处理方法是所谓的“加密法”，即通 过加密约束线段上的数据点，将约束数据转换 为普通数据 唯一的问题在于如何恰当地确定特征线上加密 数据点之间的距离，一般取平均数据点间距的 一半或更小即可


尽管加大了数据量并改变了原始数据集，但简单易行、 稳定可靠，在许多情况下可以很好地满足需要
快速定位插入点所在的三角形 三角形分裂 三角形优化
A D p A p p
ቤተ መጻሕፍቲ ባይዱ
B C
B C
(A)
(B)
(C)
(a) Initial triangulation
(b) Splitting the enclosing triangle
(c) The “swap” operation

After a triangle is split into three triangles by a inserted point, the three exterior triangle edges need to be tested, to see if they conform to the Delaunay (空圆) condition
删格法
矢量法
静态式 Voronoi 图
动态式
TIN


The most widely used method for the construction of triangles is the Delaunay triangulation 狄洛尼三角网为相互邻接且互不重叠的三角形 的集合，每一个三角形的外接圆内不包含其它 的点
递归生长法 凸闭包收缩法
B A A
E F G D
C H A B
在凸闭包中，连接任意 两点的线段必须完全位 于多边形内 凸闭包是数据点的自然 极限边界，相当于包围 数据点的最短路径 显然，凸闭包是数据集 标准Delaunay三角网的 一部分
(a) First triangle starting from the boundary

B
628 677
C A 490
481 531 A 453 C
B
461
(a) 具有山谷线的点集
B 628
(b) A possible profile across ACB
628 677
677 C A 490 481 531 453 461
C
481 531 453
A
490
461
(c) 不考虑山谷的三角网

将所有数据包括约束线段上的数据点，建立标准的 Delaunay三角网 嵌入线段约束，根据对角线交换法LOP调整每条线段影 响区域内的所有三角形
Inter-visibility of nine points and two constrained line segments
CDT生成
(a)
(b) (c) (d)

出现平三角形：三角形的三个顶点落在同一等高线上 三角形的边与等高线交叉 要彻底消除以上问题，即使将等高线都作为约束处理， 还要提取骨架点-线并估计高程，然后加入TIN
泰森多边形（ Voronoi 分区）的边是 Delaunay 三角形边 的垂直平分线
(a) A set of data point
同样的点集可能生成不同的TIN
(a) A set of data
(b) Result 1
(c) Result 2
(d) Result 3
Delaunay三角网的 “empty circumcircle” principle
B B D D
C A A