TW201738838A

TW201738838A - 共乘路徑的計算方法及使用此方法的計算裝置與記錄媒體

Info

Publication number: TW201738838A
Application number: TW105113208A
Authority: TW
Inventors: 李哲榮; 徐立人
Original assignee: 國立清華大學
Priority date: 2016-04-28
Filing date: 2016-04-28
Publication date: 2017-11-01
Also published as: US10012513B2; TWI581207B; US20170314947A1

Abstract

本發明實施例提出一種共乘路徑的計算方法及使用此方法的計算裝置與記錄媒體。此計算方法包括下列步驟。依據主軌跡資料的軌跡點決定主軌跡區域的區域範圍，且依據那些主軌跡區域的區域範圍依序將主軌跡資料中的各軌跡點歸類至那些主軌跡區域中的一者。依序判斷各主軌跡區域與對應於各副軌跡資料的副軌跡區域是否交集，以篩選出那些副軌跡資料中的至少一者。依據篩選出的那些副軌跡資料計算至少一條共乘路徑。藉此，提供較佳的共乘路徑選擇方案。

Description

共乘路徑的計算方法及使用此方法的計算裝置與記錄媒體

本發明是有關於一種路徑演算方法，且特別是有關於一種共乘路徑的計算方法及使用此方法的計算裝置與記錄媒體。

近年來政府大力推動大眾運輸服務，民眾可享受方便及快捷的搭乘服務。大眾運輸通常是既定路線及時間排程且甚至可能充滿著乘客，相較起來，機車及汽車的便利性更高。然而，並非所有民眾都自行擁有車輛。而由於資源供應過剩轉而走向資源共享的時代變遷，共乘服務亦是其中一種資源共享的應用。

近年來，已經有許多利用在空間或時空空間中的全球定位系統（Global Position system；GPS）軌跡來分析共乘問題的研究。在解決共乘問題的部份現有方法中，需要利用路線網路（road network）才能計算出共乘路徑。不需要利用路線網路的現有方法為網格地圖（grid map）方法，其係將地圖切割成多個區塊，且檢查各路徑是否屬於相同區塊。然而，網格地圖方法的問題在於，僅將屬於相同區塊中的路徑視為可能共乘路徑的候選者。換句而言，即使不屬於相同區塊的兩路徑可能僅相距幾釐米，但仍不會將相鄰區塊（即，不同區塊）中的路徑視為候選者。如此，網格地圖方法可能會忽略許多可能的共乘路徑。由此可知，有需要提出一種解決方案來在不利用路線網路的情況下找出更多且較佳的共乘路徑。

本發明提供一種共乘路徑的計算方法及使用此方法的計算裝置與記錄媒體，其依據軌跡點決定軌跡區域且將最終形成的軌跡區域集合與其他候選者的軌跡區域集合進行比較，從而有效解決網格地圖方法的問題，並提供較佳的共乘路徑選擇方案。

本發明提供一種共乘路徑的計算裝置，其包括儲存單元及處理單元。儲存單元可記錄數個模組、主軌跡資料及副軌跡資料。處理單元耦接儲存單元，且存取並執行儲存單元所儲存的那些模組。那些模組包括軌跡區域決定模組、軌跡區域比較模組及共乘路徑計算模組。軌跡區域決定模組可依據主軌跡資料的軌跡點決定主軌跡區域的區域範圍，且依據那些主軌跡區域的區域範圍依序將主軌跡資料中的各軌跡點歸類至那些主軌跡區域中的一者。軌跡區域比較模組依序判斷各主軌跡區域與對應於各副軌跡資料的那些副軌跡區域是否交集，以篩選出副軌跡資料中的至少一者。共乘路徑計算模組依據篩選出的那些副軌跡資料計算至少一條共乘路徑。

另一觀點而言，本發明提出一種共乘路徑的計算方法，其適用於計算裝置將主軌跡資料與多個副軌跡資料進行比對。此計算方法包括下列步驟。依據主軌跡資料的軌跡點決定主軌跡區域的區域範圍，且依據那些主軌跡區域的區域範圍依序將主軌跡資料中的各軌跡點歸類至那些主軌跡區域中的一者。依序判斷各主軌跡區域與對應於各副軌跡資料的副軌跡區域是否交集，以篩選出那些副軌跡資料中的至少一者。依據篩選出的那些副軌跡資料計算至少一條共乘路徑。

此外，本發明亦提出一種非暫態電腦可讀取記錄媒體，其可紀錄程式、主軌跡資料及副軌跡資料，且經由計算裝置載入以執行下列步驟。依據主軌跡資料的軌跡點決定主軌跡區域的區域範圍，且依據那些主軌跡區域的區域範圍依序將主軌跡資料中的各軌跡點歸類至那些主軌跡區域中的一者。依序判斷各主軌跡區域與對應於各副軌跡資料的副軌跡區域是否交集，以篩選出那些副軌跡資料中的至少一者。依據篩選出的那些副軌跡資料計算至少一條共乘路徑。

