论文部分内容阅读
Voronoi图是一种用于无人机航路规划的图形算法,其得到的初始航路为相邻威胁中心连线的垂直平分线,因而会穿越覆盖范围较广的威胁源。引入计算几何学中的Laguerre图用于航路规划,证明了当两个威胁区域不相交时,Laguerre图生成的初始航路必然从它们之间的空隙内穿过。针对Laguerre图生成算法不易实现的问题,提出一种基于Delaunay图的Laguerre图构造算法,其时间复杂度为线性对数阶。仿真结果证明了Laguerre图在解决航路规划问题上的有效性,所提构造算法的运行时间能够满足在线规划的要求。
The Voronoi diagram is a graphical algorithm used for UAV routing planning. Its initial route is a vertical bisector of the connection of adjacent threat centers and therefore crosses a wide range of threat sources. The introduction of Laguerre plots in computational geometry for route planning proves that the initial route generated by the Laguerre plot inevitably passes through the gap between the two threat zones. Aiming at the problem that Laguerre graph generation algorithm is not easy to be implemented, a Laguerre graph construction algorithm based on Delaunay graph is proposed, whose time complexity is linear logarithm. The simulation results prove the validity of Laguerre graph in solving the route planning problem, and the proposed algorithm can meet the requirements of online planning.