JP4543637B2 - 地図情報処理装置 - Google Patents

Description

この発明は、カーナビゲーション装置、携帯電話、携帯情報端末等の移動体または固定されたコンピュータ端末で使用される地図データのデータ構造、地図データの更新方法、地図データの格納媒体、および地図情報処理装置に関するものである。

カーナビゲーション装置、携帯電話、携帯情報端末等の移動体または固定されたコンピュータ端末で使用される従来の地図データでは、道路上の地点を表すノード、上記地点間の道路を表すリンク、道路の連なりをリンクの連なりとして表したリンク列を用いて道路網を表しており、リンク列を表すリンク列データには、リンク列に含まれるノード、リンクに関わる情報を格納しており、また、リンク列データに格納した、リンク列間のノードの同一性を示す同一ノード情報により道路網のリンク同士の接続関係を表している（例えば、特許文献１、非特許文献１参照）。

ノードにおけるリンク間の通行規制を表すために、従来の地図データでは同一ノード情報によるノードの巡回順を用いてノードへの進入リンク、脱出リンクを特定している（例えば、非特許文献１参照）。

階層化された道路網間のリンクの対応付け、経路計算用など別の用途に設けた道路網との間のリンクの対応付けのために、従来の地図データでは、最下層の道路網を構成する各リンクに全国でユニークなリンク番号をリンク列内で連続するように付与している。さらに、所定範囲のリンク番号をリンクに付与し、リンクが分割された場合でも所定範囲内のリンク番号を付与することによりリンク列内でのリンク番号の連続性を保っている（例えば、非特許文献１、特許文献２参照）。

交差点での経路案内を行う経路誘導データをノードに関連付けるために、従来の地図データでは経路誘導データの格納位置を表す情報をリンク列内のノードに設けている（例えば、非特許文献１参照）。

特開平８−２９２７１６号公報 特開２００２−１７５５９３号公報 "Kiwi Format Ver.1.22 7.2章 道路データフレーム"、Kiwi-Wコンソーシアム２００３年７月２３日検索インターネット＜ＵＲＬ：http//kiwi-w.mapmaster.co.jp＞

特許文献１、非特許文献１に記載の従来の地図データでは、リンク列を表すリンク列データには、リンク列に含まれるノードを表すノードデータとリンクを表すリンクデータが混在して格納されている。
このため、複数のリンク列が交差するノードのノードデータは複数のリンク列に含まれ、同じ内容のノードデータが重複して格納されることになり、ノードデータの更新時には複数のリンク列のノードデータを更新しなければならず、更新処理が煩雑になるという問題点があった。

また、特許文献１、非特許文献１に記載の従来の地図データでは、リンク列の各ノードに設けた同一ノード情報によりリンク列のノードと同一である他のリンク列のノードを示すようにし、同一ノード情報の指示に従いあるノードから順次他のリンク列のノードを辿り、最初のノードに戻るまでに出現したノードをすべて同一とし、これらのノードに接続している各リンク列のリンク同士が接続していることが判るようにしている。

このため、リンク列Ｘの新設時において、リンク列ＸのあるノードＡの同一ノード情報が示す既存リンク列ＹのノードＢを指す場合、ノードＢの同一ノード情報から出発して順次同一ノード情報が示す他の既存リンク列のノードを辿っていき、既存リンク列ＹのノードＢを指すリンク列ＺのノードＣを見つけ、リンク列ＺのノードＣの同一ノード情報をリンク列ＸのノードＡを指すように変更しなければならず、リンク列新設時に煩雑な更新処理を要するという問題点があった。

また、非特許文献１に記載の従来の地図データでは、ノードへの進入リンク、脱出リンクを同一ノード情報によりノードを辿ったときに上記ノードが出現する順番を用いて表している。同一ノード情報により辿る中に出現するリンク列の廃止、新設により上記順番が変化するため、既存の進入リンクから脱出リンクへの通行規制を表す情報も変更しなければならず、更新処理が煩雑となるという問題点があった。

また、特許文献１、非特許文献１に記載の従来の地図データでは、リンクが分割されたときにそれ以降に連なるノードのリンク列内ノード番号、格納位置が変化するため、上記ノードで交差する他の既存リンク列の同一ノード情報を変更しなければならず、更新処理が煩雑となるという問題点があった。

また、特許文献２に記載の従来の地図データでは、リンク識別子として、リンクにそのリンク長に比例した範囲のリンク番号を付与しているため、リンク長の長い山間部の道路、高速道路のリンク番号の範囲はより広いが、リンク長が短い市街地のリンク番号の範囲はより狭くなるため、既存道路に交差する道路の新設や拡幅される頻度が多い市街地では、リンクが分割される頻度が多く必要な回数だけリンクを分割できない場合が生じ、このような場合、分割して得られるリンクに新たなリンク番号が付与されることになり、これらのリンクを含む上層のリンク、経路計算用の道路網のリンクに対しても新たなリンク番号の付与が必要となり、更新処理が煩雑になるという問題点があった。

また、非特許文献１に記載の従来の地図データでは、ノード関連情報として交差点での案内情報を示す経路誘導データが設けられ、リンク列データ内にリンク列内の各ノード毎に誘導データの格納位置を示すアドレス情報を設けているため、経路誘導データを廃止・新設により既存の誘導データの格納位置が変化し、既存のリンク列データの誘導データの格納位置を示すアドレス情報を変更しなければならず、更新処理が煩雑となるという問題があった。

この発明は、上記のような問題点を解消するためになされたもので、地図データの更新を容易にすることを目的とするものである。

この発明に係る地図情報処理装置は、道路上の地点を表すノードに関わる情報を示すノードデータと、上記地点間の道路を表すリンクに関わる情報を示すリンクデータとを用いて道路網を表す地図データにおいて、上記道路網における道路の連なりを上記リンクの連なりとして表したリンク列に対し、上記リンク列を構成するリンクのリンクデータをリンクの連なりの順に応じて配置したリンク列データを設け、上記道路網の各ノードのノードデータをリンク列データとは別に設け、上記道路網の各ノードのノードデータにノードを識別するためのノードデータの並び順を示すノード識別子を付与し、上記リンク列データ内のすべてのリンクデータがリンク列の向きに応じて定められたリンク端の１つのノードのノード識別子を示す情報を有するようにした地図データを取得する地図データ取得手段と、上記地図データ取得手段により取得した地図データのリンクデータを参照してリンクデータの形状情報を取得するリンクデータ参照手段と、上記地図データ取得手段により取得した地図データのノードデータを参照してノードデータのノード座標を取得するノードデータ参照手段とを有し、上記リンクデータ参照手段とノードデータ参照手段とによりリンクデータの形状情報とノードデータのノード座標とを用いて道路を描画する地図情報処理を行う地図情報処理装置において、上記地図データは、リンクが分割されたとき、リンクを分割してできたリンクからなるリンク列である分割リンク列のリンク列データを設け、分割されたリンクのリンクデータが上記分割リンク列に関わる情報を有するようにしたものである。

この発明によれば、地図データをリンク列データと、リンク列データとは別に設けた各ノードのノードデータとからなるデータ構造とし、上記リンク列のリンクデータがリンク列の向きに応じて定めたリンク端の１つのノードのノードの識別子を有するようにしたため、ノードデータを重複して格納する必要がなく地図データを容易に更新できるという効果がある。

以下、この発明の実施の一形態を説明する。
実施の形態１．
図１は、この発明の実施の形態１による地図情報処理装置の構成を示すブロック図である。

図１において、入力装置１は、使用者の操作または指示に従ってプロセッサ５に指示信号を与える。具体的には、図示しないが、入力装置１は使用者の音声を認識して音声基づく指示信号を出力する音声認識装置、使用者の手動操作により指示信号を出力するボタン、その他の適切な入力装置の少なくともいずれかを有していてよい。

位置検出装置２は、例えばＧＰＳ（Global Positioning System）受信機、車速センサ、角速度センサを用いて当該地図情報処理装置を搭載している車両の現在位置を検出し、検出した位置情報をプロセッサ５に提供する。

地図データを読み取る地図データ読み取り手段および地図データを取得する地図データ取得手段および地図更新データを取得する地図更新データ取得手段としての地図情報記憶装置３は、例えば、記憶媒体としてハードディスクを用いたハードディスクドライブにより構成され、予め地図情報を格納しておき、更新情報取得装置４により取得された地図更新情報を格納する。
更新情報取得装置４は、例えば、ＤＶＤ（Digital Versatile Disk）ドライブにより構成され、更新用ＤＶＤ−ＲＯＭ（Read Only Memory）に格納された地図更新情報を読み取り、地図更新情報を取得する。

地図データ更新手段としてのプロセッサ５は、位置検出装置２から得られた現在位置と地図情報記憶装置３から読み出した地図情報を用いて各種の地図情報処理を行う。

地図情報処理としては、位置検出装置２から得た位置情報と地図データに基づいた車両の現在位置を推定するマップマッチング、出発値から目的地までの経路を算出する経路計算（経路探索）、その結果得られた好適な経路の候補を道路地図と共に表示装置の画面に表示する経路表示、好適な経路に従って出発値から目的地までの案内を行う経路誘導、および現在位置周辺の地図の表示処理等が含まれる。

また、更新情報取得装置４によりＤＶＤ−ＲＯＭから読み取った地図更新情報を地図情報記憶装置３に格納しておき、上記地図情報処理時に地図情報記憶装置３から地図情報と地図更新情報を読み取り、地図更新情報を用いて地図情報を更新する。

出力装置６は、プロセッサ５の地図情報処理出力に従って、使用者に情報を提示する。具体的には、図示しないが、出力装置６は、地図、現在位置、経路、案内情報等を表示する表示装置、および使用者に音声で指示または案内を行う音声発生装置を有していてよい。

以下、この発明の実施の形態１による地図データのデータ構造について説明する。
図２は地図情報記憶装置３に格納された地図情報の概略データ構造を示す。地図情報として、地図管理情報、１以上の地図データ、１以上の経路計算データを有している。

地図データは、道路網の詳しさの度合いにより階層化されており、階層毎に全国を幾つかの領域に分割し、階層ごとに各領域に対応して設けられ、各領域における道路網は道路上の地点を表すノードと、上記地点間の道路を表すリンクと、道路の連なりをリンクの連なりとして表したリンク列とを用いて表され、経路計算データも同様に道路網の詳しさの度合いにより階層化されており、階層毎に全国を幾つかの領域に分割し、階層ごとに各領域に対応して設けられ、各領域の道路網は道路上の地点を表すノードと、上記地点間の道路を表すリンクとを用いて表される。

地図管理情報は階層毎に各地図データ、経路計算データを管理するデータで、各領域と各地図データ、経路計算データを対応付ける情報、各地図データ、経路計算データの当該地図情報における格納位置、データサイズを階層毎に有している。
また、当該地図情報の版数を示す版数情報等を有している。

図２に示すように、地図データは、マップマッチングや道路の表示に使用する道路形状、道路の接続関係等を表す情報を有する道路網データ、河川、海等の地図背景を表示するための背景データ、地名等の名称を文字で表示するための名称データ、交差点等での経路案内を行うための経路誘導データ等を有する。

経路計算データは、上記道路網データとは異なるデータ構造で経路計算用の道路網を表すデータあり、経路計算用の道路網のリンクに対応する上記道路網データのリンクのリンク番号を有し、相互の道路網のリンクを対応付けている。

図３は、最も詳細な道路網を表す最下層の矩形の領域Ａの地図データが表す道路網の例である。
図３において、ノードＮ０〜Ｎ７とリンクＬ００、Ｌ０１、Ｌ０２、Ｌ１０、Ｌ２０、Ｌ３０、Ｌ３１からなる道路網で、リンクＬ００、Ｌ０１、Ｌ０２はリンク列０を、リンクＬ１０はリンク列１を、Ｌ２０はリンク列２を、Ｌ３０、Ｌ３１はリンク列３を形成する。

各リンク列には、リンク列の終点ノードを始点ノードとするリンクが存在するものと仮定し、これを仮想リンクと呼ぶ。仮想リンクは終点ノードを持たないものとする。以下では、リンク列は仮想リンクも含むものとして扱う。

図３において、リンク列０のノードＮ３を始点ノードとするリンクを仮想リンクＬ０２’とし、リンク列０はリンクＬ００、Ｌ０１、Ｌ０２と仮想リンクＬ０２’からなるものとして扱う。

同様にリンク列１、２、３に対し、それぞれ仮想リンクＬ１０’、Ｌ２０’、Ｌ３１’の存在を仮定する。

リンク列の両端のノードの一方を始点とし、他方を終点とするとき、始点から終点へ向かう方向をリンク列の向きとする。

図３において、実線の矢印がリンク列の向きを表し、例えばリンク列０の始点ノードはＮ０、終点ノードはＮ３、ノードＮ０からノードＮ３へ向かう方向がリンク列０の向きである。

リンク列の向きと同一方向を順方向と呼び、リンク列の向きの反対方向を逆方向と呼ぶ。
リンクの向きはリンク列の向きと同一とする。従って、リンクの始点ノードは、リンクのリンク列始点側のノードであり、終点ノードはリンク列の終点側のノードである。

図３において、リンクＬ０１の始点ノードはＮ１で終点ノードはＮ２であり、リンクＬ０１の順方向はノードＮ１からノードＮ２へ向かう方向となる。

あるノードＮに接続するリンクに関し、ノードＮに対し上記リンクが所属するリンク列の順方向側にあるリンクをノードＮの順方向リンク、逆方向側にあるリンクをノードＮの逆方向リンクと呼ぶ。ノードＮの順方向リンクは、ノードＮを含むリンク列の数だけ存在する。

図３において、ノードＮ１に接続するリンクＬ００、Ｌ０１はリンク列０に属し、ノードＮ１に対しリンクＬ０１はリンク列０の順方向側にあるのでノードＮ１の順方向リンク、リンクＬ００はリンク列０の逆方向側にあるのでノードＮ１の逆方向リンクである。同様にリンクＬ３０はノードＮ１の逆方向リンク、リンクＬ３１はノードＮ１の順方向リンクである。ノードＮ１の順方向リンクは、リンクＬ０１、Ｌ３１の２つである。

あるノードＮに接続する同一リンク列に属するリンクＬｘ、Ｌｙにおいて、リンクＬｘをノードＮの逆方向リンク、リンクＬｙをノードＮの順方向リンクとするとき即ちリンクＬｘがリンクＬｙの前方に位置するとき、リンクＬｘをリンクＬｙの前方リンクと呼び、リンクＬｙをリンクＬｘの後方リンクと呼ぶ。

図３において、ノードＮ１に接続するリンク列０のリンクＬ００、Ｌ０１において、リンクＬ００はリンクＬ０１の前方リンクであり、リンクＬ０１はリンクＬ００の後方リンクである。

あるノードＮの逆方向リンクはノードＮの順方向リンクの前方リンクとなっており、ノードＮに接続するリンクは、ノードＮの順方向リンクとその前方リンクからなる。従って、ノードの順方向リンク特定することによりノードに接続するすべてのリンクを特定できる。

図３において、ノードＮ１に接続するリンクＬ００、Ｌ０１、Ｌ３０、Ｌ３１において、ノードＮ１の順方向リンクＬ０１、Ｌ３１を特定すれば、リンクＬ００、Ｌ３０はリンクＬ０１、Ｌ３１の前方リンクとして求めることができる。