基於上述，本發明實施例所提出的共乘路徑的計算方法及使用此方法的計算裝置與記錄媒體，其係將主軌跡資料及副軌跡資料的軌跡點分別界定出對應的多段主軌跡區域及多段副軌跡區域，將所有軌跡點都分別歸類至這些主軌跡區域及那些副軌跡區域後，判斷各主軌跡區域與各副軌跡區域是否交集，從而篩選出數組副軌跡資料中部份或全部的軌跡點，並據以決定共乘路線。藉此，本發明實施例可依據軌跡點來彈性調整軌跡區域，將不受限於網格地圖方法的既定網格區塊，且能更加精確地判斷出主軌跡與副軌跡中各分段的共乘關係，從而搜尋出更多且較佳的共乘機會。

為讓本發明的上述特徵和優點能更明顯易懂，下文特舉實施例，並配合所附圖式作詳細說明如下。

圖1是依據本發明一實施例說明共乘路徑之計算裝置的方塊圖。請參照圖1，計算裝置100至少包括（但不僅限於）儲存單元110及處理單元150。計算裝置100可以是伺服器、用戶端、桌上型電腦、筆記型電腦、智慧型手機、網路電腦、工作站、個人數位助理（personal digital assistant；PDA）、平板個人電腦（personal computer；PC）等電子裝置，且不以此為限。

儲存單元110可以是任何型態的固定或可移動隨機存取記憶體（random access memory，RAM）、唯讀記憶體（read-only memory，ROM）、快閃記憶體（flash memory）或類似元件或上述元件的組合。在本實施例中，儲存單元110係用以儲存主軌跡資料（包括軌跡點）、副軌跡資料、程式碼、裝置組態、緩衝的或永久的資料，並記錄軌跡區塊決定模組111、軌跡區域比較模組113、軌跡區域篩選模組115及共乘路徑計算模組117等軟體程式。前述模組可透過處理單元150存取並執行，且其詳細運作內容待稍後實施例詳細說明。本實施例中所述的儲存單元110並未限制是單一記憶體元件，上述之各軟體模組亦可以分開儲存在兩個或兩個以上相同或不同型態之記憶體元件中。

處理單元150的功能可藉由使用諸如中央處理單元（central processing unit；CPU）、微處理器、微控制器、數位信號處理（digital signal processing；DSP）晶片、場可程式化邏輯閘陣列（Field Programmable Gate Array；FPGA）等可程式化單元來實施。處理單元150的功能亦可用獨立電子裝置或積體電路（integrated circuit；IC）實施，且處理單元150亦可用硬體或軟體實施。

為了方便理解本發明實施例的操作流程，以下將舉諸多實施例詳細說明本發明實施例中計算裝置100進行共乘路徑之計算方法的流程。圖2是依據本發明一實施例說明一種共乘路徑之計算方法流程圖。請參照圖2，本實施例的方法適用於圖1中的計算裝置100。下文中，將搭配計算裝置100中的各項元件及模組說明本發明實施例所述之方法。本方法的各個流程可依照實施情形而隨之調整，且並不僅限於此。

在步驟S210中，軌跡區域決定模組111可依據主軌跡資料的軌跡點決定主軌跡區域的區域範圍，且依據主軌跡區域的區域範圍依序將主軌跡資料中的各軌跡點歸類至主軌跡區域中的一者。具體而言，為了避免受限於習知網格地圖方法的既定區塊，本發明實施例係依據軌跡點動態調整軌跡區域的區域範圍，且判斷是否將軌跡點歸類於某一軌跡區域或另一軌跡區域。

主軌跡資料及副軌跡資料分別包括諸如GPS、伽利略定位系統（Galileo Positioning System）或全球導航衛星系統（GLObal NAvigation Satellite System，GLONASS）等定位系統的軌跡點，且可自儲存單元110、網際網路或其他電子裝置取得。各軌跡點可對應於某一經緯度、高度、時間等地理位置相關資訊。主軌跡資料及副軌跡資料中所有相鄰軌跡點可以相距相同間隔（例如，10、20、50公尺等）及/或相同時間差（例如，10、30、60分鐘等），亦可能以不固定間隔及時間差的方式來取得，或處理單元150設定取樣條件以挑選部份或全部的軌跡點，本發明不以此為限。

