麻辣GIS微信平台

更多 GIS 干货

微信关注不错过

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

有下面五种方法:

约束图法

分割-合并算法

加密算法

Shell三角化法

两步法

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

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

基本术语

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

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

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

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

目标

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

基本思路

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

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

STEP1

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

STEP2

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

STEP3 交换相交边

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

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

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

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

相关阅读

麻辣GIS-Sailor

作者:

GIS爱好者,学GIS,更爱玩GIS。

声明

1.本文所分享的所有需要用户下载使用的内容(包括但不限于软件、数据、图片)来自于网络或者麻辣GIS粉丝自行分享,版权归该下载资源的合法拥有者所有,如有侵权请第一时间联系本站删除。

2.下载内容仅限个人学习使用,请切勿用作商用等其他用途,否则后果自负。

手机阅读
公众号关注
知识星球
手机阅读
麻辣GIS微信公众号关注
最新GIS干货
关注麻辣GIS知识星球
私享圈子

留言板(小编看到第一时间回复)