ノードに接続するリンクを識別するために、ノード毎にノードに接続する各リンクにユニークなノード単位リンク識別子を付与する。但し、ノードに接続するリンクは、上記のようにノードの順方向リンクで特定されるため、ノード単位リンク識別子として、ノードの順方向リンクにのみそれらを識別するための番号を付与し、この番号をノード単位リンク番号と呼ぶ。

また、特定するリンクが、ノード単位リンク番号が示すリンク（以下自リンクと呼ぶ）であるか、またはノード単位リンク番号が示すリンクの前方リンクであるかの何れかを示す情報を前方指定と呼ぶ。
ノードに接続するリンクは、ノード単位リンク番号と前方指定により特定することができる。

図３において、ノードＮ１の順方向リンクＬ０１、Ｌ３１にそれぞれノード単位リンク番号０、１のノード単位リンク番号を付与し、ノードＮ２の順方向リンクＬ０２、Ｌ１０’、Ｌ２０にそれぞれ０、１、２のノード単位リンク番号を付与する。

ノードＮ１において、リンクＬ００はノード単位リンク番号＝０、前方指定＝前方リンクとすることにより特定でき、リンクＬ３１はノード単位リンク番号＝１、前方指定＝自リンクとすることにより特定できる。

図３において、領域Ｂは領域Ａの下側に隣接する領域であり、ノードＮ４は領域Ａの境界上に、ノードＮＸは領域Ｂの境界上に設けられたノードである。領域の境界上にあるノードを境界ノード、境界を含まない領域内部にあるノードを内部ノードと呼ぶ。

ノードＮ４とノードＮＸは同一道路の同一地点即ち道路と領域Ａと領域Ｂの境界線の交点に設けられたノードで、ノードＮ４とノードＮＸを介して領域Ａ、Ｂの道路網は結合される。ノードＮＸをノードＮ４の隣接境界ノードと呼ぶ。
尚、境界ノードには、ただ１つのリンクが接続するものとする。

地図情報の道路網データにより表される全領域のすべてのリンクを識別するためのリンク識別子として、各リンクに固有の範囲のリンク番号と呼ぶ番号を付与する。実施の形態１では、各リンクに予め定めた一定範囲のリンク番号を付与するもので、リンク列内の各リンクにリンク列の向きの昇順に連続したリンク番号を付与する。但し、仮想リンクにはリンク番号を付与しない。

上記予め定めた一定範囲をリンク番号設定定数と呼び、領域ごとに定めるものとする。

本実施の形態１では、リンク番号設定定数を２５６とし、図３のリンク列０のリンクＬ００、Ｌ０１、Ｌ０２にはそれぞれ、０〜２５５、２５６〜５１１、５１２〜７６７のリンク番号を、リンク列１のリンクＬ１０には７６８〜１０２３のリンク番号を、リンク列２のリンクＬ２０には１０２４〜１２７９のリンク番号を、リンク列３のリンクＬ３０、Ｌ３１には１２８０〜１５３５、１５３６〜１７９１のリンク番号を付与する。他の地図データのリンクにも上記とは異なるリンク番号を同様にして付与する。
以下では図３の各リンクに上記リンク番号が付与されているものとする。

図４は、道路網データのデータ構造の一例を示す図である。道路網データは、道路網データヘッダ、ノードテーブル、ノード付加リスト、リンク列テーブル、リンク列付加リストからなる。

道路網データヘッダは道路網を構成するノードの数、ノード付加リストのデータサイズ、道路網を構成するリンク列の数、リンク列付加リストのデータサイズ、リンク番号設定定数等を格納したデータである。

図５は図３の道路網を表す道路網データのノードテーブル、ノード付加リストのデータ構造の一例を示す図である。

ノードテーブルはノードに対応して設けた固定長のノードレコードの並びで、ノード付加リストはノードに対応して設けた可変長のノード付加レコードの並びである。

図５において、図３のノードＮ０〜Ｎ７に対応して、ノードレコード＃０〜＃７、ノード付加レコード＃０〜＃７が設けられる。

ノードに関わる情報を固定長部と可変長部に分け、固定長部をノードレコードに、可変長部をノード付加レコードに格納している。ノードレコードとノード付加レコードでノードデータを形成する。

ノードを識別するためのノード識別子として対応するノードデータの並び順を用い、これをノード番号と呼ぶ。但し、ノードデータはノードテーブルとノード付加リンクと分けて格納されるため、ノードデータの並び順としては、そのノードデータを構成するノードレコードのノードテーブルにおける並び順を用いる。図３のノードＮ０、Ｎ１、・・・、Ｎ７のノード番号は、それぞれのノードレコードの並び順である０、１、・・・、７となる。

図６は図３の道路網を表す道路網データのリンク列テーブル、リンク列付加リストのデータ構造の一例を示す図である。

リンク列テーブルはリンク列に対応して設けた固定長のリンク列レコードの並びで、リンク列付加リストはリンク列に対応して設けた可変長のリンク列付加レコードの並びである。

図６において、図３のリンク列０〜３に対応して、リンク列レコード＃０〜＃３、リンク列付加レコード＃０〜＃３が設けられる。
リンク列を識別するためのリンク列識別子として、対応するリンク列レコードの並び順を用い、これをリンク列番号と呼ぶ。

図３のリンク列０、リンク列１、リンク列２、リンク列３のリンク列番号はそれぞれ０、１、２、３である。

リンク列に関わる情報を固定長部と可変長部に分け、固定長部をリンク列レコードに、可変長部をリンク列付加レコードに格納している。リンク列レコードとリンク列付加レコードでリンク列データを形成する。

上記のように、ノードデータとリンク列データは独立して格納するため、１つのノードに対して１つのノードデータが格納され、同一のノードデータが重複して格納されることはない。

図７は、リンク列レコードのデータ構造の一例を示す図で、リンク列レコードはリンク列状態、リンク列種別を有する。

リンク列状態は、リンク列の状態が存続、廃止のいずれであるかを示し、存続は当該リンク列が存続していること、廃止は当該リンク列が廃止されていることをを意味する。

リンク列種別は、当該リンク列の道路種別を示し、高速道路（０）、都市高速道路（１）、国道（２）、主要地方道（３）、都道府県道（４）、一般道（５）等々のいずれに該当するかを示す。尚、上記カッコ内の値はリンク種別としてリンク列レコードに格納される値を示す。

リンク列が廃止されてもそのリンク列レコードは削除せずリンク列状態を廃止とするものとし、リンク列の廃止により既存のリンク列のリンク列番号を変化しないようにする。
また、リンク列が廃止されたときは、そのリンク列付加レコードは削除するものとし、不要なデータの保持を防止し、更新後の道路網データのデータサイズをより小さくする。

また、新設するリンク列のリンク列レコードはリンク列テーブルの末尾に追加するものとし、既存リンク列のリンク列番号の変化を防止する。

図８はリンク列付加レコードのデータ構造の一例を示す図で、リンク列付加レコードは、リンク列付加ヘッダ、リンクテーブル、リンク付加リストよりなる。

リンク列付加ヘッダは、リンク列付加レコードサイズ、リンクレコード数、最小リンク番号、最大リンク番号、デフォルト幅員情報、路線番号を有する。

リンク列付加レコードサイズは、当該リンク列付加レコードのデータサイズを示す。

リンクレコード数は、当該リンク列付加レコードのリンクテーブルが有するリンクレコードの数を示す。

最小リンク番号は、当該リンク列のリンクに付与されたリンク番号の最小値を示す。
最大リンク番号は、当該リンク列のリンクに付与されたリンク番号の最大値を示す。
デフォルト幅員情報は当該リンク列の道路幅員を示す。
路線番号は当該リンク列の道路番号を示す。

リンクテーブルはリンク列内のリンクに対応して設けた固定長のリンクレコードの並びで、リンク付加リストはリンク列内のリンクに対応して設けた可変長のリンク列付加レコードの並びである。

リンクに関わる情報を固定長部と可変長部に分け、固定長部をリンクレコードに、可変長部をリンク付加レコードに格納している。リンクレコードとリンク付加レコードでリンクデータを形成する。

リンクテーブルは、当該リンク列の順方向のリンクの並びの順に、リンクに対応して設けたリンクレコードを配置したデータである。

リンク列内のリンクを識別するためのリンク列内リンク識別子として、リンクに対応するリンクレコードの並び順を用い、これをリンク列内リンク番号と呼ぶ。このように、リンク列内リンク識別子即ちリンク列内リンク番号はリンク列の向きに依存してリンクに付与される。

リンク付加テーブルは、当該リンク列の順方向のリンクの並びの順に、リンクに対応して設けたリンク付加レコードを配置したデータである。但し、リンク付加レコードが不要なリンクのリンク付加レコードは配置しない。

リンクが廃止または分割された場合、そのリンクレコードは削除せずリンク状態を廃止または分割とするものとし、リンクの廃止または分割により既存のリンクのリンク列内リンク番号を変化しないようにする。

また、リンクが廃止または分割されたときは、そのリンク付加レコードを削除するものとし、不要なデータの保持を防止し、更新後の道路網データのデータサイズをより小さくする。

リンクレコードは、リンク状態、リンク付加有無情報、分割リンク列番号、リンク種別、一方通行情報、始点ノード番号、リンク付加ポインタを有する。

リンク状態は、当該リンクが存続、廃止、分割のいずれの状態にあるかを示す。存続は当該リンクが存続していること、廃止は当該リンクが廃止されていることを、分割は当該リンクが分割されていることを意味する。

リンク付加有無情報は、当該リンクに対応するリンク付加レコードの有無を示す。リンク状態が廃止、分割であるリンク、リンク状態が存続でありリンク付加レコードに格納すべき情報を持たないリンク、仮想リンクに対してはリンク付加レコードを設けない。

リンク状態と分割リンク列番号とで、分割リンク列に関わる情報を表し、分割リンク列番号はリンク列状態が分割のときにのみ有効で、当該リンクを分割して得られたリンクからなるリンク列のリンク列番号を示す。

尚、リンクを分割して得られたリンクからなるリンク列を分割リンク列と呼ぶ。

上記のように、分割リンク列に関わる情報として、リンク状態を有することによりリンクが分割されているか否かが分かり、分割リンク列番号を有することにより分割リンク列のリンク列レコードの所在が直ちに分かる。

リンク種別は、上下線非分離本線リンク（０）、上下線分離本線リンク（１）、本線間渡りリンク（２）、交差点内リンク（３）等の道路構造等に依拠するリンクの種類を示す。

一方通行情報は、当該リンクの一方通行規制が、規制なし（０）、順方向への通行禁止（１）、逆方向への通行禁止（２）のいずれかであるかを示す。

始点ノード番号は、当該リンクの始点ノードのノード番号を示す。このように、リンクレコードは、リンク列の向きに応じ定めた当該リンク端の１つのノードである上記始点ノードのノード番号を有している。リンクの終点ノードのノード番号は後方リンクのリンクレコードの始点ノード番号から求めることができるため、リンクレコードには終点ノードのノード番号を保有せず、始点ノードのノード番号のみを保有させることにより、道路網データのデータサイズを削減している。

リンク付加ポインタは、当該リンクに対応するリンク付加レコードのリンク付加リストにおける格納位置であるリンク付加リスト先頭を基準としたアドレスを示す。尚、上記カッコ内の値はリンク種別、一方通行情報としてリンクレコードに格納される値を示す。

リンク付加レコードは、リンク付加ヘッダ、リンク形状情報、リンク番号情報、幅員情報を有する。

リンク付加ヘッダは、リンク付加レコードのデータサイズを示すリンク付加レコードサイズ、リンク形状情報の有無を示すリンク形状有無情報、リンク番号情報の有無を示すリンク番号有無情報、幅員情報の有無を示す幅員有無情報を有する。

リンク形状情報は、当該リンクの道路形状を示し、道路形状を折れ線で近似したときの各折れ線の頂点の地理上の位置を表す補間点座標の並びと補間点座標の数を有する。道路形状が直線となる場合はリンク形状情報は設けない。

リンク番号情報は、当該リンクのリンク番号の最小値を示す。リンク番号情報が存在するときは、当該リンクのリンク番号の最小値はリンク番号情報が示す値となり、最大値は当該リンクの後方リンクの最小リンク番号の最小値から１を減じたものとなる。但し、リンク列の終点のノードを終点ノードとするリンクのリンク番号の最大値はリンク付加ヘッダの最大リンク番号で与えられる。

リンク番号情報が存在しないときは、リンク列付加ヘッダの最小リンク番号をＬＩＤＭＩＮ、当該リンクのリンク列内リンク番号をＬＮとすれば、当該リンクのリンク番号の最小値、最大値を下記（式１）、（式２）により定める。
最小値 ＝ ＬＩＤＭＩＮ＋リンク番号設定定数×ＬＮ ・・・（式１）
最大値 ＝ ＬＩＤＭＩＮ＋リンク番号設定定数×（ＬＮ＋１）−１・・・（式２）

幅員情報は、当該リンクの道路幅員を示すもので、当該リンクの道路幅員は、幅員情報が存在するときには、この幅員情報が示す値とし、幅員情報が存在しないときには、リンク列付加ヘッダのデフォルト幅員情報が示す値とする。

図９は図６のリンク列レコードの格納例を示す図である。図９において、図３のリンク列０〜３が存続しており、リンク列レコード＃０〜＃３のリンク列状態に０（存続）を格納する。リンク列０は都道府県道のリンクからなり、リンク列レコード＃０のリンク列種別に４（都道府県道）を格納する。リンク列１〜３は一般道のリンクからなり、リンク列レコード＃１〜＃３のリンク列種別に５（一般道）を格納する。

図１０は図６のリンク列０のリンク列付加レコード＃０の格納例を示す図である。図１０において、リンク列０のすべてのリンクが存続しているとし、リンク列０のリンク列付加レコードのデータサイズがｍｌａｓ０、リンク列０のすべてのリンクの道路種別が都道府県道、リンク種別が上下線非分離本線、一方通行規制がないものとしている。

また、リンク列０のリンクＬ０１以外のリンクの道路幅員がｄｗ０でリンクＬ０１の道路幅員がｗ０１、リンク列０のすべてのリンクの路線番号がｒｎ０、リンクＬ００、Ｌ０１の道路形状がそれぞれリンク形状情報ｓｉ００、ｓｉ０１で表され形状で、リンクＬ０２の道路形状は直線でリンク形状情報を有しないものとしている。

図１０のリンク列付加ヘッダには、リンク列付加レコードサイズとしてｍｌａｓ０が、リンクレコード数として仮想リンクのリンクレコードを含めた値４を、最小リンク番号としてリンクＬ００のリンク番号の最小値０を、最大リンク番号としてリンクＬ０２のリンク番号の最大値７６７を、デフォルト幅員情報として幅員ｄｗ０を、路線番号としてｒｎ０を格納する。

図１０のリンクテーブルには、リンクＬ００、Ｌ０１、Ｌ０２、仮想リンクＬ０２’のリンクレコード＃０〜３を設ける。リンクＬ００、Ｌ０１、Ｌ０２、仮想リンクＬ０２’のリンク列内リンク番号はそれぞれ０、１、２、３となる。

リンクレコード＃０〜３においても、リンク状態に０（存続）を、リンク種別に０（上下線非分離本線）、一方通行情報に０（規制無し）を格納し、分割リンク番号には無効を表す特定の値である無効値を格納する。