在本實施例中，軌跡區域決定模組111係考慮時間-空間（包括，經緯度）座標系統。舉例而言，表(1)～表(4)分別是使用者A的主軌跡資料及使用者B的副軌跡資料1～3，其中時間欄是轉換成以秒數為單位。例如，21點3分59秒轉換成75839秒。而圖3A及3B分別是將前述軌跡點呈現於空間座標圖及時間-空間座標圖的示意圖。表(1) 表(2) 表(3) 表(4)

依據不同設計需求，在其他實施例中，軌跡區域決定模組111亦可能考慮三維空間（包括，經緯度及高度）、二維空間（包括，經緯度）座標系統，且不以此為限。

軌跡區域決定模組111取得主軌跡資料及副軌跡資料的一或多個軌跡點後，將接著決定對應的主軌跡區域及副軌跡區域。軌跡區域決定模組111可定義主軌跡區域及副軌跡區域之區域範圍的範圍門檻值。例如，在時間-空間座標系統中，區域範圍為時間-空間範圍，且區域範圍的範圍門檻值包括空間距離門檻值（例如，50、100、300公尺等）及時間門檻值τ（例如，100、360、720秒等），從而將各主軌跡區域及各候選軌跡區域在時間-空間座標系統上形成立體物件（例如，立方體（cube）物件、圓形體、圓柱體等）。

需說明的是，依據不同座標系統，對應的區域範圍參數亦可能不同（例如，經緯度門檻值、高度門檻值等），但本發明不以此為限。而為了方便後續運算及說明，以下實施例將以立方體為範例來進行說明，然不以此為限。

接著，軌跡區域決定模組111初始化主軌跡區域中的一個區域（例如，第j區域），依序（例如，依據時間或輸入資料順序）將那些軌跡點中的第i軌跡點歸類至那些主軌跡區域中的第j區域，且判斷歸類至第j區域中的那些軌跡點所形成的第j區域的區域範圍是否符合範圍門檻值，以決定是否將第i軌跡點重新歸類至那些主軌跡區域中的第j+1區域。i是介於1至主軌跡資料的軌跡點總數之間的正整數，且j是介於1至那些主軌跡區域之總數之間的正整數。

具體而言，軌跡區域決定模組111先將第i軌跡點歸類至第j區域，將歸類至第j區域的那些軌跡點中的第k軌跡點作為空間基準，且依據該空間基準及歸類至第j區域的那些軌跡點計算第j區域的區域範圍。而此第k軌跡點為最先歸類至第j區域的軌跡點，且k是介於1至軌跡點總數之間的正整數。

在一實施例中，此空間基準包括經度基準及緯度基準。軌跡區域決定模組111將最先歸類至第j區域的第k軌跡點的緯度座標作為緯度基準，且自第j區域內所有的軌跡點（例如，第k至第i軌跡點）中挑選出最小經度及最大經度，以決定區域範圍中的經度範圍。經度範圍可依序由下列方程式(1)～(3)求得：…(1)…(2)…(3)代表第j區域，代表挑選最小經度，代表挑選最大經度，代表取得緯度座標，代表取得最先歸類至第j區域的軌跡點，代表最先歸類至第j區域的軌跡點的緯度座標，代表計算兩軌跡點之距離，代表經度範圍。

軌跡區域決定模組111亦將最先歸類至第j區域的第k軌跡點的經度座標作為經度基準，且自第j區域內所有的軌跡點（例如，第k至第i軌跡點）中挑選出最小緯度及最大緯度，以決定區域範圍中的緯度範圍。緯度範圍可依序由下列方程式(4)～(6)求得： d…(4)…(5)…(6)代表挑選最小緯度，代表挑選最大緯度，代表取得經度座標，代表最先歸類至第j區域的軌跡點的經度座標，代表緯度範圍。

需說明的是，在其他實施例中，軌跡區域決定模組111亦可直接計算第j區域中所有軌跡點的最大緯度與最小緯度之差距及最大經度與最小經度之差距，來分別決定緯度範圍及經度範圍。

此外，軌跡區域決定模組111可自歸類至第j區域的軌跡點中挑選具有最大時間的軌跡點及最小時間的軌跡點，以計算第j區域的區域範圍。時間範圍可由下列方程式(7)求得：…(7)代表挑選最小時間，代表挑選最大時間，time代表時間範圍。

將第i軌跡點歸類至第j區域且取得當前所形成之第j區域的區域範圍之後，軌跡區域決定模組111便可判斷第j區域當前區域範圍是否符合範圍門檻值。例如，經度範圍及緯度範圍是否小於空間距離門檻值，且時間範圍是否小於時間門檻值τ。若經度範圍及緯度範圍大於空間距離門檻值或時間範圍大於時間門檻值τ，則軌跡區域決定模組111將此第i軌跡點自第j區域中移除，並初始化第j+1區域，且將第i軌跡點重新歸類至第j+1區域。接著，軌跡區域決定模組111接續處理第i+1軌跡點，且決定第j+1區域的區域範圍。此外，在移除第i軌跡點之後，便可由所有保留於第j區域的軌跡點（例如，第k至第i-1軌跡點）來確定第j區域的區域範圍。

