An Algorithm for Delaunay Triangulation Using a Uniform Grid on Stochastic Clustered-Dot Screens
基于均匀网格的Delaunay三角网算法在随机聚合网屏中的应用

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.