Delaunay三角网生长算法改进与实现_周婷.pdf

2013 9 September 2013 34 5 JOURNAL OF GRAPHICS Vol.34 No.5 Delaunay 430072 —— Microsoft Visual Studio 2008 C++ Delaunay P 221.1 A 2095-302X (2013)05-0012-04 An Improved Delaunay Triangle Network Growth Algorithm and its Implementation Zhao Ting, Peng Zhenghong, Mi Xinwu ( School of Urban Design, Wuhan University, Wuhan Hubei 430072, China ) Abstract: A brief introduction is given for the general Triangle network growth algorithm. An improved algorithm named as “the partition search method of the third point” is provided. First, a series of circular arcs are used to divide the area of discrete points into multiple partitions. Then - the third point is restricted to be searched only in the current partition and the next adjacent partition when building the triangle network. After all the discrete points are added into the triangle network in current partition, the search can be moved into the next partition. Last, the C++ programming language is used to test the algorithm in Microsoft Visual Studio 2008 environment. The result shows that the improved algorithm can improve the speed of building the network, and the generated triangular shape is good. Key words: Delaunay; triangle network growth algorithm; partition search DEMDigital Elevation Model DEM GIS   20130715201