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

     有下面五种方法：

      约束图法

      分割-合并算法

      加密算法

     Shell三角化法

     两步法

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

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

     基本术语

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

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

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

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

     目标

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

     基本思路

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

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

     STEP1

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

     STEP2

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

     STEP3 交换相交边

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

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

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

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