Improvement of generatin algorithm of Delaunay triangulation network for the whole scatter points and software development
Wenfang Zhao · Engineering of Surveying and Mapping · 2003
In this paper, we presented an improved algorithm for triangulation generation. Based on the original triangulation generation algorithm, we divide the whole scatter points into uniform grids and set up grid-index. In this way, we can quickly make the first triangle and then begin to expand the whole triangulation network. Second, we introduce the notion of close-point. During the process of expanding triangulation, the close-points are dynamically removed, which will accelerate the process of searching new points and generating new triangle. In addition, every triangle, except the first one, has actually only two sides that need to be expanded. We also apply this discovery to our algorithm. Futher, during the software development, we introduce Carray and Clist, the CLASS of MFC, to manage the data. Moreover, we create CLASS Cbuildtin that is used to generate the triangulation network and CLASS Craster that is used to generate the grid index, which can efficiently manage and deal with the data.