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

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

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

维普资讯 doc.guandang.net

长江大学学报 (自科版) 20年 3第 3第 1理工卷 06月卷期 J unl f agz nvri N t c E i Ma.0 6 o. o 1 e&E g ora o n t U i s y( a i dt Y e e t S ) r2 0 .V 13N . i n S V

种简单多边形 Dea n y三角剖分的 lu a约束生长算法 一

刘少华,陈华军,罗小龙 (江学球学院,北荆 3 2 长大地科学湖州4 0 ) 43 [要]约束生长算法是生长算法的一个扩展 .特两者结合可实现任意数据域的 D l n y三角剖分。提出摘 e ua a 了一种简单多边形三角剖分的约束生长算法。该算法的思想是基于生长算法 .基边向外扩展时,增加了 2 个约束条件 算法思路简单。易于编程实现 .且生成的 Z角网是 D lu a - ea ny三角网。

[关键词]简单多边形}D lu a ea ny三角剖分,生长算法;约束[中围分类号]T 3 1 P 9[文献标识码]A [C mq]17—1 0 (o 6 1 0 3— 2¥i 6 3 4 9 2 o}0—0 7 0

多边形的三角剖分在计算几何、计算机图形学、科学计算可视化和图像处理等领域都有广泛的应

用,许多专家学者在此领域做了大量有益的探索。闵卫东给出了一个任意多边形的 D l ny三角剖 e ua a 分算法,其时间复杂性为 O(。。 N )文献[~3提出的算法思想都是基于凹凸顶点判定法:首先按顶点 2] 的凹凸性将多边形三角化,然后按最大一小内角准则,通过多次循环进行局部变换,得到 D lu a最 ea n y三

角剖分网。虽然这两种算法得到网形比较好,但要通过多次循环进行局部优化,从而加大了算法的复杂

度,也降低了算法的执行效率。文献[]给出了一种基于二叉树思想的多边形的三角剖分算法,该算 4法剖分的三角形的形态不理想。笔者提出一种新的简单多边形的三角剖分算法——附有约束条件的生长算法 (简称约束生长算法 ),该算法剖分多边形生成的三角网是 De u a角网,所以网形最稳定、最 l ny三 a 优。

1算

法

该算法由基边向外扩展生长时,除了考虑生长法向外扩展的的基本条件外,还要受到另外 2个约

束

条件的制约,于是把这种生长算法称为约束生长算法。2个约束条件描述如下: 1 )如果组成基边的两顶点相邻,即基边是边界边时,就不顾及它的右边是否有点,直接终止该基 边的扩展。

2用生长算法进行无约束离散数据域的三角剖分时, )基边向外扩展找满足条件的点 P, P必须满足点的条件是;在基边的右边且与基边两顶点连线组成的夹角为最大。笔者提出的约束生长算法中,条件在该被进一步限定,细描述如下:点 P在基边的右侧;点 P与两基边两点的连线不与边界边相交;详①② ③在满足上述两条件的前提下,还要使点 P与基边两顶点连线组成的夹角为最大。 简单多边形 D lu a角剖分的约束生长算法详细描述如下: ea ny三 步 l按逆时针方向顺序读人简单多边形的顶点,立多边形的顶点数组链,定义一变量 建 n d e e o n来记录边的使用计数, E g UsC u t并赋初值为零,然后转步 2。

步 2从组成多边形的顶点数组链中任取索引号相邻的两点斗和, 。 连接点 l和点组成三角+ 1 形的第一边,将该边 V有向,同)的使用次数定为 1并将它存人边数组链,该边作为基边,后 (下,把然 转步 3。

步 3在基边 V件 的右边,组成多边形的顶点数组中找一点,从使得边 W 及边 W…不与边界 [收稿日期]2 0— 1 5 0 5 1—1 [墓愈项目]江西省数字国土重点实验室开发研究娶金项目 ( LJ051;湖北省高等学校优秀中青年团队计划项目 ( '00) D 1200) . T 062。 2[作者简介]刘少华 ( 9 6 ) 1 7一,男,2 0年大学毕业,硕士,师, 00讲主要研究方向为三维 G S I数据模型、理论研究及图形算法分析。

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

第1页

你可能喜欢

热门文档

相关文档

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