[發明專利]一種導航電子地圖中避免冗余數據的差分數據產生方法

有效

• 申請號: 201210044651.1
• 申請日: 2012-02-23
• 公開（公告）號: CN103292817A
• 公開（公告）日: 2013-09-11
• 發明（設計）人: 高劍
• 申請（專利權）人: 北京四維圖新科技股份有限公司
• 主分類號: G01C21/32
• 分類號: G01C21/32
• 代理公司: 北京銀龍知識產權代理有限公司 11243
• 代理人: 郝慶芬;郭鳳麟

技術領域

本發明涉及一種導航用電子地圖的差分數據生成方法，具體來說，本發明涉及導航電子地圖中避免由點偏移引起的冗余數據的差分數據產生方法。

背景技術

由于現實世界中的地理要素存在不斷地變化和更新，為了保證地圖的準確性和實時性，導航電子地圖業界組織了大量的人力物力進行了導航電子地圖增量更新方面的研究和實踐。

圖1是現有導航電子地圖的差分數據產生方法示意圖。參照圖1，首先對原始數據進行加工，然后，經過數據訪問層，使差分數據的抽取與輸入輸出數據的規格無關。接著進行PID(permanent?ID，也即永久ID)計算，使得差分數據的抽取與原始數據是否具有PID無關。然后，動態計算好的PID存放于哈希表，并通過比較兩個版本的哈希表進行差分數據的抽取，最后生成相應的差分數據。PID動態計算存在以下優點：可以很方便地處理經過邏輯運算后得到的記錄，如路鏈記錄、路名記錄等；在保證比較的兩個版本的數據模型一致的前提下，可以做到差分數據的抽取與數據模型無關，即，可以對任意模型的數據進行差分抽取。

然而，該方法在計算動態PID時根據地理要素記錄的屬性(包括記錄的形狀坐標)生成能夠唯一標識該記錄的一個整數值。在計算過程中首先將記錄屬性轉換成一個連續的字節序列然后通過一定的計算方法生成整數值(即記錄的PID)。這種處理方法使差分數據的抽取與原始記錄是否有PID無關。由于PID計算方法對記錄屬性所對應的字節序列高度敏感，因此：

●參與比較的兩個數據版本的坐標精度必須完全一致，否則這兩個版本的數據進行比較將生成冗余的差分數據，例如：有點P其經緯度坐標為(121.517051，31.336117)，A版本的數據精度精確到小數點6位，則該點在A版本的坐標為(121.517051，31.336117)，而B版本的數據精度為精確到小數點5位，則該點在B版本的坐標為(121.51705，31.33612)，這樣它們對應的字節序列也不同，若A為基準版、B為更新版則將產生兩條冗余差分數據，即刪除了A版中的點(121.517051，31.336117)同時新增了B版中的點(121.51705，31.33612)。

●在數據編譯時存在坐標轉換，坐標轉換引起的誤差同樣會產生冗余的差分數據。

●為了避免產生點偏移引起的冗余差分數據，要求在生產和編譯更新版數據時所使用的編輯系統和編譯系統的流程完全與基準版一致，然而由于現有的數據生產規范很難保證這一點，因為這涉及到作業流程的變更、作業工具的采購和部門之間的額外溝通帶來的額外開銷等。正因為不能在生產時保證精度和流程一致，導致原有的差分數據抽取方法會產生大量的冗余差分數據，從而使得用戶在更新數據時浪費用戶大量流量增加數據傳輸時間，更新時間變長。

發明內容

有鑒于此，本發明的目的是提供一種導航電子地圖中避免冗余數據的差分數據產生方法，在產生差分數據時可避免由點偏移引起的冗余差分數據。該方法具體包括：

遍歷基準版地圖文件的所有記錄，利用哈希算法生成每條記錄的永久ID，并將生成的永久ID及對應的記錄存儲到第一哈希表中；創建所述基準版記錄的空間索引；遍歷更新版地圖文件的所有記錄，利用所述哈希算法生成每條記錄的永久ID，并將生成的永久ID及對應的記錄存儲到第二哈希表中；創建所述更新版記錄的空間索引；根據所述基準版記錄的空間索引和更新版記錄的空間索引，進行形狀相似識別處理；對經過形狀相似識別處理后的第一哈希表和第二哈希表進行比較生成差分數據，所述差分數據中包括需要刪除的記錄以及需要增加的記錄。

上述的差分數據產生方法，其中：

所述根據所述基準版記錄的空間索引和更新版記錄的空間索引，進行形狀相似識別處理具體包括：對基準版記錄或更新版記錄中的點、線、面分別構造空間索引；以四叉樹為空間索引樹，計算滿足所有的形狀相似必要條件的點偏移形狀；根據所述所有必要條件的點偏移形狀，獲得識別處理結果。

上述的差分數據產生方法，其中：

根據所述基準版記錄的空間索引和更新版記錄的空間索引，進行形狀相似識別處理進一步包括：如果基準版記錄永久ID在更新版記錄永久ID中無匹配記錄，則進行形狀相似識別處理；或者如果更新版記錄永久ID在基準版記錄永久ID中無匹配記錄，則進行形狀相似識別處理。