【摘要】 局部变换法和Watson算法是属于逐点添加、局部优化的离散点集Delaunay三角剖分的常用方法,不同的加点次序对这两种算法的局部优化影响较大。研究发现按位置相邻次序加点的方法易产生外接圆较大的扁平三角形,引起较多三角形的局部优化,而按随机次序加点,网格生成过程中网格单元相对匀称,局部优化的三角形较少。以激光点扫描采集的数据为例,统计分析了局部优化三角形的数量及分布特征,点数大于50000时,相邻次序加点方法局部优化三角形的总量是随机次序加点方法的1.6倍以上。建立离散数据的矩形空间索引,按索引轮流加点,点序对局部优化的影响降低,相邻次序加点方法局部优化的三角形总量是随机次序加点方法的1.1~1.3倍,其中随机次序加点与没有空间索引的随机次序相比,局部优化的三角形数量仅增加了约1%。更多还原

【Abstract】 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.更多还原