リンクＬ００、Ｌ０１、Ｌ０２、仮想リンクＬ０２’の始点ノードはそれぞれＮ０、Ｎ１、Ｎ２、Ｎ３であり、リンクレコード＃０〜３の始点ノード番号には、それぞれノードＮ０、Ｎ１、Ｎ２、Ｎ３のノード番号０、１、２、３を格納する。

リンクＬ０２はリンク形状情報を有せず、幅員はデフォルト幅員情報が示す幅員ｄｗ０であるためリンク付加レコードは不要となり、リンクレコード＃２のリンク付加有無情報に０（無し）を格納する。また、リンクレコード＃３は仮想リンクに対応するため、リンク付加有無情報に０（無し）を格納する。

リンクＬ００はリンク形状情報を有し、リンクＬ０１はリンク形状情報を有するとともに幅員がデフォルト幅員情報と異なる幅員ｗ０１であるため幅員情報も有する。従ってリンクレコード＃０、１のリンク付加有無情報に１（有り）を格納し、リンクＬ００、Ｌ０１に対してリンク付加レコード＃０、１を設ける。リンクレコード＃０、１のリンク付加ポインタには、それぞれリンク付加レコード＃０、１のアドレスｐ０、ｐ１が格納される。リンクレコード＃３、４のリンク付加ポインタには、該当するリンク付加レコードがないため任意の値を格納する。

図１０のリンク付加レコード＃０において、当該リンク付加レコードのデータサイズｌａｓ００を設定しリンク形状情報のみを有するように設定したリンク付加ヘッダを格納し、リンク形状情報にｓｉ００を格納する。

図１０のリンク付加レコード＃１において、当該リンク付加レコードのデータサイズｌａｓ０１を設定しリンク形状情報と幅員情報を有るように設定したリンク付加ヘッダを格納し、リンク形状情報にｓｉ０１を、幅員情報にｗ０１を格納する。

図１１はノードレコードのデータ構造の一例を示す図である。ノードレコードはノード状態、境界情報、誘導有無情報等を有する。

ノード状態は、ノードが存続しているか、廃止されたかを示す。

境界情報はノードが当該地図データの領域の境界上にあるか内部にあるかを示す。

誘導有無情報はノードに対応する経路誘導データの経路誘導レコードの有無を示す。

ノードが廃止されてもそのノードレコードは削除せずノード状態を廃止とするものとし、ノードの廃止により既存のノードのノード番号を変化しないようにする。

また、ノードが廃止されたときは、そのノード付加レコードを削除するものとし、不要なデータの保持を防止し、更新後の道路網データのデータサイズをより小さくする。

また、新設するノードのノードレコードはノードテーブルの末尾に追加するものとし、既存ノードのノード番号の変化を防止する。

図１２はノード付加レコードのデータ構造の一例を示す図である。ノード付加レコードは、ノード付加ヘッダ、ノード座標、接続リンク情報、リンク間通行規制情報等を有する。

ノード付加ヘッダは、ノード付加レコードのデータサイズを示すノード付加レコードサイズ、接続リンク情報の接続リンクレコードの数を示す接続リンクレコード数、リンク間通行規制情報の通行規制レコードの数を示す通行規制レコード数を有する。

ノード座標は当該ノード付加レコードに対応するノードの地理上の位置を示す緯度、経度を表す。

接続リンク情報は固定長の接続リンクレコードの並びからなる。接続リンクレコードには内部接続リンクレコードと隣接接続リンクレコードの２種類がある。

内部接続リンクレコードは、当該ノードの順方向リンクおよびそれらのリンクを識別するためのノード単位リンク識別子を示し、隣接接続リンクレコードは当該ノードの隣接境界ノードを示す。

接続リンク情報には、当該ノードに接続するリンクを含むリンク列の数だけ内部接続リンクレコードを配置し、当該ノードが境界ノードであれば、更に上記内部接続リンクレコードの後に隣接接続リンクレコードを配置する。

内部接続リンクレコードはノード単位リンク番号、接続リンク列番号、接続リンク列内リンク番号を有する。

接続リンク列番号、接続リンク列内リンク番号は、接続リンク特定情報を構成し、当該ノードに接続するリンクを含むリンク列の当該ノードの順方向リンクを特定するもので、上記順方向リンクのリンク列番号、リンク列内リンク番号を示す。
このように、接続リンク特定情報は、リンク列の向きに応じ、当該ノードの順方向リンクを特定するようにしている。

ノード単位リンク番号は、接続リンク列番号、接続リンク列内リンク番号が示すリンクに付与された番号を示す。ノード単位リンク番号は当該ノードの順方向リンクを識別するノード単位リンク識別子であり、ノード単位でユニークな番号を付与する。尚、ノード単位リンク番号は、該当するリンクが存続している間は変更しないようにする。

従って、ノード単位リンク番号は他のリンクの廃止、新設によって変化しない。尚、本実施の形態ではノード単位リンク番号として０〜１５を付与する。

上記のように、当該ノードの順方向リンクは内部接続リンクレコードの接続リンク列番号、接続リンク列内リンク番号から特定することができ、当該ノードの順方向リンクに対する逆方向リンクのリンク列内リンク番号は内部接続リンクレコードの接続リンク列内リンク番号から１減じることにより得られる。但し、接続リンク列内リンク番号が０のときは当該ノードの順方向リンクに対する逆方向リンクは存在しない。

このように接続リンク情報に配置された内部接続リンクレコードにより当該に接続するすべてのリンクを直ちに特定することができる。

隣接接続リンクレコードは隣接領域指定と隣接境界ノード番号を有する。隣接領域指定は当該境界ノードの隣接境界ノードが属する隣接領域の当該領域に対する位置関係即ち上（０）、右（１）、下（２）、左（３）を示し、隣接境界ノード番号は当該境界ノードの隣接境界ノードの隣接領域におけるノード番号を示す。
尚、上記カッコ内の値は隣接領域指定として隣接接続リンクレコードに格納される値を示す。

上記接続リンク情報において、ノードの順方向リンクとその前方リンクのリンク状態がともに廃止または分割となった場合は、上記順方向リンクの接続リンクレコードを削除する。

また、あるノードＮｘにあるリンクＬｘが新たに接続された場合は、リンクＬｘを含むリンク列のノードＮｘの順方向リンクを示す接続リンクレコードを上記ノードの接続リンク情報に追加する。

上記のような接続リンクレコードのデータ構造により、ノードに接続するリンクの変更は接続リンクレコードの削除、追加という単純な処理で行うことができる。

また、内部接続リンクレコードに順方向リンクのリンク列番号、リンク列内リンク番号が格納されているため、接続するリンクのリンクレコードの所在が直ちに分かる。

また、ノードの順方向リンクの前方リンクに対する内部接続リンクレコードを設けず、ノードの順方向リンクの内部接続リンクレコードを用いてリンクの接続関係を表すことで道路網データのデータサイズを削減できる。

また、ノード単位でノード単位リンク番号を付与するため、ノードに接続する最大のリンク数は１６程度であり、ノード単位リンク番号に要するデータサイズは４ビット程度でよく、リンク列番号とリンク列内リンク番号とでリンクを特定するような当該領域内の全リンクを識別する情報を用いる場合に比し、内部接続リンクレコードのデータサイズを削減できる。

また、既存のリンク列、リンクのリンク列番号、リンク列内リンク番号が、リンク列、リンクの廃止、新設により変化しないようにしているため、他のリンク列、リンクの廃止、新設による既存の内部接続リンクレコードの変更が不要である。

また、ノードの廃止、新設により既存ノードのノード番号が変化しないため、隣接領域の地図データが更新されても、当該領域の隣接接続リンクレコードの変更は不要であり、当該道路網データ更新することなく版数の異なる地図データの道路網との接続が可能となり、地域毎に分割して更新する場合、更新を所望しない地域の道路網データを更新することなく所望の地域だけを更新しても道路網の間の接続の整合性を保つことができる。

リンク間通行規制情報は固定長の通行規制レコードの並びからなり、ノードに接続するリンク間の通行規制を示す。

通行規制レコードの並び順を通行規制レコード番号と呼び、通行規制レコード番号を用いて通行規制レコードを指定する。

通行規制レコードは、進入側ノード単位リンク番号、進入側前方指定、脱出側ノード単位リンク番号、脱出側前方指定、通行規制コードを有する。

進入側ノード単位リンク番号、進入側前方指定は当該ノードへの進入リンクを特定するもので、進入側ノード単位リンク番号は進入リンクを特定するためのノード単位リンク番号を示し、進入側前方指定は進入リンクが進入側ノード単位リンク番号に対し、自リンク、前方リンクの何れに該当するかを示す。

脱出側ノード単位リンク番号、脱出側前方指定は当該ノードへの脱出リンクを特定するもので、脱出側ノード単位リンク番号は脱出リンクを特定するためのノード単位リンク番号を示し、脱出側前方指定は脱出リンクが脱出側ノード単位リンク番号に対し、自リンク、前方リンクの何れに該当するかを示す。

通行規制コードは、当該ノードにおける進入リンクから脱出リンクへの通行に関する車種規制、時間規制等の各種通行規制を示す。

上記のように通行規制コードは進入リンク、脱出リンク指定にノード単位リンク番号を使用しており、他のリンクの廃止、新設に対しノード単位リンク番号は変化しないため、他のリンクの廃止、新設に対し通行規制コードの変更は不要である。

図１３は図５のノードレコードの格納例を示す図である。図１３において、ノードＮ０〜Ｎ７が存続しており、すべてのノードレコードのノード状態には０（存続）を格納する。

ノードＮ４が境界ノードで他は内部ノードであるため、ノードレコード＃４のノード状態に１（境界）を、他のノードレコードのノード状態に０（内部）を格納する。

また、ノードＮ１、Ｎ２に対応する誘導レコードが存在しているものとし、ノードレコード＃１、＃２の誘導有無情報に１（有り）を格納し、他のノードレコードの誘導有無情報には０（無し）を格納する。

図１４は図５のノード付加レコードの格納例を示す図である。
図１４のノード付加レコード＃０において、ノードＮ０の順方向リンクはリンクＬ００で、リンク間通行規制がなく、ノード付加ヘッダの接続リンクレコート数に１を通行規制レコード数に０を格納し、ノード付加レコードサイズにはノード付加レコード＃０のデータサイズｎｒｓ０を格納する。

また、ノード座標として、ノードＮ０が位置する緯度ｘ０、経度ｙ０を格納する。

また、接続リンク情報としてリンクＬ００を示す内部接続リンクレコードＣ００を設け、ノード単位リンク番号として０を格納し、接続リンク列番号としてリンクＬ００が属するリンク列０のリンク列番号である０を格納し、接続リンク列内リンク番号としてリンクＬ００のリンク列０におけるリンク列内リンク番号である０を格納する。
また、リンク間通行規制がないため、リンク間通行規制情報は格納しない。

図１４におけるノードＮ６のノード付加レコード＃６も上記ノード付加レコード＃０と同様に格納する。

図１４におけるノード付加レコード＃３において、ノードＮ３の順方向リンクは仮想リンクＬ０２’で、リンク間通行規制がなく、ノード付加ヘッダの接続リンクレコート数に１を通行規制レコード数に０を格納する。ノード付加レコードサイズにはノード付加レコード＃０のデータサイズｎｒｓ３を格納する。

また、ノード座標として、ノードＮ３が位置する緯度ｘ３、経度ｙ３を格納する。

また、接続リンク情報としてリンクＬ０２’を示す内部接続リンクレコードＣ３０を設け、ノード単位リンク番号として３を格納し、接続リンク列番号として仮想リンクＬ０２’が属するリンク列０のリンク列番号である０を格納し、接続リンク列内リンク番号として仮想リンクＬ０２’のリンク列０におけるリンク列内リンク番号である３を格納する。

また、リンク間通行規制がないため、リンク間通行規制情報は格納しない。
図１４におけるノードＮ５、Ｎ７のノード付加レコード＃５、７も上記ノード付加レコード＃３同様にして格納する。

図１４におけるノード付加レコード＃１において、ノードＮ１の順方向リンクはリンクＬ０１、Ｌ３１で、リンク間通行規制としてリンクＬ００からリンクＬ３０への通行規制ｒｃ１０、リンクＬ３１からリンクＬ００への通行規制ｒｃ１１があり、ノード付加ヘッダの接続リンクレコート数に２を通行規制レコード数に２を格納する。ノード付加レコードサイズにはノード付加レコード＃１のデータサイズｎｒｓ１を格納する。

また、ノード座標として、ノードＮ１が位置する緯度ｘ１、経度ｙ１を格納する。

図１４におけるノード付加レコード＃１の接続リンク情報としてリンクＬ０１を示す内部接続リンクレコードＣ１０を設け、リンクＬ３１を示す内部接続リンクレコードＣ１１を設ける。

内部接続リンクレコードＣ１０において、接続リンク列番号としてリンクＬ０１が属するリンク列０のリンク列番号である０を格納し、接続リンク列内リンク番号としてリンクＬ０１のリンク列０におけるリンク列内リンク番号である１を格納し、また、内部接続リンクレコードＣ１１において、接続リンク列番号としてリンクＬ３１が属するリンク列３のリンク列番号である３を格納し、接続リンク列内リンク番号としてリンクＬ３１のリンク列３におけるリンク列内リンク番号である１を格納する。

内部接続リンクレコードＣ１０において、ノード単位リンク番号として１を格納し、内部接続リンクレコードＣ１１において、ノード単位リンク番号として１を格納する。このように、ノード単位リンク番号として、ノードＮ１の順方向リンクであるリンクＬ０１、リンクＬ３１に対し、それぞれにノードＮ１においてユニークな番号０、１を付与している。

図１４におけるノード付加レコード＃１のリンク間通行規制情報として、リンクＬ００からリンクＬ３０への通行規制を表す通行規制レコードＲ１０、リンクＬ３１からリンクＬ００への通行規制を表す通行規制レコードＲ１１を設ける。

通行規制レコードＲ１０において、進入側ノード単位リンク番号にノードＮ１の順方向リンクＬ０１のノード単位リンク番号である０（＝内部接続リンクレコードＣ１０のノード単位リンク番号）を格納し、進入側前方指定に１（前方リンク）を格納する。上記により、進入リンクがリンクＬ００であることを示す。

また、脱出側ノード単位リンク番号にノードＮ１の順方向リンクＬ３１のノード単位リンク番号である１（＝内部接続リンクレコードＣ１１のノード単位リンク番号）を格納し、進入側前方指定に１（前方リンク）を格納する。上記により、脱出リンクがリンクＬ３０であることを示す。

また、通行規制コードとしてリンクＬ００からリンクＬ３０への通行規制を表すｒｃ１０を格納する。

通行規制レコードＲ１１において、進入側ノード単位リンク番号にノードＮ１の順方向リンクＬ３１のノード単位リンク番号である１（＝内部接続リンクレコードＣ１１のノード単位リンク番号）を格納し、進入側前方指定に０（自リンク）を格納する。上記により、進入リンクがリンクＬ３１であることを示す。

また、脱出側ノード単位リンク番号にノードＮ１の順方向リンクＬ０１のノード単位リンク番号である０（＝内部接続リンクレコードＣ１０のノード単位リンク番号）を格納し、進入側前方指定に１（前方リンク）を格納する。上記により、脱出リンクがリンクＬ００であることを示す。

また、通行規制コードとしてリンクＬ３１からリンクＬ００への通行規制を表すｒｃ１１を格納する。

図１４におけるノードＮ２のノード付加レコード＃２もノード付加レコード＃１同様にして格納する。

