关键词: Delaunay, 三角网生长法, 分区搜索

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