[發明專利]檢查全網道路連通性的方法和裝置

有效

• 申請號: 201010623666.4
• 申請日: 2010-12-30
• 公開（公告）號: CN102567429A
• 公開（公告）日: 2012-07-11
• 發明（設計）人: 高超;向哲;徐晉暉;曹曉航
• 申請（專利權）人: 北京四維圖新科技股份有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G09B29/00
• 代理公司: 北京銀龍知識產權代理有限公司 11243
• 代理人: 許靜;安利霞

技術領域

本發明涉及電子地圖領域，特別是指一種檢查全網道路連通性的方法和裝置。

背景技術

路網連通性檢查是電子地圖生產行業的典型工作環節。為了保證發布數據的質量，電子地圖廠商在發布電子地圖數據前，都要檢查道路全網的連通情況，防止產生物理浮島或各種屬性下的邏輯浮島。物理浮島是指一段或多段彼此連通的道路在物理位置上不與任何其他道路連通而形成的子路網。邏輯浮島是指由于某些邏輯關系不連通而形成的一段或多段道路形成的子路網。

檢查路網連通性的傳統方法是基于計算有向圖的強連通分量(Strongly?Connected?Component)的Kosaraju算法、Tarjan算法和Gabow算法。主要步驟是：

首先，將電子地圖中的道路網絡構造為圖論中的有向圖。將道路全網中所有的道路構造為有向圖中的點(Vertex)，將相互掛接并且不存在禁止關系的道路構造為有向圖中的邊(Edge)。禁止關系指在物理上相關連接但由于交通規制而無法到達。

然后，在生成的有向圖中使用Kosaraju、Tarjan或Gabow算法或其他連通性檢查方法找到所有的強連通分量。

電子地圖生產企業面臨客戶對鮮度越來越高的要求。也就是說，局部快速更新的要求，如果現實環境中發生路網變化，需要電子生產企業盡快反映在其數據中。

電子地圖生產企業的傳統生產模式是：每次發布全網道路數據(在中國一般指全國道路)時，在全網中進行一次連通性檢查。由于全國路網數據量太大，例如達到千萬數量級，連通性檢查是一個很耗時的過程。由于局部路網進行檢查無法保證全網范圍的強連通，因此，即使僅對局部更新，每次也必須對道路全網進行檢查，因此，檢查周期長，無法適應快速更新作業的生產模式。

發明內容

本發明要解決的技術問題是提供一種檢查全網道路連通性的方法和裝置，能夠減少在道路全網的部分數據更新后對道路全網進行連通性檢查的時間。

為解決上述技術問題，本發明的實施例提供技術方案如下：

一方面，提供一種檢查全網道路連通性的方法，包括：

步驟1，獲取全局路網的道路數據對應的全局圖幅的全網概要連通圖，所述全局路網的道路數據包含多個局部路網的道路數據；所述全網概要連通圖包括：所述多個局部路網的道路數據對應的子圖幅的局部概要連通圖；所述局部概要連通圖表示所述子圖幅的圖廓點之間的連接關系；所述圖廓點之間的連接關系根據所述子圖幅內的所述圖廓點之間的道路的連接關系確定；所述圖廓點為所述子圖幅的圖廓線與所述子圖幅內的道路之間的交點；

步驟2，獲取被更新的部分道路數據；

步驟3，根據所述被更新的部分道路數據，查找所述被更新的部分道路數據所在的第一子圖幅；

步驟4，根據所述被更新的道路數據，重新生成查找到的所述第一子圖幅的局部概要連通圖；

步驟5，使用重新生成的所述第一子圖幅的局部概要連通圖，更新所述全網概要連通圖；

步驟6，根據所述第一子圖幅內的道路數據和更新后的所述全網概要連通圖內的除所述第一子圖幅的其他子圖幅的局部概要連通圖，檢查全局路網的道路連通性，生成檢查結果。

所述方法還包括：

如果所述檢查結果為：所述全網概要連通圖中存在組成浮島的圖廓點和/或道路，則輸出所述組成浮島的所述圖廓點的標識信息和/或所述道路的標識信息。

所述局部概要連通圖保存有與圖廓點連接的道路與圖廓點之間的對應關系；

所述方法還包括：根據所述對應關系，查找所述組成浮島的圖廓點對應的道路；

輸出所述組成浮島的圖廓點對應的道路的標識信息。

所述步驟1之前，所述方法還包括：

生成所述局部路網的道路數據對應的子圖幅的局部概要連通圖；

生成所述全局路網的道路數據對應的全局圖幅的全網概要連通圖。

所述生成所述局部路網的道路數據對應的子圖幅的局部概要連通圖的步驟包括：

獲取所述全局路網的道路數據對應的全局圖幅；

使用預定大小的圖廓線，將所述全局圖幅分成多個子圖幅；

將所述圖廓線與所述子圖幅中的道路之間的交點，作為圖廓點；

根據所述子圖幅的圖廓點之間的道路的連接關系，獲取圖廓點之間的連接關系；

根據所述圖廓點之間的連接關系，生成局部概要連通圖；

所述生成所述全局路網的道路數據對應的全局圖幅的全網概要連通圖的步驟包括：

組合各個子圖幅對應的局部概要連通圖，生成全網概要連通圖。