地圖信息處理裝置和地圖信息存儲媒體的製作方法

2023-05-30 12:27:16

專利名稱：地圖信息處理裝置和地圖信息存儲媒體的製作方法
技術領域：
本發明涉及處理地圖信息的地圖信息處理裝置和地圖信息存儲媒體，尤其 涉及便於進行地圖信息中包含的地圖數據的更新用的數據結構。
背景技術：
以往，導航裝置、便攜電話、便攜信息終端等使用的地圖數據中，例如， 如非專利文獻1所示，用將用表示道路上的地點的節點和表示地點間的道路的 鏈路表示的道路網中的道路連接作為鏈路的連接表示的多個鏈路串，表示道路 網。鏈路串中包含有關節點和鏈路的信息，多個鏈路串還分別具有表示節點的 同一性的同一節點信息，用此同一節點信息表示道路網的鏈路的連接關係。
以往的地圖數據為了表示節點的鏈路之間的通行規則，用同一節點信息所 示的節點的循環順序規定節點的進入鏈路和退出鏈路。以往的地圖數據為了使 進行交叉點上的引路的引路數據與節點帶有關聯關係，將表示引路數據存放位 置的信息設置在鏈路串內的節點中。
作為關聯技術，專利文獻l揭示一種導航用的差額更新數據編制裝置，即 使在原道路數據中反映差額數據也能進行正常的導航處理。此差額更新數據編 制裝置具有對表示已有的道路及其連接點且同時遵照規定格式的導航用的多 個道路數據編制包含表示以該數據為基準進行更新的新道路及其連接點的一 道路數據和與表示連接新道路或其連接點的已有道路及其連接點的另一道路 數據同樣的同一道路數據的差額更新數據的第l編制單元、以及編制按道路別 或連接點別規定差額更新數據對多個道路數據的對應關係的歸併數據並使其 包含導航處理中以從多個道路數據刪除另一道路數據的方式進行處理的刪除 標記的第2編制單元。
非專利文獻h "KIWIFormat Ver. 1. 10" ， KIWI研究委員會，7.2.道路
數據幀
專利文獻l:特開2004—198321號公報
如上文所述，以往的地圖數據利用設置在鏈路串的各節點的同一節點信息， 表示與某鏈路串同樣的其它鏈路串的節點，並按照此同一節點信息，從某鏈路 串的節點開始依次查找其它鏈路串的節點，並判斷返回初始節點前出現的全部 節點是否同樣的節點。由此，能知道連接這些節點上連接的各鏈路串的鏈路。 作為同一節點信息，使用指定鏈路串用的鏈路串號和指定節點用的鏈路串內節 點號。鏈路串號為鏈路串的排列順序，鏈路串內節點號為鏈路串的節點排列順 序。
以往的地圖數據如上文所述那樣構成，因此隨廢棄或新設鏈路串、廢棄或 新設節點而更新地圖數據時，需要分別改變鏈路串排列順序和鏈路串中的節點 的排列順序，並隨之改變鏈路串號和鏈路串內節點號。這時，比廢棄或新設的 鏈路串後配置的鏈路串，即使與廢棄或新設的鏈路串沒有關係，也必須更改。 同樣，比廢棄或新設的節點後配置的節點即使與廢棄或新設的節點沒有關係， 也必須更改。因此，存在應更新的數據量增大而且在鏈路串或節點更新時需要 煩雜的更新處理的問題。
用按照同一節點信息查找節點時，節點出現的順序表示進入節點的鏈路和 提出節點的鏈路。此順序因廢棄或新設按照同一節點信息査找節點中出現的鏈 路串而變化，所以即使廢棄或新設與本身無關的鏈路串時，也必須改變已有的 表示進入鏈路至退出鏈路的通行規則的信息。因此，存在應更新的數據量增大 而且在鏈路串或節點更新時需要煩雜的更新處理的問題。
地圖數據中包含表示交叉點上的引導信息的引路數據，並且每一鏈路內的 節點設置表示引路數據的存放位置的地址信息，所以廢棄或新設節點或鏈路造 成已有的引路數據存放位置變化。因此，必須改變已有的表示鏈路內的引路數 據存放位置的地址信息，存在應更新的數據量增大而且在鏈路串或節點更新時 需要煩雜的更新處理的問題。
本發明是為消除上述問題而完成的，其其目的在於提供一種地圖信息處理 裝置和地圖信息記錄媒體，在新設或廢棄道路或交叉點時，能減少指示更新用
的數據量，而且能簡單且迅速地進行更新處理。

發明內容
本發明的地圖信息處理裝置，具有存儲包含地圖數據的地圖信息的地圖 信息存儲裝置、以及對地圖信息存儲裝置中存儲的地圖信息進行更新的處理 器，其中，地圖信息存儲裝置存儲的地圖數據中包含的道路網數據，具有的數 據結構為該數據包含將用表示道路上的地點的節點和表示地點間的道路的鏈 路表示的道路網中的道路連接，表示為節點連接的鏈路的連接的鏈路串，鏈路 串利用按鏈路連接順序排列的鏈路串記錄，表示規定鏈路的鏈路記錄，對構成 鏈路串的鏈路，授予固有且不變的鏈路標識符，並且用將該節點作為一端的鏈 路的鏈路標識符，表示指示鏈路串包含的節點用的節點指示信息。
本發明的地圖信息處理裝置，具有存儲包含地圖數據的地圖信息的地圖 信息存儲裝置、以及對地圖信息存儲裝置中存儲的地圖信息進行更新的處理 器，其中，地圖信息存儲裝置存儲的地圖數據中包含的道路網數據具有的數據 結構為該數據包含將用表示道路上的地點的節點和表示地點間的道路的鏈路 表示的道路網中的道路連接，表示為節點連接的鏈路的連接的鏈路串，鏈路串 利用按鏈路連接順序排列的鏈路串記錄，表示規定鏈路的鏈路記錄，對鏈路串 包含的同一節點，授予同一節點間固有且不變的同一節點標識符，並且用同一 節點標識符，指示進入節點的鏈路或退出節點的鏈路。
本發明的存儲媒體，計算機可讀取，存儲的地圖數據中包含的道路網數據， 具有的數據結構為該數據包含將用表示道路上的地點的節點和表示地點間的 道路的鏈路表示的道路網中的道路連接，表示為節點連接的鏈路的連接的鏈路 串，鏈路串利用按鏈路連接順序排列的鏈路串記錄，表示規定鏈路的鏈路記錄， 對構成鏈路串的鏈路，授予固有且不變的鏈路標識符，並且用將該節點作為一 端的鏈路的鏈路標識符，表示指示鏈路串包含的節點用的節點指示信息。
根據本發明，地圖數據包含的道路網數據中，對構成鏈路串的鏈路用固有 且不變的鏈路標識符表示節點指示信息，因此此節點指示信息不變，與廢棄或 新設其它鏈路串或鏈路無關。因此，不需要廢棄或新設其它鏈路串或鏈路引起
的節點指示信息的更新，所以能減少指示更新用的數據量。而且，能簡單且迅 速地進行更新處理。
根據本發明，為了指示進入節點的鏈路或退出節點的鏈路，使用不依賴於 鏈路串記錄的排列順序的固有且不變的同一節點標識符，因此不需要廢棄或新 設其它鏈路串或鏈路引起的節點指示信息的更新。因此，能減少指示更新用的 數據量，而且能簡單且迅速地進行更新處理。
根據本發明，通過將此存儲媒體用於地圖信息處理裝置，與上述第l發明 的地圖信息處理裝置相同，也可實現能減少指示更新用的數據量而且能簡單且 迅速地進行更新處理的地圖信息處理裝置。


圖1是示出本發明實施方式1的地圖信息處理裝置的組成的框圖。
圖2是示出圖1所示地圖信息存儲裝置存放的地圖信息的概略數據結構的圖。
圖3是示出表示本發明實施方式1的地圖信息處理裝置中使用的最詳細道 路網的最下層矩形區道路網的例子的圖。
圖4是示出用鏈路串表示圖3所示道路網後得到的道路網例的圖。
圖5是示出一例本發明實施方式1的地圖信息處理裝置中使用的道路網數
據的數據結構的圖。
圖6是示出一例圖5所示鏈路串記錄的數據結構的圖。
圖7是示出一例本發明實施方式1的地圖信息處理裝置中使用的引路數據
的數據結構的圖。
圖8是示出一例表示圖4所示道路網的道路網數據的圖。
圖9是示出存在對圖4所示道路網的通行規則時的通行規則信息例的圖。
圖10是示出對圖4的道路網設置節點關聯信息作為引路記錄的引路數據例的圖。
圖ll是示出插入到圖1所示更新信息獲取裝置的更新用DVD-ROM中存 放的地圖更新信息概略數據結構的圖。
圖12是示出一例構成圖ll所示更新數據的更新記錄的數據結構的圖。
圖13是示出通過更新圖3所示道路網得到的道路網的圖。
圖14是示出用鏈路串表示圖13所示道路網後得到的道路網的圖。
圖15是示出一例表示圖14所示道路網的道路網數據的圖。
圖16是示出一例利用更新改變圖7所示引路數據後得到的引路數據的圖。
圖17是示出一例用於將圖8所示道路網數據更新為圖15所示道路網數據
的道路網更新數據的圖。
圖18是示出一例將圖IO所示引路數據更新為圖16所示引路數據用的引路
更新數據的圖。
圖19是示出本發明實施方式1的地圖信息處理裝置的運作的流程圖。 圖20是示出圖l所示處理器的存儲器分配的圖。
圖21是示出圖19的步驟ST18執行的地圖數據獲取和更新處理的詳細的流程圖。
圖22是示出圖21的步驟ST204執行的道路網數據更新處理的詳細的流程圖。
圖23是示出本發明實施方式2的地圖信息處理裝置中用鏈路串表示圖4所 示道路網後得到的道路網例的圖。
圖24是示出本發明實施方式2的地圖信息處理裝置中使用的一致節點指示 信息例的圖。
圖25是示出本發明實施方式2的地圖信息處理裝置中使用的對應節點指示 信息樹的圖。
具體實施例方式
下面，按照

