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

在審

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

技術領域

本發明屬于路徑相似度對比技術領域。

背景技術

隨著城市人口增加，上班族上下班出行的難度和體驗越來越差，人們上下班拼車出行(多人出行，由于出行線路類似，可以乘坐同一輛轎車)的需求越來越大。

隨著我國經濟的飛速發展，人們的生活水平不斷提高，人們在旅游方面的支出顯著增長，選擇自駕出游的人越來越多。人們期望在旅途中有人陪伴，同時隨著低碳環保觀念深入人心，越來越多的人渴望拼車出行來降低成本、便利交通、節省能源、保護環境、結交好友，一舉多得。

另外伴隨著我國信息化水平的不斷提高，人們習慣并且需要從互聯網上獲取各種信息，包括本專利涉及到的拼車信息。谷歌地圖、百度地圖等一些WebGIS技術迅猛發展，并提供了免費的API服務供開發者使用，給拼車類應用的實現提供了便利。

市場上天天用車、嘀嗒拼車、51拼車等拼車類應用如雨后春筍般涌現出來。用戶可以在此類應用中發布自己出行的起點和終點，系統會自動比較無車用戶與有車用戶線路相似度，當相似度較高時會自動提醒用戶選擇拼車出行。這就對相似度算法有了較高的要求。

發明內容

有鑒于此，本發明提供了一種路徑相似度比較方法，該方法計算簡單、效率高。

為了達到上述目的，本發明的技術方案包括如下步驟：

步驟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為

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

進一步地，計算數組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])上。