反之，若經度範圍及緯度範圍小於空間距離門檻值且時間範圍小於時間門檻值τ，則軌跡區域決定模組111將第i軌跡點繼續保留在第j區域，且接續處理第i+1軌跡點並繼續決定第j區域的區域範圍。換句而言，軌跡區域決定模組111在歸類軌跡點至軌跡區域的過程中調整軌跡區域的區域範圍，且依據空間門檻值來限制區域範圍。

依此類推，軌跡區域決定模組111便可決定對應於主軌跡資料的所有主軌跡區域及副軌跡資料的所有副軌跡區域的區域範圍，且分別將主軌跡資料的所有軌跡點及副軌跡資料的所有軌跡點分別歸類至這些主軌跡區域及副軌跡區域。

舉例而言，圖4A及4B分別是將軌跡點與立方體（包括，主軌跡區域、副軌跡區域）呈現於空間座標圖及時間-空間座標圖的示意圖。請同時參照圖4A及4B，假設空間距離門檻值為100公尺，且時間門檻值τ為3600秒。前述使用者A的主軌跡資料（即，表(1)）中代碼2的軌跡點加入主軌跡區域411之後，當前主軌跡區域411所形成之區域範圍中的經度範圍（大約47公尺）及緯度範圍（大約3公尺）小於空間距離門檻值且時間範圍（5秒）小於時間門檻值τ，則繼續判斷代碼3之軌跡點是否歸類至主軌跡區域411。而由於主軌跡資料中代碼4的軌跡點加入至主軌跡區域411之後，當前主軌跡區域411所形成之區域範圍中的經度範圍大於（大約120公尺）空間距離門檻值，因此自主軌跡區域411中移除此代碼4的軌跡點。此代碼4的軌跡點將加入至主軌跡區域413，且確定主軌跡區域411中僅包括代碼1～3的軌跡點，從而決定主軌跡區域411的區域範圍（例如是圖4B所示的立方體）。

依此類推，前述使用者A的主軌跡資料的軌跡點可分別歸類至主軌跡區域411及413，使用者B的副軌跡資料1的軌跡點（即，表(2)）可分別歸類至副軌跡區域421及423，使用者B的副軌跡資料2的軌跡點（即，表(3)）可分別歸類至副軌跡區域431及433，且使用者B的副軌跡資料2的軌跡點（即，表(4)）可歸類至副軌跡區域441。

需說明的是，軌跡區域決定模組111亦可在確定第j區域的區域範圍後，計算第j區域的中心點（如下方程式(8)～(11)），以作為後續交集判斷使用。…(8)…(9)…(10)…(11) center()為取得中心點座標（代表（經度座標，緯度座標，時間座標））。換句而言，軌跡區域決定模組111自第j區域中所有軌跡點挑選出最小經度、緯度及時間、最大經度、緯度及時間，且將對應的各項值相加平均後即可取得中心點座標。

另一方面，軌跡區域決定模組111可依據第k軌跡點及歸類至第j區域的那些軌跡點中的第p軌跡點所形成的連線，決定第j區域的方向。p是介於k+1至軌跡點總數之間的正整數。例如，第p軌跡點是最後歸類至第j區域的軌跡點。軌跡區域決定模組111可利用方程式(12)來決定第j區域的方向：…(12)代表取得最後歸類至第j區域的軌跡點，代表取得反正切（arctangent），代表取得方向。換句而言，軌跡區域決定模組111由最先及最後歸類至第j區域的軌跡點（例如，第k及第p軌跡點）所連成的直線，利用反正切函數推算出角度，並將此角度作為第j區域（內路徑）的方向。

此外，前述方程式(3)及(6)中所使用的可由下列方程式(13)來推算對應於地球表面的距離：…(13)及分別代表兩個位置的經緯度座標，而。

在決定出所有主軌跡區域及副軌跡區域後，在步驟S230中，軌跡區域比較模組113依序判斷各主軌跡區域與對應於各副軌跡資料的那些副軌跡區域是否交集，以篩選出副軌跡資料中的至少一者。

具體而言，軌跡區域比較模組113可將所有主軌跡區域加入至主軌跡區域集合，且將對應於所有副軌跡資料的副軌跡區域加入至副軌跡區域集合。接著，軌跡區域比較模組113依序判斷各主軌跡區域的中心點與各副軌跡資料的各副軌跡區域的中心點間之距離是否小於交集門檻值，且依序判斷各主軌跡區域與各副軌跡資料的各副軌跡區域之方向夾角是否小於夾角門檻值δ，從而決定那些主軌跡區域中的一者與對應於各副軌跡資料的那些副軌跡區域中的一者交集。

