文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 一种简单多边形Delaunay三角剖分的约束生长算法
侵权投诉

一种简单多边形Delaunay三角剖分的约束生长算法

约束生长算法是生长算法的一个扩展.将两者结合可实现任意数据域的Delaunay三角剖分。提出了一种简单多边形三角剖分的约束生长算法。该算法的思想是基于生长算法.基边向外扩展时,增加了2个约束条件,算法思路简单。易于编程实现.且生成的三角网是Delaunay三角网。

维普资讯 doc.guandang.net

7 4

长江大学学报 (自科版)

20 0 6年 3月

边相交,且点 V与 V,。 V斗夹角为最大,接 V斗, V三点组成三角形,连 -V, 将边的使用计数 n d e e o n E gUsC u t加 1在边数组链中分别检查该三角形的另两边,和边 W斗是否存在。。如果不存在,将该边的使用次数 定为 1并存入到边数组的末尾},否则,将该边的次数定

为 2然后转步 4,。

步 4取边数组链中下一条未扩展边作为待扩展的基边,查组成该边是否边界边,方法可以通过检其 组成该边的两顶点的索引号是否相邻来判别,索引号为零及索引号为最大的两点 (即首末两点)是相邻。也

如果不是边界边且边的使用次数不为 2转步 3否则,束该边的扩展,将边的使用计数 n d e e—,;结并 E gUsC o n加 l ut。

步 5重复步 4直至三角形的使用计数 n d e e o n的值与边数组链中的边的总数相等时,, E gUsC u t即对所有的边作一次循环,结束多边形的三角剖分。

2结

果

为验证上述算法,笔者用 Vi a C++6 0编程语言对算法给予实现, s l u .并用一系列数据对算法进行了 测试,实验结果之一如图 l所示。为了说明本算法剖分多边形后的网形形态好,文献 I]用 -中的实验数据 4

l两者网形上J 1 - 00 .0 _ .‘ 进行了测试,实验结果如图 2所示。文献[] 4对该数据剖分的结果如图 3所示, .L明显的差在有 别。从图 3中可以看出其三角形的形态较差,出现了很多细长三角形。实验结果有效地说明本文算法在网形方面的优越性。本文算法也省去了对构成多边形的顶点的凸凹性判断,效地降低了算法的复杂度。有 同时笔者将本文算法与无约束 TI的算法相结合, N实现了带孔等约束数据域的三角剖分。 一 . .

田 1多边形的剖分实例

圈 2约束生长法三角剖分 的实验结果

圈 3文献[] 4算法剖分的结果

[考文献]参 []卫东 .泽圣 .=维任意城内点集的 Dea ny三角划分的研究[] 1闶唐 lu a J .计算机学报 .9 5 1 ( ) 3 7 3 4 1 9,8 5 5~ 6 .

[] z马小虎,志庚,潘石教英 .基于凹凸顶点判定的简单多边形 D l ny三角剖分[]计算机辅助设计与图形学学报, 9 9 1 ( ) 1 . e ua a J. 1 9,1 1。~3 []杰 .于凹凸顶点判定的简单多边形的三角削分[]小型微型计算机系统 .0 0 2 ( )9 4 7 . 3杨基 J. 2 0, 19 7 ̄9 5 [] 4刘强,李德仁 .基于=叉树思想的任意多边形三角剖分递归算法[]武投

大学学报( J.自然科学版 )2 0,7 5 2 ̄5 2,0 2 2 ( )5 8 3 .

[编辑]洪云飞

一种简单多边形Delaunay三角剖分的约束生长算法

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email