面向航路规划的Laguerre图构造算法

被引：14

作者：

王树磊 ^{[1
,2
]}

魏瑞轩 ^{[1
]}

沈东 ^{[1
]}

祁晓明 ^{[1
]}

罗鹏 ^{[2
]}

机构：

[1] 空军工程大学无人机运用工程系

[2] 中国人民解放军部队

来源：

系统工程与电子技术 | 2013年 / 35卷 / 03期

关键词：

航路规划; Laguerre图; Voronoi图; Delaunay图; 无人机;

D O I：

暂无

中图分类号：

V219 [相关学科的应用];

学科分类号：

08 ; 0825 ;

摘要：

Voronoi图是一种用于无人机航路规划的图形算法,其得到的初始航路为相邻威胁中心连线的垂直平分线,因而会穿越覆盖范围较广的威胁源。引入计算几何学中的Laguerre图用于航路规划,证明了当两个威胁区域不相交时,Laguerre图生成的初始航路必然从它们之间的空隙内穿过。针对Laguerre图生成算法不易实现的问题,提出一种基于Delaunay图的Laguerre图构造算法,其时间复杂度为线性对数阶。仿真结果证明了Laguerre图在解决航路规划问题上的有效性,所提构造算法的运行时间能够满足在线规划的要求。

引用

页码：552 / 556

页数：5