快速粗糙域Voronoi图离散生成算法研究

Reseach on Fast Discrete Generation Algorithm of Voronoi Diagram Based Rough Area

Voronoi图是计算几何的一个重要分支,粗糙域Voronoi图是Voronoi图概念在复杂生成面上的扩展,对其离散生成进行研究有重要的现实意义。粗糙域Voronoi图离散生成一般采用最短路径法,算法的复杂度很高,很难适应宽范围、多母点的粗糙域分隔。为了降低粗糙域Voronoi图离散生成的复杂度,文章提出了加权的广度搜索算法对粗糙域Voronoi图进行离散生成,并利用边界方向直方图分析对粗糙域生成面分隔的有效性进行了验证。实验结果表明,本算法对粗糙域的分隔是有效的、解决了一般算法的空穴问题且大大降低了离散生成算法的复杂度。

Voronoi Diagram is an important branch of computational geometry and Voronoi Diagram based rough area is extension of Voronoi Diagram in complex generating surface. The study on the discrete generation of Voronoi Diagram based rough area has impor- tant practical significance. In general, the shortest path algorithm is used for the discrete generation of Voronoi Diagram based rough area and the complexity of generating algorithm is very high. so, it is difficult to adapt to a wide range and multi generators rough area partition. For reduce the complexity of generating algorithm, in this paper, a weighted breadth search algorithm is proposed for the dis-crete generation of Voronoi Diagram based rough area and the validity of the algorithm is verified by the analyzing of the Edge direction histograms which generated from regions of Voronoi Diagram. Experience results show that the algorithm is effective and solves the Hole-problems of the general algorithm, and remarkably reduces the complexity of the discrete generation algorithm.