[發(fā)明專利]一種使用二進制字符串來比較行程路徑的方法

在審

• 申請?zhí)枺?/td>: 201710850727.2
• 申請日: 2017-09-20
• 公開（公告）號: CN107818131A
• 公開（公告）日: 2018-03-20
• 發(fā)明（設計）人: 繆涵澄;齊石;金偉
• 申請（專利權）人: 上海保橙網絡科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海天翔知識產權代理有限公司31224
• 代理人: 劉粉寶

1.一種使用二進制字符串來比較行程路徑的方法，其特征在于，所述方法包括如下步驟：

(1)開始，通過智能手機中的GPS定位模塊來得到用戶駕駛外部路徑數據，其中數據包括GPS定位信息；

(2)將上述數據進行遍歷，對第一個行程進行下述處理；

(3)將第一個行程路徑的所有GPS定位點，通過RDP算法將行程上的點進行迭代平滑化，將路徑上偏移點、誤差點剔除，將主路徑點保留，并記錄下來；

(4)判斷平滑后的點是否過少，判斷條件為：是否仍然構成原路徑相似路線，通過所有點距離累加進行判斷，如果所有點的累加距離與原來軌跡總距離相差超過30％，表示平滑后的點過少，則返回步驟(2)直至平滑后的點正常；如果所有點的累加距離與原來軌跡總距離相差不超過30％，表示平滑后的點正常，則繼續(xù)下一步驟；

(5)將步驟3中保留下來的主路徑點通過DDA算法將平滑后的路徑點補齊成直線，得到由多個線段組成的路徑圖；

(6)通過將世界經緯度按400平方米來劃分，通過經度和緯度給出編號，具體是從0，0點開始，每0.00005經度和每0.00005緯度計算為一個矩形，將矩形按緯度順序排序后再按經度順序排序，給出每個矩形唯一對應的編號；

(7)如果路徑點所在的矩形編號為1則是起點，如果路徑點所在的矩形編號等于路徑點總數則為終點；

(8)將所有補全后的路徑點篩選出來，判斷補全后的路徑點是否在矩形的邊界上，如果在邊界上，則進入下一步驟；如果不在邊界上，則返回步驟(5)，直至補全后的路徑點在矩形的邊界上；該步驟是找出再矩形邊界上的點，用于確定路徑經過了哪些矩形；

(9)將所有步驟(8)保留下的點進行計算，查找出每個點經過的矩形，將矩形的編號按順序排列，拼接成一個字符串，并且將原始行程記錄到的第一個GPS點和原始行程記錄到的最后一個GPS點放入開始和結尾處；

(10)將拼接完成后的字符串進行處理，轉換為64位二進制字符串；

(11)將轉換為64位二進制字符串的所有行程路徑標識數據存入數據庫；

(12)對是否還有行程路徑未處理進行判斷，具體判斷方法為：通過數據庫中查詢是否有未處理行程，已處理會加上標記，未處理則沒有；如有未處理的，則將下一個行程作為第一個行程返回步驟3，直至沒有未處理的行程路徑；如沒有未處理的，則進入下一步驟；

(13)在所有行程路徑的標識數據處理完成后，對于所有行程進行兩兩之間的比較，比較次數為行程數的階乘次，比較方法為最小編輯距離法；

(14)最小編輯距離對否小于閾值進行判斷，若相似程度小于80％，則跳過；若相似程度大于80％，則存入相似行程數據庫，編輯距離算法返回相似比例；

(15)結束。

2.根據權利要求1所述的一種使用二進制字符串來比較行程路徑的方法，其特征在于，步驟(3)中的RDP算法即抽吸算法，其原理為：一段軌跡頭尾連接成一條線，如果其間所有的點距離這條線的距離都小于3KM，則去掉中間所有的點；如果以上條件不滿足，則取距離最大的點，把原始軌跡拆分成兩條軌跡，重復以上迭代，直至完成，其中效果為剔除偏移點、誤差點，也進行了迭代平滑。

3.根據權利要求1所述的一種使用二進制字符串來比較行程路徑的方法，其特征在于，步驟(8)中補全后的路徑點是否在矩形的邊界上的具體判斷方法為：將所有補全后的路徑點篩選出來，匹配是否第五位小數為0或5，第五位小數為0或5就是邊界上的點，否則就不是邊界上的點。

4.根據權利要求1所述的一種使用二進制字符串來比較行程路徑的方法，其特征在于，步驟(13)中的最小編輯距離算法是指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數；許可的編輯操作包括將一個字符替換成另一個字符，插入一個字符，刪除一個字符；一般來說，編輯距離越小，兩個串的相似度越大。