大规模离散点集Delaunay三角剖分加点策略的分析  

Analysis on adding point scheme of large-scale scattered data Delaunay triangulation

作　　者：徐永安[1] 刘毓[1] 沈玲玲[1] 陈崚[1] 

机构地区：[1]扬州大学信息工程学院,江苏扬州225009

出　　处：《计算机工程与设计》2008年第20期5259-5261,共3页Computer Engineering and Design

基　　金：国家自然科学基金项目(60673060)

摘　　要：局部变换法和Watson算法是离散点集Delaunay三角剖分的常用算法,算法过程中逐点添加、局部优化是三角网格生成速度的重要影响因素。按位置相邻次序逐点添加时易产生外接圆较大的扁平三角形,引起较大范围的局部优化,三角网格的生成速度下降。在位置相邻次序的点集中随机选择部分点生成相对匀称的初始三角网格,再依次添加数据点,可有效减少局部优化消耗的时间,提高三角网格的生成速度。以激光扫描测量数据为例,切分为不同数量的点集进行三角剖分测试,当数据点数大于20000点时,采用部分随机点优化策略,其三角剖分速度比直接按位置相邻次序添加的方法提高一倍以上,且数据量越大,效率越高。Local transformation and Watson method are the popular algorithms of scattered data Delaunay triangulation. The procedure of adding point and local optimization are important factors which influence on the speed of creating triangular mesh. Adding point by adjacent sequence, sliver triangle of large circumcircle is frequently created. This case causes local optimization in larger scale and low speed of creating triangular mesh. A new method is presented that creates relative uniform initial triangular mesh by choosing random partial data from a point set and then adds point in turn. The method can reduce the time of local optimization and improve the speed of creating triangular mesh. A laser scan point set is divided into a few subsets of different number. These subsets are triangulated by the new and previous method respectively. When the point number is larger than 20000, the new method is faster one time than the previous one. The more data, the higher efficiency.

关 键 词：离散数据 三角剖分 网格 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]