此交集門檻值可定義成與空間距離門檻值及時間門檻值τ相同或不同的數值，端視應用本發明實施例者自行決定。軌跡區域比較模組113可依據下列方程式(14)，依序檢查主軌跡區域集合中的各主軌跡區域之中心點及副軌跡區域集合中的各副軌跡區域之中心點是否小於交集門檻值。…(14)代表第j區域的中心點座標，代表第m區域（假設屬於副軌跡區域集合；m是正整數，且介於1至某一副軌跡資料中副軌跡區域之總數）的中心點座標，代表判斷是否交集（真（true）代表交集，假（false）代表未交集）。換句而言，依據兩個軌跡區域的中心點距離計算在時間-空間座標系統上是否有交集。

在運算此方程式(14)中，軌跡區域比較模組113可先計算經度軸是否交集。例如，以第j 區域之中心點的緯度為基準，計算第j區域之中心點的經度至第m區域之中心點的經度的距離，並判斷此距離是否小於空間距離門檻值（即，）。軌跡區域比較模組113亦可計算經度軸是否交集。例如，以第j區域之中心點的經度為基準，計算第j區域之中心點的緯度至第m區域之中心點的緯度的距離，並判斷此距離是否小於空間距離門檻值（即，）。此外，軌跡區域比較模組113計算第m及第j區域的中心點相距的時間差是否小於時間門檻值τ（即，）。最後，當前數比對結果皆符合（皆小於交集門檻值），則軌跡區域比較模組113判斷兩軌跡區域符合交集門檻值（即，在時間-空間座標系統上交集）。反之，則軌跡區域比較模組113判斷兩軌跡區域未符合交集門檻值（即，在時間-空間座標系統上未交集）。

需說明的是，在其他實施例中，軌跡區域比較模組113亦可直接判斷第m及第j區域的區域範圍所形成之立體物件或平面物件是否重疊，或透過其他演算法來判斷第m及第j區域是否交集。

另一方面，本發明實施例更判斷兩軌跡區域的方向。具體而言，軌跡區域比較模組113可基於方程式(12)決定第m及第j區域的方向，且若決定第m及第j區域的方向的方向夾角小於夾角門檻值δ，則判斷為相同方向。反之，則判斷為相反方向。並且，若第m及第j區域成相反方向，則排除此副軌跡資料的第m區域。藉此，與主軌跡區域成相反方向的副軌跡區域中的軌跡點將不作為候選的共乘路徑。換句而言，若主軌跡區域及副軌跡區域的中心點間之距離小於交集門檻值（例如，空間距離門檻值），且主軌跡區域及副軌跡區域的方向夾角小於夾角門檻值δ，軌跡區域比較模組113才會判斷此副軌跡區域與對應的主軌跡區域交集。只要任一條件不滿足（例如，兩中心點相距大於交集門檻值或方向夾角大於夾角門檻值δ），軌跡區域比較模組113便會判斷此副軌跡區域與對應的主軌跡區域未交集。

軌跡區域比較模組113將符合交集門檻值及夾角門檻值的那些副軌跡區域（即，判斷為交集的副軌跡區域）依據對應的各主軌跡區域紀錄於交集矩陣。在本實施例中，此交集矩陣為稀疏（sparse）矩陣。軌跡區域比較模組113將這些判斷為交集的副軌跡區域的編號（或代碼）（例如，在副軌跡區域集合中的順序）紀錄至對應於相交的主軌跡區域在交集矩陣中的那元素（假設不同副軌跡資料以不同欄或列紀錄）。此外，軌跡區域比較模組113將這些判斷為未交集的副軌跡區域對應於相交的主軌跡區域在交集矩陣中的那元素設為零值（假設不同副軌跡資料以不同欄或列紀錄）。

以前述表(1)～(4)的數據為例，假設夾角門檻值δ為45度，主軌跡區域集合為（對應於圖4B中主軌跡區域411及413），副軌跡區域集合為（對應於圖4B中副軌跡區域421～441），交集矩陣L為的稀疏矩陣。若判斷為交集，則在交集矩陣L中記錄對應的代碼。最後，軌跡區域比較模組113可計算出交集矩陣。

需說明的是，交集矩陣採用稀疏矩陣是為了方便後續篩選運算。在其他實施例中，軌跡區域比較模組113亦可用特定代碼、符號、編碼來記錄判斷為交集或未交集的副軌跡區域，本發明不以此為限。

接著，軌跡區域篩選模組115可依據此交集矩陣篩選那些副軌跡資料。在本實施例中，軌跡區域篩選模組115計算交集矩陣中對應於各副軌跡資料且符合交集門檻值及夾角門檻值的那些副軌跡區域之符合總數，且依據對應於各副軌跡資料的符合總數篩選那些副軌跡資料。

