[發明專利]一種用于航線規劃的最優路徑生成方法

有效

• 申請號: 201810030677.8
• 申請日: 2018-01-12
• 公開（公告）號: CN108225333B
• 公開（公告）日: 2020-03-24
• 發明（設計）人: 黃琦龍;卜卿;付強;劉唐興;茆超;張艷偉;黃山良
• 申請（專利權）人: 中國電子科技集團公司第二十八研究所
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 江蘇圣典律師事務所 32237
• 代理人: 胡建華;于瀚文

1.一種用于航線規劃的最優路徑生成方法，其特征在于，包括如下步驟：

步驟1，獲取轉彎點數據集合(P₁,P₂,...,P_N)，P_i表示第i個轉彎點，i取值為1～N，N為轉彎點總數，轉彎點數據即為航線轉彎過程序列；

步驟2，對轉彎點數據進行預處理；

步驟3，對航線進行分割處理，得到子航線序列；

步驟4，將航線轉彎過程序列表示為二叉樹，計算得到所有轉彎過程的全部信息；

步驟5，對子航線回溯處理；

步驟6，對二叉樹進行剪枝；

步驟7，輸出最優航線：搜索二叉樹中性能最好的葉子節點，將根節點到葉子節點的路徑提取并作為最優航線輸出；

步驟2包括：

步驟2-1，經緯度坐標轉換：將每個轉彎點經緯度數據轉換為XY坐標系下的坐標；

步驟2-2，轉彎點類型標注：C_i＝1時表示第i個轉彎過程的轉彎開始點，C_i＝2時表示轉彎圓心點，C_i＝3時表示轉彎結束點；

步驟2-3，如果一個轉彎點對應的轉彎方向已經指定，則標注該轉彎過程的轉彎方向，D_i＝1時表示順時針轉彎，D_i＝-1時表示逆時針轉彎；

步驟2-4，每個轉彎過程由轉彎開始點、轉彎圓心點、轉彎結束點和轉彎方向唯一確定；

步驟3包括：假設第i個轉彎點為轉彎結束點，則分別將前后兩側離第i個轉彎點最近的非轉彎結束點的位置設置為航線分割點，根據該方法對整個航線進行分割得到子航線序列；

步驟4包括：通過二叉樹的形式表示轉彎過程序列，以上一個轉彎過程為父節點進行分支，設置當前轉彎方向順時針為一個分支，當前轉彎方向逆時針為另外一個分支，由于每個轉彎過程由轉彎方向、轉彎開始點、轉彎圓心點和轉彎結束點唯一標識，當輸入一個點信息后，該轉彎過程的另外兩個未知點的位置信息利用相鄰轉彎點已獲取的信息進行解算，分為如下四種情況：

情況一，已知當前轉彎過程的轉彎開始點和下一轉彎過程的轉彎開始點情況：

情況一中，已知第i個轉彎過程的轉彎開始點位置坐標和第i+1個轉彎過程的轉彎開始點位置坐標則有如下方程：

其中，(a,b)為轉彎圓心點坐標指向轉彎結束點坐標的向量,r為轉彎半徑，公式(1)中第一個方程表示向量長度等于轉彎半徑，第二個方程表示向量(a,b)與轉出切線垂直，通過求解上述方程獲得向量(a,b)的值，其中，轉彎圓心點坐標通過下述公式(2)獲得：利用第i-1個轉彎過程的轉彎結束點位置坐標和第i個轉彎過程的轉彎開始點位置坐標得到第i個轉彎過程轉入切線與正北方向的夾角θ，則有：

情況二，已知當前轉彎過程的轉彎開始點和下一轉彎過程的轉彎圓心點情況：

情況二中，根據下一點的轉彎方向有兩種情況：順時針和逆時針；

當下一點轉彎方向為順時針時，有如下方程：

其中，根據公式(2)得到，利用公式(4)和當前轉彎過程的轉彎方向，求出(a,b)，根據公式(3)得到當前轉彎過程的轉彎結束點信息；

當下一點轉彎方向為逆時針時，有如下方程：

其中，根據公式(2)得到，利用公式(5)和當前轉彎過程的轉彎方向，求出(a,b)，根據公式(3)得到當前轉彎過程的轉彎結束點信息；

情況三，已知當前轉彎過程的轉彎圓心點和下一轉彎過程的轉彎圓心點情況：

情況三中，計算出第i-1個轉彎過程的轉彎結束點到當前第i個轉彎圓的切線，從而得到切線與正北方向的夾角θ，然后利用公式(2)計算出當前轉彎過程的轉彎開始點，根據第i+1個轉彎過程的轉彎方向，將公式(4)或者公式(5)與公式(3)進行聯立求解，計算出當前轉彎過程的轉彎結束點信息，從而獲得當前轉彎過程的全部信息；

情況四，已知當前轉彎過程的轉彎圓心點和下一轉彎過程的轉彎開始點情況：

情況四中，計算出第i-1個轉彎過程的轉彎結束點到當前第i個轉彎圓的切線，從而得到切線與正北方向的夾角θ，然后利用公式(2)計算出當前轉彎過程的轉彎開始點，利用公式(1)和公式(3)計算出當前轉彎過程的轉彎結束點，從而獲得當前轉彎過程的全部信息；

在完成當前轉彎過程的轉彎信息計算后，取下一個轉彎點對應的轉彎過程，繼續迭代計算，直至計算出本子航線序列的所有轉彎過程信息。