经过20 多年的研究,自动生成Delaunay 三角网的算法已趋于成熟。它们基本上可分为分治算法、逐点插入法、三角网生长法等3 类。其中前两类较第3 类在应用上更加广泛。但即使这两类算法也分别存在着时间和空间效率上的缺陷,使它们的应用受到了一定的限制。提出了一个融以上两类算法优点于一体,兼顾空间与时间性能的合成算法。经测试,它的运算效率大大高于逐点插入法,在大多数情况下,也高于分治算法,在分割阈值约为总数据量的十分之一时,效率最高。

A wide variety of algorithms have been proposed to construct triangulation. They fall into three broad categories: divide-and-conquer, incremental insertion and triangulation growth. The first two groups of the methods have been extensively applied to many disciplines because of their easiness in implementation. They are, however, constrained either by their computational inefficiency or by their stringent demand on computer memory. In this paper a hybridized method is proposed to take advantage of both algorithms’ strengths so that these limitations could be overcome. In a test of 2533 points, the computation efficiency of the hybridized method is much higher than that of incremental insertion method in all cases, and is also higher than that of divide-and-conquer method in most cases. The best efficiency is achieved when the data points are partitioned into one-tenth of the original size.