図１４のノード付加レコード＃４において、ノードＮ４は境界ノードであり、その順方向リンクはリンクＬ１０で、リンク間通行規制がなく、ノード付加ヘッダの接続リンクレコート数に２を、通行規制レコード数に０を格納する。ノード付加レコードサイズにはノード付加レコード＃４のデータサイズｎｒｓ４を格納する。

また、ノード座標として、ノードＮ４が位置する緯度ｘ４、経度ｙ４を格納する。

また、接続リンク情報としてリンクＬ１０に対応した内部接続リンクレコードＣ４０、隣接接続リンクレコードＣ４１を設け、内部接続リンクレコードＣ４０はノード付加レコード＃０内部接続リンクレコードと同様にして格納する。

隣接接続リンクレコードＣ４１には、ノードＮ４の隣接境界ノードＮＸは当該領域Ａの下方に隣接する領域Ｂに属するため、隣接領域指定には２（下）を格納し、隣接境界ノード番号にはノードＮＸの領域Ｂの道路網データにおけるノード番号ｎｘを格納する。

また、リンク間通行規制情報は、リンク間通行規制がないため格納しない。

図１５は経路誘導データのデータ構造の一例を示す図である。経路誘導データは、ノードに対応して設けられた経路誘導レコードの並びである。上記経路誘導レコードのようにノードに関連付けて設けた情報をノード関連情報と呼ぶ。

経路誘導レコードの並び順を経路誘導レコード番号と呼び、経路誘導レコード番号を用いて経路誘導レコードを識別する。

経路誘導レコードは、経路誘導レコードヘッダとノードの交差点名称を示す交差点名称データ、ノードに接続するリンクの道路名称を示す道路名称データ、ノードに接続するリンクの行き先を示す方面名称データ等のノードにおける案内に要する各種データからなる。

経路誘導レコードヘッダは、当該経路誘導レコードのデータサイズを示す経路誘導レコードサイズ、対応するノードのノード番号、交差点名称データ、道路名称データ、方面名称データ等のデータサイズを示すデータを有する。このように、ノード関連情報である経路誘導レコードは、対応するノードのノード識別子であるノード番号を有している。

経路誘導レコードは対応ノード番号の昇順に配置し、ノード番号による経路誘導レコードの検索が容易に行えるようにしている。

上記のように経路誘導データレコードは対応ノード番号によりノードと対応付けられているため、経路誘導データレコードの削除、追加、データサイズが変わるような内容変更等の更新を行っても、これらの更新に伴う道路網データの変更は生じない。また、既存ノードのノード番号はノードの廃止、新設に対し変化しないため、既存の経路誘導レコードの対応ノード番号の変更は不要であり、道路網データの更新に伴う経路誘導データの変更は生じない。

図１６は経路誘導データの格納例を示す図である。図１６において、図３のノードＮ１、Ｎ２に対応して経路誘導レコード＃０、経路誘導レコード＃１を設けたものである。経路誘導レコード＃０、経路誘導レコード＃１の経路誘導レコードヘッダの対応ノード番号には、ノードＮ１、Ｎ２のノード番号である１、２を格納する。

図１７は、図３の道路網を更新して得られた道路網を示す図である。図１７において、リンクＬ０１、リンク列２を廃止し、リンクＬ４０、Ｌ４１からなるリンク列４を新設し、リンクＬ００を分割して得られたリンクＬ５０、Ｌ５１からなるリンク列５を新設し、ノードＮ５を廃止し、ノードＮ８、Ｎ９を新設したものである。尚、Ｌ４１’はリンク列４の仮想リンク、Ｌ５１’はリンク列５の仮想リンクである。

尚、リンクＬ００を分割して得られたリンクＬ５０、Ｌ５１は、リンクＬ００の代わりに設けられたリンクであればよく、リンクＬ５０、Ｌ５１が表す道路形状がリンクＬ００が表す道路形状と一致しなくてもよい。また、リンクＬ００のような分割するリンクを分割前のリンク、リンクＬ５０、Ｌ５１のような分割して得られたリンクを分割後のリンクと呼ぶ。

図１７において、リンク列０の各リンクのリンク列内リンク番号の変化を防止するために、分割前のリンクＬ００を分割後のリンクＬ５０、Ｌ５１に置き換えず、リンクＬ５０、Ｌ５１からなるリンク列５を別に設けリンク列５の始点ノードと終点のノードがそれぞれリンクＬ００の始点ノード、終点ノードに接続するようにしている。

道路網を図３から図１７に更新したときの道路網データの更新について以下に説明する。
図１８は図５を更新して得られたノードテーブル、ノード付加リストの格納例を示す図である。

図１８において、ノードＮ８、Ｎ９の新設によりノードＮ８、Ｎ９のノードレコード＃８、ノードレコード＃９をノードテーブルの末尾に追加する。

また、図１８のノード付加リストにおいて、ノードＮ５の廃止によりノードＮ５のノード付加レコード＃５を削除し、ノードＮ８、Ｎ９の新設によりノードＮ８、Ｎ９のノード付加レコード＃８、＃９をノード付加リストの末尾に追加する。

図１９は図６を更新して得られたリンク列テーブル、リンク列付加リストの例を示す図である。

図１９のリンク列テーブルにおいて、リンク列４、５の新設によりリンク列４、５のリンク列レコード＃４、＃５をリンク列テーブルの末尾に追加する。

また、図１９のリンク列付加リストにおいて、リンク列２の廃止によりリンク列２のリンク付加列レコード＃２を削除し、リンク列４、５の新設によりリンク列４、５のリンク列付加レコード＃４、＃５をリンク列付加リストの末尾に追加する。

図２２は図１８のノードテーブルの各ノードレコードの格納例を示す図である。図２２において、ノードＮ５の廃止によりノードＮ５のノードレコード＃５のノード状態を１（廃止）に変更し、ノードＮ１における誘導が廃止されるものとして、ノードＮ１のノードレコード＃１の誘導有無情報を０（無し）に変更し、ノードＮ７に対する経路誘導レコードが新設されるものとして、ノードＮ７のノードレコード＃７の誘導有無情報を１（有り）に変更する。

図２３は図１４を更新して得られたノード付加レコードの格納例を示す図である。
図２３において、上記に記したようにノード付加レコード＃５は削除され、ノード付加レコード＃８、＃９が追加されている。

図２３のノードＮ０のノード付加レコード＃０において、リンクＬ００が分割されるため接続リンクレコードＣ００を削除し、新設されるリンクＬ５０を示す接続リンクレコードＣ０１を接続リンク情報に追加する。上記により、ノードＮ０には、リンクＬ００の代わりに分割して得られたリンクＬ５０が接続される。

また、ノードＮ１のノード付加レコード＃１において、分割されるリンクＬ００が分割されるとともにリンクＬ０１が廃止されるため接続リンクレコードＣ１１を削除し、その後、仮想リンクＬ５１’を示す接続リンクレコードＣ１２を接続リンク情報に追加する。

上記により、ノードＮ１には、リンクＬ００の代わりに分割して得られたリンクＬ５１が接続され、リンクＬ０１が接続されなくなる。

尚、新規に追加する接続リンクレコードのノード単位リンク番号は、追加するまでに存在する接続リンクレコードが使用していないノード単位リンク番号の中で最小の番号を付与する。ノードＮ１において、接続リンクレコードＣ１２の追加前に使用しているノード単位リンク番号は１のみであるから、接続リンクレコードＣ１２のノード単位リンク番号として０を格納する。

上記更新の結果、通行規制レコードＲ１０はリンクＬ３１からリンクＬ５１への通行規制を示し、通行規制レコードＲ１１はリンクＬ５１からリンクＬ３０への通行規制を示すことになるが、リンク間通行規制はリンクＬ００がリンクＬ５１に代わっても変化がないものとして通行通行規制レコードの更新は行わない。

図２３のノードＮ２のノード付加レコード＃２において、リンク列２即ちリンクＬ２０の廃止により接続リンクレコードＣ２２を削除し、その後、新設されるリンクＬ４０を示す接続リンクレコードＣ２３を接続リンク情報に追加する。上記により、ノードＮ２には、リンクＬ４０が接続される。尚、接続リンクレコードＣ２３の追加前に使用しているノード単位リンク番号は０、１であるから、接続リンクレコードＣ２３のノード単位リンク番号として上記０、１以外の最小の番号２を格納する。

リンク列２が廃止されるため、リンクＬ２０からリンクＬ０１への通行規制を示す通行規制レコードＲ２１を削除し、新たに設けられたリンクＬ４０からリンクＬ１０への通行規制を示す通行規制レコードＲ２２をリンク間通行規制情報に追加する。

尚、リンク列２の廃止、リンク列４の新設により、ノードＮ２に接続するリンクが変わっても、ノードＮ２おける既存リンクＬ０２、Ｌ０１’のノード単位リンク番号は変化しないため、ノードＮ２における既存の通行規制レコードＲ２０の変更は不要である。

図２３のノードＮ７のノード付加レコード＃７において、新設されるリンクＬ４１を示す接続リンクレコードＣ７１を接続リンク情報に追加する。上記により、ノードＮ７には、リンクＬ４０、Ｌ４１が接続される。尚、接続リンクレコードＣ７１の追加前に使用しているノード単位リンク番号は０であるから、接続リンクレコードＣ７１のノード単位リンク番号として上記０以外の最小の番号１を格納する。

また、ノード付加ヘッダのノード付加レコードサイズをｎｒｓ７に接続リンクレコードＣ７１分を加算したｎｒｓ７’に変更する。

図２０は、図１９のリンク列テーブルにおけるリンク列レコードの格納例を示す図である。リンク列２の廃止によりリンク列２のリンク列レコード＃２のリンク列状態を１（廃止）に変更し、新設リンク列４に対し、リンク列状態が０（存続）、リンク列種別が５（一般道）のリンク列レコード＃４を追加し、新設リンク列５に対し、リンク列状態が０（存続）、リンク列種別がリンクを分割する前と同じ４（都道府県道）のリンク列レコード＃５を追加している。

図２１は、図１０を更新して得られたリンク列０のリンク列付加レコード＃０のリンク列付加ヘッダ、リンクテーブルの格納例を示す図である。

図２１において、リンクＬ００の分割により、リンクレコード＃０のリンク状態を２（分割）に、リンク付加有無情報を０（無し）に、分割リンク番号をリンクＬ００の分割後のリンクからなるリンク列５のリンク列番号５に変更する。

上記にように、分割前のリンクＬ００のリンクレコードを分割後のリンクＬ５０、Ｌ５１の２つのリンクレコードに置き換えないため、リンク分割によりリンクレコードの構成が変化することなく、リンク列０のリンクＬ０１、Ｌ０２、Ｌ０２’のリンク列内リンク番号は変化しない。

また、上記にように、リンクＬ００のリンクレコードに分割を示すリンク状態、分割リンク列番号が格納されているため、リンクＬ００の分割リンク列５のリンク列レコードの所在が直ちに分かる。

また、リンクＬ０１の廃止により、リンクレコード＃１のリンク状態を１（廃止）に、リンク付加有無情報を０（無し）にする。
また、リンクＬ００の分割、リンクＬ００の廃止により、リンク付加リストのリンク付加レコード＃０、＃１を削除する。
また、リンク列付加ヘッダのリンク付加レコードサイズをｍｌａｓ０からリンク付加レコード＃０、リンク付加レコード＃１の削除分を減じたｍｌａｓ０’に変更する。

図２４は、リンクＬ００の分割後のリンクＬ５０、５１からなるリンク列５の図２１におけるリンク列付加レコード＃５の格納例を示す図である。

図２４のリンク列付加レコード＃５の各データは上記の各リンク列付加レコードと同様にして格納する。但し、図２４のリンク列付加ヘッダにおいて、最小リンク番号、最大リンク番号に分割前のリンクＬ００の最小リンク番号、最大リンク番号である０、２５５を格納する。また、図２４のリンク付加リストにおいて、リンクＬ５１のリンク付加レコード＃１のリンク番号情報に１２８を格納する。

従って、リンクＬ５０のリンク番号の最小値は（式１）により０、最大値はリンクＬ５１のリンク付加レコード＃１のリンク番号情報として格納されている１２８から１減じた１２７となり、リンクＬ５１のリンク番号の最小値はリンク付加レコード＃１のリンク番号情報として格納されている１２８、最大値はリンク列ヘッダ付加ヘッダにおける最大リンク番号である２５５となる。即ちリンクＬ５０には０〜１２７のリンク番号が、リンクＬ５０には１２８〜２５５のリンク番号が付与される。

このように、分割前のリンクＬ００の０〜２５５なる範囲のリンク番号を等分割して分割後のリンクＬ５０、Ｌ５１のそれぞれに０〜１２７、１２８〜２５５なる範囲のリンク番号を配分する。

図２５は上記に分割に続きリンクＬ００を更に分割したときのリンク番号の付与例を示す図である。リンクＬ５０を更にリンクＬ５０−０、Ｌ５０−１に分割し、リンクＬ５０の０〜１２７なる範囲のリンク番号を等分割した０〜６３、６４〜１２７なる範囲のリンク番号をリンクＬ５０−０、Ｌ５０−１それぞれに配分する。以下同様にリンクを分割する毎に分割前のリンクのリンク番号を等分し、分割後のリンクに配分する。リンクＬ００は８回まで分割できることが分かる。
リンク番号設定定数を２５６としているため図３の他のリンクも上記と同様に８回まで分割できる。
上記のようにして分割後のリンクにリンク番号を付与することにより、どのリンクに対しても所定回数の分割を可能としている。

尚、上記ではリンク番号設定定数を２５６としているが、リンク番号設定定数を２５７のように設定し、０〜２５６なる範囲のリンク番号を等分した場合、０〜１２７．５、１２７．５〜２５６なる範囲のリンク番号を配分することになるが、リンク番号は整数であるため、上記範囲が重複しないように上記範囲の上限、下限の小数部を切り捨て、切り上げを行って得られた０〜１２７、１２８〜２５６なる範囲のリンク番号を配分する。このように分割後のリンクに配分するリンク番号は、上記のように等分した得られた範囲に応じて定めたものであればよい。

図２６は図１６を更新して得られた経路誘導データの例を示す図である。
図２６の経路誘導データは、ノードＮ１における経路誘導を廃止し、ノードＮ７における経路誘導を新設したときの経路誘導データであり、ノードＮ１に対応する経路誘導レコード＃０を廃止し、ノードＮ７に対応する経路誘導レコード＃２を追加し、経路誘導レコード＃２の対応ノード番号としてノードＮ７のノード番号７を格納しものである。

