Analysis And Improvement On Local Optimization Of Incremental Delaunay Triangulation

With the development of equipments and technologies of data acquisition, and the complexer object of scientific calculation and engineering analysis, triangulation of large scale scatter data causes to be researched widely. How to raise the creating speed of triangular mesh is one of the hottest research points. Local transformation and Watson method are the popular algorithms of Delaunay triangulation in engineering. Both algorithms belong to incremental Delaunay triangulation of adding point by point and local optimization. The quick orientation of mesh containing new point and the decrease of scale of local optimization are keys of incremental Delaunay triangulation. Rectangular space index of scatter data can improve the efficiency of search of mesh containing new point. On this basis, the following researches have been done:(1) Different inserting point orders influence the local optimization's efficiency of local transformation and Watson algorithm. Adding point by adjacent sequence, sliver triangle of large circumcircle is frequently created. This case causes local optimization of many triangles and reduced speed of creating triangular mesh. Adding point in random, triangular mesh is created uniformly and local optimization of fewer triangles, shortening the time of local optimazation. A laser scan point set as an example, the number and distribution of local optimized triangles are analyzed. When points larger than 20000, adding point in random can improve the building speed of triangular mesh 1 time more than in sequence. The more data, the higher efficiency.(2) Rectangular space index of scatter points is set up. Adding point by index sequence, the points order influence local optimization fall. The number of local optimized triangles by adjacent sequence is between 1.1 and 1.3 times more than in random. Adding point in random with index compared without it, the number of local optimized triangles is increased about 1 percent.(3) The situation of the new point in a triangle and whether the point is contained in triangle's circumcircle are important factors of creating correct Delaunay triangulation. The space distribution of points is complex in large scale scatter data. The floating precision is limited. When the point's position coordinate is large, area coordinates, the center and radius of circumcircle can bring bigger calculation error. Calculation error can lead to the wrong discrimination of the location relationship between point and triangle, the containing relationship of point and triangle's circumcircles, and then wrong geometric topology triangular mesh is created. A new method is presented that improves the calculation precision of area coordinates and the centre and radius of circumcircle with relative coordinates. 393252 points of terrain data which are extracted from contour map as a test, the calculation precision of relative coordinates can create correct geometric topology Delaunay triangular mesh.Applying the above production to the data processing of reverse engineering and geological modeling, Delaunay triangular mesh can be created rapidly and effectively. The ratio of triangular circumradius to the longest side of triangle can evaluate triangular mesh quality. When move or add points are permitted, malformation unit are optimized.