首页 理论教育德洛奈三角划分法-飞行器协同导控

德洛奈三角划分法-飞行器协同导控

【摘要】:为在多障碍环境下确定导弹飞行的待选航迹节点,在此引入德洛奈三角划分法来确定导弹可能要飞经的边,以便为进一步设计搜索算法奠定基础。令J是点集P的一个三角划分,假设其含有m个三角形,将这m个三角形所包含的3m个角(α1,α2,…假设P是平面上的一个点集合,那么P的角度最优三角划分就是P的德洛奈三角划分。有关德洛奈三角划分的具体实现过程可参考文献[41],这里不再详述。

为在多障碍环境下确定导弹飞行的待选航迹节点,在此引入德洛奈三角划分法来确定导弹可能要飞经的边,以便为进一步设计搜索算法奠定基础。接下来,介绍相关引理。

【引理3.1】令P表示平面上一系列点构成的点集{p1,p2,…,pn },则P的三角划分定义为以P中各点为顶点的最大平面划分,该划分的特点为P中每两条边都互不相交。

【引理3.2】令J是点集P的一个三角划分,假设其含有m个三角形,将这m个三角形所包含的3m个角(α1,α2,…,α3m)升序排列并构成角度向量A(J):=(α1,α2,…,α3m)。令J′表示点集P的另一个三角划分,其角度向量为A(J′):=(,…,)(,…,为此时m个三角形的3m个角)。如果A(J)以字典式排序法大于A(J′),则有A(J)>A(J′)。如果点集P中的一个三角划分J对于其他三角划分J′都满足上式,则称该三角划分J是角度最优的。

【引理3.3】假设P是平面上的一个点集合,那么P的角度最优三角划分就是P的德洛奈三角划分。通常情况下,P中点集的德洛奈三角划分有且只有一种方式。

为计算给定点集的角度最优三角划分,可以通过对不合法边进行翻转来将所有边都合法化,进而得到角度最优的三角划分。有关德洛奈三角划分的具体实现过程可参考文献[41],这里不再详述。