"道路に沿って付与され当該道路を特定するための属性を有する複数のコアポイントのデータを外部から受信し、当該コアポイントが示す道路に該当する地図上のリンクを抽出することで前記道路を推定する道路推定装置であって、複数エリアに分割した分割領域の単位で、前記分割領域の境界に端点を有し前記コアポイントの有する属性に応じた属性を有するリンクで構成される地図データを入力する地図データ入力手段と、前記コアポイントが前記分割領域の境界を跨いで存在する場合、前記地図データ入力手段が入力した地図データにおいて、当該分割領域の境界に新たなコアポイントである仮想コアポイントを生成するとともに、当該仮想コアポイントに前記コアポイントが有する属性に基づいた属性を設定する仮想コアポイント生成手段と、前記リンクの有する属性と前記コアポイント及び前記仮想コアポイントの有する属性とに基づき、前記地図データから前記コアポイントが示す道路の候補となるリンクを抽出するリンク抽出手段と、を備えていることを特徴とする道路推定装置。請求項1に記載の道路推定装置において、前記仮想コアポイント生成手段は、前記分割領域の境界を跨いで存在する注目コアポイントを結ぶ直線からの道路の離間距離を示す離間距離情報属性PDMの値に基づき、前記仮想コアポイントを生成することを特徴とする道路推定装置。請求項2に記載の道路推定装置において、前記仮想コアポイント生成手段は、前記離間距離情報属性PDMの値により与えられる道路形状の頂点と前記注目コアポイントとを結ぶ2本の線分を算出し、線分の一方と前記分割領域の境界との交点に前記仮想コアポイントを生成することを特徴とする道路推定装置。請求項2又は3に記載の道路推定装置において、前記仮想コアポイント生成手段は、前記注目コアポイント及び前記仮想コアポイントの属性を、前記注目コアポイントの属性に基づいて設定又は再設定することを特徴とする道路推定装置。請求項2~4の何れか一項に記載の道路推定装置において、前記仮想コアポイント生成手段は、前記仮想コアポイント生成の際、前記注目コアポイントの属性を前記生成する仮想コアポイントの配置位置を利用して再設定することで、前記仮想コアポイントの属性を設定すること、を特徴とする道路推定装置。請求項4又は5に記載の道路推定装置において、前記仮想コアポイント生成手段は、脇道への角度及び当該脇道への接続距離を示す脇道情報属性CA及び属性DCA、次のコアポイントへの位置的な角度及び接続距離を示す角度距離情報属性BR及び属性DMB、コアポイント間の運転距離を示す運転距離情報属性PD、次のコアポイントまでを結ぶ直線からの道路の離間距離を示す離間距離情報属性PDM、及び、並走する道路の情報を示す並走道路情報属性PCIの少なくともいずれかの属性を設定又は再設定することを特徴とする道路推定装置。請求項1~6の何れか一項に記載の道路推定装置において、前記リンク抽出手段は、処理対象となっている前記分割領域に含まれない前記コアポイントを処理対象から外すことを特徴とする道路推定装置。ところで、VICS以外のサービスとして、TPEGTransportProtocolExpertGroupにより送信される交通情報のデータを車両などの端末側で活用することが検討されている。しかし、TPEGにより送信されるデータフォーマット等では、例えばDLRデータの形式で位置情報が示される。この位置情報は、位置座標を有すると共に道路を特定するための属性を有するコアポイントで構成される。コアポイントは、通常、道路に沿って並ぶ複数個の配列として配信される。このようなコアポイントによって位置情報を示すようにすれば、地図データを作成するメーカの違いや地図データのフォーマット、バージョンに依存する位置参照テーブルが不要になる。すなわち、車載機側の地図データに依存せず、地図データ上で道路リンクを特定することが可能となる。その反面、コアポイントに基づいて道路を特定するための種々の処理が必要になってくる。例えば、上述したように地図データにもいろんな種類があるため、必ずしもコアポイントは地図データの道路上に存在しない。そのため、コアポイントが示す道路に該当するリンクを地図上で特定する処理が必要となってくる。ところで、地図データは、地図データを複数エリアに分割した分割領域の単位で管理される。この分割領域はパーセルと呼ばれるものである。例えば、地図の表示などを行う場合、この分割領域の単位で処理が行われる。そのため、たとえば道路が分割領域を跨ぐような場合、地図データのその道路に対応するリンクにおいては分割領域の境界上には、リンクの端点例えばノードが処理の必要上、必ず設定される。一方、コアポイントは道路に沿って並ぶ複数個の配列として配信されるのであるが、上述のような地図データの分割領域の境界を跨いで存在するのが一般的である。そのため、たまたまコアポイントに対応する本当のリンク端点が境界上に存在する場合を除き、分割領域の境界上に設定されるリンクの端点上記説明した便宜上設定された端点に対応するコアポイントは通常存在しない。結果として、コアポイントが示す道路に該当するリンクを分割領域において特定することが困難となる虞がある。本発明は、上述した問題を解決するためになされたものであり、その目的は、配信されるコアポイントの情報から、地図データの分割領域においてコアポイントが示す道路に該当するリンクを適切に推定可能な道路推定装置を提供することにある。上述した目的を達成するためになされた請求項1に記載の道路推定装置は、道路に沿って付与され当該道路を特定するための属性を有する複数のコアポイントのデータを外部から受信し、当該コアポイントが示す道路に該当する地図上のリンクを抽出することで道路を推定するものである。本装置では、地図データ入力手段が、地図データを入力する。地図データは、複数エリアに分割した分割領域の単位で入力される。また、地図データは、分割領域の境界に端点を有するリンクで構成される。さらにまた、地図データは、コアポイントの有する属性に応じた属性を有するリンクで構成される。ここで特に、本装置では、仮想コアポイント生成手段によって、コアポイントが分割領域の境界を跨いで存在する場合、地図データ入力手段が入力した地図データにおいて、当該分割領域の境界に新たなコアポイントである仮想コアポイントが生成される。また、仮想コアポイント生成手段によって、生成された仮想コアポイントにコアポイントが有する属性に基づいた属性が設定される。このとき、リンク抽出手段は、リンクの有する属性とコアポイント及び仮想コアポイントの有する属性とに基づき、地図データからコアポイントが示す道路の候補となるリンクを抽出する。つまり、本発明では、地図データが分割領域の単位で入力され当該分割領域の境界にリンクの端点が設定されることに鑑み、分割領域の境界上に、新たなコアポイントを生成すし、この新たなコアポイントの属性を計算するのである。このとき、仮想コアポイントはリンクの端点と対応付けられるものとなるため、リンク抽出手段は地図データからコアポイントが示す道路の候補となるリンクを適切に抽出することができる。その結果、配信されるコアポイントの情報から、地図データの分割領域においてコアポイントが示す道路に該当するリンクを適切に推定することができる。ここで、分割領域の境界を跨いで存在する2つのコアポイントを注目コアポイントと呼ぶことにすると、例えば注目コアポイント同士を結ぶ直線と分割領域の境界との交点に仮想コアポイントを生成することが考えられる。ただし、注目コアポイント間の道路が直線であるとは限らない。そこで、請求項2に示すように、仮想コアポイント生成手段は、注目コアポイント同士を結ぶ直線からの道路の離間距離を示す離間距離情報属性PDMの値に基づき、仮想コアポイントを生成することが例示される。具体的には、請求項3に示すように、仮想コアポイント生成手段は、離間距離情報属性PDMの値により与えられる道路形状の頂点と注目コアポイントとを結ぶ2本の線分を算出し、線分の一方と分割領域の境界との交点に仮想コアポイントを生成することが考えられる。例えば、図10aに示すように、2つの注目コアポイントとしてのCPa,CPbが分割領域の境界を跨いでいるような場合、属性PDMの値により与えられる道路形状の頂点VとCPa,CPbとを結ぶ線分を算出し、線分の一方と分割領域の境界との交点に仮想CPを生成するという具合である。このように道路の離間距離情報属性PDMの値を用いれば、道路形状に合わせて仮想コアポイントが生成される可能性が高くなる。その結果、配信されるコアポイントの情報から、地図データの分割領域においてコアポイントが示す道路に該当するリンクを適切に推定することができる。なお、その後の処理で仮想コアポイントを利用するにあたり、請求項4に示すように、注目コアポイント及び仮想コアポイントの属性を、注目コアポイントの属性に基づいて設定あるいは再設定するとよい。例えば、請求項5に示すように、仮想コアポイント生成の際、注目コアポイントの属性を生成する仮想コアポイントの配置位置を利用して再設定することが考えられ、このとき、再設定された注目コアポイントの属性に基づいて、仮想コアポイントの属性を設定するという具合である。このようにすれば、仮想コアポイントの属性を適切に設定することができる。具体的には、請求項6に示すように、仮想コアポイント生成手段は、脇道への角度及び当該脇道への接続距離を示す脇道情報属性CA及び属性DCA、次のコアポイントへの位置的な角度及び接続距離を示す角度距離情報属性BR及び属性DMB、コアポイント間の運転距離を示す運転距離情報属性PD、次のコアポイントまでを結ぶ直線からの道路の離間距離を示す離間距離情報属性PDM、及び、並走する道路の情報を示す並走道路情報属性PCIの少なくともいずれかの属性を設定又は再設定することが例示される。このように注目コアポイント及び仮想コアポイントの属性を設定又は再設定すれば、上述した効果が際だつ。ところで、仮想コアポイントが付与された後のリンク抽出手段による抽出処理に要する時間を削減するという観点からは、請求項7に示すように、リンク抽出手段は、処理対象となっている分割領域に含まれないコアポイントを処理対象から外すこととしてもよい。このようにすれば、処理対象となっている分割領域に含まれるコアポイントのみが処理対象となるため、リンク抽出手段による抽出処理に要する時間を削減することができる。以下に本発明の実施例について、図面と共に説明する。<1.ナビゲーション装置の構成>最初にナビゲーション装置の構成を図1に基づいて説明する。図1に示すナビゲーション装置10が道路推定装置として機能し、具体的には、TPEGTransportProtocolExpertGroupデータを受信し、データ中の位置情報から道路のマッチングを行い、位置情報と共に送信される交通情報を道路に対応させて表示する。図1に示すナビゲーション装置10は、受信装置11、位置検出装置12、地図データ入力装置13、操作デバイス14、音声出力デバイス15、表示デバイス16、及び、制御回路17を備えている。受信装置11は、センタ20からTPEGデータを受信するためのものである。ナビゲーション装置10では、制御回路17にて選局を行うことにより、受信装置11を介してTPEGデータを取得する。位置検出装置12は、ナビゲーション装置10を搭載した車両の現在位置を検出するためのものであり、例えば、周知のジャイロスコープ、距離センサ及びGPS受信機等を有している。地図データ入力装置13は、地図データが格納された記録媒体具体的にはハードディスクやDVDを有するものであり、この記録媒体に格納された地図データを制御回路17に入力可能に構成されている。なお、地図データ入力装置13は、地図データを記憶保持するハードディスク装置に加えてDVDドライブを備えた構成にすることができる。このように地図データ入力装置13を構成すれば、ナビゲーション装置10は、DVDメディアを通じてオプション販売される地図データの追加データを、ハードディスク装置にインストール可能な構成にすることができる。なお、地図データは、パーセルと呼ばれる単位で管理され、パーセル単位でキャッシュされる。操作デバイス14は、ユーザからの指示を制御回路17に入力するためのものであり、表示デバイス16に配置されたタッチパネルや、ナビゲーション装置10の本体表面やリモートコントローラに設けられた操作スイッチ群等により構成される。この操作デバイス14を通じて、ユーザは、地図の縮尺変更やスクロール等の操作や目的地設定などナビゲーション装置10のあらゆる操作を行うことが可能である。また、音声出力デバイス15は、スピーカ等から構成され、制御回路17からの信号を受けてユーザへの案内音声等を出力するものである。この他、表示デバイス16は、フルカラー表示が可能なものであり、この表示デバイス16には、受信装置11を介して取得されるTPEGデータに基づく交通情報が、地図データ入力装置13より入力された地図データに基づく地図画像に重ねて表示される。また、制御回路17は、周知のマイクロコンピュータと同様の構成となっており、内部にCPU17a、ROM17b、RAM17c、I/O及びこれらの構成を接続するバスラインなどを備える。そして、CPU17aは、ROM17bに記憶されているプログラムに従って、種々の処理を行う。例えば、受信装置11を介して受信されるTPEGデータにはDLRDynamicLocationReferencingデータとしての位置情報が含まれる。したがって、制御回路17は、この位置情報を基に、地図データ側で該当する道路を推定する。<2.制御回路の機能>次に、TPEGデータの処理に関する制御回路17の機能を、図2に基づいて説明する。図2は、制御回路17の機能を模式的に示す説明図である。制御回路17の機能は、選局ブロック171、アプリケーションブロック172、DLRライブラリブロック173、及び、描画ブロック174に分けられる。選局ブロック171は、上述した受信装置11を介し、TPEGデータを受信するブロックである。つまり、選局ブロック171が、上述した選局機能を有している。受信されるTPEGデータは、選局ブロック171からアプリケーションブロック172へ渡される。アプリケーションブロック172は、アプリケーションプログラムの機能として実現される。アプリケーションプログラムは、ROM17bに記憶されており、CPU17aによって実行される。アプリケーションブロック172は、選局ブロック171から受け渡されるTPEGデータを管理し、新たなTPEGデータが受信されると、TPEGデータの更新を行う。また、アプリケーションブロック172は、画面に表示される表示対象のパーセル以下対象パーセルというを特定するための情報を有している。表示画面は、縮尺によって1つの対象パーセルで構成されることもあるし、複数例えば9つの対象パーセルで構成されることもある。アプリケーションブロック172は、対象パーセルの情報、及び、TPEGデータの位置情報を対象データとしてDLRライブラリブロック173へ渡す。DLRライブラリブロック173は、DLRライブラリプログラムの機能として実現される。DLRライブラリプログラムは、アプリケーションプログラムと同様、ROM17bに記憶されており、CPU17aによって実行される。DLRライブラリブロック173は、後述するマッチング処理を実行する。マッチング処理は、TPEGデータの位置情報に基づき、地図データ入力装置13から入力される地図データでの該当する道路リンクを推定するものである。このようなマッチング処理に先立ち、DLRライブラリ173は、アプリケーションブロック172からの要請により、地図データ入力装置13から地図データをRAM17cに読み込む。マッチング処理の結果は、DLRライブラリ173により、マッチング結果としてアプリケーションブロック172へ出力される。アプリケーションブロック172は、マッチング結果を管理する。そして、描画ブロック174によって、マッチング結果に基づく地図更新が行われる。これにより、上述したように、TPEGデータに基づく交通情報が、地図データ入力装置13より入力された地図データに基づく地図画像に重ねて表示される。<3.マッチング処理>本実施例は、DLRライブラリブロック173によるマッチング処理に特徴を有している。そこで、次にマッチング処理について説明する。図3は、マッチング処理を示すフローチャートである。最初のS100では、変換処理を行う。この変換処理は、TPEGデータのDLRとしての位置情報バイナリデータを、中間データに変換するものである。TPEGデータの位置情報には離散的な地点が主として用いられることは既に述べたが、これらの離散的な地点は、コアポイント以下CPというと呼ばれる。そして、CPは、様々な属性を有している。そこで、ここでは、道路推定に必要な属性を取り出して、中間データを作成する。<3.1変換後のCPの属性>中間データへの変換後のCPが有する属性を図4に示す。通常、複数個のCPがTPEGデータの位置情報として送信される。したがって、CPは配列して管理される。もちろん、一つだけのCPから位置を推定することも可能であり、CPが一つだけ送信される場合を排除する趣旨ではない。CPは、基本的な属性として、図4に示すように、緯度、経度、IPフラグ、仮想CPフラグを有している。緯度は、CPの緯度座標であり、経度は、CPの経度座標である。また、IPフラグは、CPが交差点か否かを示すフラグである。CPが交差点を示す場合には1がセットされ、それ以外の場合には0がセットされる。さらにまた、仮想CPフラグは、CPが仮想CPか否かを示すフラグである。CPが仮想CPである場合には1がセットされ、それ以外の場合には0がセットされる。なお、仮想CPについては後述する。また、CPは、CP間を繋ぐ道路に関し、種々の属性を有している。これらの属性には、道路形状に関わる形状系の属性と、道路形状に関わらない非形状系の属性とがある。まずは、非形状系の属性を説明する。<3.1.1非形状系の属性>属性FCは、道路区分を示すものである。図5に一例を示すように、道路のクラスは、0~9の10段階で示される。0がMainroadであり、1がFirstclassroadであり、2がSecondclassroadである。以下同様に、9のNinthclassroadまでランク付けされている。例えば、Mainroadは国や首都に接続されている道路であり、firstclassroadは主要都市間を結ぶ国道であるという具合に、ランク付けされている。属性FWは、物理道路タイプを示すものである。図6に一例を示すように、物理道路タイプは、0~12の13種類に分けられている。図6を見ると、不明確の場合は0であり、高速道路は1であり、複数車道高速道路以外は2であり、単一車道は3であり、ロータリーは4であり、トラフィックスクエアは5であり、取り囲まれた交通エリアは6であり、バイパスは7であり、支線道路は8であり、駐車場入口又は出口は9であり、サービスエリア入口又は出口は10であり、歩行者地帯は11であり、通路は12である。属性RDは、道路番号例えば国道1号などの国道番号が存在すれば、その道路番号がRD値となる。また、道路番号が存在しない場合、道路名称がRD値となる。道路名称は、公式名の最大5文字となっている図4参照。属性ITは、交差点の分類を示す図4参照。図7に一例を示すように、交差点の分類は、0~6の7種類に分けられている。図7を見ると、未定義の場合は0であり、高速又は制限された道路のインターチェンジは1であり、ロータリーは2であり、1,2以外の複雑な交差点は3であり、単純な交差点は4であり、トラフィックスクエアは5であり、2価の交差点道路番号や道路名称が切り替わる交差点は6である。属性RDIは、交差点の名称を示す図4参照。属性DDは、許可された合法の運転方向を示す図4参照。例えば、未定義は0となっており、順方向が1となっており、同様に、逆方向が2、両方向が3となっているという具合である。なお、属性AFRは、属性DDが参照可能であるか否かを示すフラグである。属性DDが0~3の値を持っている場合に属性AFRは1にセットされ、属性DDが値を持っていない場合には、参照不可として0がセットされる。<3.1.2形状系の属性>次に形状系の属性を説明する。属性BRは、次のCPへの位置的な角度を示す図4参照。上述したように、通常、複数個のCPが配列として管理される。BR値は、真北を基準とする時計回りの角度である。属性DMBは、次のCPへの直線距離を示す図4参照。属性BRと同様、通常、次のCPが存在するため、次のCPへの直線距離がDMB値となっている。属性CAは、脇道に対する角度を示す。脇道とは、道路番号が付加されないようなマイナーな道路である。脇道がある場合、属性BRの角度を基準に時計回りを正とし、反時計回りを負とする角度がCA値として設定される。属性DCAは、脇道に対する接続距離を示す。すなわち、CPからのベクトルを考えた場合、属性CAがベクトルの方向を示し、属性DCAがベクトルの大きさを示すことになる。したがって、属性CA及び属性DCAによって、位置座標が決定される。この位置座標が脇道の存在する地点を示すこととなる。属性PCIは、同一方向において複数の車道が存在する場合、いずれの車道が選択されるかを示す図4参照。この属性PCIには、車道数及び、対象道路が当該車道のうちの何番目かを示すシーケンス番号が含まれる。属性PDMは、次のCPまでを結ぶ直線からの対象道路の離間距離を示す図4参照。この離間距離には、対象道路までの最大距離が設定される。属性PDは、次に属性PDを含むCPまでの対象道路に沿った道なりの運転距離を示す図4参照。以上、中間データへの変換後のCPの有する属性について説明したが、このようなCPに対しての変換に伴い、仮想CPの付与、CPの属性の計算/再計算が実行される。具体的な手順は、図8に示すごとくである。<4.マッチング処理の詳細前半>図8中のS110では、対象パーセルの境界に仮想CPを付与する。図9は、CPによって表される道路形状を便宜的に二点鎖線で示す説明図である。もちろん、このような道路形状を推定し、地図データのリンク列で示される道路とのマッチングを行うことが終局的な目標である。したがって、図9中に二点鎖線で示す道路形状は、便宜的なものであり、実際の道路形状を示すものではない。ここで重要なのは、図9に示すように、CPの配列が対象パーセルだけでなくその周囲のパーセルにも跨ることがある、ということである。このような場合に、対象パーセルの境界に仮想CPを付与する。具体的には、図10aに示すように、2つのCPa,CPbが対象パーセルの境界を跨いでいるような場合、属性PDMの値により与えられる道路形状の頂点VとCPa,CPbとを結ぶ線分を算出し、線分の一方と対象パーセルの境界との交点に仮想CPを付与する。なお、以下、複数のCPを区別するために記号a,b,c,を用い、CPa,CPb,CPcと示す。<4.1属性の再計算>次のS120では、CPの属性を再計算する。仮想CPを付与することで、終端側のCP図10aではCPbは、後述するように、処理対象のCPから外される。そこで、始端側のCP図10aではCPa及び仮想CPの属性を計算又は再計算する。対象となる属性は、属性BR、属性DMB、属性PCI、属性CA、属性DCA、属性PDM、及び、属性PDである。属性BR及び属性DMBは、次のCPへの角度及び直線距離である図4参照。したがって、新たに付与した仮想CPを含め、次のCPへの角度及び直線距離を計算して設定する。属性CA及び属性DCAについては、始端側のCP図10aではCPaでの再計算は行わない。また、仮想CPには、無効値を設定する。属性CA及び属性DCAは、脇道に関するものであり、仮想CPには脇道の情報が妥当しないためである。属性PCIは、並行する車道数に関するものである図4参照。したがって、始端側のCP図10aではCPaでの再計算は行わない。仮想CPには、始端側及び終端側図10aではCPa,CPbに設定されているPCIに従った値を設定する。仮想CPに対する属性PCIの具体的な計算ルールを図11に示す。始端側のCP及び終端側のCPがいずれも属性PCIを保持する場合、両CPでの属性PCIが一致する場合には、仮想CPに対し、両CPと同一の値を設定する。一方、両CPでの属性PCIが不一致である場合、仮想CPに対し無効値を設定する。また、始端側のCP及び終端側のCPのいずれか一方が属性PCIを保持する場合、仮想CPが、属性PCIを保持するCPの近傍にある場合には、そのCPと同一の値を設定する。一方、仮想CPが属性PCIを保持するCPの近傍にない場合には、無効値を設定する。なお、近傍とは、例えば、属性PCIを保持するCPから仮想CPまでの直線距離が始端側のCPと終端側のCPとの直線距離の10以下である場合をいう。さらにまた、始端側のCP及び終端側のCPのいずれも属性PCIを保持していない場合、仮想CPに対し無効値を設定する。属性PDMは、次のCPまでを結ぶ直線からの道路の離間距離である図4参照。この属性PDMについては、仮想CPを付与する前の値に補正値を乗じて、設定する。具体的には、仮想CPの配置位置割合を算出し、次の式で補正値を計算する。i配置位置割合が50未満のとき補正値=0.6×配置位置割合/100式1ii配置位置割合が50以上のとき補正値=1.4×配置位置割合/100-0.4式2ここで、配置位置割合は、次の式で計算される。始端側のCPの属性PDMを再計算するときの配置位置割合は、始端側CPと仮想CPとの直線距離/始端側CPから終端側CPまでの直線距離合計式3となる。また、仮想CPの属性PDMを計算するときの配置位置割合は、仮想CPと終端側CPとの直線距離/始端側CPから終端側CPまでの直線距離合計式4となる。なお、直線距離合計は、始端側CPから終端側CPまでの仮想CPを経由した場合の直線距離の合計であり、始端側CPと仮想CPとの直線距離及び仮想CPと終端側CPとの直線距離の合計となる。属性PDは、属性PDを有する次のCPまでの運転距離であり図4参照、必ずしもCPに付与される属性ではない。そのため、パーセル境界を跨ぐ2つのCPが属性PDを持たない場合がある。そこで、属性PDを持つCPのうちで仮想CPに最も近いCPを用いて再計算を行う。なお、属性PDを有するCPが存在しない場合、属性PDの再計算は行わない。具体的には、CPが有する属性PDの値を、仮想CPまでの直線距離に応じて按分する。すなわち、CPの属性PDの値は、CPの元の属性PDの値に、上記式3の配置位置割合を乗じて求める。また、仮想CPの属性PDの値は、始点CPの元の属性PDの値に、上記式4の配置位置割合を乗じて求める。<4.2CPの絞り込み>ここで図8の説明に戻り、S130では、対象パーセル内のCPに絞り込む。この処理は、対象パーセル内のCPだけ仮想CPを含むを処理対象とするものである。CPの配列は対象パーセルの境界を越えて続いていくことが考えられるが、アプリケーションで表示対象としている対象パーセルについてのみマッチングを行えば十分だからである。<4.2.1仮想CPを付与しない方法>なお、本実施例では仮想CPを付与することにより対象パーセルの境界にCPが存在するものとして当該仮想CPまでを処理対象としているが、DLRデータとして引き渡される本来のCPを対象パーセルの終端CPとして処理を行うようにしてもよい。例えば、図10bに示すように対象パーセルの境界をCPが跨いでいる場合、対象パーセル内のCPaを終端CPとしてもよい。又は、対象パーセル外の最初に現れるCPbを終端CPとしてもよい。ただし、CPa,CPbが対象パーセルの境界から離れて存在する場合があるため、例えばCPa,CPbの対象パーセルの境界からの離れ具合に応じて、いずれのCPを終端CPとするかを判断するようにしてもよい。一例として、図10bに示すように、2つのCPa,CPbを結ぶ直線と対象パーセルの境界との交点Kを算出し、交点Kまでの直線距離A,Bで離れ具合を測ることが考えられる。このとき、通常は対象パーセルの外側にあるCPbを終端CPとし、直線距離Bが所定値以上となった場合に、対象パーセルの内側にあるCPaを終端CPとすることが例示される。このときは、通常、CPbまでが処理対象となるため、対象パーセルの境界まで該当道路を探索することができ、渋滞情報などの交通情報を十分に表示することができる。また、例えばCPbが高速道路を示すような場合、CPbが対象パーセルの境界から極端に離れてしまう場合、CPaまでが処理対象となるため、処理に要する時間が長くなることを抑制できる。あるいは、通常は対象パーセルの内側にあるCPaを終端CPとし、直線距離Aが所定値以上となった場合に、対象パーセルの外側にあるCPbを終端CPとすることが例示される。このときは、通常、CPaまでが処理対象となるため、処理に要する時間を極力短くすることができる。また、例えばCPaが対象パーセルの境界から極端に離れてしまう場合、CPbまでが処理対象となるため、対象パーセルの境界まで該当道路を探索することができ、渋滞情報などの交通情報の表示が不十分になることを抑制できる。またあるいは、直線距離A,Bを比較し、直線距離Aが直線距離Bよりも小さい場合に対象パーセルの内側にあるCPaを終端CPとし、一方、直線距離Bが直線距離Aよりも小さい場合に対象パーセルの外側にあるCPbを終端CPとすることが例示される。このときは、直線距離に応じて終端CPが決定されるため、CPbまでが処理対象となる場合には、対象パーセルの境界まで該当道路を探索することができ、渋滞情報などの交通情報を十分に表示することができる。一方、CPaまでが処理対象となる場合には、処理に要する時間を極力短くすることができる。いずれにしても、仮想CPを付与する構成に比べ、仮想CPの付与に関する処理に要する時間が短縮される点、また、仮想CPの付与に伴う属性の再計算の処理に要する時間が短縮される点で有利である。<4.2.2属性の引き継ぎ>ところで、図8中のS130では、処理対象のCPを決定するに伴い、属性の引き継ぎ処理も行われる。DLRデータとしてのCPでは、交差点を示すCPIPフラグがセットされているCPだけが各種の属性を有している。そこで、このようなCPが有する非形状系の属性を、交差点間に存在するCPへ引き継ぐ。これにより、後述する処理で都度、非形状系の属性を取得する手間を省くことができる。具体的に引き継がれる属性は、属性FC、属性FW、属性RD、属性DD、及び、属性AFRである。以上説明した変換処理により、中間データに変換されたCPの配列が作成されることになる。つまり、この段階で、CPは、図4に示した各種の属性を有するものとなっている。一方で、地図データを構成するノード及びリンクの少なくともいずれかが、CPの属性に対応する属性を有している。そこで、各種属性を比較することで、終局的にCPにより示される道路を推定する。<5.マッチング処理の詳細後半>図3のマッチング処理の説明に戻り、S200では、候補リンク検索処理を実行する。候補リンク検索処理は、候補となるリンク列を検索し、その後、リンク単位で絞り込みを行うものである。次のS300では、候補選定処理を実行する。候補選定処理は、S200にて絞り込まれたリンクを、さらに絞り込むものである。続くS400では、道路マッチング処理を実行する。道路マッチング処理は、CP間を繋ぐリンクを推定するものである。これらS200~S400の処理は、図8中のS130で絞り込まれる各CPを対象CPとしてCPの数だけ繰り返し実行される。そこで、以下では、これらの処理を詳細に説明する。S200の候補リンク検索処理の一例を図12に示す。最初のS210では、対象CPの情報が取得される。この処理は、CPの種類、緯度、経度を取得するものである。CPの種類は、交差点を示すCP、仮想CP、その他のCPの区別である。続くS220では、検索範囲を設定する。この処理は、対象CPを中心とするリンクの検索範囲を設定するものである。この検索範囲は特に、図13aに破線で示すように、その境界が垂直又は水平の線分で構成される多角形として設定される。本実施例では、正方形と当該正方形の一辺よりも長い十字形状とを合成したような範囲として設定されている。次のS230では、検索範囲にあるパーセルを取得する。この処理は、ノード及びリンクがパーセル単位で管理されているため、リンク列の選定を行うにあたり、検索範囲に係るパーセルを全て取得するものである。例えば図13bに示すように、検索範囲に応じて3つのパーセルP1,P2,P3が取得されるという具合である。続くS240では、リンク列選定処理を実行する。このリンク列選定処理では、非形状系の属性により、リンクがリンク列単位で検索される。なお、リンク列とは、高速道路、一般道路などの道路区分が同一となっている一連のリンク群である。ここでは、S230にて取得されたパーセルに一部が含まれるリンク列が検索対象となる。つまり、この段階では、検索範囲にあるかの判定をせず、最初に属性でリンク列を絞り込むのである。<5.1リンク列選定処理>ここで、リンク列選定処理について詳細に説明する。リンク列選定処理の一例を図14に示す。このリンク列選定処理では、非形状系の属性である属性FC、属性FW、属性RDにより、リンク列単位での抽出が行われる。最初のS241では、属性FCが一致するリンク列に絞り込む。属性FCは、上述したように道路区分を示す属性である図5参照。ここでは、リンク列を構成するリンクに付与されている道路区分と対象CPの属性FCとの比較を行い、リンク列を絞り込む。ただし、リンク列の途中で道路区分が変わることがある。したがって、リンク列を構成する全てのリンクの道路区分が属性FCに一致する場合に、当該リンク列を候補リンク列とする。次のS242では、属性FWが一致するリンク列に絞り込む。属性FWは、上述したように、物理道路タイプを示す属性である図6参照。ここでは、リンク列を構成するリンクに付与されている物理道路タイプと対象CPの属性FWとの比較を行い、リンク列を絞り込む。ただし、リンク列の途中で物理道路タイプが変わることがある。したがって、リンク列を構成する全てのリンクの物理道路タイプが属性FWに一致する場合に、当該リンク列を候補リンク列とする。続くS243では、属性RDが一致するリンク列に絞り込む。属性RDは、上述したように、道路番号又は道路名称を示す属性である図4参照。ここでは、属性RDが道路番号を示す場合に限り、道路番号による一致を判断する。すなわち、リンク列を構成するリンクに付与されている道路番号と対象CPの属性RDとの比較を行い、リンク列を絞り込む。ただし、リンク列の途中で道路番号が変わることがある。したがって、リンク列を構成する全てのリンクの道路番号が属性RDに一致する場合に、当該リンク列を候補リンク列とする。このようなリンク列選定処理により、非形状系属性で絞り込まれたリンク列が候補リンク列として残ることになる。<5.2リンクの抽出>図12のS250では、対象CPを中心とする検索範囲に一部が含まれるリンクを抽出する。S240のリンク列選定にてリンク列が選定されるため、ここでは、選定されたリンク列を構成するリンクのうち検索範囲に一部が含まれるリンクを抽出する。ここで検索範囲に一部が含まれるリンクについて説明する。以下では特に、ノードが交差点に対して通常付与されること、ノードがパーセルの境界に付与されること、必要に応じてノード間に形状補間点が設定されること、を前提として説明を続ける。<5.2.1対象CPが交差点の場合>対象CPが交差点を示す場合は、ノードを意識した処理を行う。すなわち、対象CPが交差点を示す場合は、対象CPがノードと対応付けられるためである。したがって、この場合、リンクを構成する2つのノードのうちのいずれかが検索範囲に含まれているリンクを検索範囲に一部が含まれるリンクとする。例えば図15aに示す対象CPが交差点を示すものとする。この場合、検索範囲に含まれるノードA,B,Cは、対象CPと対応付けられる。そのため、ノードA,B,Cが端点の一方となっているリンクL1,L2,L3,L4,L5が検索範囲に一部が含まれるリンクとなる。ただし、地図データは、その縮尺に応じたレベル以下パーセルレベルというを有している。このパーセルレベルは、ユーザによる縮尺の切り替えによって切り替わるため、リンクの抽出は、全てのパーセルレベルで行われる。パーセルレベルは、下位レベルから順に、LV0→LV2→LV4→LV6→LV8→LV10などとして設定される。そして、上位レベルになるほど、交差点や道路が間引かれる。CPは、最も下位のパーセルレベルであるLV0に相当するデータとなっている。したがって、LV2よりも上位のパーセルレベルでは、必ずしも交差点に対応するノードが存在するとは限らない。そこで、LV2よりも上位のパーセルレベルでの抽出処理では、ノードが検索範囲に存在しないリンクも一定条件を満たす場合には抽出する。一定条件を満たす場合については、後述する。<5.2.2対象CPが仮想CPである場合>対象CPが仮想CPである場合も、ノードを意識した処理を行う。地図データの仕様では、パーセル境界には必ずノードが設定される。したがって、対象CPが仮想CPである場合、当該仮想CPは、パーセル境界に付与されるものであるため、同一のパーセル境界に存在するノードがあれば、そのノードと対応付けられる。そこで、リンクを構成するノードのいずれかがパーセル境界に存在する場合、このパーセル境界に存在するノードが検索範囲に含まれるときは、そのリンクを検索範囲に一部が含まれるリンクとする。例えば、図15bに示す対象CPが仮想CPを示すものとし、ノードDがパーセル境界に存在するノードだとすると、ノードDを端点とするリンクL6,L8が検索範囲に一部が含まれるリンクとなる。<5.2.3対象CPが交差点でも仮想CPでもない場合>この場合、対象CPがノードと対応付けられるか否かは分からないため、ノードを意識することなく、リンクの抽出を行う。つまり、対象CPが交差点でも仮想CPでもない場合は、リンクを構成する少なくともいずれかのノードが検索範囲に含まれている場合の他に、ノードが検索範囲に存在しないリンクも一定条件を満たす場合には抽出する。この場合のリンクの抽出は、全てのパーセルレベルで同様に行われる。<5.2.4一定条件を満たす場合>一定条件を満たす場合とは、次の2つの場合をいう。一つは、ノード間に形状補間点が設定されている場合、当該形状補間点を結んだ線分の一部が検索範囲に含まれている場合である。例えば図15cに示すリンクL9は、その形状補間点小さな黒丸を結ぶ線分の一部が検索範囲に含まれているため、ノードE,Fが検索範囲に含まれていないが検索範囲に一部が含まれるリンクとなる。一方、リンクL10は、その形状補間点を結ぶ線分の一部が検索範囲に含まれていないため、検索範囲に一部が含まれるリンクにならない。もう一つは、ノード間に形状補間点が設定されていない場合、2つのノードを結ぶ線分の一部が検索範囲に含まれている場合である。例えば、図15dに示すリンクL11は、2つのノードG,Hを結ぶ線分の一部が検索範囲に含まれているため、検索範囲に一部が含まれるリンクとなる。<5.2.5その他>図12の説明に戻り、続くS260では、検索範囲に一部が含まれるリンクのうちで属性RDが一致するリンクに絞り込む。属性RDが道路番号を示す場合は図14中のS243にて判断するため、ここでは属性RDが道路名称である場合に、当該道路名称による一致を判断する。なお、道路名称は最大5文字となっているため、属性RDの値としての文字列がリンクに付与される道路名称に含まれるか否かを判断する。次のS270では、リンクの数が10本以内に収まるように絞り込む。具体的には、S260までの絞り込みによってリンクの数が10本を越えている場合、対象CPに近いものから順に10本のリンクを選択する。対象CPに近いか否かは、対象CPから各リンクへ例えば垂線を下ろすなどして距離を求めることによって判断する。<5.3候補選定処理>次に、図3中のS300の候補選定処理について説明する。候補選定処理は、リンク、ノード単位の候補選定を行うものである。候補選定処理の一例を図16に示した。最初のS310では、非形状系属性の一致判定を行う。詳細については後述するが、ここでは、S200で抽出されたリンク又は当該リンクを構成するノードに対し、属性FC、属性FW、属性IT、属性RDI、属性DD及び属性AFRを用いた一致判定を行う。なお、属性FC及び属性FWは、リンク列を絞り込む際に利用しているため図14中のS241,S242重複した処理となっているが、確実をきすために再度行うものである。また、ここでの一致判定は、確実を期すため、属性IT、属性RDI、属性DD及び属性AFRなどを用いた細かい一致判定となっている。次のS320では、非形状系属性での判定結果を基に候補となるリンクを絞り込む。具体的には、S310での非形状系属性による一致判定の結果、各属性との一致数が多いリンクを、候補リンクとする。続くS330では、形状系属性の一致判定を行う。詳細については後述するが、ここでは、S320にて候補リンクとされたリンク又は当該リンクを構成するノードに対してのみ、属性BR、属性PCI、属性CA及び属性DCAを用いた一致判定を行う。続くS340では、形状系属性での判定結果で候補となるリンクを絞り込む。具体的には、S330での形状系属性による一致判定の結果、各属性との一致数が多いリンクを、候補リンクとする。<5.3.1非形状系属性の一致判定>ここで、S310の非形状系属性の一致判定の詳細を説明する。非形状系属性の一致判定の一例を図17に示す。最初のS311では、属性FCでの一致判定を行う。属性FCは、上述したように道路区分を示す属性である図5参照。ここでは、判定対象のリンクに付与されている道路区分と対象CPの属性FCとの一致を判定する。続くS312では、属性FWでの一致判定を行う。属性FWは、上述したように、物理道路タイプを示す属性である図6参照。ここでは、判定対象のリンクに付与されている物理道路タイプと対象CPの属性FWとの一致を判定する。次のS313では、属性ITでの一致判定を行う。属性ITは、上述したように、交差点の分類を示す属性である図7参照。したがって、対象CPが交差点を示すものである場合にのみ、この一致判定が行われる。なお、属性ITに相当する属性は、ノード及びリンクの少なくともいずれか一方が有している。そこで、ノードが交差点の分類を示す交差点分類情報を持っている場合、対象CPに対応するノードの交差点分類情報と対象CPの属性ITとの一致を判定する。また、リンクが交差点の分類を示す交差点分類情報を持っている場合、対象CPに対応するノードに接続するリンクの交差点分類情報と対象CPの属性ITとの一致を判定する。後者では、2つのノードの交差点分類情報をリンクが持っていることがあるため、いずれかの交差点分類情報と属性ITとの一致を判定する。続くS314では、属性RDIでの一致判定を行う。属性RDIは、上述したように、交差点の名称を示すものである図4参照。したがって、対象CPが交差点を示すものである場合にのみ、この一致判定が行われる。ここでは、対象CPに対応するノードの交差点名称と対象CPの属性RDIとの一致を判定する。なお、この判定は、属性RDIの値である文字列がノードの交差点名称に含まれるか否かで行われる。次のS315では、属性DD及び属性AFRでの一致判定を行う。属性DDは許可された合法の運転方向を示すものであり、属性AFRは、属性DDが参照可能であるか否かを示すフラグである図4参照。ここでは、判定対象のリンクの属性一方通行コードと対象CPの属性DDとを比較して判定する。なお、属性AFRが1としてセットされており属性DDが有効である場合であって属性DDが0未定義でない場合を除いて、判定を行う。ところで、属性DDが示すのはある交通情報に対する道路の通行可能方向であり、リンクの有する一方通行コードとの比較では、両者の順逆方向までは判断できない。したがって、ここでは通行方向の一致を判断するわけではなく、片側通行の道路か両側通行の道路かを判定することにとどまる。<5.3.2形状系属性の一致判定>続けて、S330の形状系属性の一致判定の詳細を説明する。形状系属性の一致判定の一例を図18に示す。最初のS331では、属性BRでの一致判定を行う。属性BRは、上述したように、次のCPへの位置的な角度を示すものである図4参照。一方、リンクは、法定上の走行方向を属性として有している。そこで、ここでは、リンクの走行方向が対象CPの属性BRに基づく方向と大きく異なっている場合に、不一致の判定を行う。例えば、リンクの走行方向を示すベクトルと、次のCPへ向かう属性BRに基づくベクトルとのなす角度が所定角度例えば90度以上となる場合に、不一致と判定することが考えられる。なお、リンクが双方向に走行可能となっている場合、走行方向を示す2つのベクトルで判定する。例えば、図19aでは、リンクL1,L2,L3の走行方向を示すベクトルVL1,VL21,VL22,VL3と属性BRに基づくベクトルVBとのなす角度で判定を行うという具合である。ここでは両ベクトルのなす角度が90度以上となる場合に、不一致と判定するものとする。なお、リンクL2は、双方向に走行可能となっており、走行方向を示す2つのベクトルVL21,VL22で判定される。ここでベクトルVBとベクトルVL1とのなす角度は、180度に近いものとなっており、90度以上であるため、リンクL1は、不一致と判定される。また、ベクトルVL22とベクトルVBとがなす角度は90度以上となるが、ベクトルVL21とベクトルVBとがなす角度が90度よりも小さいため、リンクL2は一致と判定される。さらにまた、ベクトルVL3とベクトルVBとがなす角度は90度よりも小さいため、リンクL3は一致と判定される。つまり、90度以上となる場合を不一致とする場合は、図19bに示すように、属性BRに基づくベクトルVBに対し、リンクの走行方向がベクトルV1,V2で示される場合には一致と判定され、ベクトルV3,V4で示される場合には不一致と判定される。図18中のS332では、属性PCIでの一致判定を行う。属性PCIは、上述したように、同一方向において複数の車道が存在する場合、いずれの車道が選択されているかを示すものである図4参照。属性PCIには、車道数及びその車道の中のいずれの車道かを示すシーケンス番号が含まれる。ただし、この属性で一致を判定しようとする場合、並走するリンクを残らず特定する必要がある。そこで、図20に示すように、最初のS333では、対象CPを中心とした検索エリアを設定する。この検索エリアは、対象CPを中心とした円の内部とすることが考えられる。例えば、所定距離例えば150mを半径とする円の内部を検索エリアにするという具合である。なお、PCI属性の一つとして検索エリアのデフォルト値が設定されることがあるため、その場合は、デフォルト値に所定距離例えば150mを加えた値を半径とする円の内部を検索エリアとすることが考えられる。続くS334では、検索エリア内のリンクを抽出する。ここでは、属性PCIの一つにインジケータタイプがあるため、このインジケータタイプに基づき、緯度方向あるいは経度方向の仮想直線を引き、この仮想直線と交差するリンクを抽出する。次のS335では、抽出したリンクの数と車道数とが一致するか否かを判断する。ここで車道数が一致すると判断された場合S335でYES、S336にてシーケンス番号でリンクを特定し、当該リンクが判定対象のリンクと一致するか否かを判定して、属性PCIでの一致判定を終了する。一方、車道数が一致しないと判断された場合S335でNO、S336の処理を実行せず、属性PCIでの一致判定を終了する。これは、車道数が一致しない場合、誤判定となる虞があるからである。図18に戻り、S337では、属性CA及び属性DCAでの一致判定を行う。属性CAは脇道に対する角度を示すものであり、属性DCAは脇道に対する接続距離を示すものである図4参照。ここでは、最初に、脇道の方向を検出する。具体的には、図21aに示すように、属性CAが負値である場合、次のCPへ向かう方向属性BRに基づく方向に対し、左側に脇道があると判断する。一方、図21bに示すように、属性CAが正値である場合、次のCPへ向かう方向属性BRに基づく方向に対し、右側に脇道があると判断する。なお、属性CAが0である場合、脇道の方向が特定できないため、一致判定を行わない。次に、判定対象のリンクとそのリンクの脇道との位置関係から属性CA及び属性DCAでの一致判定を行う。以上説明してきたS300の候補選定処理によって、各CPに対し、その周辺に、候補となるリンクが選定される。これらのリンクを繋ぐリンク、すなわちCP間を繋ぐリンクを推定する処理が、図3中の道路マッチング処理S400である。<5.4道路マッチング処理>次に、S400の道路マッチング処理について説明する。道路マッチング処理の一例を図22に示す。道路マッチング処理では、2つのCPを対象CPとし、始端側に位置するCPを始端側CP、終端側に位置するCPを終端側CPとして処理を行う。<5.4.1道路探索>最初のS410では、始端候補リンクから終端候補リンクを繋ぐ道路を探索する。始端候補リンクは、始端側CPに対し抽出されたリンクである。また、終端候補リンクは、終端側CPに対し抽出されたリンクである。ここでは、始端候補リンクと終端候補リンクとを結ぶ全ての道路を探索する。例えば、図23aに示すように、始端側CPをCPaとし、終端側CPをCPbとし、CPaに対し抽出されたリンクをSLとし、CPbに対し抽出されたリンクをGLとする。このとき、始端候補リンクSLと終端候補リンクGLとの間の道路を探索する場合、リンクSLを構成する2つのノードSN1,SN2とリンクGLを構成する2つのノードGN1,GN2との全ての組み合わせを考える。具体的には、SN1→GN1、SN1→GN2、SN2→GN1、SN2→GN2を結ぶ道路を探索する。次のS420では、道路単位候補選定を実行する。この処理は、各種の形状系属性を基に、S410にて探索された道路のうちで候補となる道路を判定するものである。続くS430では、S420における判定結果に基づき、道路を絞り込む。次のS440では、道路が一意に決定されたか否かを判断する。ここで道路が一意に決定された場合S440でYES、S450にてマッチング結果を出力し、その後、道路マッチング処理を終了する。一方、道路が一意に決定されない場合S440でNO、S450の処理を実行せず、道路マッチング処理を終了する。<5.4.2道路探索の省略>なお、このような道路マッチング処理S410~S440がペアとなる2つの対象CPに対して繰り返されるのであるが、上述のS410では、先の道路マッチング処理の結果を用いて探索する道路を省略する場合がある。例えば、図23bに示すように、CPa-CPb間の道路マッチング処理の結果、リンクSL→CL→GL1という道路が一意に決定されたものとする。このときは、CPbから次のCPへの道路マッチング処理を行う場合、リンクGL1からの道路を探索する。すなわち、候補リンクにリンクGL2があっても、リンクGL2からの道路探索を省略する。また、CPの種類によっても、道路探索を省略する。CPbが交差点である場合、例えば図23cに示すように、交差点を示すノードGN2と対応するため、リンクGLについては、一方のノードGN1に接続される道路を探索する。すなわち、SN1→GN1、SN2→GN1を結ぶ道路を探索する。CPbが仮想CPである場合、例えば図23dに示すノードGN2が対象パーセルの境界に位置するノードであれば、このノードが道路の始端又は終端となる。そこで、この場合も、リンクGLについては、一方のノードGN1に接続される道路を探索する。すなわち、SN1→GN1、SN2→GN1を結ぶ道路を探索する。さらにまた、一度探索した道路を再び探索しないようにして道路探索に要する時間を短縮することが考えられる。例えば図24aに実線で示すノードN1→N2→N3→N4という探索を最初に行ったものとする。このとき、ノードN1からの道路探索を2度目に行う場合、ノードN1→N5→N2という道路探索は行うが、ノードN2から先の探索は既に行っているため、ノードN2から先の探索は行わない。また、ノードからリンクが分岐する場合、リンクに優先順位をつけて道路探索を行う。例えば、あるノードから道路探索を行う場合、対象CPを結ぶ方向を基準にして、ノードに接続されるリンクの基準方向からの角度を求め、所定角度以内にあるリンクのみを道路探索の対象とする。図24bでは、ノードN1からの道路探索を行うのであるが、CPaからCPbへ向かう方向を基準にして、ノードN1に接続されるリンクL1,L2,L3の基準方向からの角度a1,a2,a3を求める。ここで角度a1,a2が所定角度以内にあるとすると、リンクL1,L2を道路探索の対象とする。一方、角度a3が所定角度を越えている場合、リンクL3を道路探索の対象から外す。さらにまた、ノードからの探索を行う場合、そのノードまでのリンクの道路種別と同じ道路種別のリンクを道路探索の対象とする。例えば図24cでは、CPbからCPcへの道路を、ノードN1から探索する。ここで、CPa-CPb間の道路がリンクL1として確定されているものとする。このとき、リンクL1の道路種別が国道であるため、ノードN1からの道路探索にあたり、道路種別が国道であるリンクL2を道路探索の対象にする。道路種別が県道であるリンクL3は、道路探索の対象から外す。<5.4.3道路探索の中止>ところで、S410における道路探索が所定時間以内に終了するとは限らない。そこで、道路探索を途中で中止するようにしてもよい。例えば属性PDを利用することが考えられる。図25aでは、CPa及びCPbのいずれもが属性PDを有しているものとする。このとき、ノードN1からノードN2への道路を探索する際、形状補間点K1,K2,K3,K4,での累積距離を算出するようにする。そして、この累積距離が、PD値から一定値以上大きくなった場合、道路探索を中止する。また例えば属性PDMを利用することが考えられる。図25bに示すように、CPa-CPb間の直線距離とPDM値とを用い、破線で示すようなコ字状の距離を算出しておく。このとき、ノードN1からノードN2への道路を探索する際、形状補間点K1,K2,K3,K4,での累積距離を算出するようにする。そして、この累積距離が、破線で示される距離よりも一定値以上大きくなった場合に、道路探索を中止する。例えば通過するノードの数を利用することが考えられる。図25cに示すように、ノードN1からノードN2への道路を探索する際、通過するノードN3,N4,N5,N6の個数を数えるようにする。そして、ノードの数が一定値以上となった場合に、道路探索を中止する。また例えばCPが交差点であることを利用することが考えられる。図25dでは、CPa及びCPbのいずれもが交差点であるとする。このとき、ノードN1,N2が交差点であれば、ノードN1,N2がそれぞれCPa,CPbに対応するものとなるため、ノードN1,N2間の直線距離を予め算出しておく。そして、ノードN1からノードN2への道路を探索する際、通過するノードN3,N4,N5,N6までの累積距離を算出して、この累積距離が、予め算出したノードN1,N2間の直線距離よりも一定値以上大きくなった場合、道路探索を中止する。ここでは4つの手法を説明したが、いずれの手法によっても、間違っていると思われる道路の探索が途中で打ち切られるため、処理負荷が軽減される。<5.4.4道路単位候補選定>ここで、図22中の道路単位候補選定について説明する。道路単位候補選定の一例を図26に示す。道路単位候補選定は、CP間で抽出された道路の単位で、OK又はNG判定を行うものである。最初のS421では、属性CA/DCAで判定する。上述したように、属性CAは脇道に対する角度を示すものであり、属性DCAは脇道に対する接続距離を示すものである図4参照。ここでは、探索された道路の中で、属性CA及び属性DCAによって特定されるリンクを、脇道であるとして、このリンクを含む道路に対しNG判定を行うものである。具体的には、図27aに示すように、属性CA及び属性DCAが示す位置座標の周囲破線で示す範囲にリンクがあれば、当該リンクを含む道路をNGと判定する。例えば図27bには、CP間を繋ぐ道路として道路1及び道路2が示されているが、属性CA及び属性DCAから脇道と判定されたリンクを含む道路1はNGと判定されることになる。図26中のS422では、属性BR/DMBで判定する。上述したように、属性BRは次のCPへの角度を示すものであり、属性DMBは次のCPまでの直線距離を示すものである図4参照。CPが示すデータとナビゲーション装置10の地図データとの間にずれがある場合、この属性BR/DMBを利用することで、より確からしい道路を特定することができる。そこで、図28に示すように、CPb-CPc間の道路の判定を、CPbの一つ前のCPaの属性BR及び属性DMBを用いて行う。具体的には、属性BR及び属性DMBから特定される位置座標の周囲記号Hの破線で示す範囲のリンクLを含む道路はOKと判定する。なお、CPb-CPc間の道路の判定であるため、リンクLを構成するノード又は形状補間点が所定範囲に入ることを条件とする。例えば、所定範囲は、CPbとCPcとを結ぶ線分と属性PDMとから設定される矩形図中に二点鎖線で示したの内側とすることが考えられる。もちろん、所定範囲は、このような矩形に限られず、CPb及びCPcを通る楕円の内側などとしてもよい。次のS423では、属性PDで判定する。上述したように、属性PDは、属性PDを有する次のCPまでの運転距離である図4参照。したがって、探索された道路の運転距離によって、当該道路が候補となり得るか否かを判定する。具体的には、図29に示すように、CPa-CPb間の運転距離を算出する場合、各CPがノードに対応するとは限らないため、CPaからリンクL1への垂線を下ろし、また、CPbからリンクL3への垂線を下ろして、それぞれの交点をM,Nとする。そして、交点Mから交点Nまでの運転距離を算出する。なお、交点Mから直後のノードまでの運転距離は、この運転距離のリンクL1における割合を算出することで求める。ここで、交点Mから直後のノードまでがリンクL1のmである場合、リンクL1の運転距離にm/100を乗じて、交点Mから直後のノードまでの運転距離を算出する。同様に、交点Nから直前のノードまでの運転距離は、この運転距離のリンクL3における割合を算出することで求める。ここで、交点Nから直前のノードまでの距離がリンクL1の距離のnである場合、リンクL3の運転距離にn/100を乗じて、交点Nから直前のノードまでの運転距離を算出する。ところで、全てのCPが属性PDを有しているとは限らない。したがって、CPaが属性PDを有しているがCPbが属性PDを有していない場合、図30aに示すように、道路の候補判定は行わず、そのまま道路を保持する。次に、図30bに示すCPcが属性PDを有しているとすると、CPa-CPc間で属性PDに基づく道路判定を行う。すなわち、道路L1→L2→L3→L5→L6→L10と、道路L1→L4→L5→L6→L10と、道路L1→L2→L3→L5→L7→L8→L9→L10と、道路L1→L4→L5→L7→L8→L9→L10と、を候補にして、NG判定を行う。これにより、図30cに示すように道路L1→L2→L3→L5→L6→L10という道路が残った場合、CPa-CPb間の道路L4、及び、CPb-CPc間の道路L7→L8→L9は、NGと判定されることになる。続くS424では、属性PDMで判定する。上述したように、属性PDMは、次のCPまでを結ぶ直線からの道路の離間距離を示す図4参照。この処理では、属性PDMに基づき道なりの運転距離を求め、探索された道路が候補となるか否かを判定する。具体的には、属性PDMに基づく道なりの運転距離を次の式により算出する。PDM運転距離=CP間の直線距離を直径とする円周の半分×補正値式5ここで補正値は、属性PDMの値とCP間の直線距離の半分との比率からテーブルによって確定する。例えば、図31aに示すようにCPa-CPb間の直線距離の半分をrとすると、図31bに示すテーブルによって、属性PDMの値と距離rとの比率PDM/rから補正値を求める。なお、図31bに示したテーブルは、一部を抜粋したものである。そして、候補となっている道路の道なりの運転距離を道路運転距離とすると、道路運転距離が次の式を満たす場合に、その道路をOKと判定する。PDM運転距離×0.5<道路運転距離<PDM運転距離×1.5式6<5.4.5マッチング結果の出力>そして、上述したように、これらの判定結果によって道路を絞り込み図22中のS430、道路が一意に決定されるとS440でYES、S450にてマッチング結果を出力する。マッチング結果は、一意に特定された道路を構成する全リンクのリンクID、始点オフセット距離、終点オフセット距離などで構成される。なお、始点オフセット距離は、道路の始点となるリンクのどの位置からがマッチングの開始位置かを示す距離である。同様に、終点オフセット距離は、道路の終点となるリンクのどの位置までがマッチングの終了位置かを示す距離である。<5.4.6道路の決定について>なお、通常、道路が一意に決定されないとS440でNO、道路マッチング失敗となって、マッチング結果が出力されないことになる。ただし、次のような場合には、道路が一意に決定されたものとする。例えば、図32aでは、CPaからCPbへの道路を探索した結果、ノードN1→N4→N5→N2→N3という道路、及び、ノードN1→N4→N5→N2という道路の2つが残ったものとする。このとき、太線で示した道路ノードN1→N4→N5→N2は、両方の道路に包含されているため、この道路を一意に決定された道路とする。また例えば、図32bでは、CPaからCPbへの道路を探索した結果、ノードN1→N4→N5→N2→N3という道路、及び、ノードN1→N4→N6→N5→N2→N3という道路の2つが残ったものとする。このとき、太線で示した道路ノードN1→N4N5→N2→N3は、両方の道路に包含されているため、この分断された2つの道路を一意に決定された道路とする。あるいは、図32bに示すような例で、道なりの道路を一意に決定された道路とすることが考えられる。道なりとは、図32cに示すように、リンク同士のなす角度例えば記号aで示す角度が所定角度例えば15度以下である場合をいう。<6.効果>以上詳述したように本実施形態では、図8に示した変換処理において、パーセル境界に仮想CPを付与しS110、仮想CPを含むCPの属性を再計算あるいは計算するS120。そして、対象パーセル内のCPに絞り込んでS130、図12に示した候補リンク検索処理を実行する。つまり、本実施形態では、地図データがパーセルの単位で入力されパーセル境界にノードが設定されることに鑑み、パーセル境界上に、新たなCPである仮想CPを生成する。このとき、仮想CPはノードと対応付けられるものとなるため、その後の候補リンク検索処理図12参照では、CPが示す道路の候補となるリンクを適切に抽出することができる。その結果、配信されるCPの情報から、地図データのパーセルにおいてCPが示す道路に該当するリンクを適切に推定することができる。また、本実施形態では、図10aに示したように、2つのCPa,CPbが対象パーセルの境界を跨いでいるような場合、属性PDMの値により与えられる道路形状の頂点VとCPa,CPbとを結ぶ線分を算出し、線分の一方と対象パーセルの境界との交点に仮想CPを付与する。これにより、道路形状に合わせて仮想CPが付与される可能性が高くなる。さらにまた、本実施形態では、CPの属性を計算する図8中のS120。具体的には、脇道への角度及び当該脇道への接続距離を示す脇道情報属性CA及び属性DCA、次のコアポイントへの位置的な角度及び接続距離を示す角度距離情報属性BR及び属性DMB、コアポイント間の運転距離を示す運転距離情報属性PD、次のコアポイントまでを結ぶ直線からの道路の離間距離を示す離間距離情報属性PDM、及び、並走する道路の情報を示す並走道路情報属性PCIの属性を設定又は再設定する。これにより、地図データのパーセルにおいてCPが示す道路に該当するリンクをより適切に推定することができる。また、本実施形態では、対象パーセル内のCPに絞り込んで図8中のS130、その後、候補リンク検索処理図12参照を行う。これにより、処理対象となっているパーセルに含まれるCPのみが処理対象となるため、候補リンク検索処理に要する時間を削減することができる。なお、本実施例におけるナビゲーション装置10が道路推定装置に相当し、地図データ入力装置13が地図データ入力手段に相当し、制御回路17のCPU17aが仮想コアポイント生成手段及びリンク抽出手段に相当する。また、図8の変換処理のうちS110及びS120の処理が仮想コアポイント生成手段の機能としての処理に相当し、S130の処理がリンク抽出手段の機能としての処理に相当する。さらにまた、実施形態におけるパーセルが分割領域に相当し、ノードがリンクの端点に相当し、図10に示したCPa及びCPbが注目コアポイントに相当する。以上、本発明は、上述した実施形態に何ら限定されるものではなく、その要旨を逸脱しない範囲において種々なる形態で実施可能である。上記実施形態では、CPの属性を計算する図8中のS120にあたり、脇道情報属性CA及び属性DCA、角度距離情報属性BR及び属性DMB、運転距離情報属性PD、離間距離情報属性PDM、及び、並走道路情報属性PCIを設定又は再設定している。これに対し、これらの属性のうちの少なくともいずれかを設定又は再設定するようにしてもよい。"