摘要
Delaunay三角网一直是一个重要而有意义的研究课题 ,并具有极其广泛的用途 .经过 2 0多年来的研究 ,它的生成算法已趋于成熟 .为了满足印刷、印染系统中随机聚合网屏生成的实时性需要 ,将一种新的算法引入到FM网屏技术中 ,并首先简要介绍了 Delaunay三角网的特性及生成算法的分类 ;然后主要介绍了一种基于均匀网格的 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.
出处
《中国图象图形学报（A辑）》
CSCD
北大核心
2002年第5期495-500,共6页
Journal of Image and Graphics
基金
国家自然科学基金 (69873 0 2 8) (69973 0 2 8)
高等学校优秀青年教师教学科研奖励计划资助