ノードレコード、ノード付加レコードは以上ようなデータ構造としているため、ノードレコードのノードテーブルにおける格納位置は、ノード番号とノードレコードのデータサイズの積として求めることができる。また、ノード付加レコードのノード付加リストにおける格納位置は、ノード状態に依存し各ノード付加レコードサイズをノード付加リストの先頭から累積的に加算するという単純な演算処理で求めることができる。例えば、図２３において、ノード付加レコード＃ｑ（ｑ＝０、１、２、・・・、９）の格納位置Ａｑ（ｑ＝０、１、２、・・・、９）は、Ａ０＝０、Ａ１＝Ａ０＋ｎｒｓ０、Ａ２＝Ａ１＋ｎｒｓ１、Ａ３＝Ａ２＋ｎｒｓ２、Ａ４＝Ａ３＋ｎｒｓ３、Ａ５＝Ａ４＋ｎｒｓ４、Ａ６＝Ａ５、Ａ７＝Ａ６＋ｎｒｓ６、Ａ８＝Ａ７＋ｎｒｓ７’、Ａ９＝Ａ８＋ｎｒｓ８なる演算を順次行なうことにより算出できる。但し、ノードＮ５は廃止され、ノード状態が廃止となっているため、ノードＮ６のノード付加レコード＃６の格納位置Ａ６の算出時に、ノードＮ５のノード付加レコードサイズを０として、Ａ６＝Ａ５として求める。道路網データを最初に使用するときに予め上記のようにして、各ノード付加レコードの格納位置を求め、ノード番号の順にＡ０、Ａ１、Ａ２、Ａ３、Ａ４、Ａ５、Ａ６、Ａ７、Ａ８、Ａ９とノード付加レコードの格納位置を配置したノード付加レコード格納位置テーブルを作成しておけば、ノード付加レコード格納位置テーブルを参照することにより、所望のノード番号のノード付加レコードの格納位置を直ちに求めることができる。このように、ノード識別子としてノード番号を用いることより、ノード識別子を元に所用のノードのノードデータを速やかに取得できる。

この発明の実施の形態１による地図情報を更新するための地図更新情報のデータ構造について、以下に説明する。

図２７は、更新情報取得装置４に挿入される更新用ＤＶＤ−ＲＯＭに格納された地図更新情報の概略データ構造を示す図である。図２７において、地図更新情報は、地図更新管理情報、１以上の地図更新データ、経路計算更新データを有している。
地図更新管理情報は階層ごとに更新データを管理するデータで、各領域と各地図更新データ、経路計算更新データとを対応付ける情報、各地図更新データ、経路計算更新データの地図更新情報における格納位置、データサイズを階層ごとに有している。

また、当該ＤＶＤ−ＲＯＭが地図更新情報を格納していることを示すデータ識別情報、当該地図更新情報が更新の対象とする地図情報の版数を示す更新対象版数情報、当該地図更新情報により更新して得られる地図情報の版数を示す更新版数情報を有する。

地図更新データは、地図データを更新するためのデータで、地図データに対応して設けられる。尚、更新が不要な地図データに対する地図更新データは格納されていない。また、経路計算更新データは、経路計算データを更新するためのデータで、経路計算データに対応して設けられる。尚、更新が不要な経路計算データに対する経路計算更新データは格納されていない。

地図更新データは、道路網データ、背景データ、名称データ、経路誘導データ等を更新するための道路網更新データ、背景更新データ、名称更新データ、経路誘導更新データ等と地図更新ヘッダを有する。尚、更新が不要なデータの更新データは格納されていない。また、上記各更新データは、１以上の更新レコードからなる。

地図更新データヘッダは、上記各更新データを管理するためのデータで、上記各更新データの当該地図データにおける格納位置、データサイズ、更新レコード数等を有している。

図２８は更新レコードのデータ構造の一例を示す図である。図２８において、更新レコードは、更新対象実体種別、更新対象データ種別、更新操作種別、パラメータ数、オペランド数、更新対象実体指定、更新オペランドリストからなる。

更新対象実体種別は、指定無し（０）、ノード（１）、リンク（２）、リンク列（３）等更新の対象とする地理的実体の種別を示し、更新対象データ種別は道路網データ等を構成するデータの種類を示し、更新操作種別は廃止（０）、新設（１）、リンク分割（２）等の理的実体に関する更新操作、上書き（１０）、削除（１１）、置き換え（１２）、追加（１３）等のデータに関する更新操作の種別を示し、パラメータ数は更新対象指定が持つのパラメータの数を示し、オペランド数は更新オペランドが持つオペランドの数を示し、更新対象実体指定はノード番号、リンク列番号、リンク列内リンク番号等のパラメータにより更新の対象実体を指定し、更新オペランドリストはノードレコード、ノード付加レコード等更新に使用するデータを示す。尚、更新対象実体指定、更新オペランドリストとして格納されるデータの意味は更新対象実体種別、更新対象データ種別、更新操作種別によって定まる。

上記更新対象データ種別として、例えば、ノードに関するデータとして、ノードレコード（１０）、ノード状態（１１）、境界情報（１２）、誘導有無情報（１３）、ノード付加レコード（１００）、ノード付加ヘッダ（１１０）、ノード座標（１２０）、接続リンク情報（１３０）、リンク間通行規制情報（１４０）、通行規制レコード（１４１）等のように定める。
上記において、カッコ内の値は、更新レコードへ格納する値である。

尚、接続リンクレコードの削除を容易にするために、リンクの更新に関する更新レコードは、リンクが所属するリンク列の昇順となるように配置し、同一リンク列に属するリンクの更新に関する更新レコードは、リンク列内リンク番号の昇順となるように配置する。

また、リンク列の新設時に、新設するリンク列レコードおよびリンク列付加レコードを用いて新設リンクの接続リンクレコードの作成を可能とし、新設リンクのノード単位リンク番号を既存の接続リンクレコードが使用していない最小のノード単位リンク番号として付与できるようにするため、リンク列を新設するための更新レコードは、ノードの新設、リンクの廃止、リンクの分割、リンク列の廃止を示す更新レコードよりも後に配置する。

図２９は道路網を図３から図１７に更新するための道路網更新データの格納例を示す図である。図２９において、更新レコード＃ｒ０は、ノード番号１のノード（ノードＮ１）のリンクレコードの誘導有無情報の上書きを示し、更新オペランドリストに上書きすべきデータとして誘導情報（＝０（無し））を有する。

また、更新レコード＃ｒ１は、ノード番号２のノード（ノードＮ２）のリンク間通行規制情報の通行規制レコード番号が１の通行規制レコードＲ２１の削除を示す。

また、更新レコード＃ｒ２は、ノード番号２のノード（ノードＮ２）のリンク間通行規制情報への通行規制レコードの追加を示し、更新オペランドリストに追加すべきデータとして図２３の通行規制レコードＲ２２を有する。

また、更新レコード＃ｒ３はノード番号５のノードＮ５を廃止することを示す。また、更新レコード＃ｒ４は、ノードの新設を示し、更新オペランドリストにノードの新設のために追加すべきデータとして図１８のノードレコード＃８、ノード付加レコード＃８を有している。また、更新レコード＃ｒ５は、ノードの新設を示し、更新オペランドリストにノードの新設のために追加すべきデータとして図１８のノードレコード＃９、ノード付加レコード＃９を有している。

また、更新レコード＃ｒ６は、リンク列番号０のリンク列０のリンク列列内リンク番号０のリンクＬ００が分割され、更新オペランドリストにその分割リンク列のリンク列番号が５即ちリンク列５であることを示すデータを有する。また、更新レコード＃ｒ７は、リンク列番号０のリンク列０のリンク列列内リンク番号１のリンクＬ０１が廃止されることを示す。

また、更新レコード＃ｒ８は、リンク列番号２のリンク列２を廃止することを示す。また、更新レコード＃ｒ９は、リンク列の新設を示し、更新オペランドリストにリンク列の新設のために追加すべきデータある図１９のリンク列レコード＃４、リンク列付加レコード＃４を有している。また、更新レコード＃ｒ１０は、リンク列の新設を示し、更新オペランドリストにリンク列の新設のために追加すべきデータである図１９のリンク列レコード＃５、リンク列付加レコード＃５を有している。

図３０は、図１６の経路誘導データを図２５の経路誘導データへ更新するための経路誘導更新データの格納例を示す図ある。図３０において、更新レコード＃ｇ０は、経路誘導レコード番号０の経路誘導レコード＃０を削除することを示す。また、更新レコード＃ｇ１は、経路誘導レコードの追加を示し、更新オペランドとして、経路誘導レコードの新設のために追加すべきデータである図２５の経路誘導レコード＃２を有する。

図３１は、図１に示した地図情報処理装置の動作を示すフローチャートである。以下に、図１に示した地図情報処理装置の動作を図３１のフローチャートをもとに図３の道路網を図１７の道路網に更新する場合を例に説明する。

図３２は、プロセッサ５のメモリの割り当てを示す図である。図３２において、地図情報処理装置の動作を制御するためのデータを格納する動作制御データ部１０、当該位置検出装置２で得られた位置情報の時系列である走行軌跡データを格納する走行軌跡データ部１１、当該車両の現在位置を表すデータを格納する現在位置データ部１２、出発地から目的地までの経路を表す経路データを格納する経路データ部１３、所要経路計算管理データを格納する所要経路計算データ管理部１４、経路計算データを格納する経路計算データ部１５、経路計算更新データを格納する経路計算更新データ部１６、所要地図管理データを格納する所要地図データ管理部１７、地図データを格納する地図データ部１８、地図更新データを格納する地図更新データ部１９をプロセッサ５のメモリに割り当てる。

地図情報処理装置が起動し、処理を開始すると、まず、ステップＳＴ１０では、プロセッサ５のメモリの初期化を行いステップＳＴ１１へ進む。

ステップＳＴ１１では、更新情報取得装置４に更新用ＤＶＤ−ＲＯＭが挿入されたか否かを確認し、挿入されたときはステップＳＴ１２へ行き、挿入されていなければステップＳＴ１３へ行く。

ステップＳＴ１２では、更新情報取得装置４に挿入された更新用ＤＶＤ−ＲＯＭに格納されている地図更新情報の地図更新管理情報を読み取り、地図更新管理情報にある更新対象版数情報と地図情報記憶装置３に格納されている地図情報の地図管理情報にある版数情報を比較し、一致すれば、上記地図更新情報による上記地図情報の更新が可能とし、上記地図更新情報を読み取り、地図情報記憶装置３に格納し、ステップＳＴ１３へ行く。

ステップＳＴ１３では、入力装置１より使用者の操作または指示に従った指示信号に基づき、例えば地図の表示縮尺、目的地、経路計算の開始指示等の地図情報処理装置の動作を制御するためのデータを動作制御データ部１０へ格納し、ステップＳＴ１４へ行く。

ステップＳＴ１４では、位置検出装置２から位置情報取得し、取得した位置情報を走行軌跡データ部１１に累積的に格納するとともに、１回目のステップＳＴ１４の処理では取得した位置情報を現在位置として現在位置データ部１２へ格納し、ステップＳＴ１５へ行く。

ステップＳＴ１５では、動作制御データ部１０が経路計算の開始を指示しているか否かを判定し、指示していればステップＳＴ１６へ行き、指示していなければステップＳＴ１８へ行く。

ステップＳＴ１６では、現在位置データ部１２が示す位置を出発地とし動作制御データ部１０に格納し、動作制御データ部１０が示す出発地から目的地へ至る好適な経路を得るための経路計算に必要な経路計算データの取得および更新を行い、ステップＳＴ１７へ行く。

ステップＳＴ１７では、ステップＳＴ１６で取得・更新された経路計算データを用いて経路計算を行い、上記出発地から目的地への好適な経路を求め、上記経路を現す経路データを経路データ部１３に格納し、動作制御データ部１０の経路計算の開始指示を取り消し、ステップＳＴ１８へ行く。

図３３は、図３の領域Ａにおける経路計算データが表す道路網の例を示す図である。
図３３の道路網において、ノードＮｒ０、Ｎｒ１、Ｎｒ３、Ｎｒ６、Ｎｒ７は、それぞれ図３のノードＮ０、Ｎ１、Ｎ３、Ｎ６、Ｎ７に対応している。

また、図３３のリンクＬｒ００、Ｌｒ３０、Ｌｒ３１には、それぞれ図３のリンクＬ００、Ｌ３０、Ｌ３１が対応し、図３の対応するリンクのリンク番号０〜２５５、１２８０〜１５３５、１５３６〜１７９１が付与されいる。尚、リンクＬｒ０１は図３のリンクＬ０１、Ｌ０２を統合したもので、それらのリンク番号２５６〜５１１、５１２〜７６７を統合した２５６〜７６７なるリンク番号が付与されている。

図３４は、ステップＳＴ１７で得られた経路データの一例であり、出発地を図３３のノードＮｒ０、目的地を図３３のノードＮｒ６としたときに得られたリンクＬｒ００、Ｌｒ３０からなる経路を表し、図３のリンクＬ００、Ｌ３０に対応する。

経路データは経路を構成するリンクの数を示すリンク数、経路を構成するリンクに対応して設けた経路レコードからなり、経路レコードは、対応する道路網データのリンクのリンク番号の最小値、最大値、上記リンク番号で表されるリンクに対する経路の向きからなる。経路レコードの経路の向きは、経路の向きが上記リンク番号で対応付けられるリンクの向きと同一のときは順方向（０）、逆のときは逆方向（１）とする。

ステップＳＴ１８では、現在位置データ部１２が示す現在位置の周辺の地図表示、マップマッチング、経路誘導に必要な地図データを取得し、取得した地図データを地図データ部１８へ格納し、格納した地図データの更新を行いステップＳＴ１９へ行く。

ステップＳＴ１９では、走行軌跡データ部１１の走行軌跡データと地図データ部１８に格納されている地図データの道路網データにより、当該車両が走行しているリンクおよびリンク上の位置を推定することにより当該車両の現在位置を求め、求めた現在位置を現在位置データ部１２に格納し、ステップ２０へ行く。

上記リンクの推定、リンク上の位置の推定は、上記走行軌跡データとリンクまたは連なったリンクの形状の関係性から推定され、接続リンク情報、リンク間通行規制情報、一方通行情報を援用することによりリンクの推定精度をより高めている。

上記処理において、リンクの始点ノードの座標値を、リンクレコードの始点ノード番号に対応するノード付加レコードに格納されているノード座標から取得し、リンクの補間点の座標値をリンクレコードのリンク形状情報から取得し、リンクの終点ノードの座標値を、後方リンクのリンクレコードの始点ノード番号に対応するノード付加レコードに格納されているノード座標から取得し、リンクの形状を示す座標値を取得する。

尚、リンクを特定できないときは、走行軌跡データ部１１の最新の位置情報を現在位置として現在位置データ部１２に格納する。

ステップＳＴ２０では、地図データ部１８に格納されている地図データの道路網データ、背景データ、名称データに従い動作制御データ部１０が示す表示縮尺となるように描画した道路、背景、名称からなる地図画面を出力装置６に表示し、ステップ２１へ行く。

上記道路網データによる道路の描画において、リンク列レコードのリンク列種別により道路の描画色、幅を決定し、リンクレコードの始点ノード番号に対応するノード付加レコードから取得したノード座標とリンク付加レコードから取得したリンク形状情報が示す折れ線を上記描画色、幅で描画する。

ステップＳＴ２１では、ステップＳＴ２０で表示した地図画面上の現在地データ部１２が示す現在位置に該当する箇所に現在位置を表す図形を表示し、ステップ２２へ行く。

ステップＳＴ２２では、ステップＳＴ２０で表示した表示した地図画面上に、ステップＳＴ１７で得られた経路データが示す経路を経路であることが判別できるように強調して表示し、上記経路表示後、ステップ２３へ行く。

ステップＳＴ２３では、ステップＳＴ１９で得られた当該車両が走行しているリンクの前方にあるノードのノードレコードの経路誘導有無情報を調べ、対応する経路誘導レコードが有れば、経路誘導データの該当する経路誘導レコードにより、上記ノードに関する案内画面の表示、音声案内を出力装置６により行う。