具體而言，由於那些判斷為交集的副軌跡區域的編號（或代碼）已記錄於交集矩陣中，且其餘那些判斷為未交集的副軌跡區域在交集矩陣中的元素設為零值，因此交集矩陣中對應於各副軌跡資料的那欄中元素為非零值的總數即為符合總數。軌跡區域篩選模組115可將各副軌跡資料的符合總數大於0的一或多者，挑選出作為候選者的副軌跡資料。

在一實施例中，假設n個副軌跡資料，則軌跡區域篩選模組115將交集矩陣定義成，col₁ 至col_n 分別是對應於第一個副軌跡資料至第n個副軌跡資料所記錄的所屬副軌跡區域是否與主軌跡區域交集的向量。軌跡區域篩選模組115可將交集矩陣L中對應於各副軌跡資料的非零值的總數（即，符合總數）小於0的那欄刪除。例如，將向量col₂ 及col₅ 刪除。交集矩陣L所剩下的副軌跡資料即為與主軌跡有共乘關係的副軌跡（對應於一或多個主軌跡區域）。

以前述交集矩陣為例，因為交集矩陣L的第一欄皆為零值，所以軌跡區域篩選模組115便可刪除此第一欄。接著，軌跡區域篩選模組115可計算出篩選後的交集矩陣。

接著，在步驟S250中，共乘路徑計算模組117依據篩選出的那些副軌跡資料計算至少一條共乘路徑。在本實施例中，共乘路徑計算模組117將篩選出的那些副軌跡資料中符合交集門檻值及夾角門檻值的那些副軌跡區域中的軌跡點進行還原，且依據還原的那些軌跡點計算至少一條共乘路徑。

具體而言，共乘路徑計算模組117可利用篩選後之交集矩陣L，來將部分或全部主軌跡區域對應的交集副軌跡區域中的軌跡點進行還原。以前述篩選後的交集矩陣為例，表(5)是還原後的對照表。表(5)中的數值代表表(1)～(4)中軌跡點對應的代碼。表(5)

圖5A及5B分別是將還原之軌跡點呈現於空間座標圖及時間-空間座標圖的示意圖。請參照圖5A及5B，共乘路徑計算模組117可取得相鄰的軌跡區段。結果表示，使用者A的主軌跡資料與使用者B的副軌跡資料2及3有相鄰關係。共乘路徑計算模組117可進一步挑選這些相鄰的主軌跡資料及副軌跡資料中部分或全部軌跡區段來作為共乘路徑，甚至結合地圖的街道資料來決定共乘路徑。而決定的共乘路徑可透過計算裝置100上的顯示單元（例如，液晶顯示器（liquid-crystal display：LCD）、發光二極體（light emitting diode；LED）顯示器等）來呈現，或提供選項來選擇的主軌跡資料及副軌跡資料中的軌跡區段。

本發明另提供一種非暫態（non-transitory）電腦可讀取記錄媒體（例如，唯讀記憶體、快閃記憶體、CD-ROM、磁帶、軟性磁碟、光學資料儲存元件等），其中記錄電腦程式，該電腦程式是用以執行上述計算方法的各個步驟，此電腦程式是由多數個程式碼片段所組成的，並且這些程式碼片段在載入計算裝置100中並執行之後，即可完成上述計算方法的步驟。

綜上所述，本發明實施例的共乘路徑的計算方法及使用此方法的計算裝置與記錄媒體，其依據取得的軌跡點來決定可歸類這些軌跡點的軌跡區域，且將主軌跡資料的一或多個主軌跡區域依序與所有副軌跡區域進行比較，從而篩選全部或部分的副軌跡區域作為候選者。藉此，本發明實施例可搜尋出更多且更佳的共乘路線。此外，本發明實施例與網格地圖方法相比，可增加數倍（例如， 6倍）以上的共乘距離。

雖然本發明已以實施例揭露如上，然其並非用以限定本發明，任何所屬技術領域中具有通常知識者，在不脫離本發明的精神和範圍內，當可作些許的更動與潤飾，故本發明的保護範圍當視後附的申請專利範圍所界定者為準。

100‧‧‧計算裝置
150‧‧‧處理單元
110‧‧‧儲存單元
S210～S250‧‧‧步驟
111‧‧‧軌跡區域決定模組
421、423‧‧‧主軌跡區域
113‧‧‧軌跡區域比較模組
411、413、421、423、431、115‧‧‧軌跡區域篩選模組
433、441‧‧‧副軌跡區域
117‧‧‧共乘路徑計算模組

