点序对Delaunay三角剖分局部优化的影响  

Influence of Point-inserting Order on Local Optimization of Delaunay Triangulation

作　　者：徐永安[1] 沈玲玲[1] 刘毓[1] 陈崚[1] 宋长宏[2] 

机构地区：[1]扬州大学信息工程学院,江苏扬州225009 [2]北京石油化工学院经济管理学院,北京102627

出　　处：《工程图学学报》2010年第5期1-6,共6页Journal of Engineering Graphics

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

摘　　要：局部变换法和Watson算法是属于逐点添加、局部优化的离散点集Delaunay三角剖分的常用方法,不同的加点次序对这两种算法的局部优化影响较大。研究发现按位置相邻次序加点的方法易产生外接圆较大的扁平三角形,引起较多三角形的局部优化,而按随机次序加点,网格生成过程中网格单元相对匀称,局部优化的三角形较少。以激光点扫描采集的数据为例,统计分析了局部优化三角形的数量及分布特征,点数大于50000时,相邻次序加点方法局部优化三角形的总量是随机次序加点方法的1.6倍以上。建立离散数据的矩形空间索引,按索引轮流加点,点序对局部优化的影响降低,相邻次序加点方法局部优化的三角形总量是随机次序加点方法的1.1~1.3倍,其中随机次序加点与没有空间索引的随机次序相比,局部优化的三角形数量仅增加了约1%。Local transformation and Watson method are the common Delaunay triangulation algorithms which insert point by point and conduct local optimization.The algorithm’s efficiency of large-scale scattered data is greatly different from the one of adjacent data.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.As an example,a laser scan point set is divided into a few subsets from 10000 points to 100000 points,then the triangular mesh of these subsets are created respectively by adding point in sequence and random.When the point number is larger than 30000,the speed of adding point randomly is faster two times than the one of adding point in sequence.

关 键 词：计算机应用 离散数据 DELAUNAY三角剖分 网格 局部优化 

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