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

计算机工程与应用 ›› 2013, Vol. 49 ›› Issue (23): 191-194.

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

滑斌杰，林立忠，柴忠良

石家庄学院计算机系，石家庄 050035

出版日期:2013-12-01 发布日期:2016-06-12

Research on discrete generation algorithm of Voronoi diagram based rough area

HUA Binjie, LIN Lizhong, CHAI Zhongliang

Department of Computer, Shijiazhuang University, Shijiazhuang 050035, China

Online:2013-12-01 Published:2016-06-12

摘要/Abstract

摘要： Voronoi图是计算几何的一个重要分支，粗糙域Voronoi图是Voronoi图概念在复杂生成面上的扩展。提出了粗糙域Voronoi图的概念并利用A*算法计算生成面上点与各母点的最短路径对其进行离散生成。为了降低粗糙域Voronoi图离散生成算法的复杂度，对粗糙域下A*算法估价函数权值与粗糙域粗糙特性的关系进行了深入探索。实验结果表明，A*算法估价函数权值与粗糙域粗糙特性正相关，并以此获得A*算法估价函数的最优权，大大降低了粗糙域Voronoi图离散生成算法的复杂度。

关键词: Voronoi图, 粗糙域, A*算法, 估价函数, 最优权

Abstract: Voronoi diagram is an important branch of computational geometry and Voronoi diagrams based rough area are extensions 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 algorithm 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.

Key words: Voronoi diagram, rough area, A-star algorithm, evaluation function, optimal weight

滑斌杰，林立忠，柴忠良. 粗糙域Voronoi图离散生成算法研究[J]. 计算机工程与应用, 2013, 49(23): 191-194.

HUA Binjie, LIN Lizhong, CHAI Zhongliang. Research on discrete generation algorithm of Voronoi diagram based rough area[J]. Computer Engineering and Applications, 2013, 49(23): 191-194.

[1]	孔继利，张鹏坤，刘晓平. 双向搜索机制的改进A*算法研究[J]. 计算机工程与应用, 2021, 57(8): 231-237.
[2]	槐创锋，郭龙，贾雪艳，张子昊. 改进A*算法与动态窗口法的机器人动态路径规划[J]. 计算机工程与应用, 2021, 57(8): 244-248.
[3]	韩晓微，韩震，岳高峰，崔建江. 救灾无人机的优化A*航迹规划算法[J]. 计算机工程与应用, 2021, 57(6): 232-238.
[4]	赵伟，吴子英. 双层优化A*算法与动态窗口法的动态路径规划[J]. 计算机工程与应用, 2021, 57(22): 295-303.
[5]	刘子豪，赵津，刘畅，赖坤城，王玺乔. 基于改进A*算法室内移动机器人路径规划[J]. 计算机工程与应用, 2021, 57(2): 186-190.
[6]	王晓军，王博，杨春霞，晋民杰，陈海波. 紧致密集Auto Store系统AGV路径规划与避碰策略[J]. 计算机工程与应用, 2021, 57(15): 259-270.
[7]	刘建娟，薛礼啟，张会娟，刘忠璞. 融合改进A*与DWA算法的机器人动态路径规划[J]. 计算机工程与应用, 2021, 57(15): 73-81.
[8]	王保剑，胡大裟，蒋玉明. 改进A*算法在路径规划中的应用[J]. 计算机工程与应用, 2021, 57(12): 243-247.
[9]	华洪，张志安，施振稳，陈冠星. 动态环境下多重A*算法的机器人路径规划方法[J]. 计算机工程与应用, 2021, 57(10): 173-180.
[10]	袁洋，叶峰，赖乙宗，赵雨亭. 结合负载均衡与A*算法的多AGV路径规划[J]. 计算机工程与应用, 2020, 56(5): 251-256.
[11]	王磊，孙力帆. 引入必经点约束的路径规划算法研究[J]. 计算机工程与应用, 2020, 56(21): 25-29.
[12]	王凡，李铁军，刘今越，赵海文. 基于BIM的建筑机器人自主路径规划及避障研究[J]. 计算机工程与应用, 2020, 56(17): 224-230.
[13]	胡蔚旻，靳文舟. 改进平滑A*算法的多AGV路径规划[J]. 计算机工程与应用, 2020, 56(16): 204-210.
[14]	钟志峰，易明星，陈智军，谭普，曾张帆. 基于改进A*算法的导购路径规划方法[J]. 计算机工程与应用, 2019, 55(5): 129-134.
[15]	吴鹏，桑成军，陆忠华，余双，方临阳，张屹. 基于改进A*算法的移动机器人路径规划研究[J]. 计算机工程与应用, 2019, 55(21): 227-233.