[發明專利]一種快速匹配電子地圖中公交線路與道路網絡的方法

有效

• 申請號: 201711342969.7
• 申請日: 2017-12-14
• 公開（公告）號: CN108021686B
• 公開（公告）日: 2021-03-23
• 發明（設計）人: 王煒;汪宇軒;丁浩洋;秦棽;盧瑞穎
• 申請（專利權）人: 東南大學
• 主分類號: G06F16/29
• 分類號: G06F16/29
• 代理公司: 南京眾聯專利代理有限公司 32206
• 代理人: 蔣昱

1.一種快速匹配電子地圖中公交線路與道路網絡的方法，其特征在于，包括如下步驟：

步驟(1)提取電子地圖中道路網絡上的所有的交叉口節點，并將其經緯度坐標轉換為UTM平面坐標系坐標，轉換后的坐標單位為米，組成集合W；設W中有n個交叉口節點，從W中隨意選取節點w_i，逐一判斷w_i到W中的其它節點之間是否存在可通行路段，若存在可通行路段，將該節點放入w_i的鄰接節點集合S_i中，S_i初始狀態為空，對W中所有節點進行此操作，形成各節點的鄰接節點集合S₁,…,S_n；

步驟(2)將電子地圖中公交線路經過的拓撲點經緯度坐標轉換為UTM平面坐標系坐標，轉換后的坐標單位為米，按線路經過的次序組成集合R，設集合R中有m個拓撲點，第i個拓撲點為r_i，坐標為(x_i,y_i)；

步驟(3)設R中起始拓撲點為r₁，計算r₁到W中所有交叉口節點的距離，如果存在節點與r₁的距離小于D，則將該節點放入集合Q，Q初始狀態為空集，從R中刪除點r₁，進入步驟(5)；否則，找到與r₁距離最近的節點w_k；

步驟(4)設R中第二個拓撲點為r₂，判斷r₁，r₂以及W中的節點w_k組成的向量和之間在一定精度內是否滿足共線且同向，若滿足，將節點w_k放入集合Q，從R中刪除點r₁，進入步驟(5)；否則，繼續在W中尋找除了節點w_k與r₁距離最近的節點，逐一排除不滿足條件的節點，直到找到滿足條件的距離r₁最近的節點，將其賦值給w_k，放入集合Q中，并從R中刪除點r₁；

步驟(5)若集合R為空，則表示匹配完成，結束電子地圖中公交線路拓撲點與路網節點的匹配；否則從點w_k的鄰接節點集合S_k中選取第j個節點s_kj，j初始值為1；

步驟(6)逐一計算集合R中的拓撲點與點s_kj的距離d_ij，如果存在拓撲點r_i使得d_ijD，則將點s_kj放入集合Q，將其定義為新的點w_k，從R中刪除點r_i以及r_i之前所有的拓撲點，并返回步驟(5)；如果不存在拓撲點r_i使得d_ijD且點s_kj為S_k中的最后一個節點，則進入步驟(7)；否則，在鄰接節點集合S_k選取下一個節點，重復本步操作；

步驟(7)依次判斷點s_kj以及S_k中各點指向R中最后一個拓撲點r_m的向量和最后兩個拓撲點r_m-1和r_m組成的向量在一定精度內是否滿足共線且同向，若在點s_kj以及集合S_k中的點中有滿足該條件的點，將其放入集合Q中，完成公交線路與路網的匹配；否則，在電子地圖中顯示線路最后一個拓撲點的位置，由用戶確定最后一個路網節點使得該拓撲點在該節點與Q中最后一個節點組成的路段上，將用戶確定的節點放入集合Q中，結束匹配；集合Q中的每前后兩個節點連接起來的路徑即為該條公交線路在路網中依次經過的路段。

2.根據權利要求1所述的一種快速匹配電子地圖中公交線路與道路網絡的方法，其特征在于：所述步驟(1)和步驟(2)中，采用地圖學中的統一橫軸墨卡托投影方法將道路網絡中所有的交叉口節點的經緯度坐標和電子地圖中公交線路經過的拓撲點的經緯度坐標轉換為UTM平面坐標系坐標。

3.根據權利要求1所述的一種快速匹配電子地圖中公交線路與道路網絡的方法，其特征在于：所述步驟(3)，步驟(4)，步驟(6)和步驟(7)中，公交線路和路網匹配精度設為10米。