基于均匀网格的Delaunay三角网算法在随机聚合网屏中的应用

Delaunay三角网一直是一个重要而有意义的研究课题，并具有极其广泛的用途。经过20多年来的研究，它的生成算法已趋于成熟。为了满足印刷、印染系统中随机聚合网屏生成的实时性需要，将一种将的算法引处到FM网屏技术中，并首先简要介绍了Delaunay三角网的牧场考及生成算法的分类；然后主要介绍了一种基于均匀网格的Delaunay三角网生成算法在随机聚合网屏中的应用；最后给出了算法的正确性证明。经测试，该算法的运算速度相当快，具有接近于线性的时间复杂性，能够满足排版印刷、印染系统中随机聚合网屏生成的需要。

An Algorithm for Delaunay Triangulation Using a Uniform Grid on Stochastic Clustered-Dot Screens

Delaunay triangulation is widely applied in manifold fields and has a number of application dependent approaches. This paper briefly introduces its significant properties and popular generation algorithms. Then an empirically efficient algorithm for Delaunay triangulation using a uniform grid in 2D is introduced. This method first preprocesses the data, divides the whole point distributed area into grids with around the same number of grids and points, puts all points into corresponding grids. It begins with forms an initial triangle. While looking for connecting triangles, it puts all new edges of found triangles into a queue and remove the edges which are used by two triangles or are known as boundary edges out from the queue. Repeat the process until the queue is empty, then the triangulation is finished. This paper also shows the validity of the algorithm. The algorithm is very easy for implementation and uses computer resources of time and space more reasonably. Through tests with random generated data, its running speed proves fast and exhibits linear time complexity. It can meet the requirement of stochastic clustered dot screens in publishing, printing and dyeing systems.