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

有下面五种方法:

约束图法

分割-合并算法

加密算法

Shell三角化法

两步法

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

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

基本术语

影响域:约束边所经三角形构成的区域;

对角线:影响域内每一条边;

起始点:约束边的一端点;

目标点:约束边的另一端点;

目标

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

基本思路

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

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

STEP1

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

STEP2

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

STEP3 交换相交边

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

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

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

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

GIS基础-约束DT(CDT)的三角化准则 GIS应用-3D扫描技术保护1964年万国博览会

作者:,GIS爱好者。
分享本文,请您带上本文链接
分享到:

发表评论