[發明專利]一種不等距分割可通行區域的路徑規劃方法

有效

• 申請號: 201310444105.1
• 申請日: 2013-09-26
• 公開（公告）號: CN103528585A
• 公開（公告）日: 2014-01-22
• 發明（設計）人: 潘廣貞;于一;喬慧芬
• 申請（專利權）人: 中北大學
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 太原晉科知識產權代理事務所(特殊普通合伙) 14110
• 代理人: 任林芳

1.一種不等距分割可通行區域的路徑規劃方法，其特征在于步驟如下：

1）計算每個障礙曲線的凸極值點；

2）過每個凸極值點作水平線用以分割可通行區域；

3）將每個分割成的小區域抽象成一個圖的頂點；

4）把所有頂點組成一個無向圖；

5）找出起點和終點所在小區域對應的頂點序號；

6）對于無向圖通過廣度優先或深度優先遍歷，找出所有的路徑；

7）再根據實際地圖上的情形，找出運動物體實際所要行走的路徑。

2.根據權利要求1所述的不等距分割可通行區域的路徑規劃方法，其特征在于具體步驟如下：

1）障礙物建模

利用擬合曲線模擬障礙物的外沿，采用Bezier曲線，計算出構成曲線的所有點的橫、縱坐標；

2）計算障礙曲線的凸極值點

通過循環計算每段曲線上的極大值或極小值，進而求得曲線上的極值點坐標，僅保留障礙曲線的凸極值點；

3）水平分割可通行區域

通過凸極值點做水平切線對可通行區域進行一維分割，方法如下：求出所有曲線上的最大值與最小值，從而求出曲線的外接矩形，判斷極值點縱坐標是否介于一個區域的最小值與最大值之間，如果是，則得到過該極值點的水平切線與一個區域相交；如果相交，求出交點坐標，并保存在一個數組中，求曲線的交點與極值點的距離；若距離的最小值>0,說明過極值點所做的水平切線只與一個區域相交，且在所交區域的左側；同理，若距離的最大值<0,說明過極值點所做的水平切線也只與一個區域相交，且在所交區域的右側；若距離有正有負，則說明過極值點所做水平切線不止與一個區域相交；最后畫出經過每個極值點的水平切線；

4）可通行區域的存儲

在區域存儲過程中，使用隊列將所有的區域存儲；區域存儲后，根據構造的鄰接表中頂點間的鄰接關系，抽象出一個無向圖；具體方法如下：

先存儲第一個區域，若是直線邊就存儲兩個端點，若是曲線邊就將曲線上的所有的點都存儲下來，對區域編號，并入隊；構建鄰接表，存儲區域的標志位和公共邊，標志位是用來標記該區域是否已訪問，公共邊則是為了判斷區域之間的鄰接關系；隊頭元素出隊，將其相鄰的區域存儲，編號并入隊；在入隊過程中先判斷，該區域是否已經訪問過以及是否在隊列中；

若既沒有被訪問過且不在隊列中，則入隊；否則繼續判斷其相鄰區域；每個區域抽象為圖的一個頂點，若劃分出的小區域有公共邊，則與之對應的頂點間就有連線，構造無向圖；

確定無向圖中的路徑，設置訪問標記數組，用來標記該頂點是否已被訪問；先將第一個頂點入棧；棧不為空，將棧頂元素出棧，并將其相鄰的頂點入棧，設置訪問標志位為已訪問；若與它鄰接的下一個頂點沒有被訪問過，將出棧元素保存到數組中；如此構成循環，找出所有的路徑，并將這些路徑分別存放在不同的數組中；

5）反算無向圖邊計算最短路徑

確定路徑后，根據實際情況為每條路徑動態設定權值，并算出權值和，權值和最小的即為最短路徑；

設定權值遵循的原理是：求兩個直角三角形的斜邊和，若它們的水平直角邊不共線，求出起點與終點在水平方向上的中間點，連接起點與中間點，中間點與終點，此時求得的兩條斜邊和最短；

為每條路徑設定權值的過程中，將每條路徑的路徑畫出來，并算出每條路徑的權值和；權值和為最小的即為最短路徑。