当前位置:刘伯温火凤凰公式网 > 三角剖分 >

请问什么是双向插入法?

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  展开全部逐点插入法进行构网,分析该算法中制约运行速度的因素,在三角网拓扑关系、三角形的查找、LOP算法(Local Optimization Procedure)等方面进行了优化处理,使之有了较高的执行效率。

  在采用逐点插入进行Delaunay三角剖分的过程中,存在大量的查询操作,利用数据结构提供三角形之间的拓扑信息,能够有效地提高算法效率。边结构应包含点与三角形的信息,三角形结构应包含点与边的信息,再考虑到构网过程中动态的数据更新,算法中采用了双向链表结构,以方便于剖分过程中新旧边(三角形)的添加、删除工作。

  逐点插入法是Lawson在1977年提出的,该算法思路简单,易于编程实现。基本原理为:对于已有的三角网络,向其中插入一点,该点与包含它的三角形三个顶点相连,形成三个新的三角形,然后逐个对它们进行空外接圆检测,通过交换对角线的方法来保证所形成的三角网为Delaunay三角网。

  在按a进行剖分时,添加了三条新边及三个新三角形NT,删除了旧三角形T。同样,在b的情况中,记录点所在的边E,根据拓扑关系,找出该边的左右相邻三角形T1,T2,添加四条新边和四个新三角形NT,删除T1,T2以及边E。

  构网的关键是对新剖分出的三角形用LOP算法进行优化,其基本过程为:新三角形与周围的三角形构成共用同一条对角线的四边形,逐个对四边形中的两个三角形进行空外接圆检测,如果满足空外接圆准则,则略过。如果不满足,则用另一对角线替换现有对角线,在交换对角线后,又会产生相应的新四边形,继续进行空外接圆检测。这种方法可连续进行,直到全部满足空外接准则为止。这个过程是随着数据点P的逐次插入,与三角剖分同时进行的,可以通过递归调用优化程序来实现。

http://idagoldadv.com/sanjiaopoufen/106.html
点击次数:??更新时间2019-06-03??【打印此页】??【关闭
  • Copyright © 2002-2017 DEDECMS. 织梦科技 版权所有  
  • 点击这里给我发消息
在线交流 
客服咨询
【我们的专业】
【效果的保证】
【百度百科】
【因为有我】
【所以精彩】