図３４の経路データに対して、車両が図３において、リンクＬ００をノードＮ１に向かって走行しているとき、図１３のノードＮ１のノードレコード＃１の経路誘導有無情報により経路誘導レコードが存在することが判り、ノードＮ１のノード番号をキーに図１６の経路誘導データを検索し、経路誘導レコードの対応ノード番号がノードＮ１のノード番号１に一致する経路誘導レコード＃０を見つけ、経路誘導レコード＃０に基づき案内画面の表示、音声案内を出力装置６により行う。
上記処理後ステップＳＴ１１へ戻り、以後、上記ステップＳＴ１１〜ＳＴ２３を繰り返す。

上記のようにして、更新用ＤＶＤ−ＲＯＭに格納された地図更新情報により更新した地図データを用いて、地図表示、マップマッチング、経路計算、経路誘導等の地図情報処理を行う。

図３５は、図３１のステップＳＴ１６の経路計算データ取得・更新の詳細なフローチャートである。ステップＳＴ１００では、動作制御データ１０が示す出発地から目的地へ至る好適な経路を得るための経路計算に必要とする各経路計算データの階層、領域を求め、所要経路計算管理データとして所要経路計算データ管理部１４に格納し、ステップＳＴ１０１へ行く。

ステップＳＴ１０１では、地図情報記憶装置３の地図情報の中から所要経路計算データ管理部１４の所要経路計算管理データによって示される経路計算データを読み取り、経路計算データ部１５に格納し、ステップＳＴ１０２へ行く。

ステップＳＴ１０２では、地図情報記憶装置３に地図更新情報が格納されていなければステップＳＴ１０５へ行き、格納されていれば地図情報記憶装置３の地図更新情報の地図更新管理情報によりステップＳＴ１０１で取得した経路計算データと同一階層、同一領域の経路計算更新データの有無を調べ、なければステップＳＴ１０５へ行き、有ればステップＳＴ１０３へ行く。

ステップＳＴ１０３では、地図情報記憶装置３に格納されている経路計算更新データの中で、地図更新情報のステップＳＴ１０１で取得した経路計算データと同一階層、同一領域の経路計算更新データを読み取り、経路計算更新データ部１６に格納し、ステップＳＴ１０４へ行く。

ステップＳＴ１０４では、の経路計算データ部１５のステップ１０３で得た経路計算データを、経路計算更新データ部１６のステップ１０４で得た経路計算更新データにより更新し、ステップＳＴ１０５へ行く。

ステップＳＴ１０５では、所要経路計算データ管理部１４の経路計算管理データが示す所要の経路計算データすべての読み取りが終了したかを調べ、終了していれば経路計算データ取得、更新の処理を終了し、終了していなければステップＳＴ１０１に戻りステップＳＴ１０１〜ＳＴ１０５を繰り返す。

図３６は、図３１のステップＳＴ１８の地図データ取得・更新の詳細なフローチャートである。ステップＳＴ２００では、現在位置データ部１２が示す現在位置周辺の地図表示、マップマッチング、経路誘導に必要な各地図データの階層、領域を求め、所要地図管理データとして、所要地図データ管理部１７に格納し、ステップＳＴ２０１へ行く。

ステップＳＴ２０１では、地図情報記憶装置３の地図情報の中から所要地図データ管理部１７の所要地図管理データによって示される地図データを読み取り、地図データ部１８に格納し、ステップＳＴ２０２へ行く。

ステップＳＴ２０２では、地図情報記憶装置３に地図更新情報が格納されていなければステップＳＴ２０９へ行き、格納されていれば地図情報記憶装置３の地図更新情報の地図更新管理情報によりステップＳＴ２０１で取得した地図データと同一階層、同一領域の地図更新データの有無を調べ、なければステップＳＴ２０９へ行き、有ればステップＳＴ２０３へ行く。

ステップＳＴ２０３では、地図情報記憶装置３の地図更新情報の中からステップＳＴ２０１で取得した地図データと同一階層、同一領域の地図更新データを読み取り、地図更新データ部１９に格納し、ステップＳＴ２０４へ行く。

ステップＳＴ２０４では、地図データ部１８のステップ２０１で得た地図データの道路網データを、地図更新データ部１９のステップ２０３で得た地図更新データの道路網更新データにより更新し、ステップＳＴ２０５へ行く。

ステップＳＴ２０５では、地図データ部１８のステップ２０１で得た地図データの背景データを、地図更新データ部１９のステップ２０３で得た地図更新データの背景更新データにより更新し、ステップＳＴ２０６へ行く。

ステップＳＴ２０６では、地図データ部１８のステップ２０１で得た地図データの名称データを、地図更新データ部１９のステップ２０３で得た地図更新データの名称更新データにより更新し、ステップＳＴ２０７へ行く。

ステップＳＴ２０７では、地図データ部１８のステップ２０１で得た地図データの経路誘導データを、地図更新データ部 １９のステップ２０３で得た地図更新データの経路誘導更新データにより更新する。

図３０の経路誘導更新データにおける更新レコード＃ｇ０により、図１６の経路誘導データの経路誘導レコード番号＃０を削除し、更新レコード＃ｇ１により、図１６の経路誘導データに更新レコード＃ｇ１の更新オペランドリスト内の経路誘導レコード＃２を追加し、図１６の経路誘導データが、図２６の経路誘導データへ更新される。
上記更新に対し、図２６の経路誘導レコード＃１のように既存の経路誘導レコードの対応ノードは変化しないので、経路誘導データの更新は道路網データへ影響せず、道路網データの変更を生じない。
上記処理後、ステップＳＴ２０８へ行く。

ステップＳＴ２０８では、上記道路網データ、背景データ、名称データ、経路誘導データの更新に合わせて、上記地図データの地図データヘッダを更新し、ステップＳＴ２０９へ行く。

ステップＳＴ２０９では、所要地図データ管理部１７の地図管理データが示す地図データすべての読み取りが終了したかを調べ、終了していれば地図データ取得、更新の処理を終了し、終了していなければステップＳＴ２０１に戻りステップＳＴ２０１〜ＳＴ２０９を繰り返す。

図３７は、図３６のステップＳＴ２０４の道路網データ更新の詳細なフローチャートである。ステップＳＴ３００では、地図更新データ部１８のステップ２０３で得た地図更新データにおける道路網更新データから、更新レコードを取得し、ステップＳＴ３０１へ行く。

ステップＳＴ３０１では、ステップＳＴ３００で得た更新レコードの更新対象実体種別、更新対象データ種別、更新対象実体指定によって定まる道路網データの一部を更新操作種別に従い更新オペランドリストのデータを用いて更新し、上記更新に伴って変化するノード付加ヘッダ、リンク列付加ヘッダ、リンク付加ヘッダを更新する。尚、以下の説明ではノード付加ヘッダ、リンク列付加ヘッダ、リンク付加ヘッダの更新については説明を省略するが、更新内容に合わせ適宜更新するものとする。

図２９の道路網更新データにおいて、更新レコード＃ｒ０に対しては、ノード番号が１であるノードＮ１の図１３に示すノードレコード＃１の誘導有無情報を更新オペランドリストの誘導有無情報（＝０（無し））に上書きし、図２２のノードレコード＃１とする。

また、更新レコード＃ｒ１に対しては、ノード番号が２であるノードＮ２の図１４のノード付加レコード＃２のリンク間通行規制情報の通行規制レコード番号が１である通行規制レコードＲ２１を削除し、上記削除に従いノード付加レコードヘッダのノード付加レコードサイズ、通行規制レコード数を変更する。

また、更新レコード＃ｒ２に対しては、図１４のノード付加レコード＃２のリンク間通行規制情報に更新オペランドリストの通行規制レコードＲ２２を追加する。

上記のように、更新レコード＃ｒ１、ｒ２により、リンク間通行規制情報が図２３のノード付加レコード＃２に示すように更新される。

また、更新レコード＃ｒ３に対しては、ノード番号が５であるノードＮ５の図１３のノードレコード＃５のノード状態を１（廃止）に変更し、図５の上記ノードのノード付加レコード＃５を削除する。

また、更新レコード＃ｒ４、更新レコード＃ｒ５に対しては、図５のノードテーブルの末尾に更新オペランドリストのノードレコード＃８、ノードレコード＃９を追加し、図５のノード付加リストの末尾に更新オペランドリストのノード付加レコード＃８、ノード付加レコード＃９を追加する。

上記のように、更新レコード＃ｒ３、ｒ４、ｒ５により、図１８のノードテーブル、図２２のノードレコード、図１８のノード付加リスト、図２３のノード付加レコード＃８、ノード付加レコード＃９が得られる。但し、この時点では、ノード付加レコード＃８、ノード付加レコード＃９の接続リンクレコードＣ８０、Ｃ９０は格納されていない。

また、更新レコード＃ｒ６に対しては、図１０のリンク列番号が０のリンク列０におけるリンク列内リンク番号が０のリンクＬ００のリンクレコード＃０のリンク状態を２（分割）に、分割リンク番号を更新オペランドリストが示す分割リンク番号５とし、リンク付加有無情報を０（無し）に変更し、図１０の上記リンクのリンク付加レコード＃０を削除する。

また、更新レコード＃ｒ７に対しては、図１０のリンク列番号が０のリンク列０におけるリンク列内リンク番号が１のリンクＬ０１のリンクレコード＃１のリンク状態を０（廃止）に、リンク付加有無情報を０（無し）に変更し、図１０の上記リンクのリンク付加レコード＃１を削除する。

上記のように、更新レコード＃ｒ６、ｒ７により、リンク列０のリンク付加レコードは図２１に示すリンク付加レコードに更新される。

また、更新レコード＃ｒ８に対しては、図９のリンク列番号が２のリンク列２のリンク列レコード＃２のリンク列状態を０（廃止）に変更し、図６のリンク列２のリンク列付加レコード＃２を削除する。

また、更新レコード＃ｒ９、更新レコード＃ｒ１０に対しては、図６のリンク列テーブルの末尾に更新オペランドのリンク列レコード＃４、リンク列レコード＃５を、図６のリンク列付加リストの末尾にリンク列付加レコード＃４、リンク列付加レコード＃５を追加する。上記により図１７のリンク列４、リンク列５のリンク列番号はそれぞれ４、５となる。

上記のように、更新レコード＃ｒ８、ｒ９、ｒ１０により、図１９のリンク列テーブル、図２０のリンク列レコード、図１９のリンク列付加リスト、図２４のリンク列５のリンク列付加レコードが得られる。

上記処理後、ステップ３０２へ行く。

ステップＳＴ３０２では、リンクが廃止または分割されることによりノードに接続する順方向リンクおよびその前方リンクが存在しなくなる場合に、上記順方向リンクを示している接続リンクレコードを削除する。但し、上記ノードのノード状態が廃止の場合は、ノード付加レコードが存在しないため接続リンクレコードの削除は行わない。

ステップＳＴ３００で得た更新レコードがリンク列先頭のリンクの廃止または分割を示す場合、更新レコードが示すリンクの始点ノードのノード付加レコードの接続リンク情報における上記廃止するリンクを示している接続リンクレコードを削除する。

また、更新レコードがリンクの廃止または分割を示す場合で且つ以前のステップＳＴ３００で得た更新レコードが上記リンクの前方リンクの廃止または分割を示す場合、更新レコードが示すリンクの始点ノードのノード付加レコードの接続リンク情報における上記リンクの接続リンクレコードを削除する。

また、更新レコードがリンク列の廃止を示す場合、上記リンク列の仮想リンクも含めた各リンクについて、上記リンクの始点ノードのノード付加レコードにおける接続リンク情報の上記リンクの接続リンクレコードを削除する。

図２９の更新レコード＃ｒ６に対し、上記更新レコードはリンク列０の先頭のリンクＬ００の分割を示すため、リンクＬ００の図１０のリンクレコード＃０が示す始点ノード番号（＝０）により、リンクＬ００の始点ノードＮ０を求め、ノードＮ０の図１４のノード付加レコード＃０におけるリンクＬ００を示している接続リンクレコードＣ００を削除する。

また、図２９の更新レコード＃ｒ７に対し、上記更新レコードはリンク列０のリンクＬ０１の廃止を示し、前回の取得した図２９の更新レコード＃ｒ６はリンクＬ０１の前方リンクであるリンク列０リンクＬ００の分割を示すため、リンクＬ０１のリンクレコードの始点ノード番号から始点ノードＮ１を求め、ノードＮ１の図１４のノード付加レコード＃１におけるリンクＬ０１を示している接続リンクレコードＣ１０を削除する。

また、図２９の更新レコード＃ｒ８に対し、上記更新レコードはリンク列２の廃止を示し、リンク列２のリンクＬ２０、仮想リンクＬ２０’の始点ノードＮ２、Ｎ５をそれぞれのリンクレコードの始点ノード番号から求め、始点ノードＮ２の図１４のノード付加レコード＃２におけるリンクＬ２０を示している接続リンクレコードＣ２２を削除する。尚、始点ノードＮ５は廃止されているため接続リンクレコードの削除は行わない。

上記処理後、ステップＳＴ３０３へ行く。

ステップＳＴ３０３では、ステップＳＴ３００で得た更新レコードがリンク列の新設を示すとき、新設するリンク列の各リンクについて、リンクの始点ノードのノード付加レコードにおける接続リンク情報に上記リンクを示す接続リンクレコードを追加する。

また、追加する接続リンクレコードのノード単位リンク番号には、既存の接続リンクレコードのノード単位リンク番号として使用されていない最小の番号を格納する。

図２９の更新レコード＃ｒ１０に対して、ステップ３０１で得られたリンク列５の図１９、図２４のリンク列付加レコード＃５におけるリンクＬ５０、Ｌ５１、Ｌ５１’のリンクレコードの始点ノード番号により、それらの始点ノードＮ０、Ｎ９、Ｎ１を求め、ステップ３０１で得られた図１９のノード付加リストにおけるノードＮ０、Ｎ９、Ｎ１のノード付加レコード＃０、１、９の接続リンク情報の末尾にリンクＬ５０、Ｌ５１、Ｌ５１’を示す接続リンクレコード追加する。上記により、リンクＬ５０、Ｌ５１、Ｌ５１’を示す接続リンクレコードＣ０１、Ｃ９０、Ｃ１２を追加した図２３の接続リンクレコード＃０、＃１、＃９を得る。

このとき、接続リンクレコードＣ１２の接続リンク列番号にはリンク列５のリンク列番号５を格納し、接続リンク列内リンク番号はリンクＬ５０のリンク列内リンク番号０を格納し、ノード単位リンク番号には、本ステップ処理時に存在している接続リンクレコードＣ１１使用している番号１以外の最小値である０を格納する。接続リンクレコードＣ０１、Ｃ９０についても同様にして格納する。

図２９の更新レコード＃ｒ９に対しても上記と同様にして、ノードＮ２、Ｎ７、Ｎ８のノード付加レコードである図１９のノード付加レコード＃２、＃７、＃８の接続リンク情報の末尾にリンクＬ４０、Ｌ４１、Ｌ４１’を示す接続リンクレコードを追加する。上記により、リンクＬ４０、Ｌ４１、Ｌ４１’を示す接続リンクレコードＣ２３、Ｃ７１、Ｃ８０を追加した図２３のノード付加レコード＃２、＃７、＃８を得る。

上記処理後、ステップＳＴ３０４へ行く。

ステップＳＴ３０４では、上記道路網更新データから、すべての更新レコードの取得が終了したか否かを調べ、終了していればステップＳＴ３０５へ行き、終了していなければステップＳＴ３００へ戻りステップＳＴ３００からＳＴ３０４を繰り返す。

