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

Research on discrete generation algorithm of Voronoi diagram based rough area

作　　者：滑斌杰[1] 林立忠[1] 柴忠良[1] 

机构地区：[1]石家庄学院计算机系,石家庄050035

出　　处：《计算机工程与应用》2013年第23期191-194,214,共5页Computer Engineering and Applications

基　　金：河北省科技型中小企业技术创新基金(No.11C1303111004)

摘　　要：Voronoi图是计算几何的一个重要分支,粗糙域Voronoi图是Voronoi图概念在复杂生成面上的扩展。提出了粗糙域Voronoi图的概念并利用A*算法计算生成面上点与各母点的最短路径对其进行离散生成。为了降低粗糙域Voronoi图离散生成算法的复杂度,对粗糙域下A*算法估价函数权值与粗糙域粗糙特性的关系进行了深入探索。实验结果表明,A*算法估价函数权值与粗糙域粗糙特性正相关,并以此获得A*算法估价函数的最优权,大大降低了粗糙域Voronoi图离散生成算法的复杂度。Voronoi diagram is an important branch of computational geometry and Voronoi diagrams based rough area are exten- sions of Voronoi diagrams. In this paper, a conception of Voronoi diagram based rough area is proposed and it is generated with the minimum distance between points of forming face and mother-points which is calculated out using A-star algorithm. For reducing the complexity of generating algorithm, a research on relation between weight of evaluation function of A-star algo- rithm and character of rough area is launched. Experimental results show that the optimal weight of evaluation function positively correlates with the roughness characteristics of rough area. Based on this, the optimal weight of A-star algorithm is obtained and the complexity of generating algorithm of Voronoi diagrams based rough area is remarkably reduced.

关 键 词：VORONOI图 粗糙域 A'算法 估价函数 最优权 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]