[發明專利]一種路徑相似度比較方法

在審

• 申請號: 201510438467.9
• 申請日: 2015-07-23
• 公開（公告）號: CN105184387A
• 公開（公告）日: 2015-12-23
• 發明（設計）人: 李草原;王樹良;王大魁;李延
• 申請（專利權）人: 北京理工大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/30
• 代理公司: 北京理工大學專利中心 11120
• 代理人: 高燕燕;仇蕾安

1.一種路徑相似度比較方法，其特征在于，包括如下步驟：

步驟1、獲取相比較的二者的路徑信息，建立駕駛路線A和B；

步驟2、建立A外接矩形A’，和B的外界矩形B’，確定A’和B’的左上角點間的距離L₁和右下角點間的距離L₂，若L₁和L₂均小于設定閾值，進入步驟3；否則，輸出相似度為0，本方法結束；

步驟3、計算A和B之間重復的路徑長度S，首其中A的總路程長度為S₁，B的總路程長度為S₂，在相似度C為

2.如權利要求1所述的一種路徑相似度比較方法，其特征在于，所述步驟3中計算A和B之間重復的路徑長度S的方法具體為：在根據所建立的駕駛路線A和B，分別獲取A和B的折線圖A₀和B₀；從折線圖A₀上獲取每個轉折點，共N個，保存至數組R_A中，從B₀上獲取每個轉折點，共M個，保存至數組R_B中，計算數組R_A中任意兩個相鄰轉折點組成的線段和數組R_B中任意兩個相鄰轉折點所組成的線段之間的重合距離并疊加，獲得整個駕駛路線A和B的重合距離。

3.如權利要求2所述的一種路徑相似度比較方法，其特征在于，所述計算數組R_A中任意兩個相鄰轉折點組成的線段和數組R_B中任意兩個相鄰轉折點所組成的線段之間的重合距離的方法具體為：數組R_A中任意兩個相鄰轉折點組成的線段為(R_A[i],R_A[i+1])，其中R_A[i]為數組R_A中的第i個轉折點，i＝1～N-1；數組R_B中任意兩個相鄰轉折點所組成的線段為(R_B[j],R_B[j+1])，j＝1～M-1；計算(R_A[i],R_A[i+1])和(R_B[j],R_B[j+1])之間的重合距離并疊加獲得總的重合距離；

具體步驟如下：

步驟301、判斷(R_A[i],R_A[i+1])和(R_B[j],R_B[j+1])是否共線：

判斷R_B[j]是否在線段(R_A[i],R_A[i+1])上：判斷R_A[i]、R_B[j]組成的向量與R_A[i+1]、R_B[j]組成的向量是否平行，若平行則R_B[j]是在線段(R_A[i],R_A[i+1])上；

判斷R_B[j+1]是否在線段(R_A[i],R_A[i+1])上：判斷R_A[i]、R_B[j+1]組成的向量與R_A[i+1]、R_B[j+1]組成的向量是否平行，若平行則R_B[j+1]是在線段(R_A[i],R_A[i+1])上；

若R_B[j]和R_B[j+1]均在線段(R_A[i],R_A[i+1])上；則(R_A[i],R_A[i+1])和(R_B[j],R_B[j+1])共線；

若(R_A[i],R_A[i+1])和(R_B[j],R_B[j+1])共線，則進入步驟302，否則(R_A[i],R_A[i+1])和(R_B[j],R_B[j+1])之間的重合距離為0；

步驟302、找到共線線段(R_A[i],R_A[i+1])和(R_B[j],R_B[j+1])，以點R_A[i]、R_A[i+1]、R_B[j]以及R_B[j+1]的坐標值為比較基準，設R_A[i]和R_A[i+1]之間較小的為P、較大的為Q，設R_B[j]和R_B[j+1]之間較小的為R、較大的為S；然后以P、R二者中較大的為U，以Q、S二者中較小的為V；

判斷若U>＝V則重合距離為0，否則重合距離為UV兩點之間距離。