(57)【要約】【課題】版数の異なる道路網データ間の整合性を保ちつつ、道路網データの更新を容易にする。【解決手段】内部ノードに対応して設けるデータの並びの後に上記境界ノードに対応して設けるデータの並びを配置するようにし、上記各ノードにノード情報における対応するデータの並び順に基づいて定めたノード番号を付与し、上記ノード番号を用いて上記内部ノードおよび境界ノードを特定するようにし、上記境界ノードに対応したデータの並びの先頭を示すノード番号を基準にしたノード番号の相対値である相対境界ノード番号を上記境界ノードに付与し、上記相対境界ノード番号用いて上記隣接境界ノードを特定するようにした。【選択図】        図１０
2004212456.tif 000002
【特許請求の範囲】
【請求項１】
地図情報処理装置において処理される道路網データのデータ構造であって、
道路網を複数の領域に分割し、隣接し合う道路網を接続するに際し、隣接する道路網から接続相手として指し示される当該道路網のノードを境界ノードと定義し、当該道路網が接続相手として指し示す隣接する道路網のノードを隣接境界ノードと定義し、当該道路網の境界ノード以外のノードを内部ノードと定義して、上記道路網データが表す道路網を構成する各ノードに対応して設けるデータの並びであるノード情報を設け、上記内部ノードに対応して設けるデータの並びの後に上記境界ノードに対応して設けるデータの並びを配置するようにし、上記各ノードにノード情報における対応するデータの並び順に基づいて定めたノード番号を付与し、上記ノード番号を用いて上記内部ノードおよび境界ノードを特定するようにし、上記境界ノードに対応したデータの並びの先頭を示すノード番号を基準にしたノード番号の相対値である相対境界ノード番号を上記境界ノードに付与し、上記相対境界ノード番号用いて上記隣接境界ノードを特定するようにしたことを特徴とする道路網データのデータ構造。
【請求項２】
請求項１に記載のデータ構造を有する既存の道路網データを、道路網の更新に対応してコンピュータを用いて更新する方法であって、
上記道路網の更新により新設する内部ノードに対して、上記道路網の更新により不要となった内部ノードのノード番号または上記道路網の更新前までにおける内部ノードに付与されたノード番号と異なるノード番号を付与する手順と、
上記道路網の更新により新設する境界ノードに対して、上記道路網の更新前までにおける境界ノードに付与された相対境界ノード番号と異なる相対境界ノード番号を付与する手順とを備えたことを特徴とする道路網データの更新方法。
【請求項３】
請求項１に記載のデータ構造を有する各領域の道路網データが格納された地図情報記憶部と、請求項１に記載のデータ構造を有する各領域の道路網データを請求項２に記載の道路網データの更新方法によって地図情報処理装置に更新させるための道路網データ更新指示情報が格納された更新指示情報記憶部と、上記道路網データまたは道路網データ更新指示情報を送信する送信部とを備えたことを特徴とする地図情報提供装置。
【請求項４】
請求項１に記載のデータ構造を有する道路網データが格納された地図情報記憶部と、上記地図情報記憶部に格納された道路網データを請求項２に記載の道路網データの更新方法によって地図情報処理装置に更新させるための道路網データ更新指示情報を受信するまたは上記請求項１に記載のデータ構造を有する道路網データを受信する受信部と、上記道路網データ更新指示情報に従って上記道路網データを更新する更新処理部とを備え、上記受信部は、上記地図情報記憶部が所要領域の道路網データを保有している場合には当該所要領域の上記道路網データ更新指示情報を受信し、上記地図情報記憶部が所要領域の道路網データを保有していない場合には当該所要領域の道路網データを受信することを特徴とする地図情報処理装置。
【請求項５】
地図情報処理装置において処理される道路網データのデータ構造であって、
道路網を複数の領域に分割し、隣接し合う道路網を接続するに際し、隣接する道路網から接続相手として指し示される当該道路網のノードを境界ノードと定義し、当該道路網が接続相手として指し示す隣接する道路網のノードを隣接境界ノードと定義し、当該道路網の境界ノード以外のノードを内部ノードと定義して、
上記道路網データが表す道路網の上記内部ノードに対応して設けるデータの並びである内部ノード情報と、上記道路網データが表す道路網の上記境界ノードに対応して設けるデータの並びである境界ノード情報とを設け、
上記各内部ノードに、内部ノード情報における対応するデータの並び順に基づいて定めた内部ノード番号を付与し、上記各境界ノードに、境界ノード情報における対応するデータの並び順に基づいて定めた境界ノード番号を付与し、上記内部ノード番号を用いて上記内部ノードを特定するようにし、境界ノード番号を用いて上記境界ノードと隣接境界ノードを特定するようにしたことを特徴とする道路網データのデータ構造。
【請求項６】
請求項５に記載のデータ構造を有する既存の道路網データを、道路網の更新に対応してコンピュータを用いて更新する方法であって、
上記道路網の更新により新設する内部ノードに対して、上記道路網の更新により不要となった内部ノードの内部ノード番号または上記道路網の更新前までにおける内部ノードに付与された内部ノード番号と異なる内部ノード番号を付与する手順と、
上記道路網の更新により新設する境界ノードに対して、上記道路網の更新前までにおける境界ノードに付与された境界ノード番号と異なる境界ノード番号を付与する手順とを備えたことを特徴とする道路網データの更新方法。
【請求項７】
請求項５に記載のデータ構造を有する各領域の道路網データが格納された地図情報記憶部と、請求項５に記載のデータ構造を有する各領域の道路網データを請求項６に記載の道路網データの更新方法によって地図情報処理装置に更新させるための道路網データ更新指示情報が格納された更新指示情報記憶部と、上記道路網データまたは道路網データ更新指示情報を送信する送信部とを備えたことを特徴とする地図情報提供装置。
【請求項８】
請求項５に記載のデータ構造を有する道路網データが格納された地図情報記憶部と、上記地図情報記憶部に格納された道路網データを請求項６に記載の道路網データの更新方法によって地図情報処理装置に更新させるための道路網データ更新指示情報を受信するまたは上記請求項５に記載のデータ構造を有する道路網データを受信する受信部と、上記道路網データ更新指示情報に従って上記道路網データを更新する更新処理部とを備え、上記受信部は、上記地図情報記憶部が所要領域の道路網データを保有している場合には当該所要領域の上記道路網データ更新指示情報を受信し、上記地図情報記憶部が所要領域の道路網データを保有していない場合には当該所要領域の道路網データを受信することを特徴とする地図情報処理装置。
【請求項９】
地図情報処理装置において処理される道路網データのデータ構造であって、
道路網を複数の領域に分割し、隣接し合う道路網を接続するに際し、隣接する道路網から接続相手として指し示される当該道路網のノードを境界ノードと定義し、当該道路網が接続相手として指し示す隣接する道路網のノードを隣接境界ノードと定義し、当該道路網の境界ノード以外のノードを内部ノードと定義して、
上記道路網データが表す道路網を構成する各ノードに対応して設けるデータの並びであるノード情報を設け、上記境界ノードに対応して設けるデータの並びの後に上記内部ノードに対応して設けるデータの並びを配置するようにし、上記各ノードにノード情報における対応するデータの並び順に基づいて定めたノード番号を付与し、上記ノード番号を用いて上記境界ノードおよび隣接境界ノードを特定するようにし、上記内部ノードに対応したデータの並びの先頭を示すノード番号を基準にしたノード番号の相対値である相対内部ノード番号を上記内部ノードに付与し、上記相対内部ノード番号用いて上記内部ノードを特定するようにしたことを特徴とする道路網データのデータ構造。
【請求項１０】
請求項９に記載のデータ構造を有する既存の道路網データを、道路網の更新に対応してコンピュータを用いて更新する方法であって、
上記道路網の更新により新設する境界ノードに対して、上記道路網の更新前までにおける境界ノードに付与されたノード番号と異なるノード番号を付与する手順と、
上記道路網の更新により新設する内部ノードに対して、上記道路網の更新により不要となった内部ノードの相対内部ノード番号または上記道路網の更新前までにおける内部ノードに付与された相対内部ノード番号と異なる相対内部ノード番号を付与する手順とを備えたことを特徴とする道路網データの更新方法。
【請求項１１】
請求項９に記載のデータ構造を有する各領域の道路網データが格納された地図情報記憶部と、請求項９に記載のデータ構造を有する各領域の道路網データを請求項１０に記載の道路網データの更新方法によって地図情報処理装置に更新させるための道路網データ更新指示情報が格納された更新指示情報記憶部と、上記道路網データまたは道路網データ更新指示情報を送信する送信部とを備えたことを特徴とする地図情報提供装置。
【請求項１２】
請求項９に記載のデータ構造を有する道路網データが格納された地図情報記憶部と、上記地図情報記憶部に格納された道路網データを請求項１０に記載の道路網データの更新方法によって地図情報処理装置に更新させるための道路網データ更新指示情報を受信するまたは上記請求項９に記載のデータ構造を有する道路網データを受信する受信部と、上記道路網データ更新指示情報に従って上記道路網データを更新する更新処理部とを備え、上記受信部は、上記地図情報記憶部が所要領域の道路網データを保有している場合には当該所要領域の上記道路網データ更新指示情報を受信し、上記地図情報記憶部が所要領域の道路網データを保有していない場合には当該所要領域の道路網データを受信することを特徴とする地図情報処理装置。
【請求項１３】
請求項１、５および９の何れかに記載のデータ構造を有する道路網データが格納された地図情報記憶部と、上記道路網データを送信する送信部とを備えた地図情報提供装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、カーナビゲーション装置、携帯電話、携帯情報端末等の移動体または固定されたコンピュータ端末で使用される道路網データのデータ構造、道路網データの更新方法、地図情報提供装置、および地図情報処理装置に関するものである。
【０００２】
【従来の技術】
カーナビゲーション装置では、出発地から目的地への経路計算（経路探索）を行い、その結果得られた好適な経路の候補を道路地図と共に表示装置の画面に提示する。これに類似した機能は、携帯電話、携帯情報端末等の他の移動体、または固定されたコンピュータ端末でも行われている。
【０００３】
従来の交通ネットワーク経路探索方法においては、交通ネットワークがメッシュ状に分断され、なおかつ異なる時期に作成されたデータが混在し、前記データを用いて出発地点から目的地点までの経路を、地点をノード、地点間をリンクとして交通ネットワークを表現し、コンピュータを用いてラベル確定法によりコストとして移動時間または移動距離などを用いて、最短コスト条件下で探索する交通ネットワーク経路探索方法において、メッシュに分割された交通ネットワークデータは、特定の地点に対応するノード、そのノードとノードを結ぶ線は地点間の経路であるリンクで表現され、メッシュの境界をリンクが越える場合は、メッシュ区画辺上にノードを設定し、前記区画辺上のノードについては作成時期に係わらず先頭から一定の番号を優先的に付与する条件下で各メッシュ毎にノードに番号を付与し、前記区画辺上のノードについては隣接するメッシュにおける該区画辺上のノードに付与されている番号である隣接メッシュ接合データを有し、ラベル確定法による経路探索処理によって、最小ポテンシャルを探索しながら仮ラベルと永久レベルをメッシュ番号とノードとで設定し、仮ラベルを永久ラベルに変更したノードが区画辺上のノードのときは、該ノードの隣接メッシュ接合ノードデータが示すノードについて再度、経路探索処理を行っている（例えば、特許文献１参照）。また、メッシュファイルのヘッダー情報にメッシュデータの作成年月日等を登録しておき、利用者の所有するメッシュの作成年月日等を比較し、異なるときにのみ取り寄せている。
【０００４】
【特許文献１】
特開２００１−１６５６８１号公報（第１−６頁、第５−９図）
【０００５】
【発明が解決しようとする課題】
このような従来の交通ネットワーク経路探索方法にあっては、道路の新設、廃止、地図情報の充足等に伴い、現在の版の道路網データに対してノード、リンクの追加、削除を指示する更新指示情報に基づいて現在の版の道路網データを新しい版に更新する場合に、ノードの追加、削除によりメッシュ内部のノード（内部ノード）のノード番号が変化するため、現在の版の道路網データ内にあるノード番号を参照しているデータ（例えばリンクの接続ノード）を更新後のノード番号を参照するように変更する処理が必要となるという問題点があった。
また、すで取得しているメッシュの道路網データを最新の版にするのに、そのメッシュの最新の版の道路網データそのものを地図情報提供装置から取得するようにしているため、最新の版の道路網データ取得のための通信時間が長くなるという問題があった。
【０００６】
本発明は、版数の異なる道路網データ間の整合性を保ちつつ、道路網データの更新を容易にすることを第１の目的としている。
また、すで取得している所要領域（メッシュ）の道路網データを最新の版にするのに、最新の版にするための情報を取得するのに要する通信時間を短縮することを第２の目的としている。
【０００７】
【課題を解決するための手段】
本発明に係る道路網データのデータ構造は、道路網を複数の領域に分割し、隣接し合う道路網を接続するに際し、隣接する道路網から接続相手として指し示される当該道路網のノードを境界ノードと定義し、当該道路網が接続相手として指し示す隣接する道路網のノードを隣接境界ノードと定義し、当該道路網の境界ノード以外のノードを内部ノードと定義して、上記道路網データが表す道路網を構成する各ノードに対応して設けるデータの並びであるノード情報を設け、上記内部ノードに対応して設けるデータの並びの後に上記境界ノードに対応して設けるデータの並びを配置するようにし、上記各ノードにノード情報における対応するデータの並び順に基づいて定めたノード番号を付与し、上記ノード番号を用いて上記内部ノードおよび境界ノードを特定するようにし、上記境界ノードに対応したデータの並びの先頭を示すノード番号を基準にしたノード番号の相対値である相対境界ノード番号を上記境界ノードに付与し、上記相対境界ノード番号用いて上記隣接境界ノードを特定するようにしたものである。
【０００８】
また、本発明に係る道路網データの更新方法は、道路網の更新により新設する内部ノードに対して、上記道路網の更新により不要となった内部ノードのノード番号または上記道路網の更新前までにおける内部ノードに付与されたノード番号と異なるノード番号を付与する手順と、上記道路網の更新により新設する境界ノードに対して、上記道路網の更新前までにおける境界ノードに付与された相対境界ノード番号と異なる相対境界ノード番号を付与する手順とを備えたものである。
【０００９】
また、本発明の別の発明に係る道路網データのデータ構造は、道路網を複数の領域に分割し、隣接し合う道路網を接続するに際し、隣接する道路網から接続相手として指し示される当該道路網のノードを境界ノードと定義し、当該道路網が接続相手として指し示す隣接する道路網のノードを隣接境界ノードと定義し、当該道路網の境界ノード以外のノードを内部ノードと定義して、上記道路網データが表す道路網の上記内部ノードに対応して設けるデータの並びである内部ノード情報と、上記道路網データが表す道路網の上記境界ノードに対応して設けるデータの並びである境界ノード情報とを設け、上記各内部ノードに、内部ノード情報における対応するデータの並び順に基づいて定めた内部ノード番号を付与し、上記各境界ノードに、境界ノード情報における対応するデータの並び順に基づいて定めた境界ノード番号を付与し、上記内部ノード番号を用いて上記内部ノードを特定するようにし、境界ノード番号を用いて上記境界ノードと隣接境界ノードを特定するようにしたものである。
【００１０】
また、本発明の別の発明に係る道路網データの更新方法は、道路網の更新により新設する内部ノードに対して、上記道路網の更新により不要となった内部ノードの内部ノード番号または上記道路網の更新前までにおける内部ノードに付与された内部ノード番号と異なる内部ノード番号を付与する手順と、上記道路網の更新により新設する境界ノードに対して、上記道路網の更新前までにおける境界ノードに付与された境界ノード番号と異なる境界ノード番号を付与する手順とを備えたものである。
【００１１】
また、本発明のさらに別の発明に係る道路網データのデータ構造は、道路網を複数の領域に分割し、隣接し合う道路網を接続するに際し、隣接する道路網から接続相手として指し示される当該道路網のノードを境界ノードと定義し、当該道路網が接続相手として指し示す隣接する道路網のノードを隣接境界ノードと定義し、当該道路網の境界ノード以外のノードを内部ノードと定義して、上記道路網データが表す道路網を構成する各ノードに対応して設けるデータの並びであるノード情報を設け、上記境界ノードに対応して設けるデータの並びの後に上記内部ノードに対応して設けるデータの並びを配置するようにし、上記各ノードにノード情報における対応するデータの並び順に基づいて定めたノード番号を付与し、上記ノード番号を用いて上記境界ノードおよび隣接境界ノードを特定するようにし、上記内部ノードに対応したデータの並びの先頭を示すノード番号を基準にしたノード番号の相対値である相対内部ノード番号を上記内部ノードに付与し、上記相対内部ノード番号用いて上記内部ノードを特定するようにしたものである。
【００１２】
また、本発明の別の発明に係る道路網データの更新方法は、道路網の更新により新設する境界ノードに対して、上記道路網の更新前までにおける境界ノードに付与されたノード番号と異なるノード番号を付与する手順と、上記道路網の更新により新設する内部ノードに対して、上記道路網の更新により不要となった内部ノードの相対内部ノード番号または上記道路網の更新前までにおける内部ノードに付与された相対内部ノード番号と異なる相対内部ノード番号を付与する手順とを備えたものである。
【００１３】
また、本発明に係る地図情報提供装置は、上記のようなデータ構造を有する各領域の道路網データが格納された地図情報記憶部と、上記のようなデータ構造を有する各領域の道路網データを上記のような道路網データの更新方法によって地図情報処理装置に更新させるための道路網データ更新指示情報が格納された更新指示情報記憶部と、上記道路網データまたは道路網データ更新指示情報を送信する送信部とを備えたものである。
【００１４】
また、本発明に係る地図情報処理装置は、上記のようなデータ構造を有する道路網データ格納された地図情報記憶部と、上記地図情報記憶部に格納された道路網データを上記のような道路網データの更新方法によって地図情報処理装置に更新させるための道路網データ更新指示情報または道路網データを受信する受信部と、上記道路網データ更新指示情報に従って上記道路網データを更新する更新処理部とを備え、上記受信部は、上記地図情報記憶部が所要領域の道路網データを保有している場合には当該所要領域の上記道路網データ更新指示情報を受信し、上記地図情報記憶部が所要領域の道路網データを保有していない場合には当該所要領域の道路網データを受信するものである。
【００１５】
【発明の実施の形態】
実施の形態１．
図１は、この発明を実施するための実施の形態１による地図情報更新システムの構成を示すブロック図である。図１に示すように、この地図情報更新システムは、地図情報提供装置ａ２と、複数の地図情報処理装置ａ１を備える。各地図情報処理装置ａ１は、例えば、自動車に搭載されたカーナビゲーション装置である。地図情報提供装置ａ２は、通信網を介して各地図情報処理装置ａ１とリンクされ得るようになっており、地図情報、または各地図情報処理装置ａ１が有する地図情報の更新のための更新指示情報を、リンク時に各地図情報処理装置ａ１に提供することができる。
【００１６】
図２は、図１に示された地図情報処理装置ａ１の構成を示すブロック図である。図２に示すように、地図情報処理装置ａ１は、入力装置１、位置検出装置２、送受信装置３、地図情報記憶装置４、プロセッサ５、および出力装置６を備える。
入力装置１は、使用者の操作または指示に従ってプロセッサ５に指示信号を与える。具体的には、図示しないが、入力装置１は使用者の音声を認識して音声に基づく指示信号を出力する音声認識装置、使用者の手動操作により指示信号を出力するボタン、その他の適切な入力装置の少なくともいずれかを有していてよい。
位置検出装置２は、例えばＧＰＳ（Global Positioning System)受信機等により構成され、現在位置を検出し、検出した位置情報をプロセッサ５に供給する。
送受信装置３は、通信網を介して、地図情報提供装置ａ２との間で地図情報、更新指示情報に関するデータの送受信を行う。送受信装置３は道路網データ更新指示情報を受信するまたは道路網データを受信する受信部に相当する。
地図情報記憶装置４は、例えばハードディスクドライブ等で構成され、地図情報が格納されている。
プロセッサ５は、送受信装置３で受信した更新指示情報にしたがった地図情報記憶装置４の地図情報の更新、または送受信装置３で受信した地図情報の地図情報記憶装置４への格納を行う。さらにプロセッサ５は、位置検出装置２から得られた現在位置と地図情報記憶装置４から読み出した地図情報を用いて、各種のナビゲーション処理を行う。ナビゲーション処理としては、車両が走行している道路および道路上の位置を同定するマップマッチング、出発値から目的地までの経路を算出する経路計算（経路探索）、その結果得られた好適な経路の候補を道路地図と共に表示装置の画面に表示する経路表示、好適な経路に従って出発値から目的地までの案内を行う経路誘導、および現在位置周辺の地図の表示処理等が含まれる。
出力装置６は、プロセッサ５のナビゲーション処理出力に従って、使用者に情報を提示する。具体的には、図示しないが、出力装置６は、地図、現在位置、経路、案内情報等を表示する表示装置、および使用者に音声で指示または案内を行う音声発生装置を有していてよい。
【００１７】
図３は、図１に示された地図情報提供装置ａ２の構成を示すブロック図である。地図情報提供装置ａ２は、送受信装置１０、地図情報データベース（地図情報記憶部）１１、更新指示情報データベース（更新指示情報記憶部）１２および情報配信装置１３を備える。
送受信装置１０は通信網を介してリンクされた各地図情報処理装置ａ１の送受信装置３から信号を受信し、各地図情報処理装置ａ１の送受信装置３に個別に信号を送信する機能を有する。
地図情報データベース１１には、各領域の初版から最新の版までの各地図情報が蓄積されている。
更新指示情報データベース１２には、各領域の各版の地図情報を最新の版の地図情報に更新するための更新指示情報が格納されている。
情報配信装置１３は、地図情報処理装置ａ１の要求に応じ、地図情報データベース１１の所要の地図情報または更新指示情報データベース１２の所要の更新指示情報を取得し、送受信装置１０を介して、地図情報処理装置ａ１へ上記取得した地図情報または更新指示情報を提供する。
送受信装置１０および情報配信装置１３が、道路網データまたは道路網データ更新指示情報を送信する送信部に相当する。
【００１８】
以下、本発明の実施の形態１による道路網データのデータ構造について説明する。
図４は地図情報データベース１１および地図情報記憶装置４に格納された地図情報の概略データ構造を示す。地図情報として、管理情報、複数の表示系データ、複数の経路計算系データ、案内検索データおよびその他の種類のデータを有している。
表示系データおよび経路計算系データは、全国を幾つかの領域に分割したときの、各領域に対応して設けられている。表示系データおよび経路計算系データには、対応する領域を示す地図を出力装置６に表示させるための情報が格納されている。
【００１９】
案内検索データは、例えば、目的地のデータ（住所、建物の電話番号等）と、目的地と領域の関連性を示す情報を有しており、使用者が指定した目的地に従って必要な領域の表示系データおよび経路計算系データを選定するために使用される。
管理情報は、表示系データ、経路計算系データ、案内検索データ等を管理するデータであり、当該地図情報として格納されている各領域の表示系データ、経路計算系データの領域、版数、所在等を管理する情報、案内検索情報等の当該地図情報における所在を管理する情報等を有している。
【００２０】
図４に示すように、各表示系データは、マップマッチング（現在位置に基づいた道路の特定および道路上の位置の同定）や道路の表示に使用する道路形状を表す情報を有する道路網データ、河川、海等の地図背景を表示するための背景データ、地名等の名称を文字で表示するための名称データ、経路誘導のための経路誘導データ、周辺施設を検索するための周辺施設データ等を有する。また、各表示系データは表示系データヘッダを有しており、表示系データヘッダは、当該表示系データフレームが対応する領域を表す情報等を含む表示系データに関する各種属性、この表示系データに含まれる各データの所在を管理する情報等を有する。
【００２１】
また、経路計算系データは、経路計算系データヘッダ、経路計算のための道路網データ等を有する。経路計算系データヘッダは、当該経路計算系データフレームが対応する領域を表す情報等を含む経路計算系データに関する各種属性、この経路計算系データに含まれる道路網データの所在等を管理する情報等を有する。
【００２２】
道路網データは、交差点、道路の端点等をノードとし、ノード間を結ぶ道路をリンクとしたグラフにより道路網を表したものである。
以下では、経路計算系データの道路網データを用いて説明するが、表示系データの道路網データに適用してもよい。
【００２３】
図５は、２つの領域Ａ，Ｂにまたがる道路の例であり、横方向の道路Ｒ０、Ｒ１およびＲ２に縦方向の道路Ｒ３およびＲ４が交差し、道路Ｒ１とＲ２に斜め方向の道路Ｒ５が交差している。
【００２４】
図６は、図５の道路を領域ＡとＢとに分割したときに、表示系データの作成にあたって、図５の道路Ｒ０〜Ｒ５の接続関係を示すため、すなわち道路Ｒ０〜Ｒ５を領域Ａの道路網ＧＡおよび領域Ｂの道路網ＧＢとしてデータに表現するために仮想的に割り振られるノード、リンクの一例を示す図である。各道路網は、道路Ｒ０、Ｒ１、Ｒ２、Ｒ３、Ｒ４、Ｒ５の交差点には、ノードＮＡ２、ＮＡ３、ＮＡ４、ＮＡ５、ＮＢ３、ＮＢ４、ＮＢ５が割り振られ、道路Ｒ０、Ｒ１、Ｒ２の端点にはノードＮＡ０、ＮＡ１、ＮＢ０、ＮＢ１、ＮＢ２が割り振られ、道路Ｒ０、Ｒ１、Ｒ２と領域Ａ、Ｂの境界との交点にはノードＮＡ６、ＮＡ７、ＮＡ８、ＮＢ６、ＮＢ７、ＮＢ８が割り振られている。
隣接する二つのノードを結ぶ道路部分には、リンクＬＡ０、ＬＡ１、・・・、ＬＡ８、ＬＢ０、ＬＢ１、・・・、Ｌ７が割り振られる。
【００２５】
隣接し合う道路網ＧＡとＧＢとを接続するために、ノードＮＡ６とＮＢ６、ノードＮＡ７とＮＢ７、ノードＮＡ８とＮＢ８をそれぞれ接続する必要がある。このため、後述するように道路網ＧＡのノードＮＡ６、ＮＡ７、ＮＡ８には、それぞれ道路網ＧＢのノードＮＢ６、ＮＢ７、ＮＢ８が接続することを指し示す情報を付与し、道路網ＧＢのノードＮＢ６、ＮＢ７、ＮＢ８には、それぞれ道路網ＧＡのノードＮＡ６、ＮＡ７、ＮＡ８が接続することを指し示す情報を付与する。
【００２６】
本発明では、隣接し合う道路網を接続するに際し、隣接する道路網から接続相手として指し示される当該道路網のノードを境界ノードと定義し、当該道路網が接続相手として指し示す隣接する道路網のノードを隣接境界ノードと定義することとする。また、当該道路網の境界ノード以外のノードを内部ノードと定義することとする。
例えば、図６においては、ノードＮＡ６、ＮＡ７、ＮＡ８が道路網ＧＡの境界ノードに該当し、ノードＮＢ６、ＮＢ７、ＮＢ８が道路網ＧＢの境界ノードに該当する。また、ノードＮＢ６、ＮＢ７、ＮＢ８は道路網ＧＡの隣接境界ノードに該当し、ノードＮＡ６、ＮＡ７、ＮＡ８は道路網ＧＢの隣接境界ノードに該当する。このとき、ノードＮＢ６をノードＮＡ６の隣接境界ノードと定義し、ノードＮＡ６をノードＮＢ６の隣接境界ノードと定義する。ノードＮＢ７とＮＡ７、ノードＮＢ８とＮＡ８についても同様である。
また、ノードＮＡ０、ＮＡ１、ＮＡ２、ＮＡ３、ＮＡ４、ＮＡ５が道路網ＧＡの内部ノードに該当し、ノードＮＢ０、ＮＢ１、ＮＢ２、ＮＢ３、ＮＢ４、ＮＢ５が道路網ＧＢの内部ノードに該当する。
【００２７】
図７は、図５の道路を領域ＡとＢとに分割したときに、表示系データの作成にあたって、図５の道路Ｒ０〜Ｒ５の接続関係を示すため、すなわち道路Ｒ０〜Ｒ５を領域Ａの道路網ＧＡ’および領域Ｂの道路網ＧＢ’としてデータに表現するために仮想的に割り振られるノード、リンクの別の例を示す図である。この例は、図６の道路網のように道路と領域の境界との交点にノードを設けないようにしたものである。道路網ＧＡ’では領域Ａ、ＢにまたがるリンクＬＡ３、ＬＡ４、ＬＡ５を、道路網ＧＢ’では領域にまたがるリンクＬＢ３、ＬＢ４、ＬＢ５を設け、ノードＮＡ３に接続するリンクＬＡ３が道路網ＧＢ’のノードＮＢ３に接続するようし、ノードＮＢ３に接続するリンクＬＢ３が道路網ＧＡ’のノードＮＡ３に接続するようしている。また、リンクＬＡ４、ＬＡ５、ＬＢ４、ＬＢ５についても同様にしている。
【００２８】
後に詳細に説明するが、図７の例では、ノードＮＡ３、ＮＡ４、ＮＡ５が道路網ＧＡ’の境界ノードに該当し、ノードＮＢ３、ＮＢ４、ＮＢ５が道路網ＧＢ’の境界ノードに該当する。また、ノードＮＢ３、ＮＢ４、ＮＢ５は道路網ＧＡ’の隣接境界ノードに該当し、ノードＮＡ３、ＮＡ４、ＮＡ５は道路網ＧＢ’の隣接境界ノードに該当する。このとき、ノードＮＢ３をノードＮＡ３の隣接境界ノードと定義し、ノードＮＡ３をノードＮＢ３の隣接境界ノードと定義する。ノードＮＢ４とＮＡ４、ノードＮＢ５とＮＡ５についても同様である。
また、ノードＮＡ０、ＮＡ１、ＮＡ２が道路網ＧＡ’の内部ノードに該当し、ノードＮＢ０、ＮＢ１、ＮＢ２が道路網ＧＢ’の内部ノードに該当する。
【００２９】
図８は、図５の道路を領域ＡとＢとに分割したときに、表示系データの作成にあたって、図５の道路Ｒ０〜Ｒ５の接続関係を示すため、すなわち道路Ｒ０〜Ｒ５を領域Ａの道路網ＧＡ”および領域Ｂの道路網ＧＢ”としてデータに表現するために仮想的に割り振られるノード、リンクの別の例を示す図である。この例は、図６の道路網と同様に、道路と領域の境界との交点にノードを設け、道路網ＧＡ”では領域Ａの境界上のノードＮＡ６、ＮＡ７、ＮＡ８から領域Ｂの内部にあるノードＮＢ３、ＮＢ４、ＮＢ５へ接続するリンクＬＢ３’、ＬＢ４’、ＬＢ５’を、道路網ＧＢ”では領域Ｂの境界上のノードＮＢ６、ＮＢ７、ＮＢ８から領域Ａの内部にあるノードＮＡ３、ＮＡ４、ＮＡ５へ接続するリンクＬＡ３’、ＬＡ４’、ＬＡ５’を設けている。
【００３０】
図８の例では、ノードＮＡ３、ＮＡ４、ＮＡ５が道路網ＧＡ”の境界ノードに該当し、ノードＮＢ３、ＮＢ４、ＮＢ５が道路網ＧＢ”の境界ノードに該当する。また、ノードＮＢ３、ＮＢ４、ＮＢ５は道路網ＧＡ”の隣接境界ノードに該当し、ノードＮＡ３、ＮＡ４、ＮＡ５は道路網ＧＢ”の隣接境界ノードに該当する。
また、ノードＮＡ０、ＮＡ１、ＮＡ２、ＮＡ６、ＮＡ７、ＮＡ８が道路網ＧＡ”の内部ノードに該当し、ノードＮＢ０、ＮＢ１、ＮＢ２、ＮＢ６、ＮＢ７、ＮＢ８が道路網ＧＢ”の内部ノードに該当する。
【００３１】
以下では、主に図６の道路網を例に説明する。
【００３２】
図９は、図６の道路網ＧＡ、ＧＢが更新された後の道路網の例を示しており、道路網ＧＡ１は図６の道路網ＧＡのリンクＬＡ１、ＬＡ４と、ノードＮＡ１、ＮＡ７とが削除され、リンクＬＡ９、ＬＡ１０、ＬＡ１１、ＬＡ１２と、ノードＮＡ９、ＮＡ１０、ＮＡ１１、ＮＡ１２とが新設された道路網であり、道路網ＧＢ１は図６の道路網ＧＢのリンクＬＢ４とノードＮＢ７とが削除され、リンクＬＢ８とノードＮＢ９とが新設された道路網である。尚、新設されたノードのうち、ノードＮＡ１２は道路網ＧＡの境界ノード、ノードＮＢ９は道路網ＧＢの境界ノードであり、ノードＮＢ９はノードＮＡ１２の隣接境界ノード、ノードＮＡ９はノードＮＢ１２の隣接境界ノードである。また、ノードＮＡ９、ＮＡ１０、ＮＡ１１は道路網ＧＡの内部ノードである。
【００３３】
図１０は、図６の道路網ＧＡを表す版数が１の道路網データのデータ構造の一例を示す図である。道路網データは道路網データヘッダ、ノード情報、リンク情報からなる。
【００３４】
道路網データヘッダは、ノード情報の当該道路網データにおける格納位置、ノード情報のデータサイズ、収容しているノードレコードの数等を示すノード管理情報、リンク情報の当該道路網データにおける格納位置、リンク情報のデータサイズ、収容しているリンクレコードの数等を示すリンク管理情報、当該道路網データにおける境界ノードのノード番号の最小値を示す先頭境界ノード番号等を有する。
【００３５】
ノード情報は、各ノードに対応して設けられたノードレコードの並びであり、ノードＮＡ０，ＮＡ１，・・・，ＮＡ８に対してそれぞれノードレコードＮＲＡ０，ＮＲＡ１，・・・，ＮＲＡ８が設けられる。各ノードを識別するためにノード毎にノード番号を付与する。図１０の例では、各ノードに対応するノードレコードの並び順をノード番号として付与しており、ノードＮＡ０，ＮＡ１，・・・，ＮＡ８のノード番号はそれぞれ０，１，・・・，８である。
【００３６】
ノード情報において、内部ノードのノードレコードＮＲＡ０，ＮＲＡ１，・・・，ＮＲＡ５を境界ノードのノードレコードより前に配置し、境界ノードのノードレコードＮＲＡ６，ＮＲＡ７，ＮＲＡ８を内部ノードのノードレコードより後に配置しており、内部ノードＮＡ０，ＮＡ１，・・・，ＮＡ５にはノード番号０〜５が付与され、境界ノードＮＡ６，ＮＡ７，ＮＡ８にはノード番号６，７，８が付与される。
【００３７】
境界ノードに付与されたノード番号の最小値（先頭境界ノード番号）を基準にしたノード番号の相対値を相対境界ノード番号と定義する。境界ノードの相対境界ノード番号は境界ノードのノード番号から当該道路網データヘッダにある先頭境界ノード番号を減ずるこにより求めることができる。例えば、境界ノードＮＡ６，ＮＡ７，ＮＡ８の相対境界ノード番号はそれぞれ０，１，２である。
【００３８】
リンク情報は、各リンクに対応して設けられたリンクレコードの並びであり、リンクＬＡ０，ＬＡ１，・・・，ＬＡ８に対してそれぞれリンクレコードＬＲＡ０，ＬＲＡ１，・・・，ＬＲＡ８が設けられる。各リンクを識別するためにリンク毎にリンク番号を付与する。図１０の例では、各リンクに対応するリンクレコードの並び順をリンク番号として付与しており、リンクＬＡ０，ＬＡ１，・・・，ＬＡ８のリンク番号はそれぞれ０，１，・・・，８である。
【００３９】
ノードレコードは、当該ノード（当該ノードレコードに対応するノード）に関わる各種情報を有するものであり、当該ノードレコードのデータサイズ、ノード座標、接続リンク情報、隣接領域情報、隣接境界相対ノード番号等を有する。図１０では、接続リンク情報、隣接領域情報、隣接境界相対ノード番号を図示しており、データサイズ、ノード座標等は図示を省略している。
ノード座標は、当該ノードの地理的位置を示す。
リンク情報は、当該ノードに接続するリンクの数およびリンク番号を示す。図１０では、接続リンク数をＣＮで示し、接続リンク番号をＣＬｎ（ｎ＝０，１，・・・）で示している。
隣接領域情報および隣接境界相対ノード番号は、当該ノードが境界ノードである時に存在する。
隣接領域情報は、当該境界ノードの隣接境界ノードが存在する領域を示し、図１０では、ＡＩＤで示している。
隣接境界相対ノード番号は、当該境界ノードの隣接境界ノードの上記隣接する領域における相対境界ノード番号を示し、図１０では、ＣＡで示している。
【００４０】
上記のように、ノードレコードは、内部ノードのノードレコードを境界ノードのノードレコードより前に配置し、境界ノードのノードレコードを内部ノードのノードレコードより後に配置している。従って境界ノードには、内部ノードのノード番号より大きな値のノード番号が付与される。
また、上記のように隣接境界ノードは境界ノードのノード番号の最小値に応じて定められたノード番号を基準にしたノード番号の相対値である相対境界ノード番号を用いて指定される。
道路網データが上記のようなデータ構造を有することにより、下記に示すように道路網の更新の前後で同一の内部ノードのノード番号が変化したり、同一の境界ノードの相対境界ノード番号が変化したりするのを防止することを可能とし、道路網データの更新を容易にすることを可能とし、版数の異なる道路網データ間の整合性を保つことを可能とする。
【００４１】
リンクレコードは、当該リンク（当該リンクレコードに対応するリンク）に関わる各種情報を有するものであり、当該リンクレコードのデータサイズ、始点ノード番号、終点ノード番号、通行規制情報、コスト情報、形状情報等を有している。図１０では、データサイズ、通行規制情報、コスト情報、形状情報等は図示を省略しており、始点ノード番号をＳＮ、終点ノード番号をＥＮで示している。始点ノード番号は当該リンクの両端のノードのうち一方のノードのノード番号を示し、終点ノード番号は他方のノードのノード番号を示す。例えばリンクレコードＬＲＡ０において、始点ノード番号は０で、終点ノード番号は３である。尚、始点ノード番号が示すノードを始点ノード、終点ノード番号が示すノードを終点ノードと定義する。
通行規制情報は、当該リンクの通行に関して設定された通行規制を示す。コスト情報は当該リンクの通行に要する所要時間等のコストを示す。
形状情報は当該リンクの道路形状を表す情報で、経路計算により得られた経路を表示するときに使用される。
【００４２】
図１１は、図１０の場合と同様にして設けられた図６の道路網ＧＢを表す版数が１の道路網データのデータ構造の一例を示す図である。図１１において、ノードレコードＮＲＢｎ（ｎ＝０，１，・・・，８）は図６のノードＮＢｎ（ｎ＝０，１，・・・，８）に対応し、リンクレコードＬＲＢｍ（ｍ＝０，１，・・・，８）は図６のリンクＬＢｍ（ｍ＝０，１，・・・，７）に対応している。
【００４３】
道路網データは、図１０、１１に示したようなデータ構造となっており、ノードレコードを参照することによりノードに接続するリンクが得られ、そのリンクのリンクレコードを参照するにより上記ノードから到達できるノード、通行規制、到達するために要するコスト等が得られる。例えば、図１０のノードレコードＮＲＡ３により、ノードＮＡ３に接続する、リンク番号が３，６，０である３本のリンクＬＡ３、ＬＡ６、ＬＡ０が得られ、リンクＬＡ３のリンクレコードＬＲＡ３の終点ノード番号により、ノードＮＡ３からリンクＬＡ３を通って到達できるノード番号が６のノードＮＡ６が得られる。
また、境界ノードのノードレコードを参照することにより隣接境界ノードが得られ、隣接領域のノードに到達できる。例えば、図１０のノードレコードＮＲＡ６により、境界ノードＮＡ６の隣接境界ノードとして領域Ｂの相対境界ノード番号が０である境界ノードＮＢ６が得られ、領域Ａの境界ノードＮＡ６から領域Ｂの境界ノードＮＢ６へ到達できる。
このように、上記道路網データを用いて任意のノードから到達可能なノード、ノードからノードに至るのに要するコストおよび通行規制が得られ、上記道路網データを用いて、例えばダイクストラ法などにより、通行規制を加味した、コストが最小となる、出発地ノードから目的地ノードへ至る経路を求めることができる。
【００４４】
図１２は、図９の道路網ＧＡ１を表す版数が２の道路網データのデータ構造の一例を示す図である。
図１２のノード情報は、図１０の削除されたノードＮＡ１に対応するノードレコードＮＲＡ１を、図９の新設された内部ノードＮＡ９に対応するノードレコードＮＲＡ９に置き換え、図９の新設された内部ノードＮＡ１０、ＮＡ１１に対応するノードレコードＮＲＡ１０、ＮＲＡ１１を図１０のノード情報の内部ノードに対応するノードレコードの後に挿入し、図９の新設された境界ノードＮＡ１２のノードレコードＮＲＡ１２を図１０のノード情報の境界ノードに対応するノードレコードの後に追加して得られたものである。
【００４５】
上記により、新設された内部ノードＮＡ９には不要となったノードＮＡ１のノード番号１が付与され、新設された内部ノードＮＡ１０、ＮＡ１１には、道路網が図９に更新されるまでに内部ノードに付与されていたノード番号０〜５よりも大きなノード番号である６，７が付与される。
即ち、上記新設された内部ノードには、不要となった内部ノードのノード番号または当該道路網が更新されるまでに付与された内部ノードのノード番号と異なるノード番号が付与される。
【００４６】
また、道路網が図９のように更新されるまでにすでに存在している境界ノードＮＡ６、ＮＡ７、ＮＡ８のノード番号は８，９，１０、上記境界ノードの相対境界ノード番号は０，１，２となり、上記境界ノードのノード番号は変化するが、相対境界ノード番号は変化しない。
上記により新設された境界ノードＮＡ１２には、道路網が図９のように更新されるまでに境界ノードに付与されていた相対境界ノード番号０，１，２よりも大きな相対境界ノード番号である３が付与される。
即ち、上記のように新設された境界ノードには、当該道路網が変化するまでに付与された相対番号とは異なる相対境界ノード番号が付与される。
【００４７】
上記のように、道路網が変化しても境界ノードの相対境界ノード番号は変化しないために、隣接する領域の道路網データで版数が異なっていても、上記領域の道路網間の接続に不整合を生じない。例えば、図６の道路網ＧＢのノードＮＢ８の隣接境界相対境界ノード番号は、図１１の道路網データに示すように２であり、図１０の道路網データの相対境界ノード番号が２の境界ノードはＮＡ８である。また、図１０の道路網データを更新して得られた図１２の道路網データにおいても、相対境界ノード番号が２の境界ノードはＮＡ８である。従って、領域Ａの道路網の更新前と更新後とのいずれに対しても、図６の道路網ＧＢのノードＮＢ８の隣接境界ノードＮＡ８を正しく求めることができる。
【００４８】
尚、図１２のノード情報において、下記で示すリンクおよびそのリンクレコードの削除、追加に伴い、接続リンク数、接続リンク番号、隣接領域情報、隣接境界相対ノード番号が変化するため、道路網が図９に更新されるまでに存在していたノードのノードレコードの接続リンク数、接続リンク番号、隣接接続情報、隣接境界相対ノード番号が上記更新に応じて変更されている。例えば、ノードレコードＮＲＡ４の接続リンク数（ＣＮ）は５から３に、接続リンク番号（ＣＬｎ）は６，４，７，８，１から４，５，６に変更されている。また、削除された境界ノードのノードレコード（例えばＮＲＡ７）の接続リンク数（ＣＮ）は０とし、隣接領域情報（ＡＩＤ）、隣接境界相対ノード番号（ＣＡ）には該当するものがないことを示す所定の値（図１２の例ではＮＵＬＬ）を格納している。
【００４９】
図１２のリンク情報は、削除された図６のリンクＬＡ１，ＬＡ４に対応する図１０のリンクレコードＬＲＡ１，ＬＲＡ４を削除し、新設された図９のリンクＬＡ９，ＬＡ１０，ＬＡ１１，ＬＡ１２に対応するリンクレコードＬＲＡ９，ＬＲＡ１０，ＬＲＡ１１，ＬＲＡ１２を図１０のリンク情報の末尾に追加して得られたものである。
【００５０】
図１２のリンク情報において、道路網が図９に更新されるまでに存在していたリンクに対応するリンクレコードのうち、始点ノード番号または終点ノード番号が境界ノードを示しているものは、上記内部ノードの新設による境界ノードのノード番号の変化に応じ、始点ノード番号または終点ノード番号が変更される。例えば、リンクレコードＬＲＡ３，ＬＲＡ５の終点ノード番号は、図１０ではそれぞれ６，８であるが、図１２ではそれぞれ８，１０に変更されている（図１２では変更箇所が分かり易いようにＥＮ＝８とＥＮ＝１０に下線を施して示している。）。
また、図１２のリンク情報において、道路網が図９に更新されるまでに存在していたリンクに対応するリンクレコードのうち、始点ノード番号または終点ノード番号が内部ノードを示しているものは、道路網の変化によって内部ノードのノード番号は変化しないため、始点ノード番号または終点ノード番号の変更を必要としない。例えば、道路網が図６から図９に更新されても、リンクレコードＬＲＡ０の始点ノード番号、終点ノード番号は０，３のままである。
【００５１】
このように、それまでに存在していた内部ノードのノード番号が変化しないため、リンクレコードの更新においては、リンクレコードの始点ノード番号または終点ノード番号の変更は、境界ノードに関してのみ行えばよく、内部ノードについては不要である。
【００５２】
図１２の道路網データヘッダは上記更新に合わせて変更される。
【００５３】
図示しないが、図９の道路網ＧＢ１を表す版数が２の道路網データも図１２の場合と同様に図１１を更新して得られる。
【００５４】
上記道路網データでは、道路網が変化してもそれまでに存在していた境界ノードの相対境界ノード番号は変化しないために、隣接する領域の道路網データ間で版数が異なっていても、上記領域の道路網間の接続に不整合を生じない。
また、従来の道路網データでは、道路網の更新によるノードの新設、削除に伴う道路網データの更新において、境界ノードのノード番号を不変とし内部ノードのノード番号が変化するデータ構造となっている。ところが、境界ノードに比し内部ノードの数は非常に多いため、内部ノードに該当するリンクレコードの始点ノード番号または終点ノード番号を多数変更する必要があり、更新処理の負荷が重くなる。
これに対して、本実施の形態１では、道路網の更新によるノードの新設、削除に伴う道路網データの更新において、それまでに存在していた内部ノードのノード番号が変化しないため、リンクレコードの始点ノード番号または終点ノード番号の変更は境界ノードに関するものだけでよく、従来に比し上記変更処理の負荷をはるかに軽減でき、道路網データの更新が容易になる。
【００５５】
上記では、図６で示した道路網を例に説明したが、以下では、図７および図８でそれぞれ示した道路網の場合について説明する。
【００５６】
図１３は、図７の道路網ＧＡ’を表す道路網データのデータ構造の一例を示す図である。以下では、主に図１０と異なる点について説明する。
道路網ＧＡ’のノードＮＡ０，ＮＡ１，・・・，ＮＡ５に対してそれぞれノードレコードＮＲＡ０，ＮＲＡ１，・・・，ＮＲＡ５を設け、道路網ＧＡ’のリンクＬＡ０，ＬＡ１，・・・，ＬＡ８に対してそれぞれリンクレコードＬＲＡ０，ＬＲＡ１，・・・，ＬＲＡ８を設けている。
ノードレコードは、対応するノードに接続するリンク数を示す接続リンク数（ＣＮ）、対応するノードに接続するリンクのリンク番号を示す接続リンク番号（ＣＬｎ）を有する。
リンクレコードは、対応するリンクの始点ノード、終点ノードを示す始点ノード情報（ＳＮＩ）、終点ノード情報（ＥＮＩ）を有し、例えばＳＮＩ＝ＮＡ０というように、ノード番号だけでなくノードの存在する領域の情報も併記している。リンクレコードＬＲＡ３、ＬＲＡ４、ＬＲＡ５はリンクＬＡ３、ＬＡ４、ＬＡ５に隣接する道路網ＧＢ’のノードＮＢ３、ＮＢ４、ＮＢ５が接続することを示している。
【００５７】
図７の道路網ＧＢ’を表す道路網データも同様に設けられる。
【００５８】
上記のように隣接し合う道路網ＧＡ’とＧＢ’とを接続するために、道路網ＧＡ’のリンクＬＡ３、ＬＡ４、ＬＡ５のそれぞれに道路網ＧＢ’のノードＮＢ３、ＮＢ４、ＮＢ５が接続することを指し示す情報を付与し、また、道路網ＧＢ’のリンクＬＢ３、ＬＢ４、ＬＢ５のそれぞれに道路網ＧＡ’のノードＮＡ３、ＮＡ４、ＮＡ５が接続することを指し示す情報を付与している。
このように、道路網ＧＡ’のノードＮＡ３、ＮＡ４、ＮＡ５は、隣接する道路網ＧＢ’から接続相手として指し示されるノード、即ち道路網ＧＡ’の境界ノードであり、道路網ＧＢ’のノードＮＢ３、ＮＢ４、ＮＢ５は、道路網ＧＡ’が接続相手として指し示す隣接する道路網ＧＢ’のノード、即ち道路網ＧＡ’の隣接境界ノードである。同様に、道路網ＧＢ’の境界ノードはＮＢ３、ＮＢ４、ＮＢ５であり、道路網ＧＢ’の隣接境界ノードは道路網ＧＡ’のノードＮＡ３、ＮＡ４、ＮＡ５である。また、道路網ＧＡ’の内部ノードは境界ノードでないノードＮＡ０、ＮＡ１、ＮＡ２であり、道路網ＧＢ’の内部ノードは境界ノードでないノードＮＢ０、ＮＢ１、ＮＢ２である。
【００５９】
図１３においても図１０の場合と同様に、内部ノードに対応して設けるデータの並びの後に境界ノードに対応して設けるデータの並びを配置するようにし、各ノードにノード情報における対応するデータの並び順に基づいて定めたノード番号を付与し、ノード番号を用いて各ノードを特定するようにし、境界ノードに対応したデータの並びの先頭を示すノード番号を基準にしたノード番号の相対値である相対境界ノード番号を境界ノードに付与し、相対境界ノード番号用いて隣接境界ノードを特定するようにしており、図１０の場合と同様に、道路網の更新の前後で同一の内部ノードのノード番号が変化したり、同一の境界ノードの相対境界ノード番号が変化したりするのを防止することを可能とし、道路網データの更新を容易にすることを可能とし、版数の異なる道路網データ間の整合性を保つことを可能とするという効果が得られる。
【００６０】
さらに、図１２の場合と同様に、道路網の更新により新設する内部ノードに対して、道路網の更新により不要となった内部ノードのノード番号または道路網の更新前までにおける内部ノードに付与されていないノード番号を付与するようにし、道路網の更新に更新前までにおける境界ノードに付与された相対境界ノード番号と異なる相対境界ノード番号を付与するようにすることにより、図１２の場合と同様に、道路網の更新よるノードの新設、削除に伴う道路網データ更新において、内部ノードのノード番号が変化しないため、リンクレコードの始点ノード番号または終点ノード番号の変更は境界ノードに関するものだけでよく、従来に比し変更処理の負荷をはるかに軽減でき、道路網データの更新が容易になるという効果が得られる。
【００６１】
図１４は図８の道路網ＧＡ”を表す道路網データのデータ構造の一例を示す図である。以下では、主に図１０と異なる点について説明する。
道路網ＧＡ”のノードＮＡ０，ＮＡ１，・・・，ＮＡ８対してそれぞれノードレコードＮＲＡ０，ＮＲＡ１，・・・，ＮＲＡ８を設け、道路網ＧＡ”のリンクＬＡ０，ＬＡ１，・・・，ＬＡ８に対してそれぞれリンクレコードＬＲＡ０，ＬＲＡ１，・・・，ＬＲＡ８を設け、道路網ＧＡ”のリンクＬＢ３’、ＬＢ４’、ＬＢ５’に対してそれぞれリンクレコードＬＲＢ３’、ＬＲＢ４’、ＬＲＢ５’を設けている。
ノードレコードは、対応するノードに接続するリンク数を示す接続リンク数（ＣＮ）、対応するノードに接続するリンクのリンク番号を示す接続リンク番号（ＣＬｎ）を有する。
リンクレコードは、対応するリンクの始点ノード、終点ノードを示す始点ノード情報（ＳＮＩ）、終点ノード情報（ＥＮＩ）を有し、例えばＳＮＩ＝ＮＡ０というように、ノード番号だけでなくノードの存在する領域の情報も併記している。リンクレコードＬＲＢ３’、ＬＲＢ４’、ＬＲＢ５’はリンクＬＢ３’、ＬＢ４’、ＬＢ５’に道路網ＧＢ”のノードＮＢ３、ＮＢ４、ＮＢ５が接続することを示している。
【００６２】
図８の道路網ＧＢ”を表す道路網データも同様に設けられる。
【００６３】
上記のように隣接し合う道路網ＧＡ”とＧＢ”とを接続するために、道路網ＧＡ”のリンクＬＢ３’、ＬＢ４’、ＬＢ５’のそれぞれに道路網ＧＢ”のノードＮＢ３、ＮＢ４、ＮＢ５が接続することを指し示す情報を付与し、また、道路網ＧＢ”のリンクＬＡ３’、ＬＡ４’、ＬＡ５’のそれぞれに道路網ＧＡ”のノードＮＡ３、ＮＡ４、ＮＡ５が接続することを指し示す情報を付与している。
このように、道路網ＧＡ”のノードＮＡ３、ＮＡ４、ＮＡ５は、隣接する道路網ＧＢ”から接続相手として指し示されるノード、即ち道路網ＧＡ”の境界ノードであり、道路網ＧＢ”のノードＮＢ３、ＮＢ４、ＮＢ５は、道路網ＧＡ”が接続相手として指し示す隣接する道路網ＧＢ”のノード、即ち道路網ＧＡ”の隣接境界ノードである。同様に、道路網ＧＢ”の境界ノードはＮＢ３、ＮＢ４、ＮＢ５であり、道路網ＧＢ”の隣接境界ノードは道路網ＧＡ”のノードＮＡ３、ＮＡ４、ＮＡ５である。また、道路網ＧＡ”の内部ノードは境界ノードでないノードＮＡ０、ＮＡ１、ＮＡ２、ＮＡ６、ＮＡ７、ＮＡ８であり、道路網ＧＢ”の内部ノードは境界ノードでないノードＮＢ０、ＮＢ１、ＮＢ２、ＮＢ６、ＮＢ７、ＮＢ８である。
【００６４】
図１４においても図１０の場合と同様に、内部ノードに対応して設けるデータの並びの後に境界ノードに対応して設けるデータの並びを配置するようにし、各ノードにノード情報における対応するデータの並び順に基づいて定めたノード番号を付与し、ノード番号を用いて各ノードを特定するようにし、境界ノードに対応したデータの並びの先頭を示すノード番号を基準にしたノード番号の相対値である相対境界ノード番号を境界ノードに付与し、相対境界ノード番号用いて隣接境界ノードを特定するようにしており、図１０の場合と同様に、道路網の更新の前後で同一の内部ノードのノード番号が変化したり、同一の境界ノードの相対境界ノード番号が変化したりするのを防止することを可能とし、道路網データの更新を容易にすることを可能とし、版数の異なる道路網データ間の整合性を保つことを可能とするという効果が得られる。
【００６５】
さらに、図１２の場合と同様に、道路網の更新により新設する内部ノードに対して、道路網の更新により不要となった内部ノードのノード番号または道路網の更新前までにおける内部ノードに付与されていないノード番号を付与するようにし、道路網の更新に更新前までにおける境界ノードに付与された相対境界ノード番号と異なる相対境界ノード番号を付与するようにすることにより、図１２の場合と同様に、道路網の更新よるノードの新設、削除に伴う道路網データ更新において、内部ノードのノード番号が変化しないため、リンクレコードの始点ノード番号または終点ノード番号の変更は境界ノードに関するものだけでよく、従来に比し変更処理の負荷をはるかに軽減でき、道路網データの更新が容易になるという効果が得られる。
【００６６】
以下では、主に図６の道路網を例に説明するが、図７、図８に示す方法で分割された道路網であってもよい。
【００６７】
以下、図３に示した地図情報提供装置の動作について、図１５のフローチャートをもとに説明する。
地図情報データベース１１には、初版から最新の版までの各地図情報が蓄積されており、更新指示情報データベース１２には、各版の地図情報を最新版の地図情報に更新するための更新指示情報が蓄積されている。
【００６８】
地図情報提供装置が起動し、処理を開始すると、まず、ステップＳＴ１００では、図２に示した地図情報処理装置の送受信装置３から地図情報提供装置の送受信装置１０へ送信される要求情報が着信するのを待ち、着信すればステップＳＴ１０１へ進む。
【００６９】
ステップＳＴ１０１では、送受信装置１０より要求情報を取得する。この要求情報は、地図情報処理装置識別情報、データ識別情報、データ有無情報、保有版数情報を有している。
地図情報処理装置識別情報は、複数ある地図情報処理装置のうちの要求情報を発信した地図情報処理装置がどれであるかを示し、データ識別情報は要求情報を発信した地図情報処理装置における地図情報処理例えばナビゲーション処理で必要となる領域およびデータの種類を表し、データ有無情報は地図情報処理装置が上記データ識別情報で指定したデータを有しているか否かを示し、保有版数情報は地図情報処理装置が有する上記データ識別情報が示すデータの版数を示す。
【００７０】
ステップＳＴ１０２では、ステップＳＴ１０１で取得した要求情報のうちのデータ有無情報を調べ、データ有無情報がデータなしを示していればステップＳＴ１０３へ行き、データありを示していればステップＳＴ１０５へ行く。
【００７１】
ステップＳＴ１０３では、ステップＳＴ１０１で取得した要求情報のうちのデータ識別情報が指定するデータで最新版のものを地図情報データベース１１から取得する。例えば、現在の最新版の版数が１であり、上記データ識別情報が指定するデータが図５の領域Ａの経路計算系データであるとき、図１０の道路網データを含む経路計算系データを地図情報データベース１１から取得する。
【００７２】
ステップＳＴ１０４では、提供するデータが地図情報または地図情報の一部であることを示すようにした提供情報種別と、提供するデータの種類および領域を示すデータ識別情報と、ステップＳＴ１０３で取得したデータの版数を示す提供版数情報と、ステップＳＴ１０３で取得したデータとからなる提供情報を作成し、ステップＳＴ１０９へ行く。
【００７３】
ステップＳＴ１０５では、ステップＳＴ１０１で取得した要求情報のうちの保有版数情報の版数と、地図情報データベース１１に蓄積されている最新の地図情報の版数とを比較し、一致すれば要求情報を発信した地図情報処理装置がすでに最新の地図情報を保有しているとしてステップＳＴ１０８へ行き、一致しなければステップＳＴ１０６へ行く。
【００７４】
ステップＳＴ１０６では、ステップＳＴ１０１で取得した要求情報のうちのデータ識別情報が指定するデータを上記要求情報のうちの保有版数情報が示す版から最新版に更新するための更新指示情報を更新指示情報データベース１２から取得する。例えば、現在の最新版の版数が２であり、上記データ識別情報が指定するデータが図５の領域Ａの経路計算系データであり、上記の保有版数情報が示す版数が１であるとき、図１０の道路網データを含む経路計算系データを図１２の道路網データを含む経路計算系データに更新するための更新指示情報を更新指示情報データベース１２から取得する。
【００７５】
図１６は、上記更新指示情報に含まれる道路網データを更新するための道路網データ更新指示情報のデータ構造の一例を示す図であり、図１０の道路網データを図１２の道路網データに更新するための情報の一例を示している。
上記道路網データ更新指示情報は、当該道路網データ更新指示情報内の各種情報の所在等を管理する道路網データ更新指示情報ヘッダ、更新後の道路網データヘッダを示すヘッダ更新指示情報、削除する内部ノードを指示する内部ノード削除情報、リンク新設に伴いノードレコードに追加すべき接続リンク番号を示す接続リンク番号情報、新設する内部ノードを示す新設内部ノード情報、削除する境界ノードを示す削除境界ノード情報、新設する境界ノードを示す新設境界ノード情報、削除するリンクを示す削除リンク情報、新設するリンクを示す新設リンク情報を有している。
【００７６】
ヘッダ更新指示情報は、図１２の道路網データヘッダと同一内容のデータである。
削除内部ノード情報は、削除する内部ノードの数とノード番号を示し、図６の道路網ＧＡのノードＮＡ１を削除することを示している。
接続リンク番号情報は、ノードレコードＮＲＡ５に接続リンク番号９を追加することを示している。これはリンクＬＡ１１の新設に起因するものである。
新設内部ノード情報は、新設する内部ノードの数とノードレコードを示し、図６の道路網ＧＡに図９のノードＮＡ９、ＮＡ１０、ＮＡ１１を新設することを示している。
削除境界ノード情報は、削除する境界ノードの数と相対境界ノード番号を示し、図６の道路網ＧＡのノードＮＡ７を削除することを示している。
新設境界ノード情報は、新設する境界ノードの数とノードレコードを示し、図６の道路網ＧＡに図９の境界ノードＮＡ１２を新設することを示している。
削除リンク情報は、削除するリンクの数とリンク番号を示し、図６の道路網ＧＡのリンクＬＡ１、ＬＡ４を削除することを示している。
新設リンク情報は、新設するリンクの数とリンクレコードを示し、図６の道路網ＧＡに図９のリンクＬＡ９、ＬＡ１０、ＬＡ１１、ＬＡ１２を新設することを示している。
【００７７】
ステップＳＴ１０７では、提供するデータが更新指示情報であることを示すようにした提供情報種別と、提供するデータの種類および領域を示すデータ識別情報と、ステップＳＴ１０６で取得した更新指示情報による更新で得られる版数を示す更新版数情報と、ステップＳＴ１０６で取得した更新指示情報とからなる提供情報を作成する。
【００７８】
ステップＳＴ１０８では、提供するデータがないことを示すようにした提供情報種別からなる提供情報を作成する。
以上のステップＳＴ１０１〜ＳＴ１０８の処理は情報配信装置１３において行われる。
【００７９】
ステップＳＴ１０９では、ステップＳＴ１０４、ＳＴ１０７、ＳＴ１０８で作成された提供情報を、送受信装置１０により、要求情報を発信した地図情報処理装置へ送信する。
【００８０】
次にステップＳＴ１００へ戻り上記処理を繰り返す。
【００８１】
上記より、地図情報処理装置が所要領域の経路計算系データ（道路網データ）を保有していないときは、最新の経路計算系データ（道路網データ）を地図情報処理装置に提供し、地図情報処理装置が所要領域の経路計算系データ（道路網データ）を保有しているが最新の版の経路計算系データ（道路網データ）を保有していないときは、地図情報処理装置が保有している所要領域の経路計算系データ（道路網データ）を最新の版の経路計算系データ（道路網データ）に更新するための更新指示情報を提供することができ、地図情報処理装置が所要領域の経路計算系データ（道路網データ）を保有しているときは、最新の版の経路計算系データ（道路網データ）を提供する場合に比し地図情報処理装置と地図情報提供装置との通信時間を短縮することができる。
【００８２】
また、上記のステップＳＴ１０２、ＳＴ１０３、ＳＴ１０４、ＳＴ１０９により、例えば図１０〜図１２に示したようなデータ構造を有する道路網データ、即ち道路網の更新によって内部ノードのノード番号が変化せず更新が容易であり、境界ノードの相対境界ノード番号が変化せず版数の異なる道路網データ間の整合性を保つことが可能な道路網データを、地図情報処理装置に提供することができる。
【００８３】
以下、図２に示した地図情報処理装置におけるプロセッサ５の動作について、図１７のフローチャートをもとに、プロセッサ５の各種ナビゲーション処理のうちの、経路計算処理の例を説明する。
【００８４】
処理が開始されると、まず、ステップＳＴ２００では、本地図情報処理装置の利用者が入力装置１により入力した出発地と目的地を取得する。例えば、出発地として図５の道路Ｒ２の右端に対応する図６または図９のノードＮＢ２、目的地として図５の道路Ｒ０の左端に対応する図６または図９のノードＮＡ０を得る。以下では出発地、目的地が上記ノードＮＢ２、ノードＮＡ０であるものとして説明する。
【００８５】
ステップＳＴ２０１では、ステップＳＴ２００で取得した出発地と目的地から経路計算に必要な経路計算系データの領域を決定する。即ち、上記出発地のノードＮＢ２を含む領域Ｂ、上記目的地のノードＮＡ０を含む領域Ａを所要領域とする。
【００８６】
ステップＳＴ２０２では、本ステップに来る毎にステップＳＴ２０１で決定した所用領域から１つずつ選択し、選択できたら（選択未完了の場合）ステップＳＴ２０３へ行き、選択する領域がなくなったら（選択完了の場合）ステップＳＴ２１３へ行く。即ち、１回目、２回目に本ステップにきたときはそれぞれ領域Ａ、領域Ｂを選択してステップＳＴ２０３へ行き、３回目に本ステップにきたときは選択する領域がないためにステップＳＴ２１３へ行く。
【００８７】
ステップＳＴ２０３では、地図情報記憶装置４に格納されている地図情報にステップＳＴ２０２で選択した領域の経路計算系データがあるか否かを上記地図情報の管理情報により調べ、あればステップＳＴ２０７へ行き、なければステップＳＴ２０４へ行く。
【００８８】
ステップＳＴ２０４では、当該地図情報処理装置を示す地図情報処理装置識別情報と、ステップＳＴ２０２で選択した領域の経路計算系データを指定するデータ識別情報と、データなしを示すデータ有無情報と、版数を参照する必要が無いことを示すようにした保有版数情報とからなる要求情報を作成し、送受信装置３により地図情報提供装置へ送信する。
【００８９】
ステップＳＴ２０５では、ステップＳＴ２０４で送信した要求情報に応じて地図情報提供装置から送信されてくる提供情報を送受信装置３により受信し、提供情報を正しく取得できたときはステップＳＴ２０６へ行き、通信障害等によりの取得に失敗したときは所要領域の経路計算系データが欠落し経路計算を行うことができないため、経路計算処理を終了する。
上記において、取得した提供情報はプロセッサ５の内部メモリに格納される。
【００９０】
ステップＳＴ２０６では、ステップＳＴ２０５により得られた提供情報に含まれる最新の版の経路計算系データを地図情報記憶装置４の地図情報に追加するともに上記地図情報の管理情報も更新し、ステップＳＴ２０２へ戻る。
【００９１】
上記動作において、例えば現在の最新の版数が１であり、地図情報記憶装置４に上記領域Ａ、Ｂの経路計算系データがない場合において、上記ステップＳＴ２０３、ステップＳＴ２０４、ＳＴ２０５、ＳＴ２０６の上記領域Ａについての一回目の動作および上記領域Ｂについての２回目の動作により、版数が１の上記領域Ａ、Ｂの道路網データである図１０、図１１の道路網データを含む経路計算計データを地図情報提供装置から取得し地図情報記憶装置４に格納される。
【００９２】
ステップＳＴ２０７では、当該地図情報処理装置を示す地図情報処理装置識別情報、ステップＳＴ２０２で選択した領域の経路計算系データを指定するデータ識別情報、データありを示すデータ有無情報、地図情報記憶装置４に格納されている地図情報に含まれるステップＳＴ２０２で選択した領域の経路計算系データの版数を示す保有版数情報からなる要求情報を作成し、送受信装置３により地図情報提供装置へ送信する。
【００９３】
ステップＳＴ２０８では、ステップＳＴ２０７で送信した要求情報に応じて地図情報提供装置から送信されてくる提供情報を送受信装置３により受信し、提供情報を正しく取得できたときはステップＳＴ２０９へ行き、通信障害等により提供情報の取得に失敗したときはステップＳＴ２０２へ戻る。
上記において、取得した提供情報はプロセッサ５の内部メモリに格納される。
【００９４】
ステップＳＴ２０９では、ステップＳＴ２０８で取得した提供情報中の提供情報種別が提供データがないことを示しているときは、地図情報記憶装置４に格納されているステップＳＴ２０２で選択した領域の経路計算系データは最新の版であるので、更新不要としてステップＳＴ２０２へ戻り、上記提供情報種別が更新指示情報であることを示しているときは上記経路計算系データは最新の版ではないので、更新要としてステップＳＴ２１０へ行く。
【００９５】
ステップＳＴ２１０では、ステップＳＴ２０２で選択した領域の経路計算系データを地図情報記憶装置４より取得する。本ステップにおいて、取得した経路計算系データはプロセッサ５の内部メモリに格納される。
【００９６】
ステップＳＴ２１１では、ステップＳＴ２０８で取得した提供情報に含まれる更新指示情報を用いて、ステップＳＴ２１０で取得した経路計算系データを最新の版に更新する。
【００９７】
ステップＳＴ２１２では、地図情報記憶装置４のステップＳＴ２０２で選択した領域の経路計算系データをステップＳＴ２１１により得られた最新の版の経路計算系データに書き換えるとともに、上記書き換えに応じて地図情報記憶装置４の地図情報の管理情報も更新し、ステップＳＴ２０２へ戻る。
【００９８】
上記動作において、例えば版数が１の上記領域Ａ、Ｂの道路網データである図１０、図１１の道路網データを含む経路計算計データが地図情報記憶装置４に格納された状態で、地図情報提供装置において図６の道路網が更新されて図９の道路網となり、道路網データの最新の版数が２となった場合、上記ステップＳＴ２０３、ステップＳＴ２０７、ＳＴ２０８、ＳＴ２０９、ＳＴ２１０、ＳＴ２１１、ＳＴ２１２の上記領域Ａについての一回目の動作および上記領域Ｂについての２回目の動作により以下の処理がなされる。
すなわち、版数が１の上記領域Ａの道路網データを含む経路計算系データを版数が２の道路網データを含む経路計算系データに更新するための更新指示情報、版数が１の上記領域Ｂの道路網データを含む経路計算系データを版数が２の道路網データを含む経路計算系データに更新するための更新指示情報を取得し、上記更新指示情報を用いて、地図情報記憶装置４にある版数が１の上記領域Ａの図１０に示す道路網データを含む経路計算系データを更新することにより、版数が２の上記領域Ａの図１２に示す道路網データを含む経路計算系データが得られ、上記領域Ｂの図１１に示す道路網データを含む経路計算系データを更新することにより、版数が２の上記領域Ｂの図９の道路網ＧＢ１を表す道路網データ含む経路計算系データが得られる。
地図情報記憶装置４にある版数が１の上記領域Ａ、Ｂの道路網データを含む経路計算系データを上記更新により得られた版数が２の上記領域Ａ、Ｂの道路網データを含む経路計算系データに置き換える。
【００９９】
尚、ステップＳＴ２０８で通信障害等が発生し、例えば上記領域Ｂに関する更新指示情報が取得できなければ、領域Ｂの経路計算系データの更新は行われず、地図情報記憶装置４には版数が１の上記領域Ｂの経路計算系データと版数が２の上記領域Ａ経路計算系データが格納される。
【０１００】
ステップＳＴ２１３では、ステップＳＴ２０１で決定された所要領域の経路計算系データを地図情報記憶装置４より取得し、プロセッサ５の内部メモリに格納する。
上記によりプロセッサ５の内部メモリに格納された上記所要領域Ａ、Ｂの経路計算系データに含まれる道路網データとして、例えば、領域Ａ、Ｂ共に版数が１の、図１０と図１１の道路網データとなる場合（以下、Ｃ１１の場合と称する。）、または領域Ａ、Ｂ共に版数が２の、図１２の道路網データと図９の道路網ＧＢ１を表す道路網データとなる場合（以下、Ｃ１２の場合と称する。）、領域Ａが版数が２の図１２の道路網データで、領域Ｂが版数が１の図１１の道路網データとなる場合（以下、Ｃ１３の場合と称する。）、または領域Ａが版数が１の図１０の道路網データで、領域Ｂが版数が２の図９の道路網ＧＢ１を表す道路網データとなる場合（以下、Ｃ１４の場合と称する。）がある。
【０１０１】
ステップＳＴ２１４では、ステップＳＴ２１３で取得した、ステップＳＴ２０１で決定された所要領域の経路計算系データに含まれる道路網データを用いて、ステップＳＴ２００で取得した出発地から目的地までの最適経路をダイクストラ法を用いた経路計算により求め処理を終了する。
【０１０２】
上記経路計算の過程で、当該領域から他領域の隣接境界ノードへ至る時、例えば、上記Ｃ１１の場合、図６の領域ＢのノードＮＢ８からその隣接境界ノードである図６の領域ＡのノードＮＡ８へ至るとき、図１１のノードＮＢ８のノードレコードＮＲＢ８より隣接境界相対ノード番号（＝２）を求め、図１０のノード番号から先頭境界ノード番号（＝６）を減じた値即ち相対境界ノード番号が上記隣接境界相対ノード番号（＝２）に一致するノード番号８のノードＮＡ８を隣接境界ノードとして求める。
また、例えば、上記Ｃ１３の場合、図６の領域ＢのノードＮＢ８からその隣接境界ノードである図９の領域ＡのノードＮＡ８へ至るとき、図１１のノードＮＢ８のノードレコードＮＲＢ８より隣接境界相対ノード番号（＝２）を求め、図１２のノード番号から先頭境界ノード番号（＝８）を減じた値即ち相対境界ノード番号（＝２）が上記隣接境界相対ノード番号（＝２）に一致する、ノード番号１０のノードＮＡ８を隣接境界ノードとして求める。
【０１０３】
このように、同一の境界ノードの相対境界ノード番号が版数により変化することがないため、隣接する領域の道路データの版数に関わらず隣接境界ノードを正しく求めることができ、道路網データ間の不整合を来たさず、経路計算を正しく行うことができる。
また、上記より、地図情報処理装置が所要領域の経路計算系データを保有していないときは、最新の経路計算系データを地図情報提供より取得し、地図情報処理装置が所要領域の経路計算系データを保有しているときは、地図情報処理装置が保有している所要領域の経路計算系データを最新の版の経路計算系データに更新するための更新指示情報を地図情報提供より取得するため、地図情報処理装置が所要領域の経路計算系データを保有している場合は、最新の版の経路計算系データを取得する場合に比し地図情報処理装置と地図情報提供装置との通信時間をより短くできる。
【０１０４】
図１８は、図１７のステップＳＴ２１１における経路計算系データ中の道路網データに関する更新処理の一例を示すフローチャートである。
以下では、ステップＳＴ２０８で取得した提供情報に含まれる更新指示情報中にある図１６の道路網データ更新指示情報により、ステップＳＴ２１０で取得した経路計算系データ中の図１０の道路網データを更新する場合を例に説明する。
【０１０５】
処理が開始されると、ステップＳＴ３００では、図１６のヘッダ更新指示情報に基づき、プロセッサ５の内部メモリに更新された道路網データを格納するための更新領域を確保する。
【０１０６】
ステップＳＴ３０１では、図１６の削除リンク情報に基づき、図６のリンクのリンク番号の更新前と更新後の対応関係を示すリンク番号変換テーブルをプロセッサ５の内部メモリに作成する。
即ち、上記リンク番号変換テーブルは更新前のリンク番号０、１、２、３、４、５、６、７、８に対しそれぞれ更新後のリンク番号０、−１、１、２、−１、３、４、５、６が対応することを示す。但し、更新前のリンク番号１、４は削除されたことを示すため−１を対応させている。
【０１０７】
ステップＳＴ３０２では、図１６のヘッダ更新指示情報を上記更新領域に格納する。
【０１０８】
ステップＳＴ３０３では、図１７のステップＳＴ２１０で得られた道路網データのノード情報における内部ノードのノードレコードを更新領域へ格納する。このとき、削除内部ノード情報が示す削除するノードのノードレコードの代わりに新設内部ノード情報のノードレコードを格納する。これにより削除するノードのノードレコードが新設するノードのノードレコードに置き換えられたことになる。
即ち、図１０のノードレコードＮＲＡ０を更新領域に格納し、その後に、削除するノードである図１０のノードレコードＮＲＡ１の代わりに、図１６の新設内部ノード情報のノードレコードＮＲＡ９を更新領域に格納し、その後に、図１０のノードレコードＮＲＡ２、ＮＲＡ３、ＮＲＡ４、ＮＲＡ５を更新領域に格納する。上記処理で削除するノードが複数ある場合は、新設内部ノード情報のノードレコードの先頭から順に削除するノードのノードレコードの代わりに更新領域に格納する。
上記により、新設された内部ノードに不要となった内部ノードのノード番号を付与する（内部ノード置き換え）。
【０１０９】
但し、図１０のノードレコードを更新領域に格納する際には、ステップＳＴ３０１で作成したリンク番号変換テーブルに基づき、接続リンク数および接続リンク番号を更新後の値に変更したものを格納する。例えば図１０のノードレコードＮＲＡ４に対して、リンク番号変換テーブルにより接続リンク番号４、１に対応するリンク番号は−１となり、接続するリンクが２つ削除されることが分かり、接続リンク番号６、７、８に対応するリンク番号は４、５、６であることが分かり、図１０のノードレコードＮＲＡ４の接続リンク数を３に、接続リンク番号を４、５、６に変更したものを更新領域に格納する。
上記に加え、図１０のノードレコードを更新領域に格納する際には、図１６の接続リンク番号情報の上記ノードレコードに対応するノードの接続リンク番号追加レコード中の接続リンク番号を上記ノードレコードに追加する。例えば図１０のノードレコードＮＲＡ５に対して、接続リンク数を４とし、接続リンク番号を７、５、２を５、３、１に変更し、接続リンク番号９を追加したものを更新領域に格納する。
【０１１０】
上記により、図１２におけるノード番号０〜５のノードレコードが更新領域に得られ、新設された内部ノードに、不要となった内部ノードのノード番号が付与される。
【０１１１】
ステップＳＴ３０４では、図１６の新設内部ノード情報のノードレコードで、ステップＳＴ３０３で更新領域に格納されていないものを、ステップＳＴ３０３で格納したノードレコードの後に格納する（内部ノード追加）。即ち、図１２におけるノード番号０〜５のノードレコードの後にノードレコードＮＲＡ１０、ＮＲＡ１１を追加したものが更新領域に得られる。
上記により新設する内部ノードに対し当該道路網が変化するまでに付与されたノード番号と異なるノード番号を付与する。
【０１１２】
ステップＳＴ３０５では、図１７のステップＳＴ２１０で得られた道路網データのノード情報における境界ノードのノードレコードを、ステップＳＴ３０４で格納したノードレコードの後に格納する。但し、削除境界ノード情報によって示される削除する境界ノードのノードレコードの接続リンク数を０、隣接領域情報を該当するものなし、隣接境界相対ノード番号を該当するものなしとして格納する（境界ノード削除）。また、削除されない境界ノードのノードレコードの接続リンク番号は上記リンク番号変換テーブルに従い更新後の値に変更される。
即ち、図１２におけるノード番号７のノードレコードの後に、図１０のノードレコードＮＲＡ６、ＮＲＡ７、ＮＲＡ８を上記のように変更した図１２のノード番号８〜１０のノードレコードを格納したものが更新領域に得られる。
【０１１３】
ステップＳＴ３０６では、図１６の新設境界ノード情報が示すノードレコードをステップＳＴ３０５で格納したノードレコードの後に格納する（境界ノード追加）。
即ち、新設境界ノード情報のノードレコードＮＲＡ１２を、図１２におけるノード番号１０のノードレコードの後に追加し、図１２のノード情報が更新領域に得られる。
上記により、道路網の更新により新設された境界ノードに、当該道路網が変化するまでに付与された相対番号とは異なる相対境界ノード番号を付与する。
【０１１４】
ステップＳＴ３０７では、削除リンク情報が示すリンクのリンクレコードを、ステップＳＴ２１０で得られた道路網データのリンク情報から除いたものを更新領域に格納する（リンク削除）。
即ち、リンク番号１、４のリンクレコードＬＲＡ１、ＬＲＡ４を図１０のリンク情報から除いた、図１２のリンク番号０〜６のリンクレコードが、更新領域に格納される。このとき、図１０のリンクレコードＬＲＡ３、ＬＲＡ５の終点ノード番号６、８は、図１０の先頭境界ノード番号（＝６）に等しいか大きいため、図１６のヘッダ更新指示情報の最小境界ノード番号（＝８）から、図１０の先頭境界ノード番号（＝６）を減じた値２を上記終点ノード番号に加算した値８、１０を求め、リンクレコードＬＲＡ３、ＬＲＡ５の終点ノード番号を８、１０に変更して更新領域に格納する。
【０１１５】
上記のように、内部ノードのノード番号は道路網の更新により変化しないため、リンクレコードの始点ノード番号、終点ノード番号は境界ノードに対してのみ変更すればよく、内部ノードに対して変更は不要であり、更新処理の負荷を低減することができる。
【０１１６】
ステップＳＴ３０８では、新設リンク情報のリンクレコードをステップＳＴ３０７で格納したリンクレコードの後に追加する（リンク追加）。
即ち、図１２におけるリンク番号６のリンクレコードの後に、図１６の新設リンク情報のリンクレコードであるリンクレコードＬＲＡ９、ＬＲＡ１０、ＬＲＡ１１、ＬＲＡ１２が追加される。
【０１１７】
上記ステップＳＴ３０７、ＳＴ３０８により、図１２のリンク情報が更新領域に得られる。
【０１１８】
以上のようにして、図１０の道路網データを図１６の道路網データ更新指示情報により更新した図１２の道路網データが更新領域に得られ、道路網データの更新を終了する。
【０１１９】
上記動作により、道路網データの更新を容易に行なうことができ、版数の異なる道路網データに対し整合性のある道路網データを得ることができる。
【０１２０】
実施の形態２．
本発明の実施の形態２による地図情報更新システム、地図情報提供装置、地図情報処理装置の構成、および地図情報の概略データ構造は、実施の形態１の場合と同様であるので、以下では、主に、本発明の実施の形態２による道路網データのデータ構造および道路網データの更新方法について説明する。
本実施の形態２における道路網データは、実施の形態１の道路網データにおける内部ノード、境界ノードに対し、それぞれ独立にノード番号を付与してノードを識別するようにしたものである。
【０１２１】
以下では、主に図６の道路網を例に説明するが、図７、図８に示す方法で分割された道路網であってもよい。
【０１２２】
図１９は、実施の形態２による図６の道路網ＧＡを表す版数が１の道路網データのデータ構造の一例を示す図である。道路網データは、道路網データヘッダ、内部ノード情報、境界ノード情報、リンク情報からなる。
【０１２３】
道路網データヘッダは、内部ノード情報の当該道路網データにおける格納位置、内部ノード情報のデータサイズ、収容している内部ノードレコードの数等を示す内部ノード管理情報、境界ノード情報の当該道路網データにおける格納位置、境界ノード情報のデータサイズ、収容している境界ノードレコードの数等を示す境界ノード管理情報、リンク情報の当該道路網データにおける格納位置、リンク情報のデータサイズ、収容している境界リンクレコードの数を示すリンク管理情報等を有する。
【０１２４】
内部ノード情報は、内部ノードに対応して設けられた内部ノードレコードの並びであり、内部ノードレコードの内容は、実施の形態１の内部ノードに対応するノードレコードと同一である。図１９では、接続リンク数をＣＮで示し、接続リンク番号をＣＬｎ（ｎ＝０，１，・・・）で示している。
図６のノードＮＡ０，ＮＡ１，ＮＡ２，ＮＡ３，ＮＡ４，ＮＡ５に対してそれぞれ内部ノードレコードＩＮＲＡ０，ＩＮＲＡ１，ＩＮＲＡ２，ＩＮＲＡ３，ＩＮＲＡ４，ＩＮＲＡ５が設けられる。各内部ノードを識別するために内部ノード毎に内部ノード番号を付与する。図１９の例では、各内部ノードに対応する内部ノードレコードの並び順を内部ノード番号として付与しており、図６のノードＮＡ０，ＮＡ１，ＮＡ２，ＮＡ３，ＮＡ４，ＮＡ５の内部ノード番号はそれぞれ０，１，２，３，４，５である。
【０１２５】
境界ノード情報は、境界ノードに対応して設けられた境界ノードレコードの並びであり、境界ノードレコードの内容は、実施の形態１の境界ノードに対応するノードレコードと同一である。但し、隣接境界相対ノード番号の代わりに、隣接境界ノードの境界ノード番号を示す隣接境界ノード番号を格納するようにしている。図１９では、隣接領域情報をＡＩＤで示し、隣接境界ノード番号をＣＡで示している。
図６のノードＮＡ６，ＮＡ７，ＮＡ８に対してそれぞれ境界ノードレコードＢＮＲＡ０，ＢＮＲＡ１，ＢＮＲＡ２が設けられる。各境界ノードを識別するために境界ノード毎に境界ノード番号を付与する。図１９の例では、各境界ノードに対応する境界ノードレコードの並び順を境界ノード番号として付与しており、図６のノードＮＡ６，ＮＡ７，ＮＡ８の境界ノード番号はそれぞれ０，１，２である。
【０１２６】
リンク情報は、各リンクに対応して設けられた、実施の形態１と同様のリンクレコードの並びである。但し、リンクレコードの始点ノード番号ＳＮおよび終点ノード番号ＥＮは、ノード番号とノード番号が内部ノード番号、境界ノード番号の何れを指すかを示すノード番号種別を用いて表している。
例えば、図１９のリンクレコードのＩ：ｎ（ｎ＝０，１，・・・）において、Ｉはｎが内部ノード番号であることを表すノード番号種別であり、ｎは内部ノード番号を示す。また、Ｂ：ｎ（ｎ＝０，１，・・・）において、Ｂはｎが境界ノード番号であることを表すノード番号種別であり、ｎは境界ノード番号を示す。
具体的には、図１９のリンクレコードＬＲＡ４の始点ノード番号ＳＮは、ノード番号データが内部ノード番号であることを示すノード番号種別Ｉとノード番号４からなり、リンクＬＡ４の始点ノードは内部ノード番号が４のノードＮＡ４を示している。また、終点ノード番号ＥＮは、ノード番号データが境界ノード番号であることを示すノード番号種別Ｂとノード番号１からなり、リンクＬＡ４の終点ノードは境界ノード番号が１のノードＮＡ７を示している。
【０１２７】
上記のように、内部ノード番号と境界ノード番号は独立して付与されるため、下記に示すように道路網の更新による内部ノードの内部ノード番号変化、境界ノードの境界ノード番号の変化を防止することが可能であり、道路網データの更新を容易にすることを可能とし、版数の異なる道路網データ間の整合性を保つことを可能とする。
【０１２８】
図２０は図１９の場合と同様にして設けられた図６の道路網ＧＢを表す版数が１の道路網データのデータ構造の一例を示す図である。図２０において、内部ノードレコードＩＮＲＢｎ（ｎ＝０，１，・・・，８）は図６のノードＮＢｎ（ｎ＝０，１，・・・，５）に対応し、境界ノードレコードＢＮＲＢ０，ＢＮＲＢ１，ＢＮＲＢ２はそれぞれ図６の境界ノードＮＢ６，ＮＢ７，ＮＢ８に対応し、リンクレコードＬＲＢｍ（ｍ＝０，１，・・・，８）は図６のリンクＬＢｍ（ｍ＝０，１，・・・，７）に対応している。
【０１２９】
本実施の形態２では、道路網データは、図１９、２０に示したようなデータ構造となっており、内部ノードレコード、境界ノードレコードを参照することによりノードに接続するリンクが得られ、そのリンクのリンクレコードを参照するにより上記ノードから到達できるノード、通行規制、到達するために要するコスト等が得られる。
また、境界ノードレコードを参照することにより隣接境界ノードが得られ隣接領域のノードに到達できる。例えば、図１９の境界ノードレコードＢＮＲＡ０により、境界ノードＮＡ６の隣接境界ノードとして図６の領域Ｂの境界ノード番号が０である境界ノードＮＢ６が得られ、領域Ａの境界ノードＮＡ６から領域Ｂの境界ノードＮＢ６へ到達できる。
このように、上記道路網データにより、任意のノードから到達可能なノード、ノードからノードに至るのに要するコストおよび通行規制が得られ、上記道路網データを用いて、例えばダイクストラ法などにより、通行規制を加味した、コストが最小となる、出発地ノードから目的地ノードへ至る経路を求めることができる。
【０１３０】
図２１は、実施の形態２による図９の道路網ＧＡ１を表す版数が２の道路網データのデータ構造の一例を示す図である。
図２１の内部ノード情報は、図１９の削除されたノードＮＡ１に対応する内部ノードレコードＩＮＲＡ１を図９の新設された内部ノードＮＡ９に対応する内部ノードレコードＩＮＲＡ９に置き換え、図９の新設されたノードＮＡ１０、ＮＡ１１に対応する内部ノードレコードＩＮＲＡ１０、ＩＮＲＡ１１を図１９の内部ノード情報の末尾に追加したものである。
また、図２１の境界ノード情報は、図９の新設された境界ノードＮＡ１２のノードレコードＢＮＲＡ３を、図１９の境界ノード情報の末尾に追加して得られたものである。
【０１３１】
上記により新設された内部ノードＮＡ９には、不要となったノードＮＡ１の内部ノード番号１が付与され、新設された内部ノードＮＡ１０、ＮＡ１１には、道路網が図９に変化するまでに内部ノード付与されていた内部ノード番号０〜５よりも大きな内部ノード番号である６，７が付与される。
即ち、上記新設された内部ノードには、不要となった内部ノードの内部ノード番号または当該道路網が変化するまでに付与された内部ノード番号と異なる内部ノード番号が付与される。
これにより、道路網の更新による内部ノード番号の変化を防止できる。
【０１３２】
また、上記により新設された境界ノードＮＡ１２には、道路網が図９のように変化するまでに境界ノード付与されていた境界ノード番号０，１，２よりも大きな境界ノード番号である３が付与される。
即ち、上記のように新設された境界ノードには、当該道路網が変化するまでに付与された境界ノード番号とは異なる境界ノード番号が付与される。
これにより、道路網の更新による境界ノード番号の変化を防止できる。
【０１３３】
上記のように、道路網が変化してもそれまでに存在していた境界ノードの境界ノード番号は変化しないために、隣接する領域の道路網データの版数が異なっていても、上記領域の道路網間の接続に不整合を生じない。例えば、図６の道路網ＧＢのノードＮＢ８の隣接境界ノード番号は、図２０の道路網データより２であり、図１９の道路網データの境界ノード番号が２の境界ノードはＮＡ８である。また、図１９の道路網データを更新して得られた図２１の道路網データにおいても境界ノード番号が２の境界ノードはＮＡ８である。従って、領域Ａの道路網の更新前と更新後とのいずれに対しても、図６の道路網ＧＢのノードＮＢ８の隣接境界ノードＮＡ８を正しく求めることができる。
【０１３４】
尚、図２１の内部ノード情報、境界ノード情報において、下記で示すリンクおよびそのリンクレコードの削除、追加に応じ、実施の形態１の場合と同様にして、ノードレコードの接続リンク数、接続リンク番号、隣接領域情報、および隣接境界ノード番号の変更、並びに接続リンク番号の追加が行われる。例えば、内部ノードレコードＩＮＲＡ４の接続リンク数（ＣＮ）は５から３に、接続リンク番号（ＣＬｎ）は６，４，７，８，１から４，５，６に変更されている。また、削除された境界ノードの境界ノードレコード（例えばＢＮＲＡ２）の接続リンク数（ＣＮ）は０とし、隣接領域情報（ＡＩＤ）、隣接境界ノード番号（ＣＡ）には該当するものがないことを示す所定の値（図２１の例ではＮＵＬＬ）を格納している。
【０１３５】
図２１のリンク情報は、削除された図６のリンクＬＡ１，ＬＡ４に対応する図１９のリンクレコードＬＲＡ１，ＬＲＡ４を削除し、新設された図９のリンクＬＡ９，ＬＡ１０，ＬＡ１１，ＬＡ１２に対応するリンクレコードＬＲＡ９，ＬＲＡ１０，ＬＲＡ１１，ＬＲＡ１２を図１９のリンク情報の末尾に追加して得られたものである。
【０１３６】
上記により、それまでに存在していた内部ノードおよび境界ノードの内部ノード番号および境界ノード番号が変化しないため、リンクレコードの更新においては、リンクレコードの始点ノード番号または終点ノード番号の変更は不要である。
【０１３７】
図２１の道路網データヘッダは上記更新に合わせて変更される。
【０１３８】
図示しないが、図９の道路網ＧＢ１を表す版数が２の道路網データも図２１の場合と同様に図２０を更新して得られる。
【０１３９】
上記道路網データでは、道路網が変化してもそれまでに存在していた境界ノードの境界ノード番号は変化しないために、隣接する領域の道路網データ間で版数が異なっていても、上記領域の道路網間の接続に不整合を生じない。
また、道路網の更新によるノードの新設、削除に伴う道路網データの更新において、内部ノード番号および境界ノード番号が共に変化しないため、リンクレコードの始点ノード番号または終点ノード番号の変更は不要であり、従来に比し上記変更処理の負荷をはるかに軽減でき、道路網データの更新が容易になる。
【０１４０】
実施の形態２における地図情報提供装置の基本構成は、実施の形態１の図３に示したものと同じであるので、以下では、主に異なる点について説明する。本実施の形態では、地図情報提供装置の地図情報データベース１１には、初版から最新の版までの各地図情報の道路網データとして、図１９〜図２１に示したようなデータ構造を有するデータが蓄積されており、更新指示情報データベース１２には、各版の上記地図情報を最新版の上記地図情報に更新するための更新指示情報が蓄積されている。
【０１４１】
図２２は、上記更新指示情報に含まれる道路網データを更新するための道路網データ更新指示情報のデータ構造の一例を示す図であり、図１９の道路網データを図２１の道路網データに更新するための情報の一例を示している。
上記道路網データ更新指示情報は、実施の形態１で説明した図１６に示す道路網データ更新指示情報を、実施の形態２による道路網データのデータ構造に適合するように変更したものであり、削除するノードおよびリンク、並びに新設するノードおよびリンクは、図１６の場合と同一である。
【０１４２】
ヘッダ更新指示情報は、図２１の道路網データヘッダと同一内容のデータである。
削除内部ノード情報は、削除する内部ノードの数と内部ノード番号を示し、図６の道路網ＧＡの内部ノードＮＡ１を削除することを示している。
接続リンク番号情報は、内部ノードレコードＩＮＲＡ５に接続リンク番号９を追加することを示している。これはリンクＬＡ１１の新設に起因するものである。
新設内部ノード情報は、新設する内部ノードの数と内部ノードレコードを示し、図６の道路網ＧＡに図９の内部ノードＮＡ９、ＮＡ１０、ＮＡ１１を新設することを示している。
削除境界ノード情報は、削除する境界ノードの数と境界ノード番号を示し、図６の道路網ＧＡの境界ノードＮＡ７を削除することを示している。
新設境界ノード情報は、新設する境界ノードの数と境界ノードレコードを示し、図６の道路網ＧＡに図９の境界ノードＮＡ１２を新設することを示している。
削除リンク情報は、削除するリンクの数とリンク番号を示し、図６の道路網ＧＡのリンクＬＡ１、ＬＡ４を削除することを示している。
新設リンク情報は、新設するリンクの数とリンクレコードを示し、図６の道路網ＧＡに図９のリンクＬＡ９、ＬＡ１０、ＬＡ１１、ＬＡ１２を新設することを示している。尚、リンクレコードの始点ノード番号（ＳＮ）および終点ノード番号（ＥＮ）は、内部ノード番号（Ｉ）と境界ノード番号（Ｂ）とを区別するノード番号種別と共に示している。
【０１４３】
実施の形態２における地図情報提供装置の基本動作は、実施の形態１の図１５に示したフローチャートと同じであるので、説明を省略するが、実施の形態１の場合と同様に、地図情報処理装置が所要領域の道路網データを保有していないときは、最新の道路網データを地図情報処理装置に提供し、地図情報処理装置が所要領域の道路網データを保有しているが最新の版の道路網データを保有していないときは、地図情報処理装置が保有している所要領域の道路網データを最新の版の道路網データに更新するための更新指示情報を提供することができ、地図情報処理装置が所要領域の道路網データを保有しているときは、最新の版の道路網データを提供する場合に比し地図情報処理装置と地図情報提供装置との通信時間を短縮することができる。
【０１４４】
また、図１５のステップＳＴ１０２、ＳＴ１０３、ＳＴ１０４、ＳＴ１０９により、例えば図１９〜図２１に示したようなデータ構造を有する道路網データ、即ち道路網の更新によって内部ノードの内部ノード番号および境界ノードの境界ノード番号が共に変化せず、更新が容易であり、版数の異なる道路網データ間の整合性を保つことが可能な道路網データを、地図情報処理装置に提供することができる。
【０１４５】
実施の形態２における地図情報処理装置の基本構成は、実施の形態１の図２に示したものと同じであるので、以下では、主に異なる点について説明する。本実施の形態では、地図情報処理装置の地図情報記憶装置４には、各地図情報の道路網データとして、図１９〜図２１に示したようなデータ構造を有するデータが蓄積されており、プロセッサ５では上記のようなデータ構造を有する道路網データを用いて各種の処理を行う。
【０１４６】
実施の形態２による地図情報処理装置におけるプロセッサ５の基本動作は、実施の形態１の図１７に示したフローチャートと同じであるので、詳細な説明は省略するが、本実施の形態によれば、実施の形態１の場合と同様に、地図情報処理装置が所要領域の道路網データを保有していないときは、最新の道路網データを地図情報提供装置より取得し、地図情報処理装置が所要領域の道路網データを保有しているときは、地図情報処理装置が保有している所要領域の道路網データを最新の版の道路網データに更新するための更新指示情報を地図情報提供装置より取得することにより、地図情報処理装置が所要領域の道路網データを保有している場合は、最新の版の道路網データを取得する場合に比し地図情報処理装置と地図情報提供装置との通信時間を短縮することができる。
【０１４７】
また、図１７のステップＳＴ２０３、ＳＴ２０４、ＳＴ２０５、ＳＴ２０６により、道路網の更新に際し、内部ノード番号、境界ノード番号に変化を来たさないデータ構造の道路網データを取得し、上記道路網データの更新を容易し、版数が異なる道路網データが混在するようになっても道路網データ間の整合性を保てるようにできる。
【０１４８】
以下、実施の形態２による地図情報処理装置におけるプロセッサ５の動作で、実施の形態１の場合と異なる点について主に説明する。
【０１４９】
図１７のステップＳＴ２１４では、ステップＳＴ２１３で取得した、ステップＳＴ２０１で決定された所要領域の経路計算系データに含まれる道路網データを用いて、ステップＳＴ２００で取得した出発地から目的地までの最適経路を、ダイクストラ法を用いた経路計算により求め、処理を終了する。
例えば、領域Ａ、Ｂ共に版数が１の図１９と図２０の道路網データ（以下、Ｃ２１の場合と称する。）、または領域Ａ、Ｂ共に版数が２の図２１の道路網データと図９の道路網ＧＢ１を表す実施の形態２による道路網データ（以下、Ｃ２２の場合と称する。）、または領域Ａに版数が２の図２１の道路網データ、領域Ｂに版数が１の図２０の道路網データ（以下、Ｃ２３の場合と称する。）、または領域Ａに版数が１の図１９の道路網データ、領域Ｂに版数が２の図９の道路網ＧＢ１を表す道路網データ（以下、Ｃ２４の場合と称する。）を用いて、ノードＮＢ１２からノードＮＡ０への最適経路を、ダイクストラ法を用いた経路計算により求める。
【０１５０】
経路計算の過程で、当該領域から他領域の隣接境界ノードへ至る時、例えば、上記Ｃ２１の場合において、図６の領域ＢのノードＮＢ８からその隣接境界ノードである図６の領域ＡのノードＮＡ６へ至るとき、図２０のノードＮＢ８の境界ノードレコードＢＮＲＢ２より隣接境界ノード番号（＝２）を求め、上記隣接境界ノード番号（＝２）が示す図１９の境界ノード番号（＝２）の境界ノードレコードＢＮＲＡ２に対応するノードＮＡ８を隣接境界ノードとして求める。
また、例えば、上記Ｃ２３の場合において、図６の領域ＢのノードＮＢ８からその隣接境界ノードである図９の領域ＡのノードＮＡ８へ至るとき、図２０のノードＮＢ８の境界ノードレコードＢＮＲＢ２より隣接境界ノード番号（＝２）を求め、上記隣接境界ノード番号（＝２）が示す図２１の境界ノード番号（＝２）の境界ノードレコードＢＮＲＡ２に対応するノードＮＡ８を隣接境界ノードとして求める。
【０１５１】
このように、同一の境界ノードの境界ノード番号が版数により変化することがないため、隣接する領域の道路データの版数に関わらず隣接境界ノードを正しく求めることかでき、道路網データ間の不整合を来たさず、経路計算を正しく行うことができる。
【０１５２】
また、図１７のステップＳＴ２１１における経路計算系データ中の道路網データに関する更新は、道路網データのデータ構造の差異による動作の違いを除き、実施の形態１で説明した図１８のフローチャートが示す動作と同様にして行われる。但し、実施の形態１で説明した図１６の道路データ更新指示情報の代わりに、本実施の形態２で説明した図２２の道路データ更新指示情報を使用し、実施の形態１で説明した図１０道路網データの代わりに、本実施の形態２で説明した図１９の道路網データを更新する場合としている。
【０１５３】
以下に、図１８に示したフローチャートの実施の形態２における動作について説明する。
ステップＳＴ３００、ＳＴ３０１、ＳＴ３０２により、実施の形態１の場合と同様にして、リンク番号変換テーブルを作成し、図２１の道路網データヘッダが更新領域に得られる。
【０１５４】
ステップＳＴ３０３、ＳＴ３０４により、実施の形態１の場合と同様にして、図１９の内部ノード情報に対し、内部ノードレコードの置き換え、追加、接続リンク数および接続リンク番号の変更、接続リンク番号の追加を行って得られた図２１の内部ノード情報が更新領域に格納される。
上記により、道路網の更新により新設する内部ノードに対して、道路網の更新により不要となった内部ノードの内部ノード番号を付与し、さらに、新設する内部ノードに対して、当該道路網が更新されるまでに付与された内部ノード番号と異なる内部ノード番号を付与し、内部ノード番号を変化させることなく内部ノード情報を更新する。
【０１５５】
ステップＳＴ３０５、ＳＴ３０６では、実施の形態１の場合と同様にして、図１９の境界ノード情報に対して、境界ノードレコードの接続リンク数、接続リンク番号、隣接領域情報、隣接境界ノード番号の変更、新設境界ノード情報が示す境界ノードレコードの追加を行って得られた図２１の境界ノード情報が更新領域に格納される。
上記により、道路網の更新により新設された境界ノードには、当該道路網が更新されるまでに付与された境界ノード番号とは異なる境界ノード番号を付与し、境界ノード番号を変化させることなく境界ノード情報を更新する。
【０１５６】
ステップＳＴ３０７、ＳＴ３０８では、実施の形態１の場合と同様にして、リンクレコードの削除、追加を行い、図２１のリンク情報を更新領域に得る。
上記のように、内部ノード番号および境界ノード番号は何れも道路網の更新により変化しないため、ステップＳＴ３０７においてリンクレコードの内部ノードを示す始点ノード番号、終点ノード番号の変更を行わずにリンク情報を更新することができ、更新処理の負荷を低減することができる。
【０１５７】
以上のようにして、図１９の道路網データを図２２の道路網データ更新指示情報により更新した図２１の道路網データが更新領域に得られ、道路網データの更新を終了する。
【０１５８】
上記動作により、道路網データの更新を容易に行なうことができ、版数の異なる道路網データに対し整合性のある道路網データを得ることができる。
【０１５９】
実施の形態３．
本発明の実施の形態３による地図情報更新システム、地図情報提供装置、地図情報処理装置の構成、および地図情報の概略データ構造は、実施の形態１の場合と同様であるので、以下では、主に、本発明の実施の形態３による道路網データのデータ構造および道路網データの更新方法について説明する。
本実施の形態３における道路網データは、実施の形態１の道路網データにおける内部ノード、境界ノードに対応するノードレコードの配置を逆にし、境界ノードに対し内部ノードよりも小さなノード番号を付与するようにし、リンクレコードの内部ノードを示す始点ノード番号、終点ノード番号は内部ノードの相対内部ノード番号を用いて表すようにしたものである。
【０１６０】
以下では、主に図６の道路網を例に説明するが、図７、図８に示す方法で分割された道路網であってもよい。
【０１６１】
図２３は、実施の形態３による図６の道路網ＧＡを表す版数が１の道路網データのデータ構造の一例を示す図である。
道路網データは、道路網データヘッダ、ノード情報、リンク情報からなる。
【０１６２】
道路網データヘッダは、ノード情報の当該道路網データにおける格納位置、ノード情報のデータサイズ、収容しているノードレコードの数等を示すノード管理情報、リンク情報の当該道路網データにおける格納位置、リンク情報のデータサイズ、収容しているリンクレコードの数等を示すリンク管理情報、当該道路網データにおける内部ノードのノード番号の最小値を示す先頭内部ノード番号等を有する。
【０１６３】
ノード情報は、各ノードに対応して設けられたノードレコードの並びであり、ノードＮＡ０，ＮＡ１，・・・，ＮＡ８に対してそれぞれノードレコードＮＲＡ０，ＮＲＡ１，・・・，ＮＲＡ８が設けられる。各ノードを識別するためにノード毎にノード番号を付与する。図２３の例では、各ノードに対応するノードレコードの並び順をノード番号として付与しており、ノードＮＡ０，ＮＡ１，・・・，ＮＡ８のノード番号はそれぞれ０，１，・・・，８である。
【０１６４】
ノード情報において、境界ノードのノードレコードＮＲＡ６，ＮＲＡ７，ＮＲＡ８を内部ノードのノードレコードより前に配置し、内部ノードのノードレコードＮＲＡ０，ＮＲＡ１，・・・，ＮＲＡ５を境界ノードのノードレコードより後に配置しており、境界ノードＮＡ６，ＮＡ７，ＮＡ８にはノード番号０，１，２が付与され、内部ノードＮＡ０，ＮＡ１，・・・，ＮＡ５にはノード番号３〜８が付与される。
【０１６５】
内部ノードに付与されたノード番号の最小値（先頭内部ノード番号）を基準にしたノード番号の相対値を相対内部ノード番号と定義する。相対内部ノード番号は内部ノードのノード番号から当該道路網データヘッダにある先頭内部ノード番号を減ずるこにより求めることができる。例えば、内部ノードＮＡ０，ＮＡ１，ＮＡ２の相対内部ノード番号はそれぞれ０，１，２である。
【０１６６】
リンク情報は、各リンクに対応して設けられたリンクレコードの並びであり、リンクＬＡ０，ＬＡ１，・・・，ＬＡ８に対してそれぞれリンクレコードＬＲＡ０，ＬＲＡ１，・・・，ＬＲＡ８が設けられる。各リンクを識別するためにリンク毎にリンク番号を付与する。図２３の例では、各リンクに対応するリンクレコードの並び順をリンク番号として付与しており、リンクＬＡ０，ＬＡ１，・・・，ＬＡ８のリンク番号はそれぞれ０，１，・・・，８である。
【０１６７】
ノードレコードは、実施の形態１と同様のデータ構成からなるが、隣接境界相対ノード番号の代わりに隣接境界ノード番号（ＣＡ）を有する。隣接境界ノード番号（ＣＡ）は、当該ノードの隣接境界ノードの隣接領域情報が示す領域におけるノード番号を示す。
【０１６８】
上記のように、ノードレコードは内部ノードのノードレコードを境界ノードのノードレコードより後に配置し、境界ノードのノードレコードを内部ノードのノードレコードより前に配置し、境界ノードのノード番号は、内部ノードの増減によって変化しないようにしている。
また、上記のように、内部ノードは内部ノードのノード番号の最小値を基準にしたノード番号の相対値である相対内部ノード番号を用いて指定している。
道路網データが上記のようなデータ構造を有することにより、下記に示すように道路網の更新の前後で同一の内部ノードの相対内部ノード番号が変化したり、同一の境界ノードのノード番号が変化したりするのを防止することを可能とし、道路網データの更新を容易にすることを可能とし、版数の異なる道路網データ間の整合性を保つことを可能とする。
【０１６９】
リンクレコードは、実施の形態１と同様のデータ構成からなるが、始点ノード番号、終点ノード番号は、ノード番号または相対内部ノード番号を表すノード番号データとノード種別を用いて表しており、ノード種別は上記ノード番号データがノード番号および相対内部ノード番号の何れを表しているか示す。
例えば、図２３のリンクレコードのＩ：ｎ（ｎ＝０，１，・・・）において、Ｉはｎが内部ノードを示すことを表すノード種別であり、ｎは相対内部ノード番号を示す。また、Ｂ：ｎ（ｎ＝０，１，・・・）において、Ｂはｎが境界ノードを示すことを表すノード種別であり、ｎはノード番号を示す。
具体的には、図２３のリンクレコードＬＲＡ４の始点ノード番号ＳＮは、ノード番号データが内部ノードを示すことを表すノード番号種別Ｉとノード番号データ４からなり、リンクＬＡ４の始点ノードは相対内部ノード番号が４のノードＮＡ４を示している。また、終点ノード番号ＥＮは、ノード番号データが境界ノードを示すことを表すノード番号種別Ｂとノード番号データ１からなり、リンクＬＡ４の終点ノードはノード番号が１のノードＮＡ７を示している。
【０１７０】
図２４は、図２３の場合と同様にして設けられた図６の道路網ＧＢを表す版数が１の道路網データのデータ構造の一例を示す図である。図２４において、ノードＮＢ６，ＮＢ７，ＮＢ８にノードレコードＮＲＢ６，ＮＲＢ７，ＮＲＢ８が対応しており、ノードＮＢ０，ＮＢ１，・・・，ＮＢ５にはノードレコードＮＲＢ０，ＮＲＢ１，・・・，ＮＲＢ５が対応している。また、リンクＬＢｎ（ｎ＝０，１，・・・）にリンクレコードＬＲＢｎ（ｎ＝０，１，・・・）が対応している。
【０１７１】
実施の形態３では、道路網データは、図２３、２４に示したようなデータ構造となっており、ノードレコードを参照することによりノードに接続するリンクが得られ、そのリンクのリンクレコードを参照することにより上記ノードから到達できるノード、通行規制、到達するために要するコスト等が得られる
また、境界ノードのノードレコードを参照することにより隣接境界ノードが得られ、隣接領域のノードに到達できる。例えば、図２３のノードレコードＮＲＡ６の隣接領域情報（ＡＩＤ）、隣接境界ノード番号（ＣＡ）により、境界ノードＮＡ６の隣接境界ノードとして領域Ｂのノード番号が０である境界ノードＮＢ６が得られ、領域Ａの境界ノードＮＡ６から領域Ｂの境界ノードＮＢ６へ到達できる。
このように、上記道路網データにより、任意のノードから到達可能なノード、ノードからノードに至るのに要するコストおよび通行規制が得られ、上記道路網データを用いて、例えばダイクストラ法などにより、通行規制を加味した、コストが最小となる、出発地ノードから目的地ノードへ至る経路を求めることができる。
【０１７２】
図２５は、実施の形態３による図９の道路網ＧＡ１を表す版数が２の道路網データのデータ構造の一例を示すである。
図２５のノード情報は、図９の新設された境界ノードＮＡ１２のノードレコードＮＲＡ１２を図２３の境界ノードに対応するノードレコードの後に追加し、図６の削除されたノードＮＡ１に対応する図２３のノードレコードＮＲＡ１を、図９の新設された内部ノードＮＡ９に対応するノードレコードＮＲＡ９に置き換え、図９の新設された内部ノードＮＡ１０、ＮＡ１１に対応するノードレコードＮＲＡ１０、ＮＲＡ１１を図２３のノード情報の末尾に追加することにより得られたものである。
【０１７３】
上記により、新設された境界ノードＮＡ１２には、道路網が図９のように変化するまでにすでに境界ノードに付与されていたノード番号０，１，２よりも大きなノード番号である３が付与され、道路網が図９のように変化するまでにすでに存在している境界ノードＮＡ６、ＮＡ７、ＮＡ８のノード番号は、道路網が図９のように変化しても０、１、２のままで変化しない。
即ち、上記のように新設された境界ノードには、当該道路網が変化するまでに付与されたノード番号とは異なるノード番号が付与され、道路網の更新によって境界ノードのノード番号は変化しない。
【０１７４】
また、上記により、新設された内部ノードＮＡ９には、不要となったノードＮＡ１の相対内部ノード番号１が付与され、新設された内部ノードＮＡ１０、ＮＡ１１には、道路網が図９に変化するまでに内部ノード付与されていた相対内部ノード番号０〜５よりも大きな相対内部ノード番号の６，７が付与される。
即ち、上記新設された内部ノードには、不要となった内部ノードの相対内部ノード番号または当該道路網が更新されるまでに付与された相対内部ノード番号と異なる相対内部ノード番号が付与され、道路網の更新によって内部ノードの相対内部ノード番号は変化しない。
【０１７５】
上記のように、道路網が変化してもそれまでに存在していた境界ノードのノード番号は変化しないために、隣接する領域の道路網データで版数が異なっていても、上記領域の道路網間の接続に不整合を生じない。例えば、図６の道路網ＧＢのノードＮＢ８の隣接境界ノード番号は、図２４の道路網データに示すように２であり、図２３の道路網データの境界ノード番号が２の境界ノードはＮＡ８である。また、図２３の道路網データを更新して得られた図２５の道路網データにおいても、境界ノード番号が２の境界ノードはＮＡ８である。従って、領域Ａの道路網の更新前と更新後とのいずれに対しても、図６の道路網ＧＢのノードＮＢ８の隣接境界ノードＮＡ８を正しく求めることができる。
【０１７６】
尚、図２５のノード情報において、下記で示すリンクおよびそのリンクレコードの削除、追加に伴い、接続リンク数、接続リンク番号、隣接領域情報、隣接境界相対ノード番号が変化するため、実施の形態１の場合と同様にして、道路網が図９に変化するまでに存在していたノードのノードレコードの接続リンク数、接続リンク番号、隣接領域情報、および隣接境界ノード番号の変更、並びに接続リンク番号の追加が行われる。例えば、ノードレコードＮＲＡ４の接続リンク数（ＣＮ）は５から３に、接続リンク番号（ＣＬｎ）は６，４，７，８，１から４，５，６に変更されている。また、削除された境界ノードのノードレコード（例えばＮＲＡ７）の接続リンク数（ＣＮ）は０とし、隣接領域情報（ＡＩＤ）、隣接境界相対ノード番号（ＣＡ）には該当するものがないことを示す所定の値（図２５の例ではＮＵＬＬ）を格納している。
【０１７７】
図２５のリンク情報は、削除された図６のリンクＬＡ１，ＬＡ４に対応する図２３のリンクレコードＬＲＡ１，ＬＲＡ４を削除し、新設されたリンク図９のリンクＬＡ９，ＬＡ１０，ＬＡ１１，ＬＡ１２に対応するリンクレコードＬＲＡ９，ＬＲＡ１０，ＬＲＡ１１，ＬＲＡ１２を図２３のリンク情報の末尾に追加して得られたものである。
【０１７８】
上記のように、それまでに存在していた内部ノードの相対内部ノード番号、それまでに存在していた境界ノードのノード番号が変化しないため、リンクレコードの更新においては、リンクレコードの始点ノード番号または終点ノード番号の変更は不要である。
【０１７９】
図２５の道路網データヘッダは上記更新に合わせて変更される。
【０１８０】
図示しないが、図９の道路網ＧＢ１を表す版数が２の道路網データも図２５の場合と同様に図２４を更新して得られる。
【０１８１】
上記道路網データでは、道路網が更新されてもそれまでに存在していた境界ノードのノード番号は変化しないために、隣接する領域の道路網データ間で版数が異なっていても、上記領域の道路網間の接続に不整合を生じない。
また、道路網の更新によるノードの新設、削除に伴う道路網データの更新において、それまでに存在していた境界ノードのノード番号および内部ノードの相対内部ノード番号が共に変化しないため、リンクレコードの始点ノード番号または終点ノード番号の変更は不要であり、従来に比し上記変更処理の負荷をはるかに軽減でき、道路網データの更新が容易になる。
【０１８２】
実施の形態３における地図情報提供装置の基本構成は、実施の形態１の図３に示したものと同じであるので、以下では、主に異なる点について説明する。本実施の形態では、地図情報提供装置の地図情報データベース１１には、初版から最新の版までの各地図情報の道路網データとして、図２３〜図２５に示したようなデータ構造を有するデータが蓄積されており、更新指示情報データベース１２には、各版の上記地図情報を最新版の上記地図情報に更新するための更新指示情報が蓄積されている。
【０１８３】
図２６は、上記更新指示情報に含まれる道路網データを更新するための道路網データ更新指示情報のデータ構造の一例を示す図であり、図２３の道路網データを図２５の道路網データに更新するための情報の一例を示している。
上記道路網データ更新指示情報は、実施の形態１で説明した図１６に示す道路網データ更新指示情報を、実施の形態３による道路網データのデータ構造に適合するように変更したものであり、削除するノードおよびリンク、並びに新設するノードおよびリンクは、図１６の場合と同一である。
【０１８４】
ヘッダ更新指示情報は、図２５の道路網データヘッダと同一内容のデータである。
削除内部ノード情報は、削除する内部ノードの数と相対内部ノード番号を示し、図６の道路網ＧＡの内部ノードＮＡ１を削除することを示している。
接続リンク番号情報は、ノードレコードＮＲＡ５に接続リンク番号９を追加することを示している。これはリンクＬＡ１１の新設に起因するものである。
新設内部ノード情報は、新設する内部ノードの数とノードレコードを示し、図６の道路網ＧＡに図９の内部ノードＮＡ９、ＮＡ１０、ＮＡ１１を新設することを示している。
削除境界ノード情報は、削除する境界ノードの数とノード番号を示し、図６の道路網ＧＡのノードＮＡ７を削除することを示している。
新設境界ノード情報は、新設する境界ノードの数とノードレコードを示し、図６の道路網ＧＡに図９の境界ノードＮＡ１２を新設することを示している。
削除リンク情報は、削除するリンクの数とリンク番号を示し、図６の道路網ＧＡのリンクＬＡ１、ＬＡ４を削除することを示している。
新設リンク情報は、新設するリンクの数とリンクレコードを示し、図６の道路網ＧＡに図９のリンクＬＡ９、ＬＡ１０、ＬＡ１１、ＬＡ１２を新設することを示している。尚、リンクレコードの始点ノード番号（ＳＮ）および終点ノード番号（ＥＮ）は、内部ノード（Ｉ）と境界ノード（Ｂ）とを区別するノード番号種別と共に示している。
【０１８５】
実施の形態３における地図情報提供装置の基本動作は、実施の形態１の図１５に示したフローチャートと同じであるので、説明を省略するが、実施の形態１の場合と同様に、地図情報処理装置が所要領域の道路網データを保有していないときは、最新の道路網データを地図情報処理装置に提供し、地図情報処理装置が所要領域の道路網データを保有しているが最新の版の道路網データを保有していないときは、地図情報処理装置が保有している所要領域の道路網データを最新の版の道路網データに更新するための更新指示情報を提供することができ、地図情報処理装置が所要領域の道路網データを保有しているときは、最新の版の道路網データを提供する場合に比し地図情報処理装置と地図情報提供装置との通信時間を短縮することができる。
【０１８６】
また、図１５のステップＳＴ１０２、ＳＴ１０３、ＳＴ１０４、ＳＴ１０９により、例えば図２３〜図２５に示したようなデータ構造を有する道路網データ、即ち道路網の更新によって内部ノードの相対内部ノード番号および境界ノードのノード番号が共に変化せず、更新が容易であり、版数の異なる道路網データ間の整合性を保つことが可能な道路網データを、地図情報処理装置に提供することができる。
【０１８７】
実施の形態３における地図情報処理装置の基本構成は、実施の形態１の図２に示したものと同じであるので、以下では、主に異なる点について説明する。本実施の形態では、地図情報処理装置の地図情報記憶装置４には、各地図情報の道路網データとして、図２３〜図２５に示したようなデータ構造を有するデータが蓄積されており、プロセッサ５では上記のようなデータ構造を有する道路網データを用いて各種の処理を行う。
【０１８８】
実施の形態３による地図情報処理装置におけるプロセッサ５の基本動作は、実施の形態１の図１７に示したフローチャートと同じであるので、詳細な説明は省略するが、本実施の形態によれば、実施の形態１の場合と同様に、地図情報処理装置が所要領域の道路網データを保有していないときは、最新の道路網データを地図情報提供装置より取得し、地図情報処理装置が所要領域の道路網データを保有しているときは、地図情報処理装置が保有している所要領域の道路網データを最新の版の道路網データに更新するための更新指示情報を地図情報提供装置より取得することにより、地図情報処理装置が所要領域の道路網データを保有している場合は、最新の版の道路網データを取得する場合に比し地図情報処理装置と地図情報提供装置との通信時間を短縮することができる。
【０１８９】
また、図１７のステップＳＴ２０３、ＳＴ２０４、ＳＴ２０５、ＳＴ２０６により、道路網の更新に際し、相対内部ノード番号、境界ノードのノード番号に変化を来たさないデータ構造の道路網データを取得し、上記道路網データの更新を容易し、版数が異なる道路網データが混在するようになっても道路網データ間の整合性を保てるようにできる。
【０１９０】
以下、実施の形態３による地図情報処理装置におけるプロセッサ５の動作で、実施の形態１の場合と異なる点について主に説明する。
【０１９１】
図１７のステップＳＴ２１４では、ステップＳＴ２１３で取得した、ステップＳＴ２０１で決定された所要領域の経路計算系データに含まれる道路網データを用いて、ステップＳＴ２００で取得した出発地から目的地までの最適経路を、ダイクストラ法を用いた経路計算により求め、処理を終了する。
例えば、領域Ａ、Ｂ共に版数が１の図２３と図２４の道路網データ（以下、Ｃ３１の場合と称する。）、または領域Ａ、Ｂ共に版数が２の図２５の道路網データと図９の道路網ＧＢ１を表す実施の形態３による道路網データ（以下、Ｃ３２の場合と称する。）、または領域Ａに版数が２の図２５の道路網データ、領域Ｂに版数が１の図２４の道路網データ（以下、Ｃ３３の場合と称する。）、または領域Ａに版数が１の図２３の道路網データ領域Ｂに版数が２の図９の道路網ＧＢ１を表す道路網データ（以下、Ｃ３４の場合と称する。）を用いて、ノードＮＢ１２からノードＮＡ０への最適経路を、ダイクストラ法を用いた経路計算により求める。
【０１９２】
上記経路計算の過程で、当該領域のノードから他領域の隣接境界ノード至るとき、例えば図６の領域ＢのノードＮＢ８からその隣接境界ノードである図６の領域ＡのノードＮＡ６へ至るとき、上記Ｃ３１の場合においては、図２４のノードＮＢ８のノードレコードＮＲＢ８より隣接境界ノード番号（＝２）を求め、上記隣接境界ノード番号（＝２）が示す図２３のノード番号（＝２）のノードレコードＮＲＡ８対応するノードＮＡ８を隣接境界ノードとして求める。
また、例えば、Ｃ３３の場合においては、図６の領域ＢのノードＮＢ８からその隣接境界ノードである図９の領域ＡのノードＮＡ８へ至るとき、図２４のノードＮＢ８の境界ノードレコードＮＲＢ８り隣接境界ノード番号（＝２）を求め、上記隣接境界ノード番号（＝２）が示す図２５のノード番号（＝２）のノードレコードＮＲＡ８に対応するノードＮＡ８を隣接境界ノードとして求める。
【０１９３】
このように、同一の境界ノードのノード番号が版数により変化することがないため、隣接する領域の道路データの版数に関わらず隣接境界ノードを正しく求めることかでき、道路網データ間の不整合を来たさず、経路計算を正しく行うことができる。
【０１９４】
図２７は、図１７のステップＳＴ２１１における経路計算系データ中の道路網データに関する更新処理の一例を示すフローチャートである。
以下では、ステップＳＴ２０８で取得した提供情報に含まれる更新指示情報中にある図２６の道路データ更新指示情報を使用し、ステップＳＴ２１０で取得した経路計算系データ中の図２３の道路網データを更新する場合を例に、主に実施の形態１で説明した図１８のフローチャートの場合と異なる点について説明する。
【０１９５】
ステップＳＴ４００、ＳＴ４０１、ＳＴ４０２により、それぞれ実施の形態１で説明した図１８におけるステップＳＴ３００、ＳＴ３０１、ＳＴ３０２の場合と同様にして、リンク番号変換テーブルを作成し、図２５の道路網データヘッダが更新領域に得られる。
【０１９６】
ステップＳＴ４０３では、図２３の境界ノードのノードレコードを更新領域に格納する。但し、削除境界ノード情報によって示される削除する境界ノードのノードレコードの接続リンク数を０、隣接領域情報を該当するものなし、隣接境界ノード番号を該当するものなしとして格納する（境界ノード削除）。また、削除されない境界ノードのノードレコードの接続リンク番号は上記リンク番号変換テーブルに従い更新後の値に変更する。
【０１９７】
ステップＳＴ４０４では、図２６の新設境界ノード情報のノードレコードをステップＳＴ４０３で格納したノードレコードの後に格納する（境界ノード追加）。
上記により、道路網の更新により新設された境界ノードには、当該道路網が変化するまでに付与されたノード番号とは異なるノード番号を付与する。
【０１９８】
ステップＳＴ４０５では、図２３の内部ノードのノードレコードをステップＳＴ４０４で格納したノードレコードの後に格納する。このとき、図２６の削除内部ノード情報で指定された削除する内部ノードのノードレコードの代わりに、図２６の新設内部ノード情報の新設ノードレコードを格納する。上記処理で削除する内部ノードが複数ある場合は、新設内部ノード情報のノードレコードの先頭から順に削除する内部ノードのノードレコードの代わりに格納する。
尚、上記図２３の内部ノードのノードレコードを更新領域に格納する際には、ステップＳＴ４０１で作成したリンク番号変換テーブル、図２３の接続リンク番号情報に基づき、接続リンク数および接続リンク番号変更、接続リンク番号の追加を行ったものを格納する。
上記により、道路網の更新により新設された内部ノードに対して、不要となった内部ノードの相対内部ノード番号を付与する（内部ノード置き換え）。
【０１９９】
ステップＳＴ４０６では、図２６の新設内部ノード情報のノードレコードで、ステップＳＴ４０５で更新領域に格納されていないものを、ステップＳＴ４０５で格納したノードレコードの後に格納する（内部ノード追加）。
上記により、新設する内部ノードに対し当該道路網が更新されるまでに付与された相対内部ノード番号と異なる相対内部ノード番号を付与する。
【０２００】
上記ステップＳＴ４０３、ＳＴ４０４、ＳＴ４０５、ＳＴ４０６により、図２５のノード情報が更新領域に得られる。
上記により、内部ノードの相対内部ノード番号、境界ノードのノード番号を変化させることなくノード情報を更新する。
【０２０１】
ステップＳＴ４０７では、図２６の削除リンク情報が示すリンクレコードを、図２３のリンク情報から除いたものを更新領域に格納する（リンク削除）。
上記のように、内部ノードの相対内部ノード番号および境界ノードのノード番号は何れも道路網の更新により変化しないため、上記ステップＳＴ４０７においては、リンクレコードの始点ノード番号、終点ノード番号の変更を行わずにリンク情報を更新することができ、更新処理の負荷を低減することができる。
【０２０２】
ステップＳＴ４０８では、図２６の新設リンク情報に基づき、新設するリンクのリンクレコードをステップＳＴ４０７で格納したリンクレコードの後に追加する（リンク追加）。
【０２０３】
上記ステップＳＴ４０７、ＳＴ４０８により、図２５のリンク情報が更新領域に得られる。
【０２０４】
以上のようにして、図２３の道路網データを図２６の道路網データ更新指示情報により更新した図２５の道路網データが更新領域に得られ、道路網データの更新を終了する。
【０２０５】
上記動作により、道路網データの更新を容易に行なうことができ、版数の異なる道路網データに対し整合性のある道路網データを得ることができる。
【０２０６】
尚、上記実施の形態１、２、３において、地図情報処理装置ａ１が、自動車に搭載されて、車両が走行している道路および道路上の位置を同定するマップマッチング、出発値から目的地までの経路を算出する経路計算（経路探索）、その結果得られた好適な経路の候補を道路地図と共に表示装置の画面に表示する経路表示、好適な経路に従って出発値から目的地までの案内を行う経路誘導、および現在位置周辺の地図の表示処理等の各種のナビゲーション処理を行うカーナビゲーション装置である場合を例に説明したが、この発明を実施の形態に限定する意図ではなく、地図情報処理装置ａ１は、携帯電話、携帯情報端末等の移動体に設けられていてもよい。あるいは、地図情報処理装置ａ１は固定されたコンピュータ端末でもよい。これらの代替的な形態では、位置検出装置２は、地図情報処理装置ａ１が移動体である場合に設けられるが、固定された端末である場合には必要ではない。また、地図情報処理装置ａ１は、上記のような各種のナビゲーション処理のうちの少なくとも１つの処理を行うものであってもよい。
【０２０７】
また、地図情報記憶装置４がハードディスクドライブで構成されるとしたが、これに限るものではなく、例えばメモリカード、プロセッサの内部メモリなどの読み書き可能な記憶媒体であればよい。
【０２０８】
尚、実施の形態１、２、３のいずれかのデータ構造を有する道路網データは、記憶媒体に格納されて地図情報処理装置ａ１に入出力される、または通信手段を介して地図情報処理装置ａ１に送受信される。
【０２０９】
また、地図情報処理装置ａ１では、地図情報提供装置ａ２から取得した実施の形態１、２、３のいずれかのデータ構造を有する道路網データを更新してもよいし、あらかじめ地図情報記憶装置１に格納しておいた実施の形態１、２、３のいずれかのデータ構造を有する道路網データを更新するようにしてもよい。また、地図情報記憶装置１を、読み込み専用の記憶媒体の読み取り装置とし、あらかじめ上記読み込み専用の記憶媒体に格納しておいた実施の形態１、２、３のいずれかのデータ構造を有する道路網データを更新するようにしてもよい。
【０２１０】
また、更新指示情報を通信手段により地図情報提供装置から取得するようにしたが、更新指示情報を格納したＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、メモリカード等の記憶媒体から取得するようにしてもよい。
【０２１１】
また、地図情報提供装置ａ２から取得した更新指示情報を用いて道路網データを更新したが、地図情報処理装置ａ１を保有する移動体、人等が道路に沿って移動することにより位置検出装置２により得られる道路形状を利用して道路網データを更新してもよい。
【０２１２】
【発明の効果】
以上のように、本発明によれば、地図情報処理装置において処理される道路網データのデータ構造であって、道路網を複数の領域に分割し、隣接し合う道路網を接続するに際し、隣接する道路網から接続相手として指し示される当該道路網のノードを境界ノードと定義し、当該道路網が接続相手として指し示す隣接する道路網のノードを隣接境界ノードと定義し、当該道路網の境界ノード以外のノードを内部ノードと定義して、上記道路網データが表す道路網を構成する各ノードに対応して設けるデータの並びであるノード情報を設け、上記内部ノードに対応して設けるデータの並びの後に上記境界ノードに対応して設けるデータの並びを配置するようにし、上記各ノードにノード情報における対応するデータの並び順に基づいて定めたノード番号を付与し、上記ノード番号を用いて上記内部ノードおよび境界ノードを特定するようにし、上記境界ノードに対応したデータの並びの先頭を示すノード番号を基準にしたノード番号の相対値である相対境界ノード番号を上記境界ノードに付与し、上記相対境界ノード番号用いて上記隣接境界ノードを特定するようにしたので、境界ノードに比して数が非常に多い内部ノードに対応して設けるデータの並びの後に境界ノードに対応して設けるデータの並びを配置し、ノード番号を用いてノードを特定することにより、道路網データの更新において、それまでに存在していた内部ノードのノード番号が変化しないようにできるため、変更処理の負荷をはるかに軽減でき、道路網データの更新が容易になる。また、相対ノード番号を用いて隣接境界ノードを指定することにより、道路網が変化してもそれまでに存在していた境界ノードの相対境界ノード番号は変化しないようにできるために、版数の異なる道路網データ間の整合性を保つことが可能となる。従って、版数の異なる道路網データ間の整合性を保ちつつ、道路網データの更新を容易にすることができる。
【０２１３】
また、上記のデータ構造を有する既存の道路網データを、道路網の更新に対応してコンピュータを用いて更新する方法であって、上記道路網の更新により新設する内部ノードに対して、上記道路網の更新により不要となった内部ノードのノード番号または上記道路網の更新前までにおける内部ノードに付与されたノード番号と異なるノード番号を付与する手順と、上記道路網の更新により新設する境界ノードに対して、上記道路網の更新前までにおける境界ノードに付与された相対境界ノード番号と異なる相対境界ノード番号を付与する手順とを備えたので、内部ノードは境界ノードに比して数が非常に多く、道路網データの更新において、それまでに存在していた内部ノードのノード番号が変化しないため、変更処理の負荷をはるかに軽減でき、道路網データの更新が容易になる。また、道路網が変化してもそれまでに存在していた境界ノードの相対境界ノード番号は変化しないために、版数の異なる道路網データ間の整合性を保つことが可能となる。従って、版数の異なる道路網データ間の整合性を保ちつつ、道路網データの更新を容易にすることができる。
【０２１４】
また、上記道路網データが表す道路網の上記内部ノードに対応して設けるデータの並びである内部ノード情報と、上記道路網データが表す道路網の上記境界ノードに対応して設けるデータの並びである境界ノード情報とを設け、上記各内部ノードに、内部ノード情報における対応するデータの並び順に基づいて定めた内部ノード番号を付与し、上記各境界ノードに、境界ノード情報における対応するデータの並び順に基づいて定めた境界ノード番号を付与し、上記内部ノード番号を用いて上記内部ノードを特定するようにし、境界ノード番号を用いて上記境界ノードと隣接境界ノードを特定するようにしたので、内部ノードに対応して設けられたデータの並びと境界ノードに対応して設けられたデータの並びとを独立に設け、境界ノードと内部ノードに独立してノード番号を付与することにより、道路網データの更新において、それまでに存在していた内部ノードのノード番号および境界ノードのノード番号が共に変化しないようにできるため、変更処理の負荷をはるかに軽減でき、道路網データの更新が容易になる。また、境界ノード番号を用いて隣接境界ノードを指定することにより、版数の異なる道路網データ間の整合性を保つことが可能となる。従って、版数の異なる道路網データ間の整合性を保ちつつ、道路網データの更新を容易にすることができる。
【０２１５】
また、上記のデータ構造を有する既存の道路網データを、道路網の更新に対応してコンピュータを用いて更新する方法であって、上記道路網の更新により新設する内部ノードに対して、上記道路網の更新により不要となった内部ノードの内部ノード番号または上記道路網の更新前までにおける内部ノードに付与された内部ノード番号と異なる内部ノード番号を付与する手順と、上記道路網の更新により新設する境界ノードに対して、上記道路網の更新前までにおける境界ノードに付与された境界ノード番号と異なる境界ノード番号を付与する手順とを備えたので、道路網データの更新において、それまでに存在していた内部ノードのノード番号および境界ノードのノード番号が共に変化しないため、版数の異なる道路網データ間の整合性を保ちつつ、道路網データの更新を容易にすることができる。
【０２１６】
また、上記道路網データが表す道路網を構成する各ノードに対応して設けるデータの並びであるノード情報を設け、上記境界ノードに対応して設けるデータの並びの後に上記内部ノードに対応して設けるデータの並びを配置するようにし、上記各ノードにノード情報における対応するデータの並び順に基づいて定めたノード番号を付与し、上記ノード番号を用いて上記境界ノードおよび隣接境界ノードを特定するようにし、上記内部ノードに対応したデータの並びの先頭を示すノード番号を基準にしたノード番号の相対値である相対内部ノード番号を上記内部ノードに付与し、上記相対内部ノード番号用いて上記内部ノードを特定するようにしたので、道路網データの更新において、それまでに存在していた境界ノードのノード番号および内部ノードの相対内部ノード番号が共に変化しないようにできるため、版数の異なる道路網データ間の整合性を保ちつつ、道路網データの更新を容易にすることができる。
【０２１７】
また、上記のデータ構造を有する既存の道路網データを、道路網の更新に対応してコンピュータを用いて更新する方法であって、上記道路網の更新により新設する境界ノードに対して、上記道路網の更新前までにおける境界ノードに付与されたノード番号と異なるノード番号を付与する手順と、上記道路網の更新により新設する内部ノードに対して、上記道路網の更新により不要となった内部ノードの相対内部ノード番号または上記道路網の更新前までにおける内部ノードに付与された相対内部ノード番号と異なる相対内部ノード番号を付与する手順とを備えたので、道路網データの更新において、それまでに存在していた境界ノードのノード番号および内部ノードの相対内部ノード番号が共に変化しないため、版数の異なる道路網データ間の整合性を保ちつつ、道路網データの更新を容易にすることができる。
【０２１８】
また、上記のようなデータ構造を有する各領域の道路網データが格納された地図情報記憶部と、上記のようなデータ構造を有する各領域の道路網データを上記のような道路網データの更新方法によって地図情報処理装置に更新させるための道路網データ更新指示情報が格納された更新指示情報記憶部と、上記道路網データまたは道路網データ更新指示情報を送信する送信部とを備えたので、上記版数の異なる道路網データ間の整合性を保ちつつ、道路網データの更新を容易にすることができるという効果に加えて、地図情報処理装置が所要領域の道路網データを保有している場合には当該所要領域の道路網データ更新指示情報を送信し、地図情報処理装置が所要領域の道路網データを保有していない場合には当該所要領域の道路網データを送信することにより、地図情報の提供を受ける装置がすでに取得している所要領域の道路網データを最新の版にするのに、最新の版にするための情報を上記装置に提供するのに要する通信時間を短縮することができる地図情報提供装置が得られる。
【０２１９】
また、上記のようなデータ構造を有する道路網データ格納された地図情報記憶部と、上記地図情報記憶部に格納された道路網データを上記のような道路網データの更新方法によって地図情報処理装置に更新させるための道路網データ更新指示情報または道路網データを受信する受信部と、上記道路網データ更新指示情報に従って上記道路網データを更新する更新処理部とを備え、上記受信部は、上記地図情報記憶部が所要領域の道路網データを保有している場合には当該所要領域の上記道路網データ更新指示情報を受信し、上記地図情報記憶部が所要領域の道路網データを保有していない場合には当該所要領域の道路網データを受信するので、上記版数の異なる道路網データ間の整合性を保ちつつ、道路網データの更新を容易にすることができるという効果に加えて、すで取得しているメッシュの道路網データを最新の版にするのに、最新の版にするための情報を取得するのに要する通信時間を短縮することができる地図情報処理装置が得られる。
【図面の簡単な説明】
【図１】本発明の実施の形態１〜３に係る地図情報更新システムの構成を示すブロック図である。
【図２】本発明の実施の形態１〜３に係る地図情報処理装置の構成を示すブロック図である。
【図３】本発明の実施の形態１〜３に係る地図情報提供装置の構成を示すブロック図である。
【図４】本発明の実施の形態１〜３に係る地図情報の概略データ構造を示す図である。
【図５】実際の道路を示す地図である。
【図６】本発明に係る地図情報の道路データの作成のために仮想的にノード、リンクが割り振られた道路網の一例を示す図である。
【図７】本発明に係る地図情報の道路データの作成のために仮想的にノード、リンクが割り振られた道路網の別の例を示す図である。
【図８】本発明に係る地図情報の道路データの作成のために仮想的にノード、リンクが割り振られた道路網の更に別の例を示す図である。
【図９】本発明に係る地図情報の道路データの作成のために仮想的にノード、リンクが割り振られた更新後の道路網の一例を示す図である。
【図１０】本発明の実施の形態１に係る道路網ＧＡを表す版数が１の道路網データのデータ構造を示す図である。
【図１１】本発明の実施の形態１に係る道路網ＧＢを表す版数が１の道路網データのデータ構造を示す図である。
【図１２】本発明の実施の形態１に係る道路網ＧＡ１を表す版数が２の道路網データのデータ構造を示す図である。
【図１３】本発明の実施の形態１に係る道路網ＧＡ’を表す版数が１の道路網データのデータ構造を示す図である。
【図１４】本発明の実施の形態１に係る道路網ＧＡ”を表す版数が１の道路網データのデータ構造を示す図である。
【図１５】本発明の実施の形態１〜３に係る地図情報提供装置の動作を示すフローチャートである。
【図１６】本発明の実施の形態１に係る道路網データ更新指示情報のデータ構造の一例を示す図である。
【図１７】本発明の実施の形態１〜３に係る地図情報処理装置の動作を示すフローチャートである。
【図１８】本発明の実施の形態１および２に係る更新処理の一例を示すフローチャートである。
【図１９】本発明の実施の形態２に係る道路網ＧＡを表す版数が１の道路網データのデータ構造を示す図である。
【図２０】本発明の実施の形態２に係る道路網ＧＢを表す版数が１の道路網データのデータ構造を示す図である。
【図２１】本発明の実施の形態２に係る道路網ＧＡ１を表す版数が２の道路網データのデータ構造を示す図である。
【図２２】本発明の実施の形態２に係る道路網データ更新指示情報のデータ構造の一例を示す図である。
【図２３】本発明の実施の形態３に係る道路網ＧＡを表す版数が１の道路網データのデータ構造を示す図である。
【図２４】本発明の実施の形態３に係る道路網ＧＢを表す版数が１の道路網データのデータ構造を示す図である。
【図２５】本発明の実施の形態３に係る道路網ＧＡ１を表す版数が２の道路網データのデータ構造を示す図である。
【図２６】本発明の実施の形態３に係る道路網データ更新指示情報のデータ構造の一例を示す図である。
【図２７】本発明の実施の形態３に係る更新処理の一例を示すフローチャートである。
【符号の説明】
１  入力装置、２  位置検出装置、３  送受信装置、４  地図情報記憶装置、５  プロセッサ、６  出力装置、１０  送受信装置、１１  地図情報データベース（地図情報記憶部）、１２  更新指示情報データベース（更新指示情報記憶部）、１３  情報配信装置。
【図１】
2004212456.tif 000003
【図２】
2004212456.tif 000004
【図３】
2004212456.tif 000005
【図４】
2004212456.tif 000006
【図５】
2004212456.tif 000007
【図６】
2004212456.tif 000008
【図７】
2004212456.tif 000009
【図８】
2004212456.tif 000010
【図９】
2004212456.tif 000011
【図１０】
2004212456.tif 000012
【図１１】
2004212456.tif 000013
【図１２】
2004212456.tif 000014
【図１３】
2004212456.tif 000015
【図１４】
2004212456.tif 000016
【図１５】
2004212456.tif 000017
【図１６】
2004212456.tif 000018
【図１７】
2004212456.tif 000019
【図１８】
2004212456.tif 000020
【図１９】
2004212456.tif 000021
【図２０】
2004212456.tif 000022
【図２１】
2004212456.tif 000023
【図２２】
2004212456.tif 000024
【図２３】
2004212456.tif 000025
【図２４】
2004212456.tif 000026
【図２５】
2004212456.tif 000027
【図２６】
2004212456.tif 000028
【図２７】
2004212456.tif 000029