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

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

作　　者：滑斌杰[1] 习海燕 林立忠[1] 张静[1] 

机构地区：[1]石家庄学院计算机科学与工程学院,石家庄050035 [2]河北省广播电视科学技术研究所,石家庄050012

出　　处：《网络新媒体技术》2017年第4期33-38,共6页Network New Media Technology

基　　金：河北省技术创新引导计划(编号:15210141);河北省科技型中小企业技术创新基金(编号:14C26211300470)

摘　　要：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.

关 键 词：粗糙域 VORONOI图 加权广度搜索 边界方向直方图 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]