约束生长算法是生长算法的一个扩展.将两者结合可实现任意数据域的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三角剖分算法.新 的算法不仅使其剖分得到的最小单元(三角形)...
带岛屿多边形Delaunay三角剖分算法_数学_自然科学_专业资料。第 3 0 卷第 5...1 带岛屿多边形 设 P1 , P2 , …, Pn ( n > 1) 均为简单多边形 , ...
笔者 对简单多边形三角剖分算法进行了研究 , 提出了基于最小 内角判定的简单...使 三角 网具有良好的形态质量 , 本算法还可进一步用于 Delaunay三角剖分 。 ...
基于Delaunay三角网的任意多边形三角剖分算法研究_专业资料。文章通过分析现有多边形三角剖分算法,给出一种基于Delaunay三角网的任意复杂多边形三角剖分的改进算法。...
复杂多边形的Delaunay三角剖分研究_数学_自然科学_专业资料。长江大学学报 ( ...目前 ,简单 多边形的Dluaeny三角 剖分 算法已 经非 常成 a 熟 ,但对于 ...
本文提出了一种新的基于凹凸顶点 判定的简单多边形的 Delaunay 三角 剖分生成算法, 是作 者在进行表 面重构及三 角 形网格简化研究中得到的实用结果, 并得到...
一种改进的快速Delaunay三角剖分算法_专业资料。Delaunay三角剖分算法是构建... Delaunay三角网剖分中的... 19人阅读 3页 2.00 简单多边形的动态De...
现有的很多点云三维重建算法, 其中三角剖分算法由其简单实用的曲面表达形式和易于渲染、 添加纹理等特性得到了广泛的应用,Delaunay 三角网[2]所具有 的空圆特性和...
一种改进的2D-Delaunay三角剖分算法_专业资料。针对大规模工程中空间数据点的采集不均匀、等值矩形格网格分块会出现严重的两块数据点比例无效,影响Delaunay子三角...
Delaunay三角剖分算法_信息与通信_工程科技_专业资料。三角剖分:假设V是二维... 简单多边形的动态Delaun... 7页 免费 实现约束Delaunay三角剖... 12页 ...
热门文档