(57)【要約】【課題】  この発明は、地図情報を行政区域単位の更新領域で更新する際に、更新領域の境界上のノードの接続を短時間で確実に行うことができる地図情報処理装置を提供することを目的とする。【解決手段】  地図情報の作成範囲がメッシュ状の境界で分割されて１次区画に区画化されるとともに、行政区域等の更新領域の境界で２次区画に区画化され、地図情報記憶部４は、ノード情報と境界ノードの接続情報とを含む２次区画地図情報と更新領域の地図情報のバージョン情報とを記憶し、ノード情報は、境界ノードがメッシュ状の境界上の１次区画境界ノードか更新領域の境界上の更新領域境界ノードかを表すノード種別情報を含むようにして、更新手段５２による更新の際に、接続情報とノード情報に基づいて、境界ノードの接続の相手先を判断するようにした。【選択図】  図１
2010237256.tif 000002
【特許請求の範囲】
【請求項１】
地図情報の作成範囲がメッシュ状の境界で分割されることによって複数の１次区画に区画化されると共に、前記複数の１次区画の各々が前記１次区画とは異なる所定形状の領域であってかつそれぞれが前記地図情報を更新する最小単位領域である複数の更新領域の境界で分割されることによって複数の２次区画に区画化され、前記複数の１次区画の各々に含まれる前記複数の２次区画のそれぞれに対応して、
前記それぞれの第１の２次区画の境界の上に位置して地理上の地点を表す境界ノードに関するノード情報と、前記第１の２次区画に隣接する第２の２次区画の境界の上に位置して接続元としての前記第１の２次区画の境界ノードと、前記第１の２次区画の境界ノードに接続される相手先候補として指示された接続先としての前記第２の２次区画の境界ノードとの接続に関する接続情報と、を含む２次区画地図情報と、
前記複数の更新領域のそれぞれに対応する地図情報のバージョンを表すバージョン情報と、
を記憶する地図情報記憶手段と、
前記地図情報記憶手段に記憶されたバージョン情報に基づいて、前記地図情報記憶手段に記憶された２次区画地図情報を前記更新領域毎に更新する更新手段と、
を備える地図情報処理装置であって、
前記ノード情報は、前記第１の２次区画の境界ノードが前記メッシュ状の境界上に位置する１次区画境界ノードであるか、前記更新領域の境界上に位置する更新領域境界ノードであるかを表すノード種別情報を含むと共に、
前記接続情報と前記ノード情報とに基づいて、前記相手先候補として指示された接続先が前記第１の２次区画の境界ノードが接続される相手先であるかどうか判断されること
を特徴とする地図情報処理装置。
【請求項２】
接続情報は、接続先としての第２の２次区画の境界ノードを地図情報記憶手段における記憶位置で指示するものであること
を特徴とする請求項１に記載の地図情報処理装置。
【請求項３】
ノード情報に含まれるノード種別情報が、接続元としての第１の２次区画の境界ノードは１次区画境界ノードであることを表すものである場合には、前記接続元としての第１の２次区画の境界ノードの接続情報が示す境界ノードが接続される相手先であると決定されること
を特徴とする請求項１または２のいずれかに記載の地図情報処理装置。
【請求項４】
ノード情報に含まれるノード種別情報が、接続元としての第１の２次区画の境界ノードは更新領域境界ノードであることを表すものであり、かつ、前記第１の２次区画を含む更新領域の地図情報のバージョンと相手先候補として指示された接続先の位置する第２の２次区画を含む更新領域の地図情報のバージョンとが同一の場合に、前記接続元としての第１の２次区画の境界ノードの接続情報が示す境界ノードが接続される相手先であると決定されること
を特徴とする請求項１または２のいずれかに記載の地図情報処理装置。
【請求項５】
ノード情報に含まれるノード種別情報が、接続元としての第１の２次区画の境界ノードは更新領域境界ノードであることを表すものであり、かつ、前記第１の２次区画を含む更新領域の地図情報のバージョンと相手先候補として指示された接続先の位置する第２の２次区画を含む更新領域の地図情報のバージョンとが異なる場合に、前記第２の２次区画の境界ノードのうちで、接続情報が示す更新領域が前記接続元としての第１の２次区画の境界ノードを含む更新領域と一致する境界ノードに限定した中から、接続される相手先が決定されること
を特徴とする請求項１または２のいずれかに記載の地図情報処理装置。
【請求項６】
接続情報は、更新領域境界ノードが最初に設けられたバージョンを示す境界ノードバージョン情報を含み、
接続元としての更新領域境界ノードである第１の２次区画の境界ノードの境界ノードバージョン情報が表すバージョンが、相手先候補として指示された接続先の位置する第２の２次区画を含む更新領域の地図情報のバージョンより新しい場合は、前記相手先候補として指示された接続先は前記第１の２次区画の境界ノードが接続される相手先でないと決定し、
前記接続元としての更新領域境界ノードである第１の２次区画の境界ノードの境界ノードバージョン情報が表すバージョンが、前記相手先候補として指示された接続先の位置する第２の２次区画を含む更新領域の地図情報のバージョンより新しくない場合は、前記第１の２次区画の境界ノードが接続される相手先を、前記第２の２次区画の境界ノードのうちで対応する接続情報に含まれた境界ノードバージョン情報の示すバージョンより新しくない境界ノードの中から決定すること
を特徴とする請求項５に記載の地図情報処理装置。
【請求項７】
接続元としての第１の２次区画の境界ノードの所定近傍に存在する第１の２次区画の各々の第１の更新領域境界ノードを検出する第１の近傍境界ノード検出手段と、
前記接続元としての第１の２次区画の境界ノードの所定近傍に存在する相手先候補として指示された接続先としての第２の２次区画の各々の第２の更新領域境界ノードを検出する第２の近傍境界ノード検出手段と、
をさらに備え、
前記接続元としての第１の２次区画の境界ノードに対する前記第１の近傍境界ノード検出手段で検出されたそれぞれの第１の更新領域境界ノードの位置関係と前記第２の近傍境界ノード検出された前記第２の更新領域境界ノードのそれぞれの間の位置関係とを用いて、前記接続元としての第１の２次区画の境界ノードが接続される相手先を決定すること
を特徴とする請求項５または６のいずれかに記載の地図情報処理装置。
【請求項８】
接続元としての第１の２次区画の境界ノードを端点とするリンクの属性と相手先候補として指示された接続先の位置する第２の２次区画の境界ノードを端点とするリンクの属性との差異に基づいて、前記接続元としての第１の２次区画の境界ノードが接続される相手先を決定すること
を特徴とする請求項７に記載の地図情報処理装置。
【請求項９】
地図情報の作成範囲がメッシュ状の境界で分割されることによって複数の１次区画に区画化されると共に、前記複数の１次区画の各々が前記１次区画とは異なる所定形状の領域であってかつそれぞれが前記地図情報を更新する最小単位領域である複数の更新領域の境界で分割されることによって複数の２次区画に区画化され、前記複数の１次区画の各々に含まれる前記複数の２次区画のそれぞれに対応して、
前記それぞれの第１の２次区画の境界の上に位置して地理上の地点を表す境界ノードに関するノード情報と、前記第１の２次区画に隣接する第２の２次区画の境界の上に位置して接続元としての前記第１の２次区画の境界ノードと、前記第１の２次区画の境界ノードに接続される相手先候補として指示された接続先としての前記第２の２次区画の境界ノードとの接続に関する接続情報と、を含む２次区画地図情報と、
前記複数の更新領域のそれぞれに対応する地図情報のバージョンを表すバージョン情報と、
を記憶する地図情報記憶媒体であって、
前記ノード情報は、前記第１の２次区画の境界ノードが前記メッシュ状の境界上に位置する１次区画境界ノードであるか、前記更新領域の境界上に位置する更新領域境界ノードであるかを表すノード種別情報を含むこと
を特徴とする地図情報記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、例えば都道府県等の行政区域や関東や関西といった地方区域等、使用者が日常の中で慣れ親しんで認識している所定形状の領域を更新領域として、地図情報の更新を行う地図情報処理装置に関する。
【背景技術】
【０００２】
従来の地図情報処理装置においては、地図情報を所定形状の領域に分割し、当該所定形状の領域を単位として地図情報を更新しており、所定形状の領域として、都道府県等の行政区域、メッシュ状の区画、メッシュ状の区画が何枚か集まったブロックのいずれかを採用している（例えば特許文献１参照）。例えば、メッシュ状の区画の単位で更新する場合、地図情報の更新によって、隣接するメッシュ状の区画間でその地図情報のバージョンが異なる場合が存在する。
【０００３】
地図情報の更新を行わない場合には、互いに隣接するメッシュ状の区画である隣接区画間での地図情報のバージョンは常に一致しているため、ある特定の区画の境界上のノードＮ１と、そのノードＮ１に接続する隣接区画の境界上のノードＮ２とは、完全に一致したノードである。そこで当該ノードＮ２を表す情報として、前記隣接区画の地図情報におけるノードＮ２を表すデータの格納位置すなわちデータの記憶アドレスを指し示すポインタを用いることができ、ノードＮ２をより高速に求めることが可能である。
【０００４】
ただし、地図情報の更新を行う場合には、ある特定の区画の地図情報の更新無しに前記隣接区画の地図情報のみが更新されると、その隣接区画の地図情報におけるノードＮ２を表すデータの格納位置が変化するため、前記ポインタはノードＮ２のデータを正しく指し示すことができなくなる。このような問題を防止するために、従来の地図情報装置においては、格納位置に依存しないノードの座標値を利用し、当該ノードＮ１に接続する隣接区画の境界上のノードＮ２として、前記隣接区画の境界上に存在する全てのノードを検索対象として、その全てのノードの中からノードＮ１の座標値が略一致するノードを見つけるようにしている（例えば特許文献１参照）。
【０００５】
従って、従来の情報処理装置においては、地図情報を行政区域単位で更新するために、メッシュ状の区画である１次区画をさらに行政区域で分割して２次区画に区画化し、地図情報を当該２次区画毎に分割し、行政区域単位で更新する場合において、２次区画の境界は、１次区画の境界と行政区域を更新単位とする更新領域の境界とからなり、行政区域を更新単位とする更新領域単位で更新するために、更新領域の境界で隣接する２次区画の地図情報のバージョンの不一致が発生することは無く、隣接する２次区画間で地図情報のバージョンが同じであれば、隣接２次区画の地図情報におけるノードＮ２を表すデータの格納位置を指し示すポインタを用いることができ、ノードＮ２をより高速に求めることが可能である。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００２−９９２０７号公報（第２７〜３０頁、第３６〜４２図）
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、従来の情報処理装置においては、ノードがどの境界上に存在しても座標値の比較により接続する隣接１次区画の境界上のノードを求めているため、隣接する１次区画間で地図情報のバージョンの不一致が無いにも関わらず、座標値の比較による接続判定を必要とし、処理時間がより長くなるという問題があった。
【０００８】
また、ノードＮ２をノードＮ１と座標値の差異が所定範囲にあるノードとしているため、その所定範囲に複数のノードが存在する場合は、正しいノードＮ２を得ることができるとは限らないという問題があった。
【０００９】
この発明は、上記のような課題を解決するために為されたもので、地図情報を行政区域単位の更新領域で更新する際に、更新領域の境界上のノードの接続を短時間で確実に行うことが可能な地図情報処理装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
この発明に係る地図情報処理装置は、地図情報の作成範囲がメッシュ状の境界で分割されることによって複数の１次区画に区画化されると共に、前記複数の１次区画の各々が前記１次区画とは異なる所定形状の領域であってかつそれぞれが前記地図情報を更新する最小単位領域である複数の更新領域の境界で分割されることによって複数の２次区画に区画化され、前記複数の１次区画の各々に含まれる前記複数の２次区画のそれぞれに対応して、前記それぞれの第１の２次区画の境界の上に位置して地理上の地点を表す境界ノードに関するノード情報と、前記第１の２次区画に隣接する第２の２次区画の境界の上に位置して接続元としての前記第１の２次区画の境界ノードと、前記第１の２次区画の境界ノードに接続される相手先候補として指示された接続先としての前記第２の２次区画の境界ノードとの接続に関する接続情報と、を含む２次区画地図情報と、前記複数の更新領域のそれぞれに対応する地図情報のバージョンを表すバージョン情報とを記憶する地図情報記憶手段と、前記地図情報記憶手段に記憶されたバージョン情報に基づいて、前記地図情報記憶手段に記憶された２次区画地図情報を前記更新領域毎に更新する更新手段とを備える地図情報処理装置であって、前記ノード情報は、前記第１の２次区画の境界ノードが前記メッシュ状の境界上に位置する１次区画境界ノードであるか、前記更新領域の境界上に位置する更新領域境界ノードであるかを表すノード種別情報を含むと共に、前記更新手段によって更新される際に、前記接続情報と前記ノード情報とに基づいて、前記相手先候補として指示された接続先が前記第１の２次区画の境界ノードが接続される相手先であるかどうか判断されることを特徴とする。
【００１１】
また、この発明に係る地図情報記憶媒体は、地図情報の作成範囲がメッシュ状の境界で分割されることによって複数の１次区画に区画化されると共に、前記複数の１次区画の各々が前記１次区画とは異なる所定形状の領域であってかつそれぞれが前記地図情報を更新する最小単位領域である複数の更新領域の境界で分割されることによって複数の２次区画に区画化され、前記複数の１次区画の各々に含まれる前記複数の２次区画のそれぞれに対応して、前記それぞれの第１の２次区画の境界の上に位置して地理上の地点を表す境界ノードに関するノード情報と、前記第１の２次区画に隣接する第２の２次区画の境界の上に位置して接続元としての前記第１の２次区画の境界ノードと、前記第１の２次区画の境界ノードに接続される相手先候補として指示された接続先としての前記第２の２次区画の境界ノードとの接続に関する接続情報と、を含む２次区画地図情報と、前記複数の更新領域のそれぞれに対応する地図情報のバージョンを表すバージョン情報とを記憶する地図情報記憶媒体であって、前記ノード情報は、前記第１の２次区画の境界ノードが前記メッシュ状の境界上に位置する１次区画境界ノードであるか、前記更新領域の境界上に位置する更新領域境界ノードであるかを表すノード種別情報を含むことを特徴とする。
【発明の効果】
【００１２】
この発明に係る地図情報処理装置によれば、地図情報を行政区域単位の更新領域で更新する際に、更新領域の境界上のノードの接続を短時間で確実に行うことができる。
【００１３】
また、この発明に係る地図情報記憶媒体によれば、地図情報を行政区域単位の更新領域で更新する際に、更新領域の境界上のノードの接続を短時間で確実に行うことができる地図情報を得ることができる。
【図面の簡単な説明】
【００１４】
【図１】この発明に係る実施の形態１の地図情報処理装置の構成を示すブロック図である。
【図２】階層化され、各階層の作成範囲がメッシュ状に分割された地図情報の例である。
【図３】作成範囲内に更新領域が存在する様子を示した地図情報の例である。
【図４】メッシュ状に分割され区画化された作成範囲の地図情報が、さらに更新領域Ａ、Ｂ、Ｃ、Ｄ、Ｅ、及びＦで区画化された地図情報の例である。
【図５】レベル０、レベル１、及びレベル２の階層からなる地図情報における１次区画地図情報の例である。
【図６】レベル０、レベル１、及びレベル２の階層からなる地図情報における更新領域に関するバージョン管理情報の例である。
【図７】レベル０、レベル１、及びレベル２の階層からなる地図情報における１次区画管理情報の例である。
【図８】階層がレベル０の作成範囲の中のメッシュ座標が（ｉ，ｊ）＝（２，３）の１次区画（２，３）に対応する１次区画地図情報＃４６の内容を説明するための説明図である。
【図９】１次区画内の２次区画地図情報の例である。
【図１０】更新範囲を更新領域Ｃとしたときの更新情報の例である。
【図１１】レベル０の階層の１次区画（２，３）とその周辺の道路網の例である。
【図１２】レベル０の階層の１次区画（２，３）とその周辺の道路網の例において、その道路網を２次区画に区画化した結果を説明するための説明図である。
【図１３】２次区画（２，３）−Ｃの道路網を表す道路データのデータ構造の例である。
【図１４】２次区画（２，３）−Ａの道路網を表す道路データのデータ構造の例である。
【図１５】２次区画（２，３）−Ｂの道路網を表す道路データのデータ構造の例である。
【図１６】２次区画（２，３）−Ｃの道路網を表す道路データのデータ構造の例である。
【図１７】２次区画（２，４）−Ｃの道路網を表す道路データのデータ構造の例である。
【図１８】２次区画（２，２）−Ｃの道路網を表す道路データのデータ構造の例である。
【図１９】２次区画（２，３）−Ｃの道路網を表す道路データにおけるノードレコードのデータ構造の例である。
【図２０】２次区画（２，３）−Ｃの道路網を表す道路データにおける接続レコードのデータ構造の例である。
【図２１】リンクレコードのデータ構造の例である。
【図２２】形状レコードのデータ構造の例である。
【図２３】道路網全体が最新バージョンに更新され、道路網にノードＮ１９、ノードＮ２０、ノードＮ２１、リンクＬ１９、リンクＬ２０、リンクＬ２１、及びリンクＬ２２が新設されたものである。
【図２４】道路網の各々の２次区画の道路網を示すものである。
【図２５】２次区画（２，３）−Ｃの道路データの例である。
【図２６】２次区画（２，３）−Ｃの道路データの例である。
【図２７】２次区画（３，３）−Ａの道路データの例である。
【図２８】更新領域Ｂ及び更新領域Ｃのみの地図情報を更新した場合の各々の２次区画の道路網を示す。
【図２９】地図情報処理装置の動作を示すフローチャートである。
【図３０】２次区画の境界ノードである接続元ノードに対して、接続すべき隣接２次区画の境界ノードである接続先ノードを求める処理の詳細を示すフローチャートである。
【図３１】接続先ノード検索の処理を詳細に示すためのフローチャートである。
【図３２】実施の形態２の更新領域境界ノードに対する接続レコードのデータ構成例である。
【図３３】この発明に係る実施の形態２での処理を示すためのフローチャートである。
【図３４】この発明に係る実施の形態３での処理を示すためのフローチャートである。
【図３５】近傍境界ノードと隣接近傍境界ノードの例である。
【図３６】接続元ノードに対する近傍境界ノードの変位を示すベクトルの例である。
【図３７】隣接近傍境界ノード間の変位を示すベクトルの例である。
【発明を実施するための形態】
【００１５】
実施の形態１．
＜地図情報処理装置の構成＞
図１は、この発明に係る実施の形態１の地図情報処理装置の構成を示すブロック図である。
【００１６】
図１において、入力部１は、使用者の操作又は指示に従ってプロセッサ５に指示信号を与える。図示しないが、具体的には、入力部１は使用者の音声を認識して音声に基づく指示信号を出力する音声認識部、使用者の手動操作により指示信号を出力するボタン等の少なくともいずれかを有しており、入力手段として機能する。
【００１７】
位置検出部２は、例えばＧＰＳ（Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ）受信機、車速センサ、角速度センサ等のいずれかないしは複数を用いた位置検出手段であって、当該地図情報処理装置を搭載している車両の現在位置を検出し、検出した現在位置を示す位置情報をプロセッサ５に提供する。
【００１８】
更新情報取得部３は、例えば、メモリカードリーダーにより構成され、メモリカードに記憶された更新情報を読み取り、更新情報を取得する更新情報取得手段として機能する。
【００１９】
地図情報記憶部４は、例えば、地図情報記憶媒体としてハードディスクを用いたハードディスクドライブにより構成された地図情報記憶手段であり、当該地図情報記憶部４に予め地図情報を記憶しておく。
【００２０】
プロセッサ５は、入力部１から与えられた指示信号、位置検出部２から得られた現在位置を示す位置情報、及び地図情報記憶部４から読み出した地図情報とを用いて、各種の地図情報処理を行う地図情報処理手段５１として機能する。
【００２１】
この各種の地図情報処理の内容としては、位置検出部２から得た現在位置を示す位置情報と地図情報記憶部４から読み出した地図情報とに基づいて車両の現在位置を推定するマップマッチング処理、出発地から目的地までの経路を算出する経路探索（経路計算）処理、経路探索処理によって得られた好適な経路の候補を道路地図と共に出力部６が備える例えば表示部の画面に表示する経路表示処理、好適な経路の候補から選択された経路に従って出発地から目的地までの案内を行う経路誘導処理、現在位置周辺の地図の表示処理、及び施設、住所、電話番号等の各種情報を検索する各種検索処理等が含まれる。
【００２２】
また、プロセッサ５は、更新情報取得部３によりメモリカードから読み取った更新情報を用いて、地図情報記憶部４に記憶された地図情報を更新する更新手段５２としても機能する。
【００２３】
出力部６は、プロセッサ５による各種の地図情報処理の結果得られた情報を、使用者に提示する出力手段として機能する。図示しないが、具体的には、出力部６は、地図情報に基づく地図、当該地図上での車両の現在位置、当該地図上での経路探索処理によって得られた好適な経路の候補、好適な経路の候補から選択された経路に従って出発地から目的地まで案内を行うための案内情報、検索によって得られた各種情報等を表示する表示部、及び表示された内容と同様ないしは関連する内容を使用者に音声で指示又は案内を行う音声発生部のいずれか一方ないしは両方を有していても良い。
【００２４】
地図情報処理装置は以上のように構成されているので、使用者が例えば目的地周辺の道路がどのようになっているかを確認したいと考えれば、その所要の範囲の地図情報を使用者が入力部１を使って指示をすることで、地図情報処理装置はその所要の範囲の地図情報を得ることができる。その結果、使用者は当該地図情報処理装置の出力部６によって目的地周辺の道路についてどのようになっているか確認することができる。
【００２５】
また、使用者が例えば目的地に行くための地図情報を更新しようと考えれば、使用者は、まず、更新情報が記憶されたメモリカードを更新情報取得部３にセットする。次に、使用者が入力部１を使って地図情報の更新の指示を地図情報処理装置にすることで、地図情報処理装置は、更新情報に基づいて地図情報記憶部４に記憶された地図情報を更新する。その結果、使用者は、目的地に行くための最新バージョンの地図情報を利用することができる。
【００２６】
また、位置検出部２から使用者が乗車している車両の現在位置を示す位置情報を得ることができるので、地図情報処理装置は当該車両の現在位置から目的地までの所要の地図情報を得ることができる。その結果、使用者は当該地図情報処理装置の出力部６によって現在位置から目的地までの経路誘導のための案内情報を知ることができる。
【００２７】
また、地図情報処理装置は、位置検出部２から使用者が乗車している車両の現在位置を示す位置情報を得た上で、当該現在位置から目的地まで行くための所要の地図情報について、メモリカードに記憶された更新情報に基づいて自動的に地図情報記憶部４に記憶された地図情報を更新する。その結果、使用者は、現在位置から目的地に行くための最新バージョンの地図情報を利用することができる。
【００２８】
＜地図情報＞
地図情報の作成範囲は、経線及び緯線により囲まれた領域とする。なお、作成範囲の形状は、地球上の高緯度の地域を除いては近似的に略矩形とみなすことが可能である。従って、高緯度の地域以外では、地図情報の作成範囲は矩形領域として取り扱っても実用上は問題無い。そこで、以下では、作成範囲が経線及び緯線により囲まれた矩形領域であるとみなして、説明する。
【００２９】
また、地図情報は、情報の詳細さの度合いにより階層化され、地図情報の作成範囲を各階層毎に所定間隔の経線及び緯線により囲まれた矩形領域であるメッシュ状に分割することで、区画化されて管理される。この地図情報の作成範囲がメッシュ状に分割されて区画化された領域を、以下では１次区画と呼ぶこととする。
【００３０】
次に、上記のようにメッシュ状に分割することで区画化された作成範囲は、メッシュ状とは異なる分割形状にてさらに上記１次区画の集合体以外の所定形状の領域によって区画化される。以下では、メッシュ状の１次区画内をさらに上記１次区画とは異なる所定形状の領域によって区画化された領域を、２次区画と呼ぶこととする。
【００３１】
上記所定形状の領域は、地図情報処理装置の使用者の便宜の点から分割された地図情報の更新の最小単位であり、以下では、この最小単位を更新領域と呼ぶこととする。
【００３２】
各更新領域には、各々の領域を識別するための識別子である更新領域の領域識別子が付与される。所定形状の領域である更新領域としては、その呼称からその領域が容易に類推できる領域とし、例えば国、州、都道府県、市区町村等の行政区域や、行政区域そのものでは無いが社会的に認知されている地域名を有する例えば関東地方や近畿地方等の地方区域等を表すものとする。この所定形状の領域は、使用者にとっては日常の中で慣れ親しんで認識しているので、使用者は地図情報の更新の範囲を容易に理解することができる。
【００３３】
図２は、各階層化され、各階層がメッシュ状に分割された地図情報の例である。図２においては、レベル０、レベル１、及びレベル２の３階層に階層化され、レベル２、レベル１、及びレベル０の順に詳細度が大きくなるものとする。レベル０の階層では、作成範囲はメッシュ状に分割されることで８×８個の１次区画に区画化され、レベル１の階層では、作成範囲はメッシュ状に分割されることで４×４個の１次区画に区画化される。さらに、レベル２の階層では、作成範囲はメッシュ状に分割されることで２×２個の１次区画に区画化されている。
【００３４】
なお、作成範囲である矩形領域の左端の経度の値をＷｉｍｉｎ、右端の経度の値をＷｉｍａｘとする。さらに、この作成範囲である矩形領域の下端の緯度の値をＷｊｍｉｎ、上端の緯度の値をＷｊｍａｘとする。また、作成範囲の経度方向の幅をＷｉ、作成範囲の緯度方向の幅をＷｊとし、Ｗｉ＝Ｗｉｍａｘ−Ｗｉｍｉｎ及びＷｊ＝Ｗｊｍａｘ−Ｗｊｍｉｎの関係があるものとする。
【００３５】
図２に示すように、各階層の作成範囲はメッシュ状に分割されて１次区画に区画化されているので、レベル０の１次区画の経度方向の幅はＷｉ／８であり、緯度方向の幅はＷｊ／８となっている。また、レベル１の１次区画の経度方向の幅はＷｉ／４、緯度方向の幅はＷｊ／４であり、レベル２の１次区画の経度方向の幅はＷｉ／２、緯度方向の幅はＷｊ／２となっている。
【００３６】
また、各階層の作成範囲の中においてメッシュ状に分割された１次区画を特定するために、各１次区画に対して２次元のメッシュ座標（ｉ，ｊ）を付与する。２次元のメッシュ座標（ｉ，ｊ）を示すための座標軸ｉの値は、作成範囲である矩形領域の左端の１次区画から右端に向かって順にｉ＝０、１、２、・・・、ｍ（ｍは自然数）を付与し、座標軸ｊの値は、作成範囲である矩形領域の下端の１次区画から上端に向かって順にｊ＝０、１、２、・・・、ｎ（ｎは自然数）を付与する。以上により、作成範囲である矩形領域内の１次区画をメッシュ座標（ｉ，ｊ）で特定することができる。例えば、図２の中のレベル０の階層の作成範囲において、メッシュ座標（ｉ，ｊ）＝（２，３）で特定される１次区画は、図２において太枠で位置が特定されている。以下では、１次区画（ｉ，ｊ）は、メッシュ座標が（ｉ，ｊ）である１次区画を指すものとする。
【００３７】
図３は、作成範囲内に更新領域が存在する様子を示した地図情報の例である。図３において、更新領域Ａ、Ｂ、Ｃ、Ｄ、Ｅ、及びＦが示されている。
【００３８】
図４は、図２に示したメッシュ状に区画化された作成範囲の地図情報を、さらに図３に示した更新領域Ａ、Ｂ、Ｃ、Ｄ、Ｅ、及びＦで区画化された地図情報の例である。例えば、レベル０の階層の作成範囲の中に分割されて存在する１次区画（２，３）では、更新領域Ａに属する区画、更新領域Ｂに属する区画、及び更新領域Ｃに属する区画の都合３つの２次区画に区画化されている。図４のレベル０の階層だけで無く、レベル１及びレベル２の階層においても同様に同じ更新領域Ａ、Ｂ、Ｃ、Ｄ、Ｅ、及びＦで１次区画が２次区画に区画化されている。
【００３９】
地図情報記憶部４には、図４に示す各階層の地図情報において、メッシュ状に分割され区画化された１次区画に対応する地図情報である１次区画地図情報が各１次区画に対応付けられて記憶されている。さらに、これらの１次区画地図情報を管理するための１次区画管理情報と更新領域のバージョンを管理する更新領域に関するバージョン管理情報とが記憶されている。
【００４０】
図５は、図４に示したレベル０、レベル１、及びレベル２の階層からなる地図情報における１次区画地図情報の例である。
【００４１】
図５に示されるように、図４のレベル２の１次区画（０，０）〜１次区画（１，１）の４個の１次区画のそれぞれに対応して１次区画地図情報＃０〜１次区画地図情報＃３の４個の１次区画地図情報が、地図情報記憶部４に記憶される。また、レベル１の１次区画（０，０）〜１次区画（３，３）の１６個の１次区画のそれぞれに対応して１次区画地図情報＃４〜１次区画地図情報＃１９の１６個の１次区画地図情報が、地図情報記憶部４に記憶される。さらに、レベル０の１次区画（０，０）〜１次区画（７，７）の６４個の１次区画のそれぞれに対応して１次区画地図情報＃２０〜１次区画地図情報＃８３の６４個の１次区画地図情報が、地図情報記憶部４に記憶される。
【００４２】
図６は、図４に示したレベル０、レベル１、及びレベル２の階層からなる地図情報における更新領域に関するバージョン管理情報の例である。
【００４３】
図６に示す更新領域に関するバージョン管理情報は、地図情報記憶部４に記憶されている更新領域の数を示すバージョン管理ヘッダと、地図情報記憶部４に記憶されている各更新領域に対応して設けられたバージョン管理レコードとを有している。
【００４４】
バージョン管理レコードの各々は、それぞれのバージョン管理レコードがどの更新領域に対応しているのかを示すための更新領域の領域識別子と、当該更新領域の名称を示す領域名と、当該更新領域の地図情報のバージョンを示すための記憶地図情報バージョンとを有している。
【００４５】
図６に示す更新領域に関するバージョン管理情報の例において、バージョン管理ヘッダに示されている更新領域の数は６個で、図３及び図４に示されている更新領域Ａ、Ｂ、Ｃ、Ｄ、Ｅ、及びＦに対応している。バージョン管理情報は、この６個の更新領域の各々に対応して、バージョン管理レコード＃０〜バージョン管理レコード＃５からなる６個のバージョン管理レコードを有している。ここで、例えば、バージョン管理レコード＃０は、更新領域Ａの領域識別子、Ａという更新領域の領域名、及び更新領域Ａの記憶地図情報バージョンを有している。同様に、バージョン管理レコード＃２であれば、更新領域Ｃの領域識別子、Ｃという更新領域の領域名、及び更新領域Ｃの記憶地図情報バージョンを有している。
【００４６】
図７は、図４に示したレベル０、レベル１、及びレベル２の階層からなる地図情報における１次区画管理情報の例である。
【００４７】
図７に示す１次区画管理情報は、１次区画管理情報ヘッダと１次区画の各々に対応して設けられた１次区画管理レコードとを有している。
【００４８】
１次区画管理情報ヘッダは、作成範囲、階層数、及び各階層に対応して設けられた階層管理レコードを有している。さらに、作成範囲については、その矩形領域の左端経度、右端経度、下端緯度、及び上端緯度が示されている。また、階層管理レコードの各々には、それぞれの階層の地図情報に含まれる１次区画の数を示す１次区画数、当該１次区画の経度方向の幅及び当該１次区画の緯度方向の幅が示されている。
【００４９】
さらに、図７に示す１次区画管理情報は、各階層に含まれるそれぞれの１次区画に対応して設けられた１次区画管理レコードを有している。１次区画管理レコードの各々は、当該１次区画が含まれる階層の名称である階層名、当該１次区画が含まれる階層の作成範囲の中での当該１次区画の位置を特定するためのメッシュ座標、当該１次区画に対応する１次区画地図情報が地図情報記憶部４のどこに記憶されているかを特定するための１次区画地図情報の所在、及び地図情報記憶部４に記憶されている当該１次区画に対応する１次区画地図情報のデータサイズを有している。
【００５０】
図７に示す１次区画管理情報の例において、１次区画管理情報ヘッダに含まれる作成範囲は、その矩形領域の左端経度がＷｉｍｉｎ、右端経度がＷｉｍａｘ、下端経度がＷｊｍｉｎ、さらに上端緯度がＷｊｍａｘであることを示している。また、１次区画管理情報ヘッダに含まれる階層数は、レベル２の階層、レベル１の階層、及びレベル０の階層の都合３個である。１次区画管理情報ヘッダは、３個の階層であるレベル２、レベル１、及びレベル０に対応して階層管理レコード＃０〜階層管理レコード＃２からなる３個の階層管理レコードを有している。ここで、例えば、レベル２の階層に対応する階層管理レコード＃０は、１次区画数が４個であり、１次区画の経度方向の幅がＷｉ／２、１次区画の緯度方向の幅がＷｊ／２である。また、レベル１の階層に対応する階層管理レコード＃１は、１次区画数が１６個であり、１次区画の経度方向の幅がＷｉ／４、１次区画の緯度方向の幅がＷｊ／４である。また、レベル０の階層に対応する階層管理レコード＃２は、１次区画数が６４個であり、１次区画の経度方向の幅がＷｉ／８、１次区画の緯度方向の幅がＷｊ／８である。
【００５１】
次に、図７に示す１次区画管理情報の例において、１次区画管理情報は、１次区画管理情報ヘッダと併せて各階層に含まれるそれぞれの１次区画に対応して設けられた１次区画管理レコードを有している。そして、当該１次区画管理レコードは、図５に示された１次区画地図情報＃０〜１次区画地図情報＃８３からなる１次区画地図情報の各々に対応して、１次区画管理レコード＃０〜１次区画管理レコード＃８３の８４個からなる。ここで、例えば、１次区画管理レコード＃４６は、図４に示されたレベル０の階層の作成範囲に含まれるメッシュ座標（ｉ，ｊ）＝（２，３）で特定される太枠の１次区画に対応しているが、当該１次区画管理レコード＃４６においては、階層名がレベル０であり、メッシュ座標（ｉ，ｊ）が（２，３）であり、さらに、１次区画地図情報の所在としては当該１次区画（２，３）に対応する１次区画地図情報＃４６の所在であり、１次区画地図情報のデータサイズとしては当該１次区画（２，３）に対応する１次区画地図情報＃４６のデータサイズとなっている。
【００５２】
なお、１次区画管理レコードは、１次区画地図情報の検索を容易にするために、階層及びメッシュ座標に関してソートして並べられている。
【００５３】
所要の地図情報の階層及び範囲が指定されれば、１次区画管理情報ヘッダの作成範囲、所要の階層の１次区画の経度方向の幅及び緯度方向の幅から、所要の１次区画のメッシュ座標が容易に算出される。さらに、上記階層及びメッシュ座標を有する１次区画管理レコードから１次区画地図情報の所在が取得できるため、所要の地図情報の階層及び範囲の１次区画地図情報を地図情報記憶部４から容易に取得することができる。ここで、１次区画地図情報には、その１次区画に含まれる全ての更新領域の１次区画内の更新領域地図情報が含まれるため、更新領域による区画を考慮することなく、所要の１次区画の地図情報が得られる。
【００５４】
図８は、階層及び区画が図４に示すものとした場合であって、階層がレベル０の作成範囲の中のメッシュ座標が（ｉ，ｊ）＝（２，３）の１次区画（２，３）に対応する１次区画地図情報＃４６の内容を説明するための図である。
【００５５】
１次区画地図情報は、１次区画地図情報ヘッダと当該１次区画内の２次区画地図情報の並びからなる。１次区画内の２次区画地図情報は、当該１次区画内の２次区画における地図情報であり、当該１次区画に存在する２次区画の数だけ設けられる。
【００５６】
図８に示すように、１次区画地図情報ヘッダは、当該１次区画に存在する２次区画の数を表す２次区画数と、当該１次区画内に存在する２次区画の各々に対応して設けられた２次区画管理レコードとを有する。
【００５７】
２次区画管理レコードは、対応する２次区画が属する更新領域の領域識別子、対応する２次区画地図情報の所在、及び当該２次区画地図情報のデータサイズを有する。
【００５８】
所要の更新領域の領域識別子を有する２次区画管理レコードを参照することにより、所要の更新領域の２次区画地図情報を取得することができる。
【００５９】
図８に示す１次区画地図情報は、図４に示した地図情報において、階層がレベル０であり、メッシュ座標が（ｉ，ｊ）＝（２，３）である１次区画に対応する１次区画地図情報＃４６を具体的に示した例である。
【００６０】
図８に示す１次区画地図情報＃４６において、１次区画地図情報ヘッダによれば、１次区画（２，３）内の２次区画数が３個であり、２次区画管理レコードとしては更新領域がＡの２次区画管理レコード＃０と更新領域がＢの２次区画管理レコード＃１と更新領域がＣの２次区画管理レコード＃２とが含まれている。さらに、２次区画地図情報としては、１次区画（２，３）内の更新領域がＡである２次区画地図情報＃０と同じく１次区画（２，３）内の更新領域がＢである２次区画地図情報＃１と同じく１次区画（２，３）内の更新領域がＣである２次区画地図情報＃２とが含まれている。
【００６１】
なお、上記の１次区画地図情報ヘッダにおける２次区画管理レコード＃０を例にとれば、当該２次区画管理レコード＃０においては、領域識別子が更新領域Ａに対応しており、さらに、２次区画地図情報＃０の所在としては更新領域がＡである２次区画地図情報＃０の所在であり、２次区画地図情報のデータサイズとしては当該２次区画地図情報＃０のデータサイズとなっている。
【００６２】
図９は、１次区画内の２次区画地図情報の例で、経路計算、マップマッチングや道路の表示に使用するための道路網を表す道路データ、河川及び海等の地図背景を表示するための背景データ、地名等名称を表示するための名称データ、経路誘導のための経路誘導データ、施設等を検索するための検索データ等の各種のデータを有すると共に、前記各種のデータの所在や前記各種のデータのデータサイズを示す地図データヘッダを有している。
【００６３】
以上のように、１次区画地図情報は、地図情報を１次区画内の所定形状の領域に区画化された領域である２次区画毎に分類して、管理し収容しているため、１次区画地図情報を更新領域毎に更新することが容易となる。
【００６４】
＜更新情報＞
更新情報は、使用者ないしは地図情報処理装置が所要する更新領域に関するものであって、地図情報記憶部４に記憶された全階層の地図情報を更新するために必要な情報で、更新情報記憶媒体として例えばメモリカードに記憶された形態で、使用者に提供される。
【００６５】
更新情報は、更新管理情報と更新領域内の２次区画更新情報とを有する。
【００６６】
更新領域内の２次区画更新情報は、当該更新情報が更新対象とする更新領域に属する最新バージョンの２次区画更新情報で、各階層毎に更新領域に一部又は全部が含まれる１次区画に対応して設けられる。
【００６７】
更新管理情報は、更新管理情報ヘッダ及び１次区画更新管理レコードの並びを有する。
【００６８】
更新管理情報ヘッダは、使用者ないしは地図情報処理装置が所要する更新対象である更新領域を示す領域識別子、当該更新領域の名称を示す更新領域の領域名、更新バージョン、更新領域内の２次区画更新情報の数を有する。なお、更新バージョンとしては、上記最新バージョンを設定する。
【００６９】
１次区画更新管理レコードは、上記更新領域内の２次区画更新情報を管理するためのレコードで、更新情報ヘッダが示す更新領域内の２次区画更新情報の数だけ設けられ、管理対象とする更新領域内の２次区画更新情報の階層、メッシュ座標、所在及びデータサイズ等を表す情報を有する。
【００７０】
図１０は、図４の区画において更新範囲を上記更新領域Ｃとしたときの更新情報の例である。
【００７１】
図１０に示すように、レベル２に対し、更新領域Ｃを含む１次区画（０，０）、１次区画（０，１）、１次区画（１，０）、１次区画（１，１）のそれぞれについて、最新バージョンであり更新領域Ｃに属する２次区画の地図情報である更新領域内の２次区画更新情報＃０〜２次区画更新情報＃３からなる４個の２次区画更新情報、及びそれらの１次区画更新管理レコード＃０〜１次区画更新管理レコード＃３からなる４個の１次区画更新管理レコードを設ける。従って、レベル２のどの１次区画に対する更新領域内の２次区画更新情報にも更新領域Ｃ以外の地図情報は含まれない。例えば、レベル２の、１次区画（０，０）の更新領域内の２次区画更新情報＃０には更新領域Ａ、Ｂ、及びＤに属する２次区画の地図情報は含まれない。
【００７２】
レベル１に対し、更新領域Ｃを含む１次区画（１，１）、１次区画（１，２）、１次区画（２，１）、１次区画（２，２）のそれぞれについて、最新バージョンであり更新領域Ｃに属する２次区画の地図情報である更新領域内の２次区画更新情報＃４〜２次区画更新情報＃７、及びそれらの１次区画更新管理レコード＃４〜１次区画更新管理レコード＃７を設ける。従って、レベル１のどの１次区画に対する更新領域内の２次区画更新情報にも更新領域Ｃ以外の地図情報は含まれない。例えば、レベル１の、１次区画（１，１）の更新領域内の２次区画更新情報＃４には更新領域Ａ、Ｂ、及びＤに属する２次区画の地図情報は含まれない。
【００７３】
レベル０に対し、更新領域Ｃを含む１次区画（２，２）、１次区画（２，３）、１次区画（２，４）、１次区画（３，２）、１次区画（３，３）、１次区画（３，４）、１次区画（３，５）、１次区画（４，２）、１次区画（４，３）、１次区画（４，４）、１次区画（４，５）のそれぞれについて、最新バージョンであり更新領域Ｃに属する２次区画の地図情報である更新領域内の２次区画更新情報＃８〜２次区画更新情報＃１８、及びそれらの１次区画更新管理レコード＃８〜１次区画更新管理レコード＃１８を設ける。従って、レベル０のどの１次区画に対する更新領域内の２次区画更新情報にも更新領域Ｃ以外の地図情報は含まれない。例えば、レベル０の、１次区画（２，３）の更新領域内の２次区画更新情報＃９には更新領域Ａ及びＢに属する２次区画の地図情報は含まれない。
【００７４】
上記のように更新領域Ｃの更新用のメモリカードには、更新領域Ｃ以外の更新情報は一切含まれず、更新情報の不要な増大を防止でき、提供範囲外の地図情報の使用料の発生を防止できる。
【００７５】
また、上記更新領域Ｃの更新用のメモリカードにおける更新情報の更新範囲は、レベル２、レベル１、及びレベル０の全ての階層で、同じ更新領域Ｃとなるため、レベル２、レベル１、及びレベル０の全ての階層で、更新領域Ｃの地図情報を同じバージョンに更新することができ、更新後の更新領域Ｃにおいて、階層間のバージョン不一致による不整合の発生を防止できる。
【００７６】
また、更新領域内の２次区画更新情報として、当該２次区画の最新バージョンの地図情報を用いるので、最新バージョンの地図情報から当該２次区画分だけを切り出すことにより更新領域内の２次区画更新情報が得られ、容易に更新情報を作成することができ、利用者はより安価な更新情報が得られる。
【００７７】
また、更新情報の更新対象の更新領域が地図情報と同じ行政区域又は行政区域以外で社会的に認知されている地域となるため、使用者は更新の範囲を容易に理解することができ、所要する地域の更新情報を的確に購入できる。
【００７８】
＜道路データに関するデータ構造＞
以下に、図９に示された２次区画地図情報のうちの道路データに関するデータ構造を説明する。道路データは、地理上の地点を表すノードとノード間を結ぶ道路を表すリンクからなる当該２次区画における道路網を表すデータである。
【００７９】
図１１は、図４に示す各階層の地図情報のうちで、レベル０の階層の１次区画（２，３）とその周辺の道路網の例である。ここで、「Ｎ」はノードを意味し、その後ろの数字はノード番号を意味している。また、「Ｌ」はリンクを意味し、その後ろの数字はリンク番号を意味している。また、１次区画（２，３）と他の１次区画との境界は、太い実線で示されている。
【００８０】
図１１の道路網の例では、ノードＮ０からノードＮ１８の１９個のノード、及びリンクＬ０からリンクＬ１８の１９個のリンクが示されている。また、各更新領域の境界が破線で示されている。境界Ａ−Ｂは、更新領域Ａと更新領域Ｂの境界であり、境界Ｂ−Ｃは、更新領域Ｂと更新領域Ｃの境界である。さらに、境界Ａ−Ｃは、更新領域Ａと更新領域Ｃの境界を示している。
【００８１】
また、ノードＮ４、ノードＮ１２、及びノードＮ１３は、一区画（２，３）とその周辺の１次区画との境界上に位置している。ノードＮ４は、１次区画（２，３）と１次区画（３，３）との境界上に存在して、リンクＬ３とリンクＬ１６とを接続する。ノードＮ１２は、１次区画（２，３）と１次区画（２，４）の境界上に存在して、リンクＬ１１とリンクＬ１４とを接続する。ノードＮ１３は、１次区画（２，３）と１次区画（２，２）との境界上に存在して、リンクＬ１３とリンクＬ１５とを接続する。
【００８２】
上記のように、１次区画や２次区画の境界上に位置するノードを境界ノードと呼び、特に、１次区画の境界上に位置するノードを以下では１次区画境界ノードと呼ぶものとする。
【００８３】
一方、ノードＮ２、ノードＮ７、及びノードＮ１０は、それぞれ更新領域の境界に位置している。ノードＮ２は、境界Ａ−Ｃ上に存在して、リンクＬ１とリンクＬ２とを接続する。ノードＮ７は、境界Ｂ−Ｃ上に存在して、リンクＬ５とリンクＬ６とを接続する。ノードＮ１０は、境界Ａ−Ｂ上に存在して、リンクＬ８とリンクＬ９とを接続する。
【００８４】
上記のように、境界ノードのうちで、特に更新領域の境界上に位置するノードを以下では更新領域境界ノードと呼ぶものとする。
【００８５】
図１２は、図１１の道路網を２次区画に区画化した結果を説明するための説明図である。１次区画（２，３）は、更新領域Ａ、Ｂ、及びＣで２次区画に区画化されている。以下では、１次区画（２，３）を更新領域Ａで区画化した２次区画を２次区画（２，３）−Ａと表すこととする。同様に、１次区画（２，３）を更新領域Ｂで区画化した２次区画は、２次区画（２，３）−Ｂ、更新領域Ｃで区画化した２次区画は、２次区画（２，３）−Ｃで表されるものとする。
【００８６】
さらに、図１２においては、１次区画（２，３）の周辺の１次区画が更新領域Ｃで区画化された２次区画（２，２）−Ｃ、２次区画（２，４）−Ｃ、及び２次区画（３，３）−Ｃも示されている。
【００８７】
なお、図１２において、ノードＮ４’及びノードＮ４”は、図１１のノードＮ４と実質的に同一ノードであり、更新領域間の境界でのリンクの接続を説明するために、便宜上、図１１におけるノードＮ４をノードＮ４’及びノードＮ４”で表現したものである。ノードＮ２’とノードＮ２”、ノードＮ７’とノードＮ７”、ノードＮ１０’とノードＮ１０”、ノードＮ１２’とノードＮ１２”、及びノードＮ１３’とノードＮ１３”についても同様である。
【００８８】
図１３は、図１１及び図１２における２次区画（２，３）−Ｃの２次区画地図情報のうちの道路網を表す道路データのデータ構造の例である。
【００８９】
図１３において、２次区画（２，３）−Ｃの道路網の道路データは、道路データ管理部、ノード情報、接続情報、リンク情報、及びリンク形状情報からなる。
【００９０】
ここで、道路データ管理部は、ノード情報、接続情報、リンク情報、及びリンク形状情報のそれぞれの格納位置やデータサイズやレコード数等を示す。
【００９１】
ノード情報は、２次区画（２，３）−Ｃに属するノードに対応して設けられたノードレコードからなる情報で、図１２に示されたノードＮ２”、ノードＮ３、ノードＮ４’、ノードＮ７”、ノードＮ８、ノードＮ９、ノードＮ１２”、及びノードＮ１３’のそれぞれに対応してノードレコード＃０〜ノードレコード＃７からなる。なお、ノード情報におけるノードレコードの並び順をノードレコード番号と呼ぶものとする。
【００９２】
接続情報は、２次区画（２，３）−Ｃに属するノードに対応して設けられた接続レコードからなる情報で、図１２に示されたノードＮ２”、ノードＮ３、ノードＮ４’、ノードＮ７”、ノードＮ８、ノードＮ９、ノードＮ１２”、及びノードＮ１３’のそれぞれに対応して接続レコード＃０〜接続レコード＃７からなる。
【００９３】
リンク情報は、２次区画（２，３）−Ｃに属するリンクに対応して設けられたリンクレコードからなる情報で、図１２に示されたリンクＬ２、リンクＬ３、リンクＬ６、リンクＬ７、リンクＬ１１、リンクＬ１２、及びリンクＬ１３のそれぞれに対応してリンクレコード＃０〜リンクレコード＃６からなる。なお、リンク情報におけるリンクレコードの並び順をリンクレコード番号と呼ぶものとする。
【００９４】
リンク形状情報は、２次区画（２，３）−Ｃに属するリンクに対応して設けられた形状レコードからなる情報で、図１２に示されたリンクＬ２、リンクＬ３、リンクＬ６、リンクＬ７、リンクＬ１１、リンクＬ１２、及びリンクＬ１３のそれぞれに対応して形状レコード＃０〜形状レコード＃６からなる。
【００９５】
図１４は、図１１及び図１２における２次区画（２，３）−Ａの２次区画地図情報のうちの道路網を表す道路データのデータ構造の例である。
【００９６】
図１４において、ノード情報は、図１２に示されたノードＮ０、ノードＮ１、ノードＮ２’、ノードＮ１０”、及びノードＮ１１のそれぞれに対応してノードレコード＃０〜ノードレコード＃４からなる。接続情報は、図１２に示されたノードＮ０、ノードＮ１、ノードＮ２’、ノードＮ１０”、及びノードＮ１１のそれぞれに対応して接続レコード＃０〜接続レコード＃４からなる。リンク情報は、図１２に示されたリンクＬ０、リンクＬ１、リンクＬ９、及びリンクＬ１０のそれぞれに対応してリンクレコード＃０〜リンクレコード＃３からなる。リンク形状情報は、図１２に示されたリンクＬ０、リンクＬ１、リンクＬ９、及びリンクＬ１０のそれぞれに対応して形状レコード＃０〜形状レコード＃３からなる。
【００９７】
以下、同様に、図１５は、図１１及び図１２における２次区画（２，３）−Ｂの２次区画地図情報のうちの道路網を表す道路データのデータ構造の例である。
【００９８】
図１５において、ノード情報は、図１２に示されたノードＮ５、ノードＮ６、ノードＮ７’、及びノードＮ１０’のそれぞれに対応してノードレコード＃０〜ノードレコード＃３からなる。接続情報は、図１２に示されたノードＮ５、ノードＮ６、ノードＮ７’、及びノードＮ１０’のそれぞれに対応して接続レコード＃０〜接続レコード＃３からなる。リンク情報は、図１２に示されたリンクＬ４、リンクＬ５、及びリンクＬ８のそれぞれに対応してリンクレコード＃０〜リンクレコード＃２からなる。リンク形状情報は、図１２に示されたリンクＬ４、リンクＬ５、及びリンクＬ８のそれぞれに対応して形状レコード＃０〜形状レコード＃２からなる。
【００９９】
また、図１６は、図１１及び図１２における２次区画（２，３）−Ｃの２次区画地図情報のうちの道路網を表す道路データのデータ構造の例である。
【０１００】
図１６において、ノード情報は、図１２に示されたノードＮ４”、ノードＮ１６、ノードＮ１７、及びノードＮ１８のそれぞれに対応してノードレコード＃０〜ノードレコード＃３からなる。接続情報は、図１２に示されたノードＮ４”、ノードＮ１６、ノードＮ１７、及びノードＮ１８のそれぞれに対応して接続レコード＃０〜接続レコード＃３からなる。リンク情報は、図１２に示されたリンクＬ１６、リンクＬ１７、及びリンクＬ１８のそれぞれに対応してリンクレコード＃０〜リンクレコード＃２からなる。リンク形状情報は、図１２に示されたリンクＬ１６、リンクＬ１７、及びＬ１８のそれぞれに対応して形状レコード＃０〜形状レコード＃２からなる。
【０１０１】
また、図１７は、図１１及び図１２における２次区画（２，４）−Ｃの２次区画地図情報のうちの道路網を表す道路データのデータ構造の例である。
【０１０２】
図１７において、ノード情報は、図１２に示されたノードＮ１４及びＮ１２’のそれぞれに対応してノードレコード＃０〜ノードレコード＃１からなる。接続情報は、図１２に示されたノードＮ１４及びＮ１２’のそれぞれに対応して接続レコード＃０〜接続レコード＃１からなる。リンク情報は、図１２に示されたリンクＬ１４に対応してリンクレコード＃０からなる。リンク形状情報は、図１２に示されたリンクＬ１４に対応して形状レコード＃０からなる。
【０１０３】
さらに、図１８は、図１１及び図１２における２次区画（２，２）−Ｃの２次区画地図情報のうちの道路網を表す道路データのデータ構造の例である。
【０１０４】
図１８において、ノード情報は、図１２に示されたノードＮ１５及びノードＮ１３”のそれぞれに対応してノードレコード＃０〜ノードレコード＃１からなる。接続情報は、図１２に示されたノードＮ１５及びノードＮ１３”のそれぞれに対応して接続レコード＃０〜接続レコード＃１からなる。リンク情報は、図１２に示されたリンクＬ１５に対応してリンクレコード＃０からなる。リンク形状情報は、図１２に示されたリンクＬ１５に対応して形状レコード＃０からなる。
【０１０５】
また、図１９は、図１３に示す２次区画（２，３）−Ｃの２次区画地図情報のうちの道路網を表す道路データにおけるノードレコードのデータ構造の例である。
【０１０６】
図１９において、ノードレコードは、ノード座標、ノード種別情報、接続リンク数、及び接続レコードオフセットからなる固定長のレコードである。
【０１０７】
ここで、ノード座標は、ノードの地理上位置を、その経度及び緯度により表す。ノードレコード＃ｉ（ｉ＝０〜７）に対応するノードの経度及び緯度としてそれぞれＸｉ及びＹｉが設定される。なお、ノード座標として、経度及び緯度に加えて高さを表す情報である例えば高度を保有するようにしても良い。
【０１０８】
ノード種別情報は、ノードが２次区画（２，３）−Ｃの内部に存在する内部ノード、一次区画境界上に存在する１次区画境界ノード、及び更新領域境界上に存在する更新領域境界ノードのいずれであるかを示すノード種別を表す。例えば、図１９においては、内部ノードを０、１次区画境界ノードを１、そして更新領域境界ノードを２で表すものとしている。
【０１０９】
図１３に示されたノードＮ３、ノードＮ８、及びノードＮ９のノード種別は図１２から明らかなように内部ノードなので、図１９に示すように、ノードレコード＃１、ノードレコード＃４、及びノードレコード＃５のノード種別情報はいずれも０が設定されている。図１３に示されたノードＮ４’、ノードＮ１２”、及びノードＮ１３’のノード種別は一次区画境界ノードなので、図１９に示すように、ノードレコード＃２、ノードレコード＃６、及びノードレコード＃７のノード種別情報はいずれも１が設定されている。図１３に示されたノードＮ２”及びノードＮ７”のノード種別は更新領域境界ノードなので、図１９に示すように、ノードレコード＃０及びノードレコード＃３のノード種別情報はいずれも２が設定されている。
【０１１０】
次に、接続リンク数は、ノードに接続するリンクの数を表す。ノードＮ３にはリンクＬ２、リンクＬ３、リンクＬ１２、及びリンクＬ１３の都合４個のリンクが接続しているので、ノードレコード＃１の接続リンク数は４と設定している。同様に、ノードＮ８にはリンクＬ６、リンクＬ７、リンクＬ１１、及びリンクＬ１２の都合４個のリンクが接続しているので、ノードレコード＃４の接続リンク数は４と設定している。また、ノードＮ２”、ノードＮ４’、ノードＮ７”、ノードＮ１２”、及びノードＮ１３’には、それぞれリンクＬ２、リンクＬ３、リンクＬ６、リンクＬ７、リンクＬ１１、及びリンクＬ１３が１個ずつ接続されているので、ノードレコード＃０、ノードレコード＃２、ノードレコード＃３、ノードレコード＃６、及びノードレコード＃７のそれぞれのノード種別情報はいずれも１が設定されている。
【０１１１】
次に、接続レコードオフセットは、ノードレコードのノードに対応する接続レコードの地図情報記憶部４における格納位置を、接続情報の格納領域の先頭位置から当該接続レコードまでのバイト数で表したものである。例えば、ノードＮ３に対応するノードレコード＃１の接続レコードオフセットは４であって、これは、地図情報記憶部４での接続情報が格納されている格納領域において、その格納領域の先頭位置から４バイトオフセットした位置から接続レコード＃１が格納されていることを意味している。
【０１１２】
図２０は、図１３に示す２次区画（２，３）−Ｃの２次区画地図情報のうちの道路網を表す道路データにおける接続レコードのデータ構造の例である。
【０１１３】
図２０において、接続レコードは、接続リンクレコード番号と隣接２次区画ノード情報とからなる。
【０１１４】
ここで、接続リンクレコード番号は、接続レコードが対応するノードに接続するリンクのリンクレコード番号を表す。
【０１１５】
また、隣接２次区画ノード情報は、接続レコードが対応するノードのノード種別が内部ノード以外の時にのみ設けられ、当該ノードのノード種別が１次区画境界ノードの場合と更新領域境界ノードの場合とで、隣接２次区画ノード情報の内容は異なる。ノード種別が１次区画境界ノードの場合には、隣接２次区画ノード情報は、隣接１次区画情報と隣接２次区画内のノード指示情報とからなる。一方、ノード種別が更新領域境界ノードの場合には、隣接２次区画ノード情報は、隣接更新領域情報と隣接２次区画内のノード指示情報とからなる。
【０１１６】
一方、ノード種別が内部ノードの場合は、接続リンク番号は設定されるが、隣接２次区画ノード情報は設定されない。
【０１１７】
さて、隣接２次区画ノード情報が設定された場合において、隣接１次区画情報は、図１３に示す２次区画（２，３）−Ｃに隣接する隣接２次区画で、当該接続レコードに対応するノードと同一のノードを１次区画境界ノードに持つ２次区画が属する１次区画を２次区画（２，３）−Ｃに対する位置関係で表す。２次区画（２，３）−Ｃに対する当該隣接２次区画が属する１次区画の位置関係について、右、右上、直上、左上、左、左下、直下、及び右下の８方向をそれぞれ０〜７の値で表すものとする。
【０１１８】
さらに、隣接更新領域情報は、図１３に示す２次区画（２，３）−Ｃに隣接する隣接２次区画で、当該接続レコードに対応するノードと同一のノードを更新領域境界ノードに持つ２次区画が属する更新領域を表す。
【０１１９】
さらに、隣接２次区画内のノード指示情報は、ノード種別が１次区画境界ノードないしは更新領域境界ノードのいずれの場合であっても、図１３に示す２次区画（２，３）−Ｃに隣接する隣接２次区画内にあって、当該接続レコードに対応するノードと同一のノードについて、当該ノードのノードレコード番号を示すものである。
【０１２０】
図２０を用いて、接続レコードを具体的に説明する。
【０１２１】
ノードＮ２”にはリンクＬ２が接続されているので、図２０に示された接続レコード＃０の接続リンクレコード番号は０が設定される。また、隣接２次区画ノード情報については、ノードＮ２”と同一のノードＮ２’を更新領域境界ノードに持つ２次区画（２，３）−Ａは、更新領域Ａに属している。そこで、隣接更新領域情報として、更新領域がＡであることを示す領域識別子（Ａ）が設定される。さらに、ノードＮ２’は、隣接２次区画（２，３）−Ａ内にある更新領域境界ノードである。そこで、接続レコード＃０において、隣接２次区画内のノード指示情報は、隣接２次区画（２，３）−Ａ内の更新領域境界ノードであるノードＮ２’という意味で、図１４に示されたノード情報から明らかなように、２が設定される。
【０１２２】
同様にして、ノードＮ３にはリンクＬ２、リンクＬ３、リンクＬ１２、及びリンクＬ１３が接続されているので、図２０に示された接続レコード＃１の接続リンクレコード番号は、それぞれ０、１、５、及び６が設定される。なお、隣接２次区画ノード情報については、ノードＮ３は内部ノードであるので、設定されずになしとなる。
【０１２３】
次に、ノードＮ４’にはリンクＬ３が接続されているので、図２０に示された接続レコード＃２の接続リンクレコード番号は１が設定される。また、隣接２次区画ノード情報については、ノードＮ４’と同一のノードＮ４”を１次区画境界ノードに持つ２次区画（３，３）−Ｃが属する１次区画（３，３）は、隣接２次区画が属する１次区画であるが、当該１次区画（３，３）は２次区画（２，３）−Ｃの右に位置する。そこで、隣接１次区画情報として、０が設定される。さらに、ノードＮ４”は、隣接２次区画（３，３）−Ｃ内にある１次区画境界ノードである。そこで、接続レコード＃２において、隣接２次区画内のノード指示情報は、隣接２次区画（３，３）−Ｃ内の１次区画境界ノードであるノードＮ４”という意味で、図１６に示されたノード情報から明らかなように、０が設定される。
【０１２４】
次に、ノードＮ７”にはリンクＬ６が接続されているので、図２０に示された接続レコード＃３の接続リンクレコード番号は２が設定される。また、隣接２次区画ノード情報については、ノードＮ７”と同一のノードＮ７’を更新領域境界ノードに持つ２次区画（２，３）−Ｂは、更新領域Ｂに属している。そこで、隣接更新領域情報として、更新領域がＢであることを示す領域識別子（Ｂ）が設定される。さらに、ノードＮ７’は、隣接２次区画（２，３）−Ｂ内にある更新領域境界ノードである。そこで、接続レコード＃３において、隣接２次区画内のノード指示情報は、隣接２次区画（２，３）−Ｂ内の更新領域境界ノードであるノードＮ７’という意味で、図１５に示されたノード情報から明らかなように、２が設定される。
【０１２５】
次に、ノードＮ８にはリンクＬ６、リンクＬ７、リンクＬ１１、及びリンクＬ１２が接続されているので、接続レコード＃４の接続リンクレコード番号は、それぞれ２、３、４、及び５が設定される。なお、隣接２次区画ノード情報については、ノードＮ８は内部ノードであるので、設定されずになしとなる。
【０１２６】
次に、ノードＮ９にはリンクＬ７が接続されているので、接続レコード＃５の接続リンクレコード番号は、３が設定される。なお、隣接２次区画ノード情報については、ノードＮ９は内部ノードであるので、設定されずになしとなる。
【０１２７】
次に、ノードＮ１２”にはリンクＬ１１が接続されているので、接続レコード＃６の接続リンクレコード番号は４が設定される。また、隣接２次区画ノード情報については、ノードＮ１２”と同一のノードＮ１２’を１次区画境界ノードに持つ２次区画（２，４）−Ｃが属する１次区画（２，４）は、隣接２次区画が属する１次区画であるが、当該１次区画（２，４）は２次区画（２，３）−Ｃの真上に位置する。そこで、隣接１次区画情報として、２が設定される。さらに、ノードＮ１２’は、隣接２次区画（２，４）−Ｃ内にある１次区画境界ノードである。そこで、接続レコード＃６において、隣接２次区画内のノード指示情報は、隣接２次区画（２，４）−Ｃ内の１次区画境界ノードであるノードＮ１２’という意味で、図１７に示されたノード情報から明らかなように、１が設定される。
【０１２８】
次に、ノードＮ１３’にはリンクＬ１３が接続されているので、接続レコード＃７の接続リンクレコード番号は６が設定される。また、隣接２次区画ノード情報については、ノードＮ１３’と同一のノードＮ１３”を１次区画境界ノードに持つ２次区画（２，２）−Ｃが属する１次区画（２，２）は、隣接２次区画が属する１次区画であるが、当該１次区画（２，２）は２次区画（２，３）−Ｃの真下に位置する。そこで、隣接１次区画情報として、６が設定される。さらに、ノードＮ１３”は、隣接２次区画（２，２）−Ｃ内にある１次区画境界ノードである。そこで、接続レコード＃７において、隣接２次区画内のノード指示情報は、隣接２次区画（２，２）−Ｃ内の１次区画境界ノードであるノードＮ１３”という意味で、図１８に示されたノード情報から明らかなように、１が設定される。
【０１２９】
図２０に示す２次区画（２，３）−Ｃの道路網を表す道路データにおける接続レコードのデータ構造の例は、以上のように設定されている。従って、接続レコード＃２の隣接２次区画ノード情報の隣接１次区画情報から、隣接１次区画（３，３）を求めることができ、その隣接１次区画（３，３）の１次区画地図情報の１次区画地図情報ヘッダを参照して、当該２次区画が属する更新領域Ｃに属する２次区画（３，３）−Ｃの１次区画内２次区画地図情報を上記１次区画地図情報から取得することにより、図１６の２次区画（３，３）−Ｃの道路データが得られ、また、接続レコード＃２の隣接２次区画ノード情報の隣接２次区画内のノード指示情報から上記道路データのノードレコード＃０が得られ、ノードＮ４”が特定される。
【０１３０】
以上のように、接続レコード＃２の隣接２次区画ノード情報により、１次区画境界ノードＮ４’に接続する隣接２次区画の１次区画境界ノードＮ４”を求めることができる。
【０１３１】
同様にして、接続レコード＃６及び接続レコード＃７により、１次区画境界ノードＮ１２”に接続する隣接２次区画の１次区画境界ノードＮ１２’及び１次区画境界ノードＮ１３’に接続する隣接２次区画の１次区画境界ノードＮ１３”を求めることができる。
【０１３２】
また、図２０に示す２次区画（２，３）−Ｃの道路網を表す道路データにおける接続レコードのデータ構造の例は、以上のように設定されているので、接続レコード＃０の隣接２次区画ノード情報の隣接更新領域情報から、隣接更新領域Ａを求めることができ、当該１次区画（２，３）の１次区画地図情報の１次区画地図情報ヘッダを参照して、隣接更新領域Ａに属する２次区画（２，３）−Ａの１次区画内２次区画地図情報を上記１次区画地図情報から取得することにより、図１４の２次区画（２，３）−Ａの道路データを得ることができる。また、接続レコード＃０の隣接２次区画ノード情報の隣接２次区画内のノード指示情報から上記道路データのノードレコード＃２が得られ、ノードＮ２’が特定される。
【０１３３】
以上のように、接続レコード＃０の隣接２次区画ノード情報により、更新領域境界ノードＮ２”に接続する隣接２次区画の更新領域境界ノードＮ２’を求めることができる。
【０１３４】
同様にして、接続レコード＃３の隣接２次区画ノード情報により、更新領域境界ノードＮ７”に接続する隣接２次区画の更新領域境界ノードＮ７’を求めることができる。
【０１３５】
以上のようにして、２次区画の境界ノードに接続する隣接２次区画の境界ノードを求めることにより、隣接する２次区画の道路網を辿ることができる。
【０１３６】
図２１は、図１３におけるリンクレコードのデータ構造の例である。
【０１３７】
図２１において、リンクレコードは、始点ノードレコード番号、終点ノードレコード番号、リンク属性、及び形状レコードオフセットからなる。
【０１３８】
ここで、始点ノードレコード番号及び終点ノードレコード番号は、それぞれリンクの始点側及び終点側のノードのノードレコード番号を表す。
【０１３９】
具体的には、リンクＬ２のノードＮ２”及びノードＮ３をそれぞれ始点ノード及び終点ノードとするため、リンクレコード＃１の始点ノードレコード番号及び終点ノードレコード番号として、それぞれ０及び１を設定する。
【０１４０】
また、リンクＬ３のノードＮ３及びノードＮ４’をそれぞれ始点ノード及び終点ノードとするため、リンクレコード＃１の始点ノードレコード番号及び終点ノードレコード番号として、それぞれ１及び２を設定する。
【０１４１】
リンクレコード＃２〜リンクレコード＃６の始点ノードレコード番号及び終点ノードレコード番号も上記と同様にして設定する。
【０１４２】
次に、図２１において、リンク属性は、高速道路、国道、都道府県道路等の道路の種別を表す道路種別、道路番号、一方通行規制等、当該リンクが表す道路の属性を表す。
【０１４３】
リンクレコード＃ｉ（ｉ＝０〜６）に対応するリンク属性としてＡｉが設定される。
【０１４４】
さらに、形状レコードオフセットは、当該リンクに対応する形状レコードの格納位置を、リンク形状情報先頭からの上記形状レコードまでのバイト数で表したものである。形状レコード＃０〜形状レコード＃６のリンク形状情報先頭からのバイト数をそれぞれＯＳＲ０、ＯＳＲ１、ＯＳＲ２、ＯＳＲ３、ＯＳＲ４、ＯＳＲ５、及びＯＳＲ６が設定される。
【０１４５】
接続レコードとリンクレコードにより、ノードに対して１つのリンクで到達できるノードを求めることができる。例えば、図１２に示されたノードＮ３に対して、図１３に示されたノードＮ３のノードレコード＃１が示す接続レコード＃１を参照して、図２０の接続リンクレコード番号が示すリンクＬ２、リンクＬ３、リンクＬ１２、及びリンクＬ１３のリンクレコードをさらに参照し、ノードＮ３を始点または終点となるノードとして持つリンクレコード＃０、リンクレコード＃１、リンクレコード＃５、及びリンクレコード＃６を見つけ、これらのリンクレコードが持つノードＮ３側でない側の始点または終点となるノードＮ２”、ノードＮ４’、ノードＮ８、及びノードＮ１３’を求める。これらのノードがノードＮ３から１つのリンクで到達できるノードである。
【０１４６】
以上のようにして、ノードに接続するリンク及びノードを順次求めることにより、２次区画内の道路網を辿ることができる。
【０１４７】
図２２は、図１３における形状レコードのデータ構造の例である。
【０１４８】
形状レコードは対応するリンクの道路形状を折れ線で表したもので、形状点数と形状点列とからなる。ここで、形状点数は、上記折れ線の頂点の数を表す。また、形状点列は、上記折れ線の頂点の地理的位置を示すための緯度及び経度を表す情報を形状点列の数だけ並べたものである。例えば、図１２において、形状レコード＃０はリンクＬ２の道路形状を折れ線で表すものであり、リンクＬ２を表す折れ線の頂点の数を意味する形状点数はＳＰＮ０個である。さらに、形状点列ＳＰＳ０は、リンクＬ２の道路形状に対応する折れ線の頂点の緯度及び経度を表す情報を形状点列の数だけ並べたものである。
【０１４９】
図２３は、道路網全体が最新バージョンに更新され、図１１の道路網にノードＮ１９、ノードＮ２０、ノードＮ２１、リンクＬ１９、リンクＬ２０、リンクＬ２１、及びリンクＬ２２が新設されたものである。更新領域Ａ、更新領域Ｂ、及び更新領域Ｃのいずれもが最新バージョンに更新されている。
【０１５０】
また、図２４は、図２３に示された道路網の各々の２次区画の道路網を示す。図２４において、ノードＮ１９’及びノードＮ１９”は図２３のノードＮ１９と同一ノードであり、図２４のノードＮ１９’及びノードＮ１９”は図２３のノードＮ１９と同一ノードであり、図２４のノードＮ２１’及びノードＮ２１”は図２３のノードＮ２１と同一ノードである。
【０１５１】
図２５は、図２４における２次区画（２，３）−Ｃの道路データの例である。図２５において、ノードＮ１９”、ノードＮ２０、及びノードＮ２１’のノードレコード＃０、ノードレコード＃１、ノードレコード＃２、接続レコード＃０、接続レコード＃１、及び接続レコード＃２が新設される。さらに、リンクＬ２０及びリンクＬ２１のそれぞれリンクレコード＃０及びリンクレコード＃１、形状レコード＃０、及び形状レコード＃１が新設される。その結果、更新前から存在していたノードレコードのノードレコード番号及びリンクレコードのリンクレコード番号が変化している。
【０１５２】
図２６は、図２４における２次区画（２，３）−Ｃの道路データの例である。図２６において、ノードＮ１９’のノードレコード＃０及び接続レコード＃０が新設される。さらに、リンクＬ１９のリンクレコード＃０及び形状レコード＃０が新設される。その結果、更新前から存在していたノードレコードのノードレコード番号及びリンクレコードのリンクレコード番号が変化している。
【０１５３】
図２７は、図２４における２次区画（３，３）−Ａの道路データの例である。図２７において、ノードＮ２１’のノードレコード＃０及び接続レコード＃０が新設される。さらに、リンクＬ２２のリンクレコード＃０及び形状レコード＃０が新設される。その結果、更新前から存在していたノードレコードのノードレコード番号及びリンクレコードのリンクレコード番号が変化している。
【０１５４】
なお、図２４における２次区画（２，３）−Ｂ、２次区画（２，４）−Ｃ、及び２次区画（２，２）−Ｃは、道路網が変化していないため、それらの道路データのデータ構造はそれぞれ更新前の図１５、図１７、及び図１８に同じであるが、上記のように隣接する２次区画の道路網の変化によりノードレコード番号が変化しているため接続レコードにおける隣接２次区画内のノード指示情報が変化している。
【０１５５】
図２３は、図１１の道路網全体が最新バージョンに更新されたものであるが、図２８は、図１１の道路網に対し、更新領域Ｂ及び更新領域Ｃのみの地図情報を更新した場合の各々の２次区画の道路網を示す。
【０１５６】
図１２は図１１の道路網を２次区画に区画化した結果が分かり易いように２次区画単位で分離して示した説明図であるが、図１２での更新領域Ａ、更新領域Ｂ、及び更新領域Ｃの地図情報のバージョンをいずれも０とする。それが、更新領域Ｂ及び更新領域Ｃのみの地図情報を更新することにより、更新領域Ｂ及び更新領域Ｃの地図情報のバージョンが１にバージョンアップするものとする。なお、更新領域Ａの地図情報のバージョンは０のままである。
【０１５７】
その場合、図６に示された更新領域に関するバージョン管理情報においては、バージョン管理レコード＃０（Ａ）の記憶地図情報バージョンは０のままで、バージョン管理レコード＃１（Ｂ）及びバージョン管理レコード＃２（Ｃ）の記憶地図情報バージョンは１に設定される。
【０１５８】
以上のように、更新領域のバージョンが異なる場合は、更新領域境界で隣接する２次区画同士でバージョンが異なる場合がある。例えば、図２８において、２次区画（２，３）−Ａと２次区画（２，３）−Ｂとのバージョンは異なる。さらに、２次区画（２，３）−Ｃと２次区画（２，３）−Ａとのバージョンも異なる。なお、２次区画（２，３）−Ｃと２次区画（２，３）−Ｂとのバージョンは同一である。
【０１５９】
任意の２次区画における更新領域境界ノードに接続する隣接２次区画の更新領域境界ノードは、上記２次区画同士のバージョンが同一であれば、上記任意の２次区画における更新領域境界ノードの接続レコードの隣接２次区画ノード情報により求めることができる。
【０１６０】
一方、上記２次区画同士のバージョンが異なるとき、図２８の２次区画（２，３）−Ｃは、図２５に示された道路データを有し、図２８に示された２次区画（２，３）−Ａは、図１４に示された道路データを有している。図２５に示された道路データは、隣接２次区画が図１３に示された道路データを有することを前提としている。図１４に示された道路データは、隣接２次区画が図１３に示された道路データを有することを前提としている。その結果、図２８に示された２次区画（２，３）−Ｃと２次区画（２，３）−Ａとの道路データ同士は整合しない。
【０１６１】
以上のように、任意の２次区画における更新領域境界ノードに接続する隣接２次区画の更新領域境界ノードは、上記２次区画同士のバージョンが異なるときは上記道路データ同士が整合しないため、上記任意の２次区画における更新領域境界ノードの接続レコードの隣接２次区画ノード情報により求めることができない。
【０１６２】
地図情報の更新は、更新領域毎に行うため、更新領域内の２次区画のバージョンはすべて同一となる。１次区画を更新領域で区画化したもの、言い換えれば、更新領域を１次区画で区画化したものが２次区画であるから、更新領域内の隣接する２次区画同士は１次区画境界で接する。従って、１次区画境界で隣接する２次区画のバージョンは必ず一致する。例えば、図２８において、２次区画（２，３）−Ｃと１次区画境界で隣接する、２次区画（３，３）−Ｃ、２次区画（２，２）−Ｃ、及び２次区画（２，４）−Ｃのバージョンは２次区画（２，３）−Ｃのバージョンと同一である。
【０１６３】
以上により、任意の２次区画における１次区画境界ノードに接続する隣接２次区画の１次区画境界ノードは、上記任意の２次区画における１次区画境界ノードの接続レコードの隣接２次区画ノード情報により求めることができる。
【０１６４】
任意の２次区画における境界ノードに接続する隣接２次区画の境界ノードを、上記任意の２次区画における境界ノードの接続レコードの隣接２次区画ノード情報により求める場合に、ノードレコードを固定長として、隣接２次区画内のノード指示情報としてノードレコード番号を用いているため、該当するノードレコードの格納位置を直ちに求めることができる。
【０１６５】
なお、隣接２次区画内のノード指示情報として、該当するノードレコードのノード情報先頭からのオフセットを用いても良い。
【０１６６】
＜地図情報処理装置の動作＞
図２９は、図１に示された地図情報処理装置の動作を示すフローチャートである。
【０１６７】
図２９において、地図情報処理装置が起動し、処理が開始されると、まず、ステップＳＴ１０では、更新情報取得部３に更新用のメモリカードが挿入されたか否かを確認し、挿入されたときはステップＳＴ１１へ行き、挿入されていなければステップＳＴ１２へ行く。
【０１６８】
ステップＳＴ１１では、更新情報取得部３に挿入された更新用のメモリカードに記憶されている更新情報を読み取り、読み取った更新情報を用いて地図情報記憶部４に記憶されている地図情報を更新する。更新情報中の１次区画管理レコードの階層名及びメッシュ座標により示される地図情報記憶部４に記憶されている１次区画地図情報中の２次区画地図情報で、更新管理情報の領域識別子が示す更新領域に属する２次区画地図情報を、上記の１次区画管理レコードが管理対象とする更新情報中の２次区画更新情報に書き換える。また、上記更新に従って、地図情報記憶部４に記憶された１次区画管理情報及びバージョン管理情報の変更を行う。以上の更新処理が終了すると、ステップＳＴ１２へ行く。
【０１６９】
なお、ステップＳＴ１１において、例えば図１０の更新情報により、図４に示すレベル２における１次区画（０，０）、１次区画（０，１）、１次区画（１，０）、及び１次区画（１，１）、レベル１における１次区画（１，１）、１次区画（１，２）、１次区画（２，１）、及び１次区画（２，２）、レベル０における１次区画（２，２）、１次区画（２，３）、１次区画（２，４）、１次区画（３，２）、１次区画（３，３）、１次区画（３，４）、１次区画（３，５）、１次区画（４，２）、１次区画（４，３）、１次区画（４，４）、及び１次区画（４，５）の地図情報記憶部４に記憶された各々の１次区画地図情報は、更新領域Ｃの２次区画地図情報のみが最新のバージョンに更新される。
【０１７０】
以上のように、更新領域毎に更新されるため、更新領域の各々の２次区画地図情報のバージョンはすべて同一となる。
【０１７１】
次に、ステップＳＴ１２において、使用者が地図情報処理装置の動作を指示するための指示信号を入力部１に入力する。例えば、地図の表示縮尺、目的地、経路計算の開始指示等の指示信号を入力する。その後、ステップＳＴ１３へ行く。
【０１７２】
次に、ステップＳＴ１３では、位置検出部２から車両の現在位置を取得し、ステップＳＴ１４へ行く。
【０１７３】
次に、ステップＳＴ１４では、ステップＳＴ１２で入力された指示信号及びステップＳＴ１３で取得した現在位置に基づいて定まる所要の階層の所要の１次区画の１次区画地図情報を地図情報記憶部４から取得する。さらに、取得された１次区画地図情報を用いて、各種の地図情報処理を行い、ステップＳＴ１０へ戻る。以下、上記ステップを繰り返す。
【０１７４】
図３０は、ステップ１４におけるマップマッチング及び経路探索で実行されるノード及びリンクの接続関係により道路網を辿る処理において、２次区画の境界ノードに至り、隣接２次区画へ渡る場合の処理で、２次区画の境界ノードである接続元ノードに対して、接続すべき隣接２次区画の境界ノードである接続先ノードを求める処理の詳細を示すフローチャートである。
【０１７５】
図３０において、接続元ノードが属する２次区画地図情報を有する１次区画地図情報が、既に地図情報記憶部４から取得されているものとし、接続元ノードのノードレコード番号が指定されているとして以下のような処理が行われる。
【０１７６】
以下では図２３に示された道路網に対して更新領域Ｂ及び更新領域Ｃの地図情報を更新して得られた図２８の道路網において、メッシュ座標（２，３）の１次区画地図情報が取得されており、上記１次区画地図情報に含まれる図２５の２次区画（２，３）−Ｃの２次区画地図情報の境界ノードであるノードＮ２”、ノードＮ４’、ノードＮ７’、ノードＮ１２”、ノードＮ１３’、ノードＮ１９”、及びノードＮ２１’のいずれか１つが接続元ノードとなっており、そのノードレコード番号が指定されているものとする。
【０１７７】
図３０において、ステップＳＴ２０では、地図情報記憶部４に記憶されているバージョン管理情報のバージョン管理レコードに記載された記憶地図情報バージョンを参照して、接続元ノードが属する２次区画地図情報のバージョンを求める。すなわち、本ステップにより、接続元ノードが属する２次区画（２，３）−Ｃの２次区画地図情報は、更新領域Ｃに属し、更新領域Ｃの地図情報のバージョンは１に更新されているので、２次区画（２，３）−Ｃの２次区画地図情報のバージョンとして１が得られる。
【０１７８】
次に、ステップＳＴ２１において、接続元ノードの属する２次区画地図情報の道路データより、接続元ノードのノードレコード番号に対応するノードレコードを取得する。
【０１７９】
次に、ステップＳＴ２２において、ステップＳＴ２１で取得したノードレコードの接続レコードオフセットが示す接続レコードを取得する。
【０１８０】
次に、ステップＳＴ２３において、ステップＳＴ２１で取得したノードレコードのノード種別情報が１次区画境界ノードか否かを判断し、１次区画境界ノードのときは、ステップＳＴ２４へ行き、１次区画境界ノードでないとき、すなわち更新領域境界ノードであるときは、ステップＳＴ２７へ行く。すなわち、本ステップにおいて、接続元ノードがノードＮ４’、ノードＮ１２”、ノードＮ１３’、及びノードＮ２１’のときはステップＳＴ２４へ行き、接続元がノードＮ２”、ノードＮ７”、及びノードＮ１９”のときはステップＳＴ２７へ行く。
【０１８１】
次に、ステップＳＴ２４において、接続元ノードが属する２次区画地図情報が属する１次区画のメッシュ座標と、ステップＳＴ２２で取得した接続レコードにおける隣接２次区画ノード情報の隣接１次区画情報を用いて、隣接１次区画のメッシュ座標を求め、上記メッシュ座標の１次区画地図情報を地図情報記憶部４から取得する。すなわち、本ステップにより、例えば、接続元ノードＮ４’に対し、１次区画（３，３）の１次区画地図情報が得られる。
【０１８２】
次に、ステップＳＴ２５において、ステップＳＴ２４で取得した１次区画地図情報の１次区画地図情報ヘッダを参照して、接続元ノードが属する２次区画地図情報の更新領域と同じ領域の２次区画地図情報の所在を求め、その位置にある２次区画地図情報を隣接２次区画地図情報に指定する。すなわち、本ステップにより、例えば、接続元ノードＮ４’に対し、１次区画（３，３）の１次区画地図情報に含まれる更新領域がＣである２次区画（３，３）−Ｃの２次区画地図情報が隣接２次区画地図情報に指定される。
【０１８３】
次に、ステップＳＴ２６において、ステップＳＴ２２で取得した接続レコードにおける隣接２次区画ノード情報の隣接２次区画内のノード指示情報が示すノードレコード番号に対応するノードレコードを、ステップＳＴ２５で指定した隣接２次区画地図情報の道路データから取得し、ここに接続先ノードが得られたとして処理を終了する。すなわち、本ステップにより、例えば、接続元ノードＮ４’に対し、２次区画（３，３）−Ｃの２次区画地図情報のノードＮ４”が接続先ノードとなる。
【０１８４】
以上の処理において、ノードレコードが固定長であり、隣接２次区画内のノード指示情報をノードレコード番号としているため、隣接２次区画内のノード指示情報は、ノードレコードの格納位置を表し、直ちにノードレコードを取得することができる。
【０１８５】
次に、ステップＳＴ２７において、地図情報記憶部４に記憶されているバージョン管理情報を参照して、ステップＳＴ２２で取得した接続レコードにおける隣接２次区画ノード情報の隣接更新領域情報が示す更新領域の地図情報のバージョンを求め、ステップＳＴ２０で求めたバージョンと比較する。その結果、バージョンが同一のときはステップＳＴ２８へ行き、バージョンが異なるときはステップＳＴ３０へ行く。すなわち、ステップＳＴ２０で得たバージョンは１で、例えば、接続元ノードがノードＮ２”の場合、ノードＮ２”の接続レコードの隣接更新領域情報が示す更新領域はＡで、更新領域Ａの地図情報のバージョンは０であるため、ステップＳＴ３０へ行くこととなる。また、接続元ノードがノードＮ７”であれば、ノードＮ７”の接続レコードの隣接更新領域情報が示す更新領域はＢで、更新領域Ｂの地図情報のバージョンは１であるため、ステップＳＴ２８へ行くこととなる。
【０１８６】
次に、ステップＳＴ２８において、接続元ノードが属する１次区画地図情報の１次区画地図情報ヘッダを参照して、ステップＳＴ２２で取得した接続レコードにおける隣接２次区画ノード情報の隣接更新領域情報が示す更新領域の２次区画地図情報の所在を求め、その位置にある２次区画地図情報を隣接２次区画地図情報に指定する。すなわち、本ステップにより、例えば、接続元ノードがノードＮ７”である場合、ノードＮ７”の接続レコードの隣接更新領域情報が示す更新領域はＢで、接続元ノードが属する１次区画のメッシュ座標は（２，３）であるので、２次区画（２，３）−Ｂの２次区画地図情報が隣接２次区画地図情報に指定される。
【０１８７】
次に、ステップＳＴ２９において、ステップＳＴ２２で取得した接続レコードにおける隣接２次区画ノード情報の隣接２次区画内のノード指示情報が示すノードレコード番号に対応するノードレコードを、ステップＳＴ２８で指定した隣接２次区画地図情報の道路データから取得し、ここに接続先ノードが得られたとして処理を終了する。すなわち、本ステップにより、例えば、接続元ノードＮ７”に対し、２次区画（３，３）−Ｂの２次区画地図情報のノードＮ７’が接続先ノードとなる。
【０１８８】
以上の処理において、ノードレコードが固定長であり、隣接２次区画内のノード指示情報をノードレコード番号としているため、隣接２次区画内のノード指示情報は、ノードレコードの格納位置を表し、直ちにノードレコードを取得できる。
【０１８９】
次に、ステップＳＴ３０において、接続元ノードが属する２次区画地図情報の１次区画地図情報ヘッダを参照して、ステップＳＴ２２で取得した接続レコードにおける隣接２次区画ノード情報の隣接更新領域情報が示す更新領域の２次区画地図情報の所在を求め、その位置にある２次区画地図情報の更新領域境界ノードの中から接続先ノードとして相応しいノードを見つけて、処理を終了する。
【０１９０】
以上のように、地図情報が更新領域を単位として更新された倍における接続元ノードに対する接続先ノードの決定処理において、接続先ノードが１次区画境界ノードであるとき、または接続元ノードが更新領域境界ノードで、隣接する２次区画同士のバージョンが一致するとき、隣接２次区画ノード情報により接続先ノードを取得するので、その処理時間を短縮することができる。
【０１９１】
図３１は、図３０におけるステップＳＴ３０の接続先ノード検索の処理を詳細に示すためのフローチャートである。
【０１９２】
ステップＳＴ４０において、接続元ノードが属する２次区画地図情報の１次区画地図情報ヘッダを参照して、ステップＳＴ２２で取得した接続レコードにおける隣接２次区画ノード情報の隣接更新領域情報が示す更新領域の２次区画地図情報の所在を求め、その位置にある２次区画地図情報を隣接２次区画地図情報に指定する。すなわち、本ステップにより、例えば、接続元ノードがノードＮ２”のとき、ノードＮ２”の接続レコードの隣接更新領域情報が示す更新領域はＡで、接続元ノードが属する１次区画のメッシュ座標は（２，３）であるので、２次区画（２，３）−Ａの２次区画地図情報が隣接２次区画地図情報に指定される。なお、上記隣接２次区画地図情報は、更新されていないので、図１４に示された道路データを保持し、この道路データは図１２の２次区画（２，３）−Ａの道路網を表している。
【０１９３】
次に、ステップＳＴ４１において、ステップＳＴ４０で指定された隣接２次区画地図情報における道路データのノード情報からノードレコードを取得する。ノードレコードは、ステップＳＴ４１に来る度にノード情報の先頭から順に１つずつ取得する。すなわち、本ステップにより、例えば、接続元ノードがノードＮ２”のとき、図１４に示されたノード情報からノードレコード＃０、ノードレコード＃１、ノードレコード＃２、ノードレコード＃３、及びノードレコード＃４が、その並びの順に取得される。なお、上記ノードレコードに対応するノードを検索ノードと呼ぶものとする。
【０１９４】
次に、ステップＳＴ４２において、ステップＳＴ４１で取得したノードレコードのノード種別情報が更新領域境界ノードである場合には、ステップＳＴ４３へ行き、更新領域境界ノードでない場合は、ステップＳＴ４６へ行く。すなわち、本ステップにより、例えば、接続元ノードがノードＮ２”のとき、図１２に示された２次区画（２，３）−Ａにおいて、ノードＮ２’及びノードＮ１０”は更新領域境界ノードであるのでステップＳＴ４３へ行き、これら以外のノードの場合はステップＳＴ４６へ行く。
【０１９５】
次に、ステップＳＴ４３において、ステップＳＴ４１で取得したノードレコードの接続レコードオフセットが示す接続レコードを取得する。すなわち、本ステップで検索ノードの接続レコードが得られる。
【０１９６】
次に、ステップＳＴ４４において、接続元ノードが属する２次区画地図情報の更新領域と検索ノードの接続レコードにおける隣接２次区画ノード情報の隣接更新領域情報が示す更新領域とを比較し、更新領域が同一のときはステップＳＴ４５へ行き、更新領域が異なるときはステップＳＴ４６へ行く。すなわち、本ステップにより、例えば、接続元ノードがノードＮ２”のとき、ノードＮ２”が属する更新領域はＣであり、検索ノードがノードＮ２’であれば、検索ノードの接続レコードの隣接更新領域情報は更新領域Ｃを示すのでステップＳＴ４５へ行き、検索ノードがノードＮ１０”であれば、検索ノードの接続レコードの隣接更新領域情報は更新領域Ｂを示すのでステップＳＴ４６へ行く。
【０１９７】
次に、ステップＳＴ４５において、ステップＳＴ２１で取得した接続元ノードのノードレコードのノード座標と、検索ノードのノード座標の離隔距離を求め、離隔距離が所定値以下のときは、ノード座標が一致していると判定し、検索ノードを接続先ノードとする。その上で、ステップＳＴ４１で取得したノードレコードを接続先ノードのノードレコードとして処理を終了する。また、上記離隔距離が所定値を超えるときは、ノード座標が不一致と判定し、ステップＳＴ４６へ行く。すなわち、本ステップにより、例えば、接続元ノードがノードＮ２”のとき、ノードＮ２”と検索ノードＮ２’の離隔距離が所定範囲にあれば、ノードＮ２’を接続先ノードと判定し、そのノードレコードが接続先ノードのノードレコードとなる。
【０１９８】
ところで、隣接する２次区画の地図情報のバージョンが同じであれば、接続元ノードと接続先ノードのノード座標は完全に一致するが、バージョンが異なれば、計測誤差等によりノード座標は異なることが起こり得るため、本ステップのように計測誤差等による不一致の程度を考慮し、所定値以下の離隔距離を許容することにより、接続先ノードをより正確に検出することができる。
【０１９９】
次に、ステップＳＴ４６において、ステップＳＴ４１で取得したノードレコードが、ノード情報の最後のノードレコードであるか否かを確認し、最後のノードレコードであるときは、接続先ノードに該当するノードが存在しないとして処理を終了する。最後のノードレコードでないときは、ステップＳＴ４１へ戻り上記処理を繰り返す。
【０２００】
実施の形態２．
実施の形態２は、実施の形態１における更新領域境界ノードの接続レコードに、当該更新領域境界ノードが最初に設けられたバージョンを示す境界ノードバージョン情報を設け、また、実施の形態１における図３１に示された処理フローを図３３に示された処理フローに置き換えたものである。
【０２０１】
図３２は、実施の形態２の更新領域境界ノードに対する接続レコードのデータ構成例である。なお、更新領域境界ノード以外のノードに対する接続レコードのデータ構成は実施の形態１と同じである。
【０２０２】
図３３は、図３１のフローチャートにステップＳＴ５０、ステップＳＴ５１、及びステップＳＴ５２を追加したもので、ステップＳＴ５０とステップＳＴ５１以外は実施の形態１と同様の処理を行う。
【０２０３】
ステップＳＴ５０において、ステップＳＴ２２で取得した接続レコードから当該接続元ノードの境界ノードバージョン情報を取得する。
【０２０４】
次に、ステップＳＴ５１において、ステップＳＴ５０で取得した当該接続元ノードの境界ノードバージョン情報が表すバージョンと、ステップＳＴ２７で取得した隣接２次区画のバージョンとを比較し、当該接続元ノードの境界ノードバージョン情報が表すバージョンが新しいときは、隣接２次区画に接続先ノードが存在しないとして処理を終了する。また、バージョンが新しくないときは、ステップＳＴ４０へ行く。すなわち、接続元ノードが最初に設けられたバージョンが隣接２次区画のバージョンより新しければ、上記隣接２次区画の作成時点よりも後に設けられているため、接続先ノードは上記隣接２次区画には存在しないことが判定でき、本ステップにより、ステップＳＴ４０以降の処理を行わずに接続先ノードが存在しないことが判定でき、処理時間を短縮できる。
【０２０５】
さらに、ステップＳＴ５２において、ステップＳＴ５０で取得した接続元ノードの境界ノードバージョン情報が表すバージョンが、ステップＳＴ４３で取得した検索ノードの接続レコードが保持する境界ノードバージョン情報が表すバージョンより新しくないときは、ステップＳＴ４５へ行き、新しいときは、ステップＳＴ４１で得た検索ノードは接続先ノードではないとしてステップＳＴ４６へ行く。
【０２０６】
接続元ノードが最初に設けられたバージョンが検索ノードが最初に設けられたバージョンより新しいときは、検索ノードは接続元ノードより以前から存在している接続先ノードでは有り得ず、この検索ノードに対しステップＳＴ４５の処理を行わないので、処理時間を短縮することができる。
【０２０７】
実施の形態３．
実施の形態３は、更新領域境界ノードが近接して複数存在する場合でも接続先ノードを正確に決定するようにしたもので、実施の形態２における図３３のフローチャートで表された処理フローを図３４のフローチャートで表された処理フローに置き換えたものである。
【０２０８】
図３４は、図３３のフローチャートで表された処理フローにステップＳＴ６０からステップＳＴ６４までの処理ステップを追加したものである。
【０２０９】
ステップＳＴ６０においては、接続元ノードが属する２次区画地図情報における道路データのノード情報を検索し、接続元ノードから所定距離以内に位置する更新領域境界ノードである近傍境界ノードを求め、それらのノードの数、ノードレコード番号、及びノード座標を例えばプロセッサ５の主記憶メモリに保持する。
【０２１０】
また、ステップＳＴ４５において、離隔距離が所定値以下の場合は、検索ノードが接続先ノードであると判定して、ステップＳＴ６１において、検索ノードのノードレコード番号及びノード座標をプロセッサ５の主記憶メモリに保持する。また、上記保持した検索ノードの数をプロセッサ５の主記憶メモリに保持する。すなわち、本ステップにより、接続元ノードの近傍に存在する隣接２次区画の更新領域境界ノードである隣接近傍境界ノードがプロセッサ５の主記憶メモリに保持される。
【０２１１】
次に、ステップＳＴ６２において、接続元ノードとステップＳＴ６０で得られた各近傍境界ノードとの位置関係を求める。すなわち、Ｎ個の近傍境界ノードが得られたとき、各近傍境界ノードｉに対し、接続元ノードに対する近傍境界ノードｉのノード座標の変位を示すベクトルＶｉを求め、位置関係ベクトル列ＲＳとして｛Ｖ１，Ｖ２，・・・，ＶＮ｝を得る。
【０２１２】
図３５は、近傍境界ノードと隣接近傍境界ノードの例である。ノードＮａ２を接続元ノードとし、その近傍にある更新単位領域境界ノードをＮａ１及びＮａ３とする。ノードＮａ１’、Ｎａ２’、及びＮａ３’は隣接近傍境界ノードで、それぞれノードＮａ１、Ｎａ２、及びＮａ３が表す地理的実体と同じ地理的実体を表しているが、更新されたことにり、それらのノード座標が誤差の範囲で移動している。
【０２１３】
図３６は、接続元ノードに対する近傍境界ノードの変位を示すベクトルの例である。図３６において、ノードＮａ１、Ｎａ２、及びＮａ３は、図３４に示されたノードＮａ１、Ｎａ２、及びＮａ３と同一である。また、ベクトルＶ１は、接続元ノードＮａ２に対するノードＮａ１のノード座標の変位を示し、ベクトルＶ２は、接続元ノードノードＮａ２に対するノードＮａ３のノード座標の変位を示す。従って、図３６において、位置関係ベクトル列ＲＳとして｛Ｖ１，Ｖ２｝が得られる。
【０２１４】
次に、ステップＳＴ６３において、ステップＳＴ６２で得られた各隣接近傍境界ノードについて、他の隣接近傍境界ノードとの位置関係を求める。すなわち、Ｎ＋１個の隣接近傍境界ノードが得られたとき、各隣接近傍境界ノードｊに対する他の隣接近傍境界ノードｋのノード座標の変位を示すベクトルＵｊｋ（ｋ≠ｊ）を求め、次のようなＮ個の位置関係ベクトル列を得る。
【０２１５】
隣接近傍境界ノード１の位置関係ベクトル列ＲＤ１：
｛Ｕ１２，Ｕ１３，Ｕ１４，・・・，Ｕ１Ｎ｝
隣接近傍境界ノード２の位置関係ベクトル列ＲＤ２：
｛Ｕ２１，Ｕ２３，Ｕ２４，・・・，Ｕ２Ｎ｝
隣接近傍境界ノード３の位置関係ベクトル列ＲＤ３：
｛Ｕ３１，Ｕ３２，Ｕ３４，・・・，Ｕ３Ｎ｝
・・・（中途省略）・・・
隣接近傍境界ノードＮの位置関係ベクトル列ＲＤＮ：
｛ＵＮ１，ＵＮ２，ＵＮ３，・・・，ＵＮＮ−１｝
【０２１６】
図３７は、隣接近傍境界ノード間の変位を示すベクトルの例である。図３７において、ノードＮａ１’、Ｎａ２’、及びＮａ３’は図３５に示された隣接近傍境界ノードである。また、ベクトルＵａは、ノードＮａ１’に対するノードＮａ２’のノード座標の変位を示し、ベクトルＵｂは、接続元ノードノードＮａ２’に対するノードＮａ３’のノード座標の変位示し、ベクトルＵｃは、接続元ノードノードＮａ３’に対するノードＮａ１’のノード座標の変位示す。
【０２１７】
図３６において、下記位置関係ベクトル列が得られる。
【０２１８】
ノードＮａ１’の位置関係ベクトル列ＲＤ１：
｛Ｕ１２＝  Ｕａ，Ｕ１３＝−Ｕｃ｝
ノードＮａ２’の位置関係ベクトル列ＲＤ２：
｛Ｕ２１＝−Ｕａ，Ｕ２３＝  Ｕｂ｝
ノードＮａ３’の位置関係ベクトル列ＲＤ３：
｛Ｕ３１＝  Ｕｃ，Ｕ３２＝−Ｕｂ｝
【０２１９】
次に、ステップＳＴ６４において、ステップＳＴ６３で得た位置関係ベクトル列ＲＤ１〜ＲＤＮの中から、位置関係ベクトル列を構成するすべてのベクトルが、ステップＳＴ６２で得た位置関係ベクトル列ＲＳを構成するすべてのベクトルに誤差による差異を除き一致する位置関係ベクトル列を見つけ、その隣接近傍境界ノードを接続先ノードに決定し、そのノードレコードを取得して処理を終了する。
【０２２０】
図３５、図３６、及び図３７において、誤差を考慮し、Ｖ１と−Ｕａは同等で、Ｖ２とＵｂは同等とみなし、位置関係ベクトル列ＲＳを｛−Ｕａ，Ｕｂ｝とし、位置関係ベクトル列ＲＤ１，ＲＤ２，ＲＤ３の中から、ベクトル−Ｕａ，Ｕｂから構成される位置関係ベクトル列を見つける。その結果、位置関係ベクトル列ＲＤ２が見つかり、ノードＮａ２’を接続先ノードと決定する。
【０２２１】
以上のように、近傍境界ノードの位置関係と隣接近傍境界ノードの位置関係とから決定するようにしたので、更新領域境界ノードが近接して複数存在する場合でも接続先ノードを正確に決定することができる。
【０２２２】
実施の形態４．
実施の形態４は、実施の形態３において、ステップＳＴ６４で決定された接続先ノードに接続するリンクのリンク属性と、接続元ノードに接続するリンクのリンク属性を求め、それらのリンク属性を比較し、リンク属性が一致した場合はステップＳＴ６４で決定された接続先ノードを接続ノードと判定し、リンク属性が一致しない場合は接続先ノードが存在しないと判定したものである。
【０２２３】
上記リンク属性として、一方通行規制など、道路が更新単位領域を跨いでも変化しないリンク属性を用いる。なお、上記リンク属性は、接続先ノード又はの接続元ノードのノードレコードよりその接続レコードを求め、その接続レコードの接続リンクレコード番号が示すリンクレコードより求める。
【０２２４】
道路が更新単位領域を跨いでも変化しないリンク属性を用いて、接続元ノードに接続するリンクと接続先ノードに接続するリンクとの整合性を確認しているので、より正確に接続先ノードを決定できる。
【０２２５】
実施の形態１において、同一階層における１次区画はすべて同じ大きさとしたが、地図情報のデータサイズが所定値を超える１次区画では、更に小さな１次区画に分割してもよい。
【０２２６】
また、隣接する更新領域の組毎に、更新領域境界ノードのノードレコードを連続して並べてもよく、更に上記連続して並べたノードレコードを隣接する更新領域の組に関連付けて管理してもよい。
【０２２７】
さらに、実施の形態３において、近傍境界ノード及び隣接近傍境界ノードを、接続元ノードが最初に設けられたバージョンと同一バージョンのノードに限定してもよい。
【０２２８】
また、上記実施の形態１乃至実施の形態４において、作成範囲が経線及び緯線により囲まれた矩形領域であるとみなして説明したが、高緯度の地域のように、矩形領域とみなせない場合においても、本願発明に係る技術的思想は適用可能で、同様の効果を奏する。その場合は、作成範囲は例えば曲線の経線及び曲線の緯線により囲まれた２次元の平面領域ないしは３次元の曲面領域となる点だけが相違する。
【符号の説明】
【０２２９】
１  入力部
２  位置検出部
３  更新情報取得部
４  地図情報記憶部
５  プロセッサ
６  出力部
５１  地図情報処理手段
５２  更新手段
【図１】
2010237256.tif 000003
【図２】
2010237256.tif 000004
【図３】
2010237256.tif 000005
【図４】
2010237256.tif 000006
【図５】
2010237256.tif 000007
【図６】
2010237256.tif 000008
【図７】
2010237256.tif 000009
【図８】
2010237256.tif 000010
【図９】
2010237256.tif 000011
【図１０】
2010237256.tif 000012
【図１１】
2010237256.tif 000013
【図１２】
2010237256.tif 000014
【図１３】
2010237256.tif 000015
【図１４】
2010237256.tif 000016
【図１５】
2010237256.tif 000017
【図１６】
2010237256.tif 000018
【図１７】
2010237256.tif 000019
【図１８】
2010237256.tif 000020
【図１９】
2010237256.tif 000021
【図２０】
2010237256.tif 000022
【図２１】
2010237256.tif 000023
【図２２】
2010237256.tif 000024
【図２３】
2010237256.tif 000025
【図２４】
2010237256.tif 000026
【図２５】
2010237256.tif 000027
【図２６】
2010237256.tif 000028
【図２７】
2010237256.tif 000029
【図２８】
2010237256.tif 000030
【図２９】
2010237256.tif 000031
【図３０】
2010237256.tif 000032
【図３１】
2010237256.tif 000033
【図３２】
2010237256.tif 000034
【図３３】
2010237256.tif 000035
【図３４】
2010237256.tif 000036
【図３５】
2010237256.tif 000037
【図３６】
2010237256.tif 000038
【図３７】
2010237256.tif 000039