基于Voronoi图的无人机快速航迹规划研究

Voronoi图的快速构建是快速完成基于Voronoi图的航迹规划的关键。针对Voronoi图构建效率不高的问题,提出了一种快速构建Voronoi图的方法。首先,利用改进的Bowyer-Watson算法构建Delaunay三角网。在确定待插入点的影响域时,引入bool类型的数组对已构建三角网中的三角形是否为Delaunay三角形进行标记,从而缩小三角形的遍历范围,加快Delaunay三角网的构建速度。然后用间接法得到Voronoi图。此外,对航迹规划过程中起始航迹和终止航迹的确定进行了讨论,完成了基于Voronoi图的无人机航迹规划。结果表明,采用提出的间接法能快速完成Voronoi图的构造。当母点(威胁点)为20 000个时,只需要20 s的时间。对快速完成无人机的航迹规划具有重要的意义。

Fast Route Planning for UAV Based on Voronoi Diagram

The key of path planning based on Voronoi diagram is to build Voronoi diagram. Considering the problem that the algorithm of building Voronoi diagram is of low efficiency, the paper put forward a method of building Voronoi diagram rapidly. Firstly, using the improved Bowyer-Watson algorithm to construct Delaunay triangulation. In obtaining the influence domain of the insertion point, the paper introduced an array of bool to mark whether the triangle of triangulation was Delaunay triangle, which narrowed the scope of traversing triangle, thus accelerating the speed of building Delaunay triangulation. After the construction of Delaunay triangulation, then used the indirect method to generate Voronoi diagram. Furthermore, the paper discussed the obtain of starting path and ending path and finally completed the route planning for UAV based on Voronoi diagram. The result shows that the indirect way proposed can quickly build Voronoi diagram. It only needs 20s when the number of point is 20000, which has great significance in rapidly completing route planning for UAV.