计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (16): 197-200.DOI: 10.3778/j.issn.1002-8331.2009.16.058

• 图形、图像、模式识别 • 上一篇    下一篇

先边界后方差的改进的Delaunay三角网划分算法

杨 勇,顾耀林   

  1. 江南大学 信息工程学院,江苏 无锡 214122
  • 收稿日期:2008-04-03 修回日期:2008-06-24 出版日期:2009-06-01 发布日期:2009-06-01
  • 通讯作者: 杨 勇

Improved first boundary and last variance algorithm in Delaunay triangulation

YANG Yong,GU Yao-lin   

  1. School of Information Engineering,Jiangnan University,Wuxi,Jiangsu 214122,China
  • Received:2008-04-03 Revised:2008-06-24 Online:2009-06-01 Published:2009-06-01
  • Contact: YANG Yong

摘要: 基于Delaunay三角网划分的两个特性:最大最小特性与空外接圆特性,论文构网过程分三步:生成边界,构造内三角网,对边界与内三角网之间的空洞进行处理。具体实现过程:先通过边界点集构造边界,再在已生成的边界内,利用区域生长法思想,以及方差的方法对非边界点集进行插入,来构造内三角网,最后采用等比例划分方法处理边界与边界内三角网之间的空洞。实验表明,改进后,不需要对每次生成的边进行判断是否是边界边,插入的点是否是边界点的处理,避免了复杂构网的过程,并且快速实现了物体表面Delaunay三角网划分的目的。且上述方法简单、快捷,易于实现,经实验证明是行之有效的。

Abstract: Based on the two features of the Delaunay triangulation:maximum and minimum feature,empty circumcircle feature,in this article the procedure of building triangulation network needs three steps:creating boundary,building up the interior triangulation network,coping with the hole between the boundary and the interior triangulation network.The detial process is that we can build up the boundary throught the boundary point set at first,then we can form the inside nework by the method of variance and aera growth—inserting the non-boundary points,at the last,we shall deal with the hole between the boundary and the interior network boundary in the method of equal proportion partition.After the improvement,we needn’t judge the new born edges and the points are whether or not belonged to the boundary,and avoid the complex process,acquire the Delaunay triangulation surface of the object quickly.Experiment results demonstrate that the method proposed is simple and effective.