GIS基础-CDT构造算法之两步法

有下面五种方法：

约束图法

分割-合并算法

加密算法

Shell三角化法

两步法

两步法构造CDT是目前采用最多的CDT构建方法，先构建无约束三角网，后引入约束线段（调整过程）。Sloan采用连续的对角线交换法实现约束线段的嵌入；Floriani的算法则采用简单多边形D三角化的方式实现之。

约束三角网的对角线交换迭代思想

基本术语

影响域：约束边所经三角形构成的区域；

对角线：影响域内每一条边；

起始点：约束边的一端点；

目标点：约束边的另一端点；

目标

从起始点出发，按照一定的规则逐步交换对角线，最终使起始点和目标点相连。

基本思路

从起始点出发，对遇到的每条对角线的可交换性进行判断，可交换就交换，不可交换就判断下一条，到达最后一条对角线后，第一轮交换结束。然后从头再来，开始下一轮，直到约束边的加入。

约束三角网的对角线交换迭代算法步骤

STEP1

形成初始D_三角网（可或不含约束线段的顶点，但有不同处理）。

STEP2

对每一约束线段，检查是否已是三角形的边；是则检查下一约束线段，否则找出与该约束线段相交的所有三角形边，存入相交边表中。

STEP3 交换相交边

① 如共用相交边的两三角形构不成严格的凸四边形，则该边仍放回相交边表中

② 构成严格的凸四边形，则交换对角线；检查新的对角线是否与当前约束线段相交，相交则放入相交边表中；不相交则放入不相交边表中；

③ 对不相交边表中每条边进行局部三角网优化处理。

多对角线交换循环算法实例