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

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

Laguerre diagram construction algorithm for path planning

The Voronoi diagram is a graph-based commonly used technique for creating the initial feasible path sets of an unmanned aerial vehicle (UAV), whose edges are the perpendicular bisector of the two closest threat sites. It does not take the threats’ effective range into consideration, thus certain paths may go through some of the threat zones. To overcome the drawback of the Voronoi diagram, an important structure in computation geometry, Laguerre diagram, is introduced. It is proved that the generated initial paths will fall inside the interspaces of two closest threat zones when they do not intersect. Since the construction algorithm is difficult to implement, a new approach to build the Laguerre diagram based on the Delaunay graph is developed, whose time complexity is O(nlg n). Simulation results demonstrate the validity of the Laguerre diagram for path planning, and verify that the runtime of the construction algorithm can fulfill the requirement of on line planning.