圖1是依據本發明一實施例說明共乘路徑之計算裝置的方塊圖。圖2是依據本發明一實施例說明一種共乘路徑之計算方法流程圖。圖3A及3B分別是將前述軌跡點呈現於空間座標圖及時間-空間座標圖的示意圖。圖4A及4B分別是將軌跡點與立方體呈現於空間座標圖及時間-空間座標圖的示意圖。圖5A及5B分別是將還原之軌跡點呈現於空間座標圖及時間-空間座標圖的示意圖。

S210~S250‧‧‧步驟

Claims

一種共乘路徑的計算裝置，包括：一儲存單元，記錄多個模組、一主軌跡資料及多個副軌跡資料；以及一處理單元，耦接該儲存單元，且存取並執行該儲存單元所儲存的該些模組，該些模組包括：一軌跡區域決定模組，依據該主軌跡資料的多個軌跡點決定多個主軌跡區域的區域範圍，且依據該些主軌跡區域的該區域範圍依序將該主軌跡資料中的各該些軌跡點歸類至該些主軌跡區域中的一者；一軌跡區域比較模組，依序判斷各該些主軌跡區域與對應於各該些副軌跡資料的多個副軌跡區域是否交集，以篩選出該些副軌跡資料中的至少一者；以及一共乘路徑計算模組，依據篩選出的該些副軌跡資料計算至少一共乘路徑。
如申請專利範圍第1項所述的計算裝置，其中該軌跡區域決定模組將該些軌跡點中的一第i軌跡點歸類至該些主軌跡區域中的一第j區域，且判斷歸類至該第j區域中的該些軌跡點所形成的該第j區域的區域範圍是否符合一範圍門檻值，以決定是否將該第i軌跡點重新歸類至該些主軌跡區域中的一第j+1區域，其中i是介於1至該主軌跡資料的軌跡點總數之間的正整數，且j是介於1至該些主軌跡區域之總數之間的正整數。
如申請專利範圍第2項所述的計算裝置，其中該軌跡區域決定模組將歸類至該第j區域的該些軌跡點中的一第k軌跡點作為一空間基準，且依據該空間基準及歸類至該第j區域的該些軌跡點計算該第j區域的該區域範圍，其中該第k軌跡點為最先歸類至該第j區域的軌跡點，且k是介於1至該軌跡點總數之間的正整數。
如申請專利範圍第2項所述的計算裝置，其中該軌跡區域決定模組自歸類至該第j區域的該些軌跡點中挑選具有最大時間的軌跡點及最小時間的軌跡點，以計算該第j區域的該區域範圍。
如申請專利範圍第3項所述的計算裝置，其中該軌跡區域決定模組依據該第k軌跡點及歸類至該第j區域的該些軌跡點中的一第p軌跡點所形成的連線，決定該第j區域的方向，其中p是介於k+1至該軌跡點總數之間的正整數。
如申請專利範圍第1項所述的計算裝置，其中該軌跡區域比較模組依序判斷各該些主軌跡區域的中心點與各該些副軌跡資料的各該些副軌跡區域的中心點間之距離是否小於一交集門檻值，且依序判斷各該些主軌跡區域與各該些副軌跡資料的各該些副軌跡區域之方向夾角是否小於一夾角門檻值，從而決定該些主軌跡區域中的一者與對應於各該些副軌跡資料的該些副軌跡區域中的一者交集。
如申請專利範圍第6項所述的計算裝置，其中該軌跡區域比較模組將符合該交集門檻值及該夾角門檻值的該些副軌跡區域依據對應的各該些主軌跡區域紀錄於一交集矩陣，且該計算裝置更包括：一軌跡區域篩選模組，依據該交集矩陣篩選該些副軌跡資料。
如申請專利範圍第7項所述的計算裝置，其中該軌跡區域篩選模組計算該交集矩陣中對應於各該些副軌跡資料且符合該交集門檻值及該夾角門檻值的該些副軌跡區域之符合總數，且依據對應於各該些副軌跡資料的該符合總數篩選該些副軌跡資料。
如申請專利範圍第1項所述的計算裝置，其中該共乘路徑計算模組將篩選出的該些副軌跡資料中符合該交集門檻值及該夾角門檻值的該些副軌跡區域中的多個軌跡點進行還原，且依據還原的該些軌跡點計算該至少一共乘路徑。
如申請專利範圍第1項所述的計算裝置，其中該軌跡區域決定模組將各該些主軌跡區域及各該些候選軌跡區域在時間-空間座標系統上形成一立體物件，且該區域範圍為一時間-空間範圍。
一種共乘路徑的計算方法，適用於一計算裝置將一主軌跡資料與多個副軌跡資料進行比對，所述計算方法包括：依據該主軌跡資料的多個軌跡點決定多個主軌跡區域的區域範圍，且依據該些主軌跡區域的該區域範圍依序將該主軌跡資料中的各該些軌跡點歸類至該些主軌跡區域中的一者；依序判斷各該些主軌跡區域與對應於各該些副軌跡資料的多個副軌跡區域是否交集，以篩選出該些副軌跡資料中的至少一者；以及依據篩選出的該些副軌跡資料計算至少一共乘路徑。
如申請專利範圍第11項所述的計算方法，其中所述依據該些主軌跡區域的該區域範圍依序將該主軌跡資料中的各該些軌跡點歸類至該些主軌跡區域中的一者的步驟包括：將該些軌跡點中的一第i軌跡點歸類至該些主軌跡區域中的一第j區域；以及判斷歸類至該第j區域中的該些軌跡點所形成的該第j區域的區域範圍是否符合一範圍門檻值，以決定是否將該第i軌跡點重新歸類至該些主軌跡區域中的一第j+1區域，其中i是介於1至該主軌跡資料的軌跡點總數之間的正整數，且j是介於1至該些主軌跡區域之總數之間的正整數。
如申請專利範圍第12項所述的計算方法，其中所述依據該主軌跡資料的該些軌跡點決定該些主軌跡區域的該區域範圍的步驟包括：將各該些主軌跡區域及各該些副軌跡區域在時間-空間座標系統上形成一立體物件，其中該區域範圍為一時間-空間範圍；將歸類至該第j區域的該些軌跡點中的一第k軌跡點作為一空間基準，其中該第k軌跡點為最先歸類至該第j區域的軌跡點，且k是介於1至該軌跡點總數之間的正整數；以及依據該空間基準及歸類至該第j區域的該些軌跡點計算該第j區域的該區域範圍。
如申請專利範圍第12項所述的計算方法，其中所述依據該主軌跡資料的該些軌跡點決定該些主軌跡區域的該區域範圍的步驟包括：自歸類至該第j區域的該些軌跡點中挑選具有最大時間的軌跡點及最小時間的軌跡點，以計算該第j區域的該區域範圍。
如申請專利範圍第13項所述的計算方法，其中所述依據該空間基準及歸類至該第j區域的該些軌跡點計算該第j區域的該區域範圍的步驟之後，更包括：該軌跡區域決定模組依據該第k軌跡點及歸類至該第j區域的該些軌跡點中的一第p軌跡點所形成的連線，決定該第j區域的方向，其中p是介於k+1至該軌跡點總數之間的正整數。
如申請專利範圍第11項所述的計算方法，其中所述依序判斷各該些主軌跡區域與對應於各該些副軌跡資料的該些副軌跡區域是否交集的步驟包括：依序判斷各該些主軌跡區域的中心點與各該些副軌跡資料的各該些副軌跡區域的中心點間之距離是否小於一交集門檻值；以及依序判斷各該些主軌跡區域與各該些副軌跡資料的各該些副軌跡區域之方向夾角是否小於一夾角門檻值，從而決定該些主軌跡區域中的一者與對應於各該些副軌跡資料的該些副軌跡區域中的一者交集。
如申請專利範圍第16項所述的計算方法，其中所述決定該些主軌跡區域中的一者與對應於各該些副軌跡資料的該些副軌跡區域中的一者交集的步驟之後，更包括：將符合該交集門檻值及該夾角門檻值的該些副軌跡區域依據對應的各該些主軌跡區域紀錄於一交集矩陣；以及依據該交集矩陣篩選該些副軌跡資料。
如申請專利範圍第17項所述的計算方法，其中所述依據該交集矩陣篩選該些副軌跡資料的步驟包括：計算該交集矩陣中對應於各該些副軌跡資料且符合該交集門檻值及該夾角門檻值的該些副軌跡區域之符合總數；以及依據對應於各該些副軌跡資料的該符合總數篩選該些副軌跡資料。
如申請專利範圍第11項所述的計算方法，其中所述依據篩選出的該些副軌跡資料計算該至少一共乘路徑的步驟包括：將篩選出的該些副軌跡資料中符合該交集門檻值及該夾角門檻值的該些副軌跡區域中的多個軌跡點進行還原；以及依據還原的該些軌跡點計算該至少一共乘路徑。
一種非暫態電腦可讀取記錄媒體，記錄一程式、一主軌跡資料及多個副軌跡資料，經由一計算裝置載入以執行下列步驟：依據該主軌跡資料的多個軌跡點決定多個主軌跡區域的區域範圍，且依據該些主軌跡區域的該區域範圍依序將該主軌跡資料中的各該些軌跡點歸類至該些主軌跡區域中的一者；依序判斷各該些主軌跡區域與對應於各該些副軌跡資料的多個副軌跡區域是否交集，以篩選出該些副軌跡資料中的至少一者；以及依據篩選出的該些副軌跡資料計算至少一共乘路徑。