ステップＳＴ３０５では、上記更新レコードによる更新結果、更新されたリンク列付加レコードに対し、リンク付加レコード有無情報を参照し、リンク付加レコードを有するリンクレコードのリンク付加ポインタに対応するリンク付加レコードのアドレスを格納する。 尚、上記アドレスは、リンク付加リスト先頭から対応するリンク付加レコードの前までに格納されている各リンク付加レコードにおけるリンク付加ヘッダのリンク付加レコードサイズを累積することにより求める。

上記処理後、ステップＳＴ３０６へ行く。

ステップＳＴ３０６では、上記更新レコードによる更新結果に合わせて上記道路網データの道路網データヘッダの更新し、道路網データ更新を終了する。

上記ステップＳＴ３００〜ＳＴ３０６により、図３の道路網を表す道路網データである図５、図６、図９、図１０、図１３、図１４のデータを、図１７の道路網を表す道路網データである図１８、図１９、図２０、図２１、図２２、図２３、図２４に示すデータに更新される。

図３８は、図３１のステップＳＴ２２の経路表示の詳細なフローチャートである。ステップＳＴ４００では、ステップＳＴ１７で得た経路データから経路レコードをその並びの順に１つ取り出し、ステップＳＴ４０１へ行く。

ステップＳＴ４０１では、ステップＳＴ４００で取得した経路レコードのリンク番号の最小値、最大値に含まれるリンク番号を持つリンクを特定する。
地図データが更新されていない場合において、図３２の経路レコード＃０に対して、図３の道路網に対応する図６のリンク列テーブル、リンク列付加リストから、リンク番号が０〜２５５であるリンクＬ００を特定し、図１０におけるリンクＬ００のリンクレコード＃０、リンク付加レコード＃０を得る。また、図３４の経路レコード＃１に対しても、同様にしてリンク番号が１２８０〜１５３５であるリンクＬ３０を特定し、そのリンクレコード、リンク付加レコードを得る。

また、地図データが更新されている場合において、図３２の経路レコード＃０に対して、図１７の道路網に対応する図１９のリンク列テーブル、リンク列付加リストから、リンク番号が０〜２５５であるリンクＬ００を特定し、図２１におけるリンクＬ００のリンクレコード＃０、リンク付加レコード＃０を得る。また、図３４の経路レコード＃１に対しても、同様にしてリンク番号が１２８０〜１５３５であるリンクＬ３０を特定し、そのリンクレコード、リンク付加レコードを得る。

上記処理後ステップＳＴ４０２へ行く。

ステップＳＴ４０２では、ステップＳＴ４０１で特定したリンクのリンクレコードのリンク状態が存続であるか否かを確認し、存続であればステップＳＴ４０３へ行き、存続でなければステップＳＴ４０４へ行く。

地図データが更新されていない場合において、図３４の経路レコード＃０に対して、リンクＬ００の図１０のリンクレコード＃０のリンク状態は存続であるためステップＳＴ４０３へ行き、地図データが更新されている場合において、図３４の経路レコード＃０に対して、リンクＬ００の図２１のリンクレコード＃０のリンク状態は分割であるためステップＳＴ４０４へ行く。

図３４の経路レコード＃１に対して、対応するリンクＬ３０は存続するため、ステップＳＴ４０３へ行く。

ステップＳＴ４０３では、ステップＳＴ４０１で特定したリンクの両端のノードのノード番号をステップＳＴ４０１で特定したリンクとその後方リンクのリンクレコードの始点ノード番号から求め、ノードテーブル、ノード付加テーブルから上記リンクの両端のノードのノード座標を取得し、ステップＳＴ４０１で特定したリンクのリンク付加レコードからリンク形状情報を取得し、取得したノード座標、リンク形状情報を用いてステップＳＴ２０で表示した表示した地図画面上に、ステップＳＴ４０１で特定したリンクの形状を強調して表示する。

地図データが更新されていない場合において、図３４の経路レコード＃０に対して、図１４のノード付加レコード＃１、ノードレ付加コード＃２からノードＮ０、Ｎ１のノード座標（ｘ０，ｙ０）、（ｘ１，ｙ１）と、リンクＬ００の図１０におけるリンク付加レコード＃０からリンク形状情報ｓｉ００とによりリンクＬ００の形状を上記地図画面上に強調して表示する。

図３４の経路レコード＃１に対して、対応するリンクＬ３０の形状も上記と同様にして表示する。

上記処理後ステップＳＴ４０４へ行く。

上記ステップＳＴ４０２、ＳＴ４０３により、経路に対応するリンクで、存続しているリンクの形状が表示される。

ステップＳＴ４０４では、ステップＳＴ４０１で特定したリンクレコードのリンク状態が分割であるか否かを確認し、分割であればステップＳＴ４０５へ行き、分割でなければステップＳＴ４０６へ行く。

地図データが更新されていない場合において、図３４の経路レコード＃０に対して、リンクＬ００の図１０のリンクレコード＃０のリンク状態は存続であるためステップＳＴ４０６へ行き、地図データが更新されている場合において、図３４の経路レコード＃０に対して、リンクＬ００の図２１のリンクレコード＃０のリンク状態は分割であるためステップＳＴ４０５へ行く。

図３４の経路レコード＃１に対して、対応するリンクＬ３０は存続するため、ステップＳＴ４０６へ行く。

ステップＳＴ４０５では、ステップＳＴ４０１で特定したリンクのリンクレコード中の分割リンク番号が示すリンク列の各リンクのリンク形状をステップＳＴ２０で表示した表示した地図画面上に強調して表示する。

地図データが更新されている場合において、図３４の経路レコード＃０に対して、リンクＬ００の図２１のリンクレコード＃０の分割リンク列番号からリンク列番号が５であるリンク列５を求め、リンク列５の図２０におけるリンク列レコード＃５およびリンク列５の図２４のリンク列付加レコードにより、リンクＬ５０、Ｌ５１のリンク形状をステップＳＴ４０３と同様にして上記地図画面上に表示する。このように、リンクＬ００が分割されても、リンクＬ００に対応する経路計算データのリンクである図３３のリンクＬｒ００に付与したリンク番号を変更することなくリンクの対応関係を保つことができ、正しく経路を表示できる。

上記処理後、ステップＳＴ４０６へ行く。

上記ステップＳＴ４０４、ＳＴ４０５により、経路に対応するリンクで、分割して得られたリンクの形状を表示する。

ステップＳＴ４０６では、経路データからすべての経路レコードの取得が終了したかを確認して、終了していなければステップＳＴ４００へ戻り上記ステップＳＴ４００〜ＳＴ４０６を繰り返し、終了していれば経路表示を終了する。

上記のようにして、経路データが示す経路に対応するリンクの形状を表示する。また、リンク状態、分割リンク列番号により、リンクが分割されていることが判るとともにその分割リンク列のリンク列レコードの格納位置が直ちに判るため、リンクが分割された場合でも経路をすばやく表示する。

尚、図３８はリンク分割が一回の時の例であるが、リンク分割が多数回の場合も、分割リンク列の各リンクに対してステップＳＴ４０２〜ＳＴ４０５を再帰的に行うことにより、経路表示が可能である。

実施の形態１による地図データは上記のようなデータ構造としているため、ノードデータをリンク列データから分離してノードテーブル、ノード付加リストに格納することにより、同一のノードデータを重複して格納することがなく、同一のノードデータに関する重複した更新が不要で、更新が容易な地図データが得られるという効果があり、ノード識別子としてノード番号を用いることによりノードデータを速やかに手得できるという効果があり、また、上記のデータ構造の地図データを格納した媒体により更新が容易でより高速な地図情報処理が可能な地図データを地図情報処理装置へ提供できるという効果があり、また、上記媒体に格納した地図データを用いることにより処理負荷がより軽く、より高速な地図データの更新を可能とし、より高速な地図情報処理を可能とする地図情報処理装置が得られるという効果がある。

また、ノードの順方向リンクを示す接続リンクレコードからなる接続リンク情報によりノードに接続するリンクを表しているため、リンクの廃止、新設に伴う接続リンク情報の更新を接続リンクレコード削除、追加という単純な処理行うことができ、更新が容易な地図データが得られ、また、ノードの順方向リンクを表す接続リンクレコードのみを設けることにより地図データのデータサイズを削減できるという効果があり、また、上記のデータ構造の地図データを格納した媒体により更新が容易な地図データを地図情報処理装置へ提供できるという効果があり、また、上記媒体に格納した地図データを用いることにより処理負荷がより軽く、より高速な地図データの更新を可能とする地図情報処理装置が得られるという効果がある。

また、接続リンクレコードの接続リンク特定情報として、リンク列番号、リンク列内リンク番号を使用しているため、ノードに接続しているリンクのリンクレコードの所在が直ちに分かり、リンクに関する情報を素早く取得できる地図データが得られるという効果があり、上記地図データを用いることにより処理負荷がより軽く、より高速な地図データの更新を可能とする地図情報処理装置が得られるという効果がある。

また、ノードに接続する順方向リンクにノード単位リンク識別としてノード単位リンク番号を付与しているため、リンクが存在している間不変なノード単位リンク番号を付与することができ、他のリンクの廃止、新設により既存の通行規制レコードの内容変更が不要となり、更新が容易な地図データが得られるという効果があり、上記地図データを用いることにより処理負荷がより軽く、より高速な地図データの更新を可能とする地図情報処理装置が得られるという効果がある。

また、リンクの分割に対して分割リンク列を設け、リンクレコードにリンクの分割に関する情報、即ちリンクが分割されていることを示すリンク状態、分割リンク列を示す分割リンク列番号を設けたため、分割するリンク以降のリンクのリンク列内リンク番号を変化させることなくリンク分割を可能とし、分割リンク列のリンク列レコード、リンク列付加レコードを素早く取得でき、更新が容易な地図データが得られるとともに経路表示等の素早い表示を可能にする地図データが得られるという効果があり、上記地図データを用いることにより処理負荷がより軽く、より高速な地図データの更新を可能とし、経路表示等の素早い表示を可能とする地図情報処理装置が得られるという効果がある。

また、経路誘導レコードのようなノード関連情報に対応ノード番号を格納するようにしたため、ノード関連情報の更新に伴う地図データの更新が発生せず、更新が容易な地図データが得られるという効果があり、上記地図データを用いることにより処理負荷がより軽く、より高速な地図データの更新を可能とする地図情報処理装置が得られるという効果がある。

また、分割前のリンクに付与されていたリンク番号を、分割後のリンクに配分するようにし、配分により得られる分割後のリンクのリンク番号の範囲を、分割前のリンクのリンク番号の範囲を等分割した範囲に応じて定めるようにしたため、どのリンクに対しても所定回数の分割が可能となり、リンク分割時の更新が容易な地図データが得られるという効果があり、また、上記のデータ構造の地図データを格納した媒体により更新が容易な地図データを地図情報処理装置へ提供できるという効果があり、また、上記媒体に格納した地図データを用いることにより処理負荷がより軽く、より高速な地図データの更新を可能とする地図情報処理装置が得られるという効果がある。

また、ノードの廃止、新設時の地図データ更新方法として、既存のノードのノード番号が変化しないようにしたため、既存のリンクレコードの始点ノード番号の変更、既存の経路誘導レコードの変更が不要となり、地図データの更新をより高速に行えるという効果がある。

また、リンクの廃止、新設時の地図データ更新方法として、既存のリンク列、リンクのリンク列番号、リンク列内リンク番号が変化しないようにしたために、既存の接続リンクレコードの変更が不要となり、地図データの更新が容易にでき、地図データの更新をより高速に行えるという効果がある。

また、リンク列の新設時の地図データ更新方法として、新設するリンク列のリンク列データから、新設するリンク列のリンクが接続するノードの接続リンクレコードを作成するようにしたため、接続リンクレコードを追加するための更新レコードが不要となり、より少ない道路網更新データで地図データの更新を可能とするという効果がある。

また、リンク列の分割時の地図データ更新方法として、リンクに一定範囲のリンク番号を付与し、リンク分割時に、分割前のリンクのリンク番号の範囲の等分に基づいて定めた範囲の番号をリンクを分割してできるリンクに付与するようにしたため、どのリンクに対しても所定回数の分割が可能となり、地図データの更新をより高速に行えるという効果がある。

実施の形態２．
実施の形態２は、実施の形態１において、リンクを分割する場合に、分割後のリンクのリンク番号の範囲が、分割前のリンクに付与されていたリンク番号の範囲を、分割語のリンクのリンク長に比例して配分するようにしたものである。

図３９は、図３のリンクＬ００を図１７のリンクＬ５０、Ｌ５１に分割した場合のリンク番号の付与例を示す図である。図３９において、リンクＬ００のリンクの一端から他端へ至る距離即ちリンク長を１００ｍとし、リンクＬ００を分割して得られたリンクＬ５０、Ｌ５１のリンク長をそれぞれ２５ｍ、７５ｍとするとき、リンクＬ００に付与されていた０〜２５５の範囲のリンク番号をリンクＬ００のリンク長に対するリンクＬ５０、Ｌ５１のリンク長の比に応じて配分し、リンクＬ５０、Ｌ５１のそれぞれに０〜６３、６４〜２５５なるリンク番号を付与する。

図４０は、実施の形態２におけるリンクＬ００の分割後のリンクＬ５０、Ｌ５１からなるリンク列５のリンク付加リストの格納例を示す図である。
実施の形態２におけるリンク列５のリンク列付加レコードは、図２４の実施の形態１におけるリンク列５のリンク列付加レコードのリンク付加リストを図４０のリンク付加リストとしたものとなる。

図４０のリンク付加リストにおいて、リンク付加レコード＃１に値が６４であるリンク番号情報を設け、リンクＬ５０、Ｌ５１のリンク番号がれぞれ０〜６３、６４〜２５５となるようにしている。

また、図３９に示すように、リンクＬ５０をさらに、リンク長２０ｍのリンクＬ５０−０とリンク長５ｍのリンクＬ５０−１に分割する場合には、リンクＬ５０に付与されていた０〜６３の範囲をリンクＬ５０のリンク長に対するリンクＬ５０−０、Ｌ５１−１のリンク長の比に応じて配分し、リンクＬ５０−０、Ｌ５１−１のそれぞれに０〜５１、５２〜６３なるリンク番号を付与する。但し、上記比によって配分した範囲は０〜５１．２、５１．２〜６３となるがリンク番号は整数であるため、上記範囲が重複しないように上記範囲の少数部の切り捨て、切り上げを行っている。
以下同様にして、配分ができなくなるまで分割を繰り返すことができる。

上記のように実施の形態２によれば、リンクの分割においてリンク長の比に応じてリンク番号を配分したため、地図データ作成当初におけるリンク長の長短に関わらず、どのリンクに対しても同程度の回数のリンク分割を可能とし、リンク分割時の更新が容易な地図データが得られるという効果があり、上記のデータ構造の地図データを格納した媒体により更新が容易な地図データを地図情報処理装置へ提供できるという効果があり、上記媒体に格納した地図データを用いることにより処理負荷がより軽く、より高速な地図データの更新が可能な地図情報処理装置が得られるという効果がある。

また、リンクの分割時の地図データ更新方法として、リンク長の比に応じてリンク番号を配分するようにしたため、地図データの更新をより高速に行えるという効果がある。

尚、実施の形態１において、地図情報記憶装置３の記憶媒体としてハードディスクを用いたが、メモリリーカード、光磁気ディスク等読み書きが可能な記憶媒体であればいずれを用いてもよい。