上述本發明用的最佳實施方式，以進一步詳細說明本 發明。
實施方式1
圖1是示出本發明實施方式1的地圖信息處理裝置的組成的框圖。此地圖 信息處理裝置包含輸入裝置l、位置檢測裝置2、地圖信息存儲裝置3、更新
信息獲取裝置4、處理器5、以及輸出裝置6。
輸入裝置1按照用戶的操作或指示，輸出指示信號。具體而言，其組成部 分可包含識別用戶的聲音並輸出基於識別結果的指示信號的聲音識別裝置、 根據用戶的手動操作輸出指示信號的按鍵和其它適當的輸入裝置中的至少一 個。將此輸入裝置l輸出的指示信號，送到處理器5。
位置檢測裝置2使用例如GPS (Global Positioning System:全球定位系統) 接收機、車速傳感器和角度傳感器，檢測出裝載該地圖信息處理裝置的車輛的 當前位置。將此位置檢測裝置2檢測出的當前位置作為位置信息，送到處理器
地圖信息存儲裝置3由例如將硬碟用作地圖信息存儲媒體的硬碟驅動器構 成，作為獲取地圖數據的地圖數據獲取單元進行工作。此地圖信息存儲裝置3 預先存放地圖信息，並由處理器5讀出此存放的地圖信息。此地圖信息存儲裝 置3還存放處理器5從更新信息獲取裝置4取得的地圖更新信息。
更新信息獲取裝置4由例如DVD (Digital Versatile Disk:數字多用途光碟) 驅動器構成，讀取更新用DVD-ROM (Read Only Memory:只讀存儲器)存放 的地圖更新信息。此更新信息獲取裝置4作為獲取地圖更新數據的地圖更新數 據獲取單元進行工作。將更新信息獲取裝置4從共用鑰DVD - ROM讀取的地 圖更新信息，送到處理器5。
處理器5作為地圖數據更新單元進行工作，使用從位置檢測裝置2得到的 位置信息和從地圖信息存儲裝置3讀出的地圖信息，執行各種地圖信息處理。 地圖信息處理包括根據位置信息和地圖信息包含的地圖數據，估計車輛當前位 置的地圖對位、算出出發地至目的地的路線計算(路線檢索)、將路線計算結果 得到的較佳路線連同道路地圖一起顯示在輸出裝置6的屏幕上的路線顯示、按 照較佳路線進行出發地至目的地的導航的引路、當前位置周邊的地圖的顯示處 理等。
處理器5預先將更新信息獲取裝置4從更新用DVD - ROM讀取的地圖更 新信息存放到地圖信息存儲裝置3，在需要更新地圖信息時，從地圖信息存儲 裝置3讀取地圖信息和地圖更新信息，用地圖更新信息執行更新地圖信息的處理。
輸出裝置6按照處理器5送來的地圖信息處理結果，給用戶提示各種信息。 此輸出裝置6具體可包含例如顯示地圖、當前位置、路線、引導信息等的顯示 裝置和對用戶用聲音進行指示或引導的聲音發生裝置。
(l)地圖信息的數據結構
說明本發明實施方式1的地圖信息處理裝置使用的地圖信息的數據結構。 圖2示出地圖信息存儲裝置3存放的地圖信息的概略數據結構。地圖信息由"地 圖管理信息"、"地圖數據"和"路線計算數據"構成。
地圖數據根據道路網的詳細程度分層，並以每層分別對應於通過將全國劃 分為若千部分而得到的多個區的方式準備該數據。用"鏈路串"表示各區的道 路網，該"鏈路串"將以表示道路上的地點的"節點"和表示地點間的道路的 "鏈路"表示的道路網的連接表示為鏈路的連接。
與上述地圖數據相同，路線計算數據也根據道路網的詳細程度分層，並以 每層分別對應於通過將全國劃分為若干部分而得到的多個區的方式準備該數 據。用上述節點和鏈路表示各區的道路網。
地圖管理信息由管理每層準備的地圖數據和路線計算數據用的數據構成。 此地圖管理信息包含使各層的區域與地圖數據和路線計算數據帶有對應關係 用的信息、表示有關地圖信息中的地圖數據和路線計算數據的存放位置的信 息、表示數據規模的信息。地圖管理信息還包含表示有關地圖信息的版本的版 本信息等。
地圖數據由"地圖數據首部"、"道路網數據"、"背景數據"、"名稱 數據"、"引路數據"等構成。地圖數據首部由管理背景數據、名稱數據、引 路數據等的信息構成。道路網數據用於表示地圖對位和道路顯示中使用的道路 形狀、道路連接關係等。背景數據用於表示河川、海等地圖背景。名稱數據用 於以字符表示地名等。引路數據用於進行在交叉點等處的引路。
路線計算數據是表示計算路線用的道路網的數據，具有與構成地圖數據的 道路網數據不同的數據結構。此路線計算數據包含與計算路線用的道路網的鏈 路對應的地圖數據道路網的鏈路的鏈路號，能使雙方的道路網鏈路帶有相互對
應的關係。
接著，說明用上述地圖信息表示的道路網的具體例。圖3是示出表示最詳
細的道路網的最下層的矩形區A的道路網的例子。區A的道路網由節點N0 N9以及鏈路L00、 LIO、 L20、 L30、 L40、 L41、 L42和L50構成。圖4是用鏈 路串表示圖3所示道路網例後得到的道路網。這裡，鏈路串是指不少於l條鏈 路的連接。圖4所示的道路網中，鏈路L00和L01形成鏈路串ML0，鏈路L10 和Lll形成鏈路串ML1，鏈路L20形成鏈路串ML2，鏈路L30形成鏈路串ML3， 鏈路L40、 L41和L42形成鏈路串ML4，鏈路L50形成鏈路串ML5。
鏈路串具有方向性，將鏈路串的方向性稱為"鏈路串方向"。例如，圖4 所示道路網中，將鏈路串MLO的從節點N0朝N2方向稱為鏈路串方向。鏈路 也有方向性，並稱之為"鏈路方向"。鏈路方向與所屬鏈路串的方向相同。例 如，圖4所示道路網中，鏈路LOO的方向與鏈路串MLO的方向相同，為從節 點N0朝節點N1的方向。
鏈路兩端的節點中，相對於鏈路方向，居前(下遊)側的節點被稱為始點節點， 終端(上遊)側的節點被稱為終點節點。例如，圖4所示道路網中，鏈路LOO的 始點節點為NO，終點節點為N1。鏈路串包含的節點中，相對於鏈路串方向， 位於居前的節點被稱為鏈路串的居前節點，位於終端的節點被稱為鏈路串的終 端節點。例如，圖4所示道路網中，節點NO為鏈路串MLO的居前節點，節點 N2為鏈路串MLO的終端節點。
對鏈路授予識別該鏈路用的固有的鏈路標識符。鏈路標識符至少在該鏈路
存在於地圖數據中的期間不變。作為鏈路標識符，可用具有範圍的鏈路標識符。 將具有範圍的標識符授給將來有可能劃分成多條的鏈路和將多條鏈路合併為i
條的上層鏈路。例如，圖4所示道路網中，對鏈路LOO、 LIO、 Lll、 L20、 L30、 L40、 L41和L50分別授予編號"100" 、 "110"、 "111"、 "120"、 "130"、 "140" 、 "141" 、 "142"和"150"，作為鏈路標識符。而且，對鏈路LOl 授予具有範圍的鏈路標識符"101 104"。
現考慮某節點Nx連接多條鏈路並且存在多個包含這些鏈路的鏈路串的情 況，則多個鏈路串分別包含同樣的節點Nx。反之，多個鏈路串包含同樣的節點Nx的情況下，匯集多個鏈路串各自的節點Nx連接的鏈路，則得到節點Nx連
接的全部鏈路。因此，通過在不同的鏈路串之間示出這些鏈路串包含的節點的 同一性，能表示節點的鏈路的連接關係。
例如，圖4所示道路網中，通過示出鏈路串ML0的節點N1、鏈路串ML1 的節點N1、鏈路串ML2的節點N1、鏈路串ML3的節點N1是同樣的，能表 示節點N1上連接鏈路LOO、 LOl、 LIO、 Lll、 L20禾n L30，從而能表現圖3中 節點N1上的鏈路的連接關係。
為了示出鏈路串間的節點的同一性，鏈路串包含的各節點持有"一致節點 指示信息"。 一致節點指示信息指示與持有該一致節點指示信息的節點一致(即 同樣)的其它鏈路串的節點，並規定指示同樣節點的各一致節點指示信息，使其 指示不同的鏈路串的節點。將一致節點指示信息那樣指示鏈路串的節點的信息 稱為"節點指示信息"。
以某鏈路串MLx的節點Nx為起點，依次査找一致節點指示信息指示的節 點時，由於各一致節點指示信息指示不同的鏈路串的節點，各時間點上，到達 與包含在該時間點以前查找的節點Nx的鏈路串不同的鏈路串的節點Nx，經包 含節點Nx的全部鏈路串，最後到達初始鏈路串MLx的節點Nx。因此，可通 過依次査找一致節點指示信息指示的節點，求出多個鏈路串包含的同一節點。
例如，圖4所示道路網中，鏈路串MLO的節點N1的一致節點指示信息SO 指示其它的鏈路串ML1的節點N1，鏈路串ML1的節點N1的一致節點指示信 息Sl指示其它的鏈路串ML2的節點Nl,鏈路串ML2的節點Nl的一致節點 指示信息S2指示其它的鏈路串ML3的節點N1，鏈路串ML3的節點N1的一 致節點指示信息S3指示其它的鏈路串ML0的節點N1。這些一致節點指示信 息S0、 Sl、 S2和S3分別指示不同的鏈路串的節點N1。
利用上述結構，可根據一致節點指示信息S0的指示到達鏈路串ML1的節 點N1，根據一致節點指示信息S1的指示到達鏈路串ML2的節點N1，根據一 致節點指示信息S2的指示到達鏈路串ML3的節點Nl，根據一致節點指示信 息S3的指示到達鏈路串ML0的節點N1，能對包含節點N1的全部鏈路串ML0、 ML1、 ML2和ML3進行一次循環。由此，能求出鏈路串MLO、 ML1、 ML2和
ML3的節點Nl。
用表示將一致節點指示信息指示的節點作為端點的鏈路的鏈路標識符的 "鏈路指示信息"和表示一致節點指示信息指示的節點相當於始點側或終點側 的"始點終點指示信息"，表示該一致節點指示信息。例如，圖4所示道路網 中， 一致節點指示信息SO指示鏈路Lll的始點節點N1，所以將"1U"用作 鏈路指示信息。將"始點"用作始點終點指示信息。
再者，將一致節點指示信息指示的節點作為端點的鏈路的鏈路標識符具有 範圍時，作為鏈路指示信息，始點終點指示信息表示始點節點時使用具有範圍 的下限值的鏈路標識符，始點終點指示信息表示終點節點時使用具有範圍的上 限值的鏈路標識符。例如，圖4所示道路網中， 一致節點指示信息S3指示鏈 路LOl的始點節點N1，所以將"101"用作鏈路指示信息，將"始點"用作始 點終點指示信息。 一致節點指示信息S5指示鏈路L01的終端節點N2，所以將 "104"用作鏈路指示信息，將"終點"用作始點終點指示信息。
對各鏈路串包含的同一節點授予同一節點之間固有且不變的同一節點標識 符，以便識別各同一節點。例如，圖4所示道路網中，對鏈路串MLO的節點 Nl、鏈路串ML1的節點Nl、鏈路串ML2的節點N1和鏈路串ML3的節點Nl 分別授予編號"3" 、 "1" 、 "4"和"2"作為同一節點標識符。同樣，對鏈 路串MLO的節點N2和鏈路串ML4的節點N2分別授予編號"1"和"2"作為 同一節點標識符。
圖5示出一例表示道路網的道路網數據的數據結構。道路網數據由"道路 網數據首部"和"鏈路串列表"構成。道路網數據首部存放用於管理該道路網 數據的數據規模、存放鏈路串列表的鏈路串記錄的數量等該道路網數據用的信 息。鏈路串列表包含與構成該道路網數據表示的道路網的鏈路串對應設置的鏈 路串記錄的集合。從鏈路串包含的鏈路的鏈路標識符值小的開始，依次排列鏈 路串記錄。
圖8是一例表示圖4所示道路網的道路網數據。表示道路網的鏈路串列表 包含分別對應於鏈路串MLO、 ML1、 ML2、 ML3、 ML4和ML5的鏈路串記錄 #1、鏈路串記錄弁2、鏈路串記錄#3、鏈路串記錄#4和鏈路串記錄#5。鏈
路串ML0、ML1、ML2、ML3、ML4和ML5的鏈路標識符的範圍分別為"100" "104"、 "IIO，， "111" 、 "20，， "120" 、 "130" "130" 、 "140，， "142"和"150"，從這些鏈路標識符的值小的開始，依次排列鏈路串記錄。
圖6示出一例圖5所示鏈路串記錄的數據結構。鏈路串記錄由"鏈路串首 部"和"鏈路列表"構成。鏈路串首部包含表示該鏈路串記錄的數據規模的"鏈 路串記錄規模"、表示該鏈路串記錄設置的鏈路記錄的數量的"鏈路記錄數"、 表示與該鏈路串記錄對應的鏈路串包含的鏈路的鏈路標識符的範圍(最小值和 最大值)的"鏈路標識符範圍信息"和表示與該鏈路串記錄對應的鏈路串的道路 類別、線路號等的"鏈路串屬性信息"。
鏈路列表包含與構成有關鏈路串記錄所對應的鏈路串對應設置的鏈路記錄 的集合。排列鏈路記錄，使對應的鏈路的排列順序與往鏈路串方向的相同方向 查找鏈路串時的鏈路排列順序相同。
再者，此道路網數據中，規定將鏈路串的終端節點作為始點節點的虛擬鏈 路(即終端虛擬鏈路)，將對終端虛擬鏈路的鏈路記錄配置在鏈路列表的末尾。 例如，圖8中，作為鏈路列表，對圖4所示道路網的鏈路串ML0分別與鏈路 L00和L01對應地設置鏈路記錄#00和鏈路記錄#01，而且對以鏈路串MLO 的終端節點N2為始點的終端虛擬鏈路設置鏈路記錄弁02，並按鏈路記錄#00、 鏈路記錄弁Ol和鏈路記錄#02的順序排列它們。
如圖6所示，鏈路記錄由"鏈路首部"、"一致節點指示信息"、"鏈路 形狀信息"和"通行規則信息"構成。
鏈路首部包含表示該鏈路記錄的數據規模的"鏈路記錄規模"；表示構 成鏈路形狀信息的形狀記錄的數量的"插補點記錄數"；構成通行規則信息的 "規則記錄數"的管理該鏈路記錄用的信息；表示該鏈路的鏈路標識符的"鏈 路識別信息"；表示該鏈路的道路寬度、車道數、單行線規則、上下行線分離 /非分離的道路結構上的特性的鏈路類別、表示鏈路始點側是否連接該道路網 數據所示區域的邊界的邊界信息；示出有沒有涉及始點節點的引導信息的有無 引導信息的該鏈路的各種屬性的"鏈路屬性信息"。
再者，鏈路標識符具有範圍時，由有關鏈路的鏈路記錄的鏈路識別信息表
示鏈路標識符的下限值，通過從下一鏈路記錄的鏈路識別信息表示的鏈路標識 符的值減去"1"，得到鏈路標識符的上限值。而且，從有關鏈路串首部的鏈 路標識符範圍信息的最大值得到鏈路為鏈路串的終端鏈路時的鏈路標識符的 上限值。
一致節點指示信息表示對鏈路的始點節點授予的一致節點指示信息，並且 如上文所述，由鏈路指示信息和始點終點指示信息構成。其它的鏈路串不存在 與鏈路的始點節點同樣的節點時，作為鏈路指示信息，使用"一l"(即作為鏈
路標識符未授予鏈路的值)。例如，圖8中，對圖4所示的道路網而言，鏈路串 ML0的鏈路LOl的鏈路記錄弁Ol的一致節點指示信息使用鏈路Lll的鏈路標 識符"111"作為鏈路指示信息，使用表示始點側的值作為始點終點指示信息， 以表示一致節點指示信息S0。而且，鏈路串ML4的鏈路L42的鏈路記錄弁42 的一致節點指示信息使用鏈路LOl的鏈路標識符"104"作為鏈路指示信息， 使用表示終點側的值作為始點終點指示信息，以表示一致節點指示信息S5。
鏈路形狀信息包含由近似道路中心線的折線表示鏈路的道路形狀時的、與 折線的始點節點側端點和各頂點對應設置的形狀記錄的集合。
通行規則信息包含表示有關鏈路的始點節點的鏈路間的通行所涉及的規則 的信息，由與此規則對應設置的通行規則記錄的集合組成。再者，在多個鏈路 串包含的l個同一節點設置通行規則信息。通行規則記錄的組成部分包含表示 進入鏈路的始點節點的同一節點標識符的"進入側同一節點標識符"、表示與 包含同一節點標識符所示節點的鏈路串的方向同方向或反方向的"進入方向指 示信息"、表示退出鏈路的始點節點的同一節點標識符的"退出側同一節點標 識符"、表示與包含同一節點標識符所示節點的鏈路串的方向同方向或反方向 的"退出方向指示信息"和表示進入鏈路至退出鏈路的通行規則內容"通行規 則碼"。
圖9是對圖4所示的道路網存在從鏈路L00進入並退出到鏈路L10的通行 規則時，鏈路串L01的鏈路L10的鏈路記錄弁01中設置的通行規則信息的例子。 此例中，對通行規則的通行規則記錄中，存放鏈路串MLO的節點N1的同一節 點標識"3"作為進入側同一節點標識符，存放表示同一方向的值作為從與鏈
路串ML0同一方向進入到鏈路串ML0的節點Nl用的進入方向指示信息，存 放鏈路串ML1的節點N1的同一節點標識"1"作為退出側同一節點標識符， 存放表示反方向的值作為往與鏈路串MLO相反的方向退出鏈路串ML1的節點 Nl用的退出方向指示信息，存放例如表示禁止通行的碼作為通行規則碼。
接著，說明引路數據。圖7示出一例引路數據的數據結構。引路數據由與 節點對應設置的引路記錄的集合構成。將此引路記錄那樣設置得與節點帶有關 聯關係的信息稱為節點關聯信息。
引路記錄由節點中的引路需要的各種數據組成，包括"引路記錄首部"、 表示節點的交叉點名稱的"交叉點名稱數據"、表示節點連接的鏈路的道路名 稱的"道路名稱數據"、以及表示節點連接的鏈路走向的"方向名稱數據"。
引路記錄首部包含表示該引路記錄的數據規模的"引路記錄規模"、指示 對應的節點的"對應節點指示信息"、表示交叉點名稱數據的規模的"交叉點 名稱規模"、表示方向名稱數據的規模的"方向名稱數據規模"。
對應節點指示信息表示與該引路記錄對應的節點，其組成部分包含表示將 對應的節點作為端點的鏈路的鏈路標識符的鏈路指示信息和表示對應的節點 是對應鏈路指示信息表示的鏈路的始點節點或終點節點的始點終點指示信息。 對應節點指示信息指示鏈路串的節點，是一種節點指示信息。
這樣，使節點與引路記錄帶有對應關係的數據被保持在引路數據側，而不 保持在道路網數據側。因此，對使節點與引路記錄帶有對應關係的數據而言， 即使更新引路數據也不影響道路網數據。
又，對應節點指示信息中使用的鏈路標識符不變，因此即使發生廢棄或新 設鏈路指示信息表示的鏈路以外的鏈路、廢棄或新設由鏈路指示信息表示的鏈 路以外的鏈路組成的鏈路串，該引路記錄的對應節點指示信息也不變化。因此， 對上述道路網更新不必更新該引路記錄的對應節點指示信息。再者，按鏈路指 示信息表示的鏈路標識符的值遞增的順序排列引路記錄，能方便地進行基於鏈 路標識符的引路記錄的檢索。
圖IO示出引路數據的例子，其中對圖4所示道路網，在鏈路串ML2的節 點N1和鏈路串ML4的節點N2分別設置引路記錄弁0和引路記錄弁1。此例中，
使用鏈路L20的鏈路標識符"120"作為引路記錄#0的對應節點指示信息的鏈 路指示信息，使用表示終點的值作為始點終點指示信息，使用鏈路L42的鏈路 標識符"142"作為引路記錄弁l的對應節點指示信息的對應鏈路指示信息，使 用表示始點的值作為始點終點指示信息，並按引路記錄#0、引路記錄#1的順 序進行存放，以便形成鏈路指示信息表示的鏈路標識符的值遞增的順序。再者， 將鏈路串ML2的節點N1作為始點的終端虛擬鏈路的鏈路記錄弁01和將鏈路串 ML4的節點N2作為始點的L42的鏈路記錄#42各自的鏈路首部的鏈路屬性信 息內的有無引導信息中存放表示"有"引導信息的值。 (2)地圖更新信息的數據結構
說明更新本發明實施方式1的地圖信息處理裝置使用的地圖信息用的地圖 更新信息的數據結構。圖11是概略示出插入到更新信息獲取裝置4的更新用 DVD-ROM中存放的地圖更新信息的數據結構的圖。此地圖更新信息由"地 圖更新管理信息"、"地圖更新數據"和"路線計算更新數據"構成。
地圖更新管理信息由每層管理地圖更新數據用的數據構成，包含使各層中 的區域與地圖更新數據和路線計算更新數據帶有對應關係用的信息、表示地圖 更新數據和路線計算更新數據在地圖更新信息中的存放位置的信息、表示數據 規模的信息。地圖更新管理信息包含表示DVD-ROM存放地圖更新信息的"數 據識別信息"、表示因該地圖更新信息而成為更新對象的地圖信息的版本的"更 新對象版本信息"、通過該地圖更新信息進行更新而得到的地圖信息的版本的 "更新版本信息"。
地圖更新數據是更新地圖數據用的數據，設置得與地圖數據對應。地圖更 新信息中不包含對不必更新的地圖數據的地圖更新數據。路線計算更新數據是 更新路線計算數據用的數據，設置得與路線計數據對應。地圖更新信息中不 包含對不必更新的路線計算數據的路線計算更新數據。
地圖更新數據的組成部分包含分別更新道路網數據、背景數據、名稱數據 和引路數據等用的道路網更新數據、背景更新數據、名稱更新數據和引路更新 數據等(後文統稱為"更新數據")以及地圖更新數據首部。地圖更新信息中不 包含不必更新的道路網數據、背景數據、名稱數據或引路數據等所對應的更新
數據。由不少於l個的更新記錄構成各更新數據。
圖12是示出一例更新記錄的數據結構的圖。更新記錄的組成部分包含"更 新記錄規模"、"更新對象數據類別"、"更新操作類別"、"更新對象指定" 和"更新操作數"。更新記錄規模表示該更新記錄的數據規模。更新對象數據 類別表示該更新記錄構成形成更新對象的道路網數據、背景數據、名稱數據、 引路數據等的數據的類別。更新操作類別表示對更新對象類別、更新對象指定 所示數據的蓋寫、刪除、置換、添加等更新操作的類別。更新對象指定表示更 新對象類別所示數據的更新處。更新操作數表示按照更新操作類別蓋寫、置換 或添加的數據及其數據規模。而且，由以更新對象數據類別和更新對象指定的 數據的始端為基準的地址示出進行蓋寫、置換的始點位置。再者，更新操作類 別為刪除時，不設更新操作數。
地圖更新數據首部是管理地圖更新數據首部、道路網更新數據、背景更新 數據、名稱更新數據、引路更新數據等用的數據，包含表示這些更新數據在該 地圖更新數據中的存放位置、數據規模、更新記錄數等的信息。
接著，說明道路網的更新例。圖13示出通過更新圖3所示道路網而得到的 道路網。此圖13所示的道路網構成廢棄圖3所示道路網的節點N5和N7、鏈 路L20禾BL40，新設節點N10和N11、鏈路L60和L61，而且將鏈路L01劃分 成鏈路L01a和L01b這2條，在劃分的地點新設節點Nla。
圖14示出用鏈路串表示圖13所示的道路網後得到的道路網。此圖14所示 的道路網在圖4的道路網中廢棄鏈路串ML2，廢棄鏈路串ML4的節點N7和鏈 路L40，新設鏈路串ML6，將鏈路串MLO的鏈路LOl置換成鏈路L01a和鏈路 L01b，並且授予"101" "102"作為鏈路L01a的鏈路標識符，授予"103" "104"作為鏈路L01b的鏈路標識符
接著，說明道路網更新中的道路網數據更新例。圖15是一例表示圖14所 示道路網的道路網數據，此道路網數據是以下那樣更新圖8所示的道路網數據 後得到的數據。即，對圖8所示的鏈路串列表，隨著廢棄鏈路串ML2，刪除鏈 路串記錄#2，隨著新設鏈路串ML6，將表示鏈路串ML6的鏈路串記錄井6插 入到鏈路串記錄#1的前面，使鏈路串記錄形成鏈路標識符範圍的遞增順序，
從而構成圖15所示的鏈路串列表。
對圖8所示的鏈路列表0，隨著劃分鏈路LOl，刪除鏈路記錄弁Ol，並插入 鏈路L01a的鏈路記錄井01a和鏈路L01b的鏈路記錄弁01b，從而構成圖15所 示的鏈路串記錄#0的鏈路列表0。又，對圖8所示的鏈路列表4，隨著廢棄鏈 路L40，刪除鏈路記錄#40，從而構成圖15所示的鏈路串記錄#4的鏈路列表 4。
圖15所示的道路網數據首部'、鏈路串首部O'、鏈路串首部4'是改變圖8 所示的道路網數據首部、鏈路串首部O、鏈路串首部4以便反映上述更新而得 的。圖15所示的鏈路記錄#11'是隨著廢棄鏈路串ML2改變圖8所示的鏈路記 錄#11的一致節點指示信息以便指示鏈路串ML3的節點N1而得的，並改變成 指示鏈路串ML3的節點N1作為鏈路串ML1的節點N1的同一節點。
圖15所示的鏈路記錄#43，是將圖8所示的鏈路記錄弁43的一致節點指示 信息改變成指示鏈路串ML6的節點N9而得的。而且，將圖15所示的鏈路記 錄弁62的一致節點指示信息設定成指示鏈路串ML4的節點N9。因而，能利用 圖15所示的鏈路記錄#43'的一致節點指示信息和圖15所示的鏈路記錄#62 的一致節點指示信息示出鏈路串ML4的節點N9和鏈路串ML6的節點N9是同 樣的節點。
再者，圖14中，即使更新上述道路網，鏈路L01a的鏈路標識符下限值、 鏈路L01b的鏈路標識符上限值、鏈路Lll和鏈路L42的鏈路標識符也不變， 所以一致節點指示信息S0、 S3、 S4、 S5不變化。因此，不必更新表現它們的 —致節點指示信息。即使更新道路網時，鏈路串MLO、 ML1和ML3的節點Nl 的各同一節點標識符也不變，所以鏈路串MLO的鏈路LOl的鏈路記錄弁Ol中 設置的通行規則信息(參考圖9)不因上述更新而變化，不必對其更新。
接著，說明更新引路數據的例子。圖16所示的引路數據中，決定隨著廢棄 鏈路串ML2，廢棄對鏈路串ML2的節點Nl的引路，並從引路數據刪除作為其 節點關聯信息的引路記錄#0(參考圖10)。
接著，說明道路網更新數據的例子。圖17示出一例用於將圖8所示的道路 網數據更新為圖15所示的道路網數據的道路網更新數據。圖17中，鏈路串號
意指將始端取為"0"的鏈路串記錄的鏈路串列表的排列順序，鏈路號意指將 始端取為"0"的鏈路記錄的鏈路列表的排列順序。利用設定來指定更新對象 的鏈路串號、鏈路號指定成為更新對象的鏈路串記錄、鏈路記錄。圖17中， 省略更新操作數的數據規模、始端位置的說明。
下面，說明圖17所示的各更新記錄。
(1) 更新記錄井rl指示在圖8所示的鏈路串首部0蓋寫反映刪除鏈路記錄# 01和插入鏈路記錄弁01a和鏈路記錄井01b的圖15所示的鏈路串記錄#0'。
(2) 更新記錄弁r2指示從圖8所示的鏈路列表0刪除鏈路記錄#01。
(3) 更新記錄井r3指示在圖8所示的鏈路列表0的鏈路記錄#2的前面插入 鏈路記錄W01a和鏈路記錄弁01b。
(4) 更新記錄#r4指示在圖8所示的鏈路串記錄# 1的前面插入圖15的鏈路 串記錄弁6。
(5) 更新記錄弁r5指示用表示指示鏈路串ML3的節點Nl的一致節點指示信 息S1'的一致節點指示信息蓋寫圖8所示的鏈路列表1的鏈路記錄弁Ol的一致 節點指示信息。
(6) 更新記錄ftr6指示刪除圖8所示的鏈路串記錄井2。
(7) 更新記錄弁r7指示用圖15所示的鏈路串首部4'蓋寫圖8所示的鏈路串記 錄#4的鏈路串首部4。
(8) 更新記錄弁r8指示刪除圖8所示的鏈路列表4的鏈路記錄井40。
(9) 更新記錄弁r9指示用表示指示鏈路串ML6的節點N9的一致節點指示信 息Sll的一致節點指示信息蓋寫圖8所示的鏈路列表4的鏈路記錄#03的一致 節點指示信息。
接著，說明引路更新數據。圖18示出一例將圖IO所示的引路數據更新為 圖16所示的引路數據用的引路更新數據。示出此引路更新數據中，更新記錄 弁gO刪除圖8所示的引路記錄#0。
這裡，利用上述數據結構說明能減少更新數據量的理由。如上文所述，即 使進行廢棄鏈路串ML2、廢棄鏈路L40、新設鏈路串ML6，鏈路標識符也不變， 所以分別指示與這些廢棄或新設的鏈路或鏈路串無關的節點(即作為沒有指示
它們包含的節點的一致節點指示信息的節點的鏈路串ML1的節點Nl和N4、 鏈路串ML3的節點N6、鏈路串ML5的節點N4和N6)的一致節點指示信息S0、 S8、 S6、 S9和S7不變。因此，圖17所示的道路網更新數據不必包含無關鏈路 或鏈路串的廢棄或新設引起的更新一致節點指示信息用的更新記錄，所以能比 以往減少道路網更新數據量。
劃分鏈路LOl的情況下，鏈路L01a的鏈路標識符下限值和L01b的鏈路標 識符上限值也不變，而且指示鏈路串ML0的節點Nl和N2的一致節點指示信 息S3和S5不變。因此，圖17所示的道路網更新數據不必包含鏈路劃分引起 的更新一致節點指示信息用的更新記錄，所以能減少道路網更新數據量。
又，圖4所示的鏈路串LM4的節點N2的一致節點指示信息S5那樣，使一 致節點指示信息包含始點終點指示信息，從而鏈路串的終端節點也能作基於鏈 路指示信息的同一節點的指示，所以可對道路網的全部節點使用鏈路標識符表 示節點的同一性，取得上述能減少道路網更新數據量的效果。
如上文所述，對廢棄與圖9所示的通行規則信息無關的鏈路串ML2，鏈路 串ML0、 ML1和ML3的節點N1的各同一節點標識符不變，所以鏈路串ML0 的鏈路LOl的鏈路記錄#01中設置的通行規則記錄弁O的進入側同一節點標識 符、退出側同一節點標識符沒有變化，不需要對它們的更新數據。因此，圖17 所示的道路網更新數據不必包含與圖9所示的通行規則信息無關的鏈路串更新 引起的通行規則信息的更新記錄，所以能減少道路網更新數據量D
如上文所述，刪除圖10所示的引路數據的引路記錄#0時，引路記錄#1 的存放位置變化，但以往為了使節點與引路記錄帶有對應關係，在道路網數據 側保持對應的引路記錄的存放位置，所以不管引路記錄#1本身未受到更新， 需要更新其存放位置，產生本來不需要的更新數據。與此相反，本實施方式l 中，道路網數據側不保持對應的引路記錄的存放位置，所以不需要上述更新， 圖17所示的道路網更新數據不必包含更新存放位置用的更新記錄，能減少道 路網更新數據量。
而且，如上文所述，即使進行廢棄鏈路串ML2、廢棄鏈路L40、新設鏈路 串ML6，也使用不變的鏈路標識符作為對應節點指示信息，所以不必改變與它
們無關的引路記錄井1的對應節點指示信息，圖18所示的引路更新數據不必包 含與該引路數據無關的鏈路串或鏈路的更新引起的更新記錄，所以能減少道路 網更新數據量。
接著，參照圖19所示的流程圖說明更新具有上文那樣構成的數據結構的地
圖數據的地圖信息處理裝置。下面，作為一個例子，說明將圖8所示的道路網
數據和圖IO所示的引路數據分別更新為圖15所示所道路網數據和圖16所示 的引路數據從而將圖4所示的道路網更新為圖14所示的道路網的情況。
圖20是示出處理器5的存儲器(未示出)的分配的圖。此存儲器中分配存放 控制地圖信息處理裝置的運作用的數據的運作控制數據部10、存放位置檢測裝 置2得到的位置信息的時間序列(即行駛軌跡數據)的行駛軌跡數據部11、存放 表示車輛當前位置的數據的當前位置數據部12、存放表示出發地至目的地的路 線的路線數據的路線數據部13、存放所需路線計算管理數據的所需路線計算數 據管理部14、存放路線計算數據的路線計算數據部15、存放路線計算更新數 據的路線計算更新數據部16、存放所需地圖管理數據的所需地圖數據管理部 17、存放地圖數據的地圖數據部18、存放地圖更新數據的地圖更新數據部19。
首先，進行初始化處理(步驟STIO)。接著，調査更新信息獲取裝置4中是 否插入更新用DVD-ROM(步驟STll)。此步驟STll中判斷為插入更新用 DVD-ROM時，獲取地圖更新信息(步驟ST12)。即，處理器5讀取插入在更新 信息獲取裝置4的更新用DVD-ROM存放的地圖更新信息的地圖更新管理信 息，同時還讀取地圖信息存儲裝置3存放的地圖信息的地圖管理信息。於是， 對讀取的地圖更新管理信息中包含的更新對象版本信息和地圖管理信息中包 含的版本信息進行比較，如果它們一致，判定可作基於地圖更新信息的地圖信 息更新，從更新用DVD-ROM讀取地圖更新信息，存放到地圖信息存儲裝置 3。然後，程序進至步驟ST13。上述步驟ST11中判定未插入更新用DVD-ROM 時，不進行獲取地圖更新信息，程序進至步驟ST13。
步驟ST13中，進行輸入處理。即，處理器5根據從輸入裝置1接收的、遵 照用戶的操作或指示的指示信號，產生例如控制地圖顯示縮小比例尺、目的地、 路線計算啟動指示等地圖信息處理裝置運作用的數據，存放到運作控制數據部
10。接著，獲取當前位置(步驟ST14)。即，處理器5從位置檢測裝置2獲取位
置信息，將取得的位置信息累積存放到行駛軌跡數據部11，同時還將第l次的
步驟ST14的處理中取得的位置信息作為當前位置，存放到當前位置數據部12。 接著，調查是否指示啟動路線計算(步驟ST15)。即，處理器5根據運作控 制數據部IO存放的數據讀出是否啟動路線計算。這裡，判定指示啟動路線計 算，則程序進至步驟ST16;判定未啟動路線計算，則進至步驟ST18。
步驟ST16中，進行路線計算數據的獲取和更新。即。處理器5將當前位置 數據部12存放的位置信息作為出發地，存放到運作控制數據部10，並進行得 到運作控制數據部IO存放的出發地至目的地的較佳路線用的路線計算所需的 路線計算數據的獲取和更新。接著，進行路線計算(步驟ST17)。即，處理器5 用步驟ST17中取得並加以更新的路線計算數據進行路線計算，求出出發地至 目的地的較佳路線，並將表示此求出的路線的路線數據存放到路線數據部13。 而且，處理器5取消運作控制數據部10存放的路線計算啟動指示。然後，程 序進至步驟ST18。
步驟ST18中，進行地圖數據的獲取和更新。SP，處理器5獲取當前位置數 據部12存放的位置信息所示的當前位置的周邊的地圖顯示、地圖對位和引路 所需的地圖數據，將此取得的地圖數據存放到地圖數據部18，從而進行地圖數 據的更新。後面進一步詳細說明此步驟ST18執行的處理。
接著，進行地圖對位(步驟ST19)。 SP，處理器5利用行駛軌跡數據部ll存 放的行駛軌跡數據和地圖數據部18存放的地圖數據中包含的道路網數據，估 計車輛行駛的鏈路和鏈路上的位置，求出該車輛的當前位置，將此求出的當前
位置存放到當前位置數據部12。根據行駛軌跡數據與鏈路或連接的鏈路的形狀 的關係性進行鏈路和鏈路上的位置的估計。通過這樣引用鏈路的連接關係，謀 求提高鏈路的估計精度。
上述地圖對位的處理中，根據鏈路記錄的鏈路形狀信息取得鏈路形狀。根 據鏈路記錄的一致節點指示信息求出鏈路連接關係。即，按照一致節點指示信 息依次查找同樣的節點，從而求出全部同一節點，並形成將以此求出的節點作 為始點或終點的鏈路相互連接的鏈路。不能確定鏈路時，將行駛軌跡數據部ll
存放的最新位置信息存放到當前位置數據部12，作為當前位置。
上述按照一致節點指示信息依次查找同樣的節點的處理中，找具有鏈路指 示信息所示鏈路標識符的鏈路時，求出包含鏈路標識符的鏈路串記錄，從求出 的鏈路串記錄包含的鏈路列表中找出具有鏈路指示信息所示的鏈路標識符的 鏈路記錄，但按鏈路串包含的鏈路的鏈路標識符的範圍的小到大順序排列鏈路 串記錄，所以能較快速地找到符合的鏈路串記錄。
接著，進行地圖顯示(步驟ST20)。即，處理器5按照地圖數據部18存放的 地圖數據包含的道路網數據、背景數據和名稱數據，使描繪成運作控制數據部 IO存放的數據指示的顯示縮小比例尺的道路、背景和名稱組成的地圖畫面顯示 在輸出裝置6上。遵照道路網數據的道路描繪中，根據鏈路串首部的鏈路串屬 性信息的道路類別決定道路的描繪色，用該節點的描繪色描繪鏈路記錄的鏈路 形狀信息所示的折線。
接著，顯示當前位置(步驟ST21)。 g卩，處理器5使表示當前位置的圖形顯 示在步驟ST20中顯示的地圖畫面上的相當於當前位置數據部12存放的位置信 息所示的當前位置的部位。接著，進行路線顯示(步驟ST22)。 g卩，處理器5在 步驟ST20中顯示的地圖畫面上突出顯示步驟ST17中得到的路線數據，以便能 判別為路線。
接著，進行引路(步驟ST23)。 gp，處理器5調查是否有處於步驟ST19中得 到的有關車輛行駛的鏈路的前方的節點的引路記錄，如果有對應的引路記錄，
將引路數據的相當的引路記錄送到輸出裝置6，從而進行有關處於前方的節點 的引導畫面的顯示、聲音引導。然後，程序返回步驟ST11後，重複執行上述 步驟ST11 ST23的處理。
綜上所述，使用由更新用DVD - ROM存放的地圖更新信息更新的地圖數 據，進行地圖顯示、地圖對位、路線計算、引路等地圖信息處理。
接著參照圖21所示的流程圖說明上述步驟ST10執行的地圖數據的獲取和 更新處理的詳細。
此地圖數據的獲取和更新處理中，首先，決定所需地圖數據(步驟ST200)。 即，處理器5求出當前位置數據部12存放的位置信息所示的當前位置的周邊
的地圖顯示、地圖對位和引路所需的各地圖數據的層和區，作為所需地圖管理 數據，存放到所需地圖數據管理部17。
其次，進行地圖數據的讀取(步驟ST201)。即，處理器5從地圖信息存儲裝 置3的地圖信息中讀取所需地圖數據管理部17的所需地圖管理數據，存放到 地圖數據部18。接著，調査是否存在地圖更新數據(步驟ST202)。 g卩，處理器 5調查地圖信息存儲裝置3是否存放地圖更新信息，詳細而言，調査是否存在 與利用地圖信息存儲裝置3的地圖更新信息的地圖更新管理信息在步驟ST201 取得的地圖數據同一層且同一區的地圖更新數據。這裡，判定不存在地圖更新 數據，則程序進至步驟ST209。
另一方面，上述步驟ST202中判定存在地圖更新數據，則進行地圖更新數 據的讀取(步驟ST203)。 SP，處理器5讀取與步驟ST201從地圖信息存儲裝置 3的地圖更新數據中取得的地圖數據同一層且同一區的地圖更新數據，存放到 地圖更新數據部19。接著，進行道路網數據更新(步驟ST204)。 g卩，處理器5 利用在步驟ST203取得並存放到地圖更新數據部19的地圖更新數據中包含的 道路網更新數據更新在步驟ST201取得並存放到地圖數據部18的地圖數據中 包含的道路網數據。後面進一步詳細說明此電路區數據的更新處理。
接著，進行背景數據更新(步驟ST205)。 S卩，處理器5利用在步驟ST203取 得並存放到地圖更新數據部19的地圖更新數據中包含的背景更新數據更新在 步驟ST201取得並存放到地圖數據部18的地圖數據中包含的背景數據。接著， 進行名稱數據更新(步驟ST206)。 g口，處理器5利用在步驟ST203取得並存放 到地圖更新數據部19的地圖更新數據中包含的名稱更新數據更新在步驟 ST201取得並存放到地圖數據部18的地圖數據中包含的名稱數據。
接著，進行引路數據更新(步驟ST207)。 S卩，處理器5利用在步驟ST203取 得並存放到地圖更新數據部19的地圖更新數據中包含的引路更新數據更新在 步驟ST201取得並存放到地圖數據部18的地圖數據中包含的引路數據。由此， 根據圖18所示的引路更新數據的更新記錄弁g0刪除圖IO所示的引路數據的引 路記錄號弁O，將圖IO所示的引路數據更新為圖16所示的引路數據。此引路 數據更新處理中，圖18所示的引路更新數據不包含與該引路數據無關的鏈路
串或鏈路的更新引起的更新記錄，所以能快速進行引路數據更新。
接著，進行地圖數據首部更新(步驟ST208)。 gp，處理器5依據上述道路網 數據、背景數據、名稱數據和引路數據的更新，更新地圖數據中包含的地圖數
據首部的內容。接著，調查所需地圖數據的讀取是否結束(步驟ST209)。艮卩， 處理器5調查所需地圖數據管理部17的地圖管理數據表示的全部地圖數據的 讀取是否結束。這裡，判定所需地圖數據的讀取結束，則記述地圖數據的獲取 和更新處理。反之，判定所需地圖數據的讀取未結束，則程序返回步驟ST201， 其後重複步驟ST201 ~ ST209的處理。
接著，參照圖22所示的流程圖說明圖21的步驟ST204執行的道路網數據 更新處理的詳細。
此道路網數據更新處理中，首先，進行更新記錄的獲取(步驟ST300)。艮卩， 處理器5從在步驟ST203取得並存放到地圖更新數據部18的地圖更新數據中 包含的道路網更新數據獲取更新記錄。接著，進行更新對象的更新(步驟ST31)。 即，處理器5按照更新操作類別，用更新操作數的數據更新步驟ST300中取得 的更新記錄的更新對象數據類別和更新對象指定所確定的部分道路網數據。
具體而言，對步驟ST300取得的圖17所示道路網更新數據中包含的各更新 記錄進行下列處理。
(1) 對更新記錄tfrl用鏈路串首部O'蓋寫圖8所示鏈路串記錄#0的鏈路串 首部。
(2) 對更新記錄弁r2刪除圖8所示鏈路列表0的鏈路記錄弁Ol。
(3) 對更新記錄# r3在圖8所示鏈路列表0的鏈路記錄# 02的前面插入鏈路 記錄井01a和鏈路記錄弁01b。
(4) 對更新記錄Wr4在圖8所示鏈路串記錄#1的前面插入鏈路串記錄弁6。
(5) 對更新記錄弁r5用指示鏈路串ML3的節點Nl的一致節點指示信息蓋寫 圖8所示鏈路列表1的鏈路記錄#01的一致節點指示信息。
(6) 對更新記錄弁r6刪除圖8所示的鏈路串記錄#2。
(7) 對更新記錄井r7用鏈路串首部4'蓋寫圖8時鏈路串記錄井4的鏈路串首 部4。
(8) 對更新記錄弁r8刪除圖8所示鏈路列表4的鏈路記錄弁40。
(9) 對更新記錄ftr9用指示鏈路串ML5的節點N9的一致節點指示信息蓋寫 圖8所示鏈路列表4的鏈路記錄井03的一致節點指示信息。
接著，調查更新記錄獲取是否結束(步驟ST302)。即，處理器5根據道路網 更新數據調查全部更新記錄的獲取是否結束。這裡，判定更新記錄獲取未結束， 則程序返回步驟ST300，重複執行上述處理。此重複執行的中途，在步驟ST302 判定更新記錄獲取結束，則進行道路網數據首部更新(步驟ST303)。 g卩，依據 按照更新記錄進行更新的結果，進行道路網數據中包含的道路網數據首部的更 新。至此，道路網數據的更新處理結束。
利用上迷步驟ST300 ST303的處理，將圖8所示的道路網數據和圖10所 示的引路數據分別更新為圖15所示的道路網數據和圖16所示的引路數據，從 而將圖4所示的道路網更新為圖14所示的道路網。
上述步驟ST300 ST303的處理中，圖17所示的道路網更新數據不包含廢 棄或新設無關鏈路或鏈路串引起的一致節點指示信息的更新記錄，所以能進一 步快速進行道路網數據的更新。而且，圖n所示的道路網更新數據不包含劃 分鏈路引起的一致節點指示信息的更新記錄，所以能進一步快速進行道路網數 據的更新。
又，通過將始點終點指示信息用作一致節點指示信息，鏈路串的終端節點 也可作基於鏈路指示信息的同一節點的指示，可對道路網的全部節點用鏈路標 識符表示同一性。其結果，不產生不需要的更新數據，能進一步快速進行道路 網數據的更新。
圖17所示的道路網更新數據也不包含與圖9所示通行規則信息無關的鏈路 串的更新引起的通行規則信息的更新記錄，因此能進一步快速進行道路網數據 的更新。而且，圖17所示的道路網更新數據不包含更新對應的引路記錄的存 放位置用的更新記錄，所以能進一步快速進行道路網數據的更新。
如上文所說明，根據本發明實施方式1的地圖信息處理裝置，構成用不依 賴於鏈路串記錄或鏈路記錄的排列順序的鏈路固有且不變的鏈路標識符表示 節點的同一性，因此不發生廢棄或新設無關鏈路串或鏈路引起的一致節點指示
信息的改變。其結果，能減少更新數據量，同時還能進一步快速進行道路網數 據的更新。而且，可用始點終點指示信息指定鏈路串的終端節點，所以能用鏈 路固有且不變的鏈路標識符表示全部節點的同一性。
又，構成將上述鏈路標識符的範圍的下限值或上限值用作鏈路指示信息， 因此即使劃分鏈路，也不必更新指示劃分前的鏈路兩端的節點用的鏈路指示信 息，能減少更新數據量，同時還能進行較快速的更新處理。
而且，構成將對應節點指示信息設置在引路記錄內，而非道路網數據內， 因此即使更新引路記錄也不必更新道路網數據。因此，能減少道路網數據的更 新數據量，同時還能進行較快速的更新處理。又，將鏈路固有且不變的鏈路標 識符用作對應節點指示信息的鏈路指示信息，所以不必進行廢棄或新設無關鏈 路串或鏈路引起的對應節點指示信息的更新，能減少引路數據的更新數據量， 同時還能進行較快速的更新處理。
由於按鏈路標識符範圍信息值遞增的順序排列鏈路串記錄，因此能方便地 找到包含希望的鏈路標識符的鏈路的鏈路串記錄，可快速進行地圖信息處理。 又由於進入節點的鏈路或退出節點用的鏈路的指示使用不依賴於鏈路串記錄 排列順序的、節點固有且不變的同一節點標識符，因此不必進行刪除或新設無 關鏈路串引起的同一節點標識符的更新，能減少更新數據量，同時還能較快速 地進行道路網數據的更新。
再者，上述實施方式1的地圖信息處理裝置可變換如下。即，能變換成用 將一致節點指示信息和對應節點指示信息指示的節點作為終點節點的鏈路的 鏈路標識符表示這些指示信息。此情況下，使用鏈路標識符作為一致節點指示 信息和對應節點指示信息的鏈路指示信息。
此外，規定成指示的節點是鏈路串的始點節點時， 一致節點指示信息和 對應節點指示信息的始點終點指示信息表示始點；指示的節點是鏈路串的始點 節點以外的節點時，始點終點指示信息表示終點。鏈路標識符具有範圍的情況 下，使用鏈路標識符的範圍的上限值作為一致節點指示信息和對應節點指示信 息的鏈路指示信息。
本發明實施方式1的變換例的地圖信息處理裝置，根據與實施方式1的地
圖信息處理裝置相同的理由，能取得與實施方式1的地圖信息處理裝置相同的 效果。
實施方式2
本發明實施方式2在實施方式1中做成對終端虛擬鏈路也授予鏈路標識符， 並僅用鏈路指示信息表示一致節點指示信息。鏈路標識符具有範圍的情況下， 使用鏈路標識符的範圍的下限值作為鏈路指示信息。而且，用將對應的節點作 為始點的鏈路的鏈路標識符表示引路記錄的對應節點指示信息。這些一致節點 指示信息和對應節點指示信息是實施方式2的節點指示信息。
圖23是對圖4所示的道路網的終端虛擬鏈路也授予鏈路標識符的圖，對終 端虛擬鏈路L02、 L12、 L21、 L31、 L43和L51分別授予105、 112、 121、 131、 143和151作為鏈路標識符，這樣，實施方式2對全部鏈路和終端虛擬鏈路授 予鏈路標識符，所以對構成鏈路串的全部節點授予將這些節點作為始點的鏈路 的鏈路標識符。因此，能用將節點作為始點的鏈路的鏈路標識符表示全部該節 點，從而一致節點指示信息能僅用鏈路指示信息指示同樣的節點。
本實施方式2使用的道路網數據僅由鏈路指示信息構成實施方式1的道路 網數據的一致節點指示信息。圖24示出實施方式2中使用的一致節點指示信 息的例子。此情況下，例如對圖23的鏈路串ML0的鏈路L01的鏈路記錄中設 置的一致節點指示信息存放鏈路Lll的鏈路標識符"lll"作為指示鏈路串ML1 的節點N1的鏈路指示信息，以表示一致節點指示信息SO。而且，對鏈路串 ML4的鏈路L42的鏈路記錄中設置的一致節點指示信息存放終端虛擬鏈路L02 的鏈路標識符"105"作為指示鏈路串MLO的終端節點N2的鏈路指示信息， 以表示一致節點指示信息S5。
本實施方式2使用的引路數據僅由對應鏈路指示信息構成實施方式1的引 路數據的對應節點指示信息。圖25示出實施方式2中使用的對應節點指示信 息的例子。此情況下，例如圖10的引路記錄#0和引路記錄#1，與實施方式 1相同，對圖23的道路網也分別是鏈路串ML2的節點N1和鏈路串ML4的節 點N2的節點關聯信息。
本實施方式2中，存放將節點Nl作為始點的終端虛擬鏈路L21的鏈路標識 符"121"作為引路記錄#0的對應節點指示信息的鏈路指示信息，存放將節點 N2作為始點的鏈路L42的鏈路標識符"142"作為引路記錄弁1的對應節點指 示信息的鏈路指示信息。而且，按引路記錄#0、引路記錄#1的順序進行存放， 以便形成對應鏈路指示信息表示的鏈路標識符的值遞增的順序。
本實施方式2的地圖信息處理裝置的運作在實施方式1的地圖信息處理裝 置的運作中省略有關一致節點指示信息的始點終點指示信息和對應節點指示 信息的始點終點指示信息的處理。
如上文所說明，根據本發明實施方式2的地圖信息處理裝置，構成對全部 鏈路和終端虛擬鏈路授予不變的鏈路標識符，用不依賴於鏈路串記錄或鏈路記 錄的排列順序的鏈路標識符表示節點的同一性，因此可對道路網的全部節點用 鏈路標識符表示節點的同一性，不產生刪除或新設無關鏈路串或鏈路引起的一 致節點指示信息的改變，能減少更新數據量，同時還能快速進行道路網數據的 更新。
而且，構成將鏈路標識符的範圍的下限值用作鏈路指示信息，因此即使劃 分鏈路，也不必更新指示劃分前的鏈路的始點節點用的一致節點指示信息，能 減少更新數據量，同時還能進行較快速的更新處理。
又，構成將對應節點指示信息設置在引路記錄內，而非道路網數據內，因 此即使更新引路記錄也不必更新道路網數據，能減少道路網數據的更新數據 量，同時還能進行較快速的更新處理。又，將不變的鏈路標識符用作對應節點 指示信息的鏈路指示信息，所以不必進行廢棄或新設無關鏈路串或鏈路引起的 對應節點指示信息的更新，能減少引路數據的更新數據量，同時還能進行較快 速的更新處理。
由於按鏈路標識符範圍信息值遞增的順序排列鏈路串記錄，因此能方便地 找到包含希望的鏈路標識符的鏈路的鏈路串記錄，可快速進行地圖信息處理。 又由於進入節點的鏈路或退出節點用的鏈路的指示使用不依賴於鏈路串記錄 排列順序的、節點固有且不變的同一節點標識符，因此不必進行刪除或新設無 關鏈路串引起的同一節點標識符的更新，能減少更新數據量，同時還能較快速
地進行道路網數據的更新。
再者，實施方式2的地圖信息處理裝置可變換如下。即，能變換成用將一 致節點指示信息和對應節點指示信息指示的節點作為終點節點的鏈路的鏈路 標識符表示這些指示信息。此情況下，使用鏈路標識符作為一致節點指示信息 和對應節點指示信息的鏈路指示信息。
而且，鏈路標識符具有範圍的情況下，將鏈路標識符的範圍的上限值用作 鏈路指示信息。還設想將鏈路串的始點節點作為終點節點的虛擬鏈路(即虛擬始 點鏈路)，以代替虛擬終端鏈路，並對虛擬始點鏈路也授予不變的鏈路標識符。
本發明實施方式2的變換例的地圖信息處理裝置，根據與實施方式2的地 圖信息處理裝置相同的理由，能取得與實施方式2的地圖信息處理裝置相同的 效果。
再者，上述實施方式l、 2的地圖信息處理裝置中，將硬碟用作地圖信息存 儲裝置2的存儲媒體，但也可用例如存儲卡、光磁碟等可讀寫的存儲媒體，以 代替硬碟。又，構成將地圖信息存放在地圖信息存儲裝置3的硬碟，但也可構 成存放在例如CD - ROM (Compact Disc - Read Only Memory:音頻光碟一隻讀 存儲器)、DVD-ROM這些只讀存儲媒體，並利用該存儲媒體的讀取裝置讀 取存儲媒體存放的地圖信息。構成通過從地圖信息存儲裝置3讀取，取得地圖 信息，但也可構成用通信單元從其它裝置取得地圖信息。
又，將DVD - ROM用作地圖更新信息存放媒體，但也可用例如CD - ROM、 存儲卡這些可讀出的存儲媒體。將DVD驅動器用作更新信息獲取裝置4，但只 要是適合地圖更新信息存儲媒體的裝置，可用各種裝置。構成更新信息獲取裝 置4從地圖更新信息記錄媒體獲取地圖更新信息，但也可構成用通信單元從其 它裝置獲取地圖更新信息。構成將更新信息獲取裝置4取得的地圖更新信息存 放到地圖信息存儲裝置3，並從地圖信息存儲裝置3讀取地圖更新數據，但也 可構成用通信單元從其它裝置獲取地圖更新數據。構成將地圖信息獲取裝置4 取得的地圖更新信息存放到地圖信息存儲裝置3，並從地圖信息存儲裝置3讀 取地圖更新數據，但也可構成更新信息獲取裝置4直接從地圖更新信息存儲媒 體讀取地圖更新數據。
對將更新後的地圖數據存放到地圖信息存儲裝置3的處理省略說明，但可 構成將更新後的地圖數據存放到地圖信息存儲裝置3。構成用路線計算數據進 行路線計算，但也可構成用地圖數據的道路網數據進行路線計算。構成在更新 對象指定中使用鏈路串記錄號和鏈路號，但也可構成使用鏈路標識符。
工業上的實用性
綜上所述，本發明的地圖信息處理裝置和地圖信息存儲媒體在新設和廢棄 道路、或交叉點時，能減少指示更新用的數據量，同時還能簡單且迅速地進行 更新處理，適合用於導航裝置、便攜電話、便攜信息終端等。
權利要求
1、一種地圖信息處理裝置，具有存儲包含地圖數據的地圖信息的地圖信息存儲裝置、以及對所述地圖信息存儲裝置中存儲的地圖信息進行更新的處理器，其特徵在於，所述地圖信息存儲裝置存儲的地圖數據中包含的道路網數據，具有的數據結構為該數據包含將用表示道路上的地點的節點和表示地點間的道路的鏈路表示的道路網中的道路連接，表示為節點連接的鏈路的連接的鏈路串，所述鏈路串利用按鏈路連接順序排列的鏈路串記錄，表示規定鏈路的鏈路記錄，對構成所述鏈路串的鏈路，授予固有且不變的鏈路標識符，並且用將該節點作為一端的鏈路的鏈路標識符，表示指示所述鏈路串包含的節點用的節點指示信息。
2、 如權利要求1中所述的地圖信息處理裝置，其特徵在於， 指示所述鏈路串包含的節點用的節點指示信息，包括作為將該節點作為一端的鏈路的鏈路標識符的鏈路指示信息、以及表示該節點是所述鏈路指示信 息指示的鏈路的始點或終點的始點終點指示信息。
3、 如權利要求2中所述的地圖信息處理裝置，其特徵在於，將節點指示信息指示的節點作為一端的鏈路的鏈路標識符，具有規定範圍內的多個值，並且作為所述節點指示信息的鏈路指示信息，使用所述鏈路標識 符具有的規定範圍內的多個值中的下限值或上限值。
4、如權利要求2中所述的地圖信息處理裝置，其特徵在於， 作為指示與鏈路串中包含的節點同一且包含在其它鏈路串中的節點的一致節點指示信息，使用指示所述同一的節點的鏈路指示信息和始點終點指示信息。
5、如權利要求2中所述的地圖信息處理裝置，其特徵在於，具有有關與道路網數據分別開設置的節點的節點關聯信息，並且作為指示 與該節點關聯信息對應的節點的對應節點指示信息，使用指示該節點的鏈路指 示信息和始點終點指示信息。
6、 如權利要求1中所述的地圖信息處理裝置，其特徵在於， 用作為將按照鏈路串方向規定該節點的始點節點或終點節點作為一端的鏈路的鏈路標識符的鏈路指示信息，表示指示鏈路串中包含的節點用的節點指示fe息。
7、 如權利要求6中所述的地圖信息處理裝置，其特徵在於， 將節點指示信息指示的節點作為一端的鏈路的鏈路標識符，具有規定範圍內的多個值，並且作為所述節點指示信息的鏈路指示信息，使用所述規定範圍 內的多個值中的下限值或上限值。
8、 如權利要求6中所述的地圖信息處理裝置，其特徵在於， 具有僅虛擬連接按與鏈路串方向規定的鏈路串的一端側的節點的虛擬鏈路，對包含該虛擬鏈路的全部鏈路，授予固有且不變的鏈路標識符，並且 作為鏈路指示信息，使用包含虛擬鏈路的全部鏈路的鏈路標識符。
9、 如權利要求6中所述的地圖信息處理裝置，其特徵在於， 作為指示與鏈路串中包含的節點同一且包含在其它鏈路串中的節點的一致節點指示信息，使用指示所述同一的節點的鏈路指示信息。
10、 如權利要求6中所述的地圖信息處理裝置，其特徵在於， 具有有關與道路網數據分別開設置的節點的節點關聯信息，並且作為指示與該節點關聯信息對應的節點的對應節點指示信息，使用指示該節點的鏈路指 示信息。
11、 如權利要求1中所述的地圖信息處理裝置，其特徵在於， 鏈路串記錄包含表示賦予構成鏈路串的鏈路的鏈路標識符值的範圍的鏈路標識符範圍信息，並被排列成該鏈路標識符範圍信息表示的值的遞增順序或遞 減順序。
12、 如權利要求1中所述的地圖信息處理裝置，其特徵在於， 具有獲取更新所述地圖信息存儲裝置中存儲的地圖數據用的地圖更新數據 的更新信息獲取裝置， 所述處理器具有從所述地圖信息存儲裝置獲取地圖數據的地圖數據獲取單元、 從所述更新信息獲取裝置獲取地圖更新數據的地圖更新數據獲取單元、以及用所述地圖更新數據獲取單元取得的地圖更新數據，更新所述地圖數據獲 取單元取得的地圖數據的地圖數據更新單元。
13、 一種地圖信息處理裝置，具有存儲包含地圖數據的地圖信息的地圖信息存儲裝置、以及對所述地圖信息存儲裝置中存儲的地圖信息進行更新的處理器，其特徵在於，所述地圖信息存儲裝置存儲的地圖數據中包含的道路網數據，具有的數據 結構為該數據包含將用表示道路上的地點的節點和表示地點間的道路的鏈路表示 的道路網中的道路連接，表示為節點連接的鏈路的連接的鏈路串，所述鏈路串利用按鏈路連接順序排列的鏈路串記錄，表示規定鏈路的鏈路 記錄，對所述鏈路串包含的同一節點，授予同一節點間固有且不變的同一節點標 識符，並且用所述同一節點標識符，指示進入節點的鏈路或退出節點的鏈路。
14、 如權利要求13中所述的地圖信息處理裝置，其特徵在於， 具有獲取更新所述地圖信息存儲裝置中存儲的地圖數據用的地圖更新數據的更新信息獲取裝置，所述處理器具有從所述地圖信息存儲裝置獲取地圖數據的地圖數據獲取單元、 從所述更新信息獲取裝置獲取地圖更新數據的地圖更新數據獲取單元、以及 用所述地圖更新數據獲取單元取得的地圖更新數據，更新所述地圖數據獲 取單元取得的地圖數據的地圖數據更新單元。
15、 一種存儲媒體，計算機可讀取，其特徵在於， 存儲的地圖數據中包含的道路網數據，具有的數據結構為 該數據包含將用表示道路上的地點的節點和表示地點間的道路的鏈路表示的道路網中的道路連接，表示為節點連接的鏈路的連接的鏈路串，所述鏈路串利用按鏈路連接順序排列的鏈路串記錄，表示規定鏈路的鏈路記錄，對構成所述鏈路串的鏈路，授予固有且不變的鏈路標識符，並且用將該節點作為一端的鏈路的鏈路標識符，表示指示所述鏈路串包含的節 點用的節點指示信息。
全文摘要
具有更新包含地圖信息存儲裝置(3)中存儲的地圖數據的地圖信息的處理器(5)的地圖信息處理裝置中，地圖信息存儲裝置(3)存儲的地圖數據包含的道路網數據構成具有下列數據結構該數據包含將用節點和鏈路表示的道路網中的道路連接，表示為節點連接的鏈路的連接的鏈路串，鏈路串利用按鏈路連接順序排列的鏈路串記錄，表示規定鏈路的鏈路記錄，對構成鏈路串的鏈路，授予固有且不變的鏈路標識符，並且用將該節點作為一端的鏈路的鏈路標識符，表示指示鏈路串包含的節點用的節點指示信息。
文檔編號G01C21/00GK101111878SQ20058004732
公開日2008年1月23日 申請日期2005年11月14日 優先權日2005年2月8日
發明者下谷光生, 御廚誠, 梅津正春, 池內智哉 申請人:三菱電機株式會社