また、地図情報を地図情報記憶装置３のハードディスクに格納したが、ＣＤ−ＲＯＭ（Compact Disc−Read Only Memory）、ＤＶＤ−ＲＯＭ等の読み取り専用の記憶媒体に格納し、その記憶媒体の読み取り装置を設け、読み取り装置により記憶媒体の地図情報を読み取るようにしてもてもよい。

また、地図更新情報の格納媒体としてＤＶＤ−ＲＯＭを用いたが、ＣＤ−ＲＯＭ、メモリカード等読み出し可能な記憶媒体であればいずれを用いてもよく、更新情報取得装置４としてＤＶＤドライブを用いたが、地図更新情報の格納媒体に適合した装置であればいずれを用いてもよい。

また、地図データを地図情報記憶装置３から読み取ることにより取得したが、通信手段を用いて、他の装置から地図データを取得するようにしてもよい。

また、更新情報取得装置４により取得した地図更新情報を地図情報記憶装置３に格納し、地図情報記憶装置３から地図更新データを読み取るようにしたが、更新情報取得装置４により地図更新情報の記憶媒体から地図更新データを読み取るようにしてもよい。

また、更新情報取得装置４として、地図更新情報の記憶媒体から地図更新情報を取得するようにしたが、通信手段を用いて、他の装置から地図更新情報を取得するようにしてもよい。

また、更新情報取得装置４により取得した地図更新情報を地図情報記憶装置３に格納し、地図情報記憶装置３から地図更新データを読み取るようにしたが、通信手段を用いて、他の装置から地図更新データを取得するようにしてもよい。

また、更新した地図データを地図情報記憶装置３に格納していなかったが、更新した地図データを地図情報記憶装置３に格納するようにしてもよい。

また、リンクの始点ノードを指定するためにリンクレコードに始点ノードのノード番号を格納したが、始点ノードのノードレコードの格納位置を示す情報を格納するようにしてもよい。

また、リンクレコードに分割リンクに関わる情報として、リンク状態、分割リンク列番号を格納するようにしたが、リンク状態だけを格納するようにし、分割リンク列はリンク状態が分割となっているリンクのリンク番号を持つリンク列を分割リンク列として見つけるようにしてもよい。

また、リンクの分割時に、分割リンク列を設けるようにしたが、分割リンク列を設けず分割前のリンクを分割後のリンクに置き換えてもよい。即ち、リンクの分割により新たに生じたノードのノードレコード、ノード付加レコードをノードテーブル、ノード付加レコードに追加し、分割前のリンクのリンクレコード、リンク付加レコードを分割後の各リンクのリンクレコード、リンク付加レコードに置き換えるようにしてもよい。

また、リンク列、リンクの廃止・新設により、既存のリンク列番号とリンク列内識別番号がともに変化しないようにしたが、既存のリンク列番号とリンク列内識別番号の少なくともいずれかが変化しないようにしてもよい。

また、経路計算データを用いて経路計算は行ったが、地図データの道路網データを用いて経路計算を行ってもよい。

この発明の実施の形態１における地図情報処理装置の構成を示すブロック図である。 この発明の実施の形態１における地図情報の概略データ構造を示す図である。 この発明の実施の形態１における道路網の例を示す図である。 この発明の実施の形態１における道路網データのデータ構造の一例を示す図である。 この発明の実施の形態１におけるノードテーブル、ノード付加リストのデータ構造の一例を示す図である。 この発明の実施の形態１におけるリンク列テーブル、リンク列付加リストのデータ構造の一例を示す図である。 この発明の実施の形態１におけるリンク列レコードのデータ構造の一例を示す図である。 この発明の実施の形態１におけるリンク列付加レコードのデータ構造の一例を示す図である。 この発明の実施の形態１におけるリンク列レコードの格納例を示す図である。 この発明の実施の形態１におけるリンク列０のリンク列付加レコード＃０の格納例を示す図である。 この発明の実施の形態１におけるノードレコードのデータ構造の一例を示す図である。 この発明の実施の形態１におけるノード付加レコードのデータ構造の一例を示す図である。 この発明の実施の形態１におけるノードレコードの格納例を示す図である。 この発明の実施の形態１におけるノード付加レコードの格納例を示す図である。 この発明の実施の形態１における経路誘導データのデータ構造の一例を示す図である。 この発明の実施の形態１における経路誘導データの格納例を示す図である。 この発明の実施の形態１における道路網を更新して得られた道路網を示す図である。 この発明の実施の形態１における更新して得られたノードテーブル、ノード付加リストの格納例を示す図である。 この発明の実施の形態１における更新して得られたリンク列テーブル、リンク列付加リストの例を示す図である。 この発明の実施の形態１におけるリンク列テーブルにおけるリンク列レコードの格納例を示す図である。 この発明の実施の形態１における更新して得られたリンク列０のリンク列付加レコード＃０のリンク列付加ヘッダ、リンクテーブルの格納例を示す図である。 この発明の実施の形態１におけるノードテーブルの各ノードレコードの格納例を示す図である。 この発明の実施の形態１における更新して得られたノード付加レコードの格納例を示す図である。 この発明の実施の形態１における分割して得られたリンク列５のリンク列付加レコード＃５の格納例を示す図である。 この発明の実施の形態１におけるリンクを分割したときのリンク番号の付与例を示す図である。 この発明の実施の形態１における更新して得られた経路誘導データの例を示す図である。 この発明の実施の形態１における更新用ＤＶＤ−ＲＯＭに格納された地図更新情報の概略データ構造を示す図である。 この発明の実施の形態１における更新レコードのデータ構造の一例を示す図である。 この発明の実施の形態１における道路網更新データの格納例を示す図である。 この発明の実施の形態１における経路誘導更新データの格納例を示す図ある。 この発明の実施の形態１における地図情報処理装置の動作を示すフローチャートである。 この発明の実施の形態１におけるプロセッサ５のメモリの割り当てを示す図である。 この発明の実施の形態１における経路計算データが表す道路網の例を示す図である。 この発明の実施の形態１における経路データの一例を示す図である。 この発明の実施の形態１における経路計算データ取得・更新の詳細なフローチャートである。 この発明の実施の形態１における地図データ取得・更新の詳細なフローチャートである。 この発明の実施の形態１における道路網データ更新の詳細なフローチャートである。 この発明の実施の形態１における経路表示の詳細なフローチャートである。 この発明の実施の形態２における分割したリンクへのリンク番号の付与例を示す図である。 この発明の実施の形態２における分割して得られたリンクからなるリンク列のリンク付加リストの格納例を示す図である。

符号の説明

１ 入力装置、２ 位置検出装置、３ 地図情報記憶装置、４ 更新情報取得装置、５ プロセッサ、６ 出力装置、１０ 動作制御データ部、１１ 走行軌跡データ部、１２ 現在位置データ部、１３ 経路データ部、１４ 所要経路計算データ管理部、１５ 経路計算データ部、１６ 経路計算更新データ部、１７ 所要地図データ管理部、１８ 地図データ部、１９ 地図更新データ部。

Claims (5)

1. 道路上の地点を表すノードに関わる情報を示すノードデータと、上記地点間の道路を表すリンクに関わる情報を示すリンクデータとを用いて道路網を表す地図データであって、
   上記道路網における道路の連なりを上記リンクの連なりとして表したリンク列に対し、上記リンク列を構成するリンクのリンクデータをリンクの連なりの順に応じて配置したリンク列データを設け、上記道路網の各ノードのノードデータをリンク列データとは別に設け、上記道路網の各ノードのノードデータにノードを識別するためのノードデータの並び順を示すノード識別子を付与し、上記リンク列データ内のすべてのリンクデータがリンク列の向きに応じて定められたリンク端の１つのノードのノード識別子を示す情報を有するようにした地図データを取得する地図データ取得手段と、
   上記地図データ取得手段により取得した地図データのリンクデータを参照してリンクデータの形状情報を取得するリンクデータ参照手段と、
   上記地図データ取得手段により取得した地図データのノードデータを参照してノードデータのノード座標を取得するノードデータ参照手段とを有し、
   上記リンクデータ参照手段とノードデータ参照手段とによりリンクデータの形状情報とノードデータのノード座標とを用いて道路を描画する地図情報処理を行う地図情報処理装置において、
   上記地図データは、リンクが分割されたとき、リンクを分割してできたリンクからなるリンク列である分割リンク列のリンク列データを設け、分割されたリンクのリンクデータが上記分割リンク列に関わる情報を有するようにしたことを特徴とする地図情報処理装置。
2. 道路上の地点を表すノードに関わる情報を示すノードデータと、上記地点間の道路を表すリンクに関わる情報を示すリンクデータとを用いて道路網を表す地図データであって、
   上記道路網における道路の連なりを上記リンクの連なりとして表したリンク列に対し、上記リンク列を構成するリンクのリンクデータをリンクの連なりの順に応じて配置したリンク列データを設け、上記道路網の各ノードのノードデータをリンク列データとは別に設け、上記道路網の各ノードのノードデータにノードを識別するためのノードデータの並び順を示すノード識別子を付与し、上記リンク列データ内のすべてのリンクデータがリンク列の向きに応じて定められたリンク端の１つのノードのノード識別子を示す情報を有するようにした地図データを取得する地図データ取得手段と、
   上記地図データ取得手段により取得した地図データのリンクデータを参照してリンクデータの形状情報を取得するリンクデータ参照手段と、
   上記地図データ取得手段により取得した地図データのノードデータを参照してノードデータのノード座標を取得するノードデータ参照手段とを有し、
   上記リンクデータ参照手段とノードデータ参照手段とによりリンクデータの形状情報とノードデータのノード座標とを用いて道路を描画する地図情報処理を行う地図情報処理装置において、
   上記地図データは、ノードデータに当該ノードが廃止されたか否かを示すノード状態情報を設け、
   上記地図データを更新するための地図更新データを取得する地図更新データ取得手段と、地図データ取得手段により取得した地図データを地図更新データ取得手段により取得した地図更新データを用いて更新する地図データ更新手段とを有し、
   地図データ更新手段を、地図データ取得手段により取得した地図データに対し上記ノード状態情報の書き換え、またはノードデータの並びの末尾への新規ノードデータを付加するようにしたことを特徴とする地図情報処理装置。
3. 道路上の地点を表すノードに関わる情報を示すノードデータと、上記地点間の道路を表すリンクに関わる情報を示すリンクデータとを用いて道路網を表す地図データであって、
   上記道路網における道路の連なりを上記リンクの連なりとして表したリンク列に対し、上記リンク列を構成するリンクのリンクデータをリンクの連なりの順に応じて配置したリンク列データを設け、上記道路網の各ノードのノードデータをリンク列データとは別に設け、上記道路網の各ノードのノードデータにノードを識別するためのノードデータの並び順を示すノード識別子を付与し、上記リンク列データ内のすべてのリンクデータがリンク列の向きに応じて定められたリンク端の１つのノードのノード識別子を示す情報を有するようにした地図データを取得する地図データ取得手段と、
   上記地図データ取得手段により取得した地図データのリンクデータを参照してリンクデータの形状情報を取得するリンクデータ参照手段と、
   上記地図データ取得手段により取得した地図データのノードデータを参照してノードデータのノード座標を取得するノードデータ参照手段とを有し、
   上記リンクデータ参照手段とノードデータ参照手段とによりリンクデータの形状情報とノードデータのノード座標とを用いて道路を描画する地図情報処理を行う地図情報処理装置において、
   上記地図データは、リンク列データに当該リンク列が廃止されたか否かを示すリンク列状態情報を設け、
   リンクデータに当該リンクが廃止されたか否かを示すリンク状態情報を設け、
   上記地図データを更新するための地図更新データを取得する地図更新データ取得手段と、地図データ取得手段により取得した地図データを地図更新データ取得手段により取得した地図更新データを用いて更新する地図データ更新手段とを有し、
   地図データ更新手段を、地図データ取得手段により取得した地図データに対し上記リンク列状態情報の書き換え、またはリンク列データの並びの末尾への新規リンク列データの付加、または上記リンク状態情報の書き換え、またはリンクデータの並びの末尾への新規リンクデータの付加を行うようにしたことを特徴とする地図情報処理装置。
4. 道路上の地点を表すノードに関わる情報を示すノードデータと、上記地点間の道路を表すリンクに関わる情報を示すリンクデータとを用いて道路網を表す地図データであって、
   上記道路網における道路の連なりを上記リンクの連なりとして表したリンク列に対し、上記リンク列を構成するリンクのリンクデータをリンクの連なりの順に応じて配置したリンク列データを設け、上記道路網の各ノードのノードデータをリンク列データとは別に設け、上記道路網の各ノードのノードデータにノードを識別するためのノードデータの並び順を示すノード識別子を付与し、上記リンク列データ内のすべてのリンクデータがリンク列の向きに応じて定められたリンク端の１つのノードのノード識別子を示す情報を有するようにした地図データを取得する地図データ取得手段と、
   上記地図データ取得手段により取得した地図データのリンクデータを参照してリンクデータの形状情報を取得するリンクデータ参照手段と、
   上記地図データ取得手段により取得した地図データのノードデータを参照してノードデータのノード座標を取得するノードデータ参照手段とを有し、
   上記リンクデータ参照手段とノードデータ参照手段とによりリンクデータの形状情報とノードデータのノード座標とを用いて道路を描画する地図情報処理を行う地図情報処理装置において、
   上記地図データ取得手段をさらに道路網のリンクそれぞれに固有の範囲のリンク番号を付与した地図データを取得するようにし、上記地図データにおけるリンクを分割する更新に際し、分割前のリンクに付与されていた上記範囲のリンク番号を、分割後のリンクに配分するようにし、上記配分により得られる分割後のリンクのリンク番号の範囲を、上記分割前のリンクのリンク番号の範囲を等分割した範囲に応じて定めるようにしたことを特徴とする地図情報処理装置。
5. 道路上の地点を表すノードに関わる情報を示すノードデータと、上記地点間の道路を表すリンクに関わる情報を示すリンクデータとを用いて道路網を表す地図データであって、
   上記道路網における道路の連なりを上記リンクの連なりとして表したリンク列に対し、上記リンク列を構成するリンクのリンクデータをリンクの連なりの順に応じて配置したリンク列データを設け、上記道路網の各ノードのノードデータをリンク列データとは別に設け、上記道路網の各ノードのノードデータにノードを識別するためのノードデータの並び順を示すノード識別子を付与し、上記リンク列データ内のすべてのリンクデータがリンク列の向きに応じて定められたリンク端の１つのノードのノード識別子を示す情報を有するようにした地図データを取得する地図データ取得手段と、
   上記地図データ取得手段により取得した地図データのリンクデータを参照してリンクデータの形状情報を取得するリンクデータ参照手段と、
   上記地図データ取得手段により取得した地図データのノードデータを参照してノードデータのノード座標を取得するノードデータ参照手段とを有し、
   上記リンクデータ参照手段とノードデータ参照手段とによりリンクデータの形状情報とノードデータのノード座標とを用いて道路を描画する地図情報処理を行う地図情報処理装置において、
   上記地図データ取得手段をさらに道路網のリンクそれぞれに固有の範囲のリンク番号を付与した地図データを取得するようにし、上記地図データにおけるリンクを分割する更新に際し、分割前のリンクに付与されていた上記範囲のリンク番号を、分割後のリンクに配分するようにし、上記配分により得られる分割後のリンクのリンク番号の範囲を、上記分割前のリンクのリンク長と上記分割後のリンクのリンク長との比に応じて定めるようにしたことを特徴とする地図情報処理装置。

Images