JP5116236B2

JP5116236B2 - 地図データ作成方法及び地図データ作成装置

Info

Publication number: JP5116236B2
Application number: JP2006020436A
Authority: JP
Inventors: 実関根; 正明大平
Original assignee: Alpine Electronics Inc; Mobilemedia Brain Association Inc
Current assignee: Alpine Electronics Inc; Mobilemedia Brain Association Inc
Priority date: 2006-01-30
Filing date: 2006-01-30
Publication date: 2013-01-09
Anticipated expiration: 2026-01-30
Also published as: JP2007199575A; US20070179708A1

Description

本発明は、地図データ作成方法及び地図データ作成装置に係わり、特に詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成方法及び該方法を実現する地図データ作成装置に関する。

ナビゲーション装置は、車両の現在位置に応じた地図データをCD−ROM、DVD，HDDなどの地図記憶媒体から読み出してディスプレイ画面に描画すると共に、車両マークをディスプレイ画面の一定位置に固定表示し、走行に応じて地図をスクロ−ル表示する。また、ナビゲーション装置は以上に加えて、出発地から目的地に到る誘導経路あるいは出発地から指定された経由点を経由して目的地に到る誘導経路を探索し、該誘導経路を地図上に表示する経路誘導機能を備えている。かかる経路探索を高速に行う第１従来技術として、メッシュからメッシュへの専用のネットワークを地図データに格納し、該専用ネットワークを用いて探索枝数を減らし、探索の高速化を行なう方法がある（特許文献１）。又、第２の従来技術として、専用ネットワークを用いずに、階層化構造を有する地図データを用いて、階層型の探索を行う方法がある（特許文献２）。

第１従来技術は、図１５の（Ａ）に示すように、詳細度に応じて５つのレベルを設け、各レベルの道路情報と専用ネットワーク情報により地図の道路情報を構成している。各レベルの基本部は該レベルに応じた領域に存在する道路の道路情報を特定する部分であり、レベル１及びレベル２の拡張部は高速探索用の情報部分である。専用ネットワークは、任意の２つのレベル２領域の組み合わせに対応させて、これら２つのレベル２領域間を接続ずる経路を探索する必要な経路情報(リンクやノード情報)を保持している。
図１５の（Ｂ）に示すように出発地Sが特定されると、該出発地が含まれるレベル１領域A１と該レベル１領域A１が含まれるレベル２領域Ｃ１を特定する。同様に、目的地Ｅが特定されると、該目的地が含まれるレベル１領域Ａ２と該レベル１領域Ａ２が含まれるレベル２領域Ｃ２を特定する。専用ネットワーク情報は、これら２つのレベル２領域Ｃ１，Ｃ２の組み合わせに応じて設けられているから、該専用ネットワーク情報を用いて経路探索を行う。具体的には、出発地と目的地に対応する上位移行ノードＰ１１，Ｐ１２，Ｐ１３；Ｑ１１，Ｑ１２，Ｑ１３を、レベル１の地図情報及び専用ネットワークの拡張情報を用いて抽出する。ついで、上位移行ノードに対応する上位ノードＮ１１，Ｎ１２，Ｎ１３と上位ノード１１，Ｍ１２，Ｍ１３間の複数の経路を専用ネットワーク情報(リンクやノード情報)を用いて探索し、最小コストの経路を誘導経路として決定する。

第２従来技術は、図１６に示すように地図をレベル１−４に階層化して道路情報を構成している。レベル1は誘導経路対象道路と非誘導経路対象道路（細街路）の地図情報を特定する部分、レベル2は誘導経路対象道路の道路情報を特定する部分、レベル３は主要道路の地図情報を特定する部分、レベル４は更に主要な道路(県道、国道、高速道路)の地図情報を特定する部分である。出発地Sおよび目的地Ｅが特定されると、レベル２において出発地Ｓからレベル３の上位ノードに移行するノードｂ１０を求め、ついで、ノードｂ１０からレベル４の上位ノードに移行するノードｃ１０を求め、出発地Sから上位ノードｃ１０に到る経路を求める。同様に、目的地Ｅより最上位レベル４の上位ノードＣ２０に到る経路をもとめる。ついで、出発地側の上位ノードｃ１０から目的地側の上位ノードｃ２０へ到る経路をレベル４の道路情報を用いて探索し、最終的に出発地から目的地へ到るコスト最小の経路を探索する。
特開２００３−３３７０３４号公報特開２００４−２８６５２４号公報

第１従来技術では、専用ネットワークの数が非常に多いので、道路情報のデータサイズが大きくなる問題がある。ま地図データの更新を、差分データを作成して行う場合、専用ネットワーク情報の差分データ量が大きくなってしまい、該差分データを通信で取得するには通信時間が非常に長くなって通信コストが高くなり、また、地図更新時間が長くなる問題がある。
第２従来技術の階層化構造の探索では、ヒューリスティックコストをかけ、出来るだけ無駄に探索枝をのばさないで目的地までの最適解を得る方法が存在する。しかし、それでも余計に探索枝がのびてしまい、探索時間が長くなる問題がある。図１７は、東京駅→大阪駅の経路探索における探索枝ののびかたを示すもので、塗りつぶし部分が探索枝がのびたところを示している。
以上から、本発明の目的は、探索した経路品位を保ち、かつ経路探索を高速化することである。

・地図データ作成方法
本発明の地図データ作成方法は、詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成方法である。
第１の地図データ作成方法では、所定レベルにおける任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用する該レベルのメッシュを特定するデータを探索範囲情報として地図データに含めて地図を作成する際、メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成し、任意の２つのメッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクから他方のメッシュの各境界進入リンクに到る全経路を探索し、探索された各経路を構成するリンクが属するメッシュを特定するデータにより前記探索範囲情報を作成する。
第２の地図データ作成方法では、所定レベルにおける任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用する該レベルのメッシュを特定するデータを探索範囲情報として地図データに含めて地図を作成する際、メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成し、任意の第１メッシュの境界脱出リンクから探索が不可能となるまで探索を行い、探索終了後、探索結果を参照し、前記第１メッシュの境界脱出リンクから任意の第２メッシュの各境界進入リンクに到る全経路を求め、同様に、前記第１メッシュの各境界脱出リンクについて該境界脱出リンクから前記第２メッシュの各境界進入リンクに到る全経路を求め、前記各経路を構成するリンクが属するメッシュを特定することにより、前記第１、第２メッシュの組み合わせに応じた探索範囲情報を作成する。

・地図データ作成装置、
また、上記課題は本発明によれば、詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成装置により達成される。
本発明の第１の地図データ作成装置は、メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成するリンクリスト作成部、任意の２つのメッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクから他方のメッシュの各境界進入リンクに到る全経路を探索する探索部、探索された各経路を構成するリンクが属するメッシュを特定するデータにより前記一方のメッシュから他方のメッシュに到る経路を探索する際に使用するメッシュを特定する探索範囲情報を作成する探索範囲情報作成部を備えている。
本発明の第２の地図データ作成装置は、メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成するリンクリスト作成部、任意の第１メッシュの境界脱出リンクから探索が不可能となるまで探索を行い、探索終了後、探索結果を参照して前記第１メッシュの境界脱出リンクから任意の第２メッシュの各境界進入リンクに到る全経路を求め、同様に、前記第１メッシュの各境界脱出リンクについて該境界脱出リンクから前記第２メッシュの各境界進入リンクに到る全経路を求める経路探索部、前記各経路を構成するリンクが属するメッシュを特定するデータにより、前記第１のメッシュから第２のメッシュに到る経路を探索する際に使用するメッシュを特定する探索範囲情報を作成する探索範囲情報作成部を備えている。

本発明によれば、所定レベルにおける任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用する該レベルのメッシュを特定するデータを探索範囲情報として地図データに含めるようにしたから、該探索範囲情報を用いることにより探索範囲を狭めることができ、高速の経路探索が可能になった。
又、本発明によれば、探索範囲情報として探索すべきメッシュの識別データを保存するだけでよいため、該探索範囲情報のサイズを少なくでき、しかも、地図更新時における差分データサイズを小さくできる。
又、本発明によれば、任意の第１メッシュの境界脱出リンクから探索が不可能となるまで探索を行い、探索終了後、探索結果を参照し、前記第１メッシュの境界脱出リンクから任意の第２メッシュの各境界進入リンクに到る全経路を求め、同様に、前記第１メッシュの各境界脱出リンクについて該境界脱出リンクから前記第２メッシュの各境界進入リンクに到る全経路を求め、前記各経路を構成するリンクが属するメッシュを特定することにより、前記第１、第２メッシュの組み合わせに応じた探索範囲情報を作成するようにしたから、高速に探索範囲データを作成することができるようになった。

詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成方法において、所定レベルにおける任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用する該レベルのメッシュを特定するデータを探索範囲情報として地図データに含める。
この探索範囲情報は、以下のように作成する。第１の探索範囲情報作成方法では、(1) メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成し、(2)任意の２つのメッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクから他方のメッシュの各境界進入リンクに到る全経路を探索し、(3)探索された各経路を構成するリンクが属するメッシュを特定するデータにより前記探索範囲情報を作成する。
第２の探索範囲情報作成方法では、（1）任意の第１メッシュの境界脱出リンクから探索が不可能となるまで探索を行い、探索終了後、探索結果を参照し、前記第１メッシュの境界脱出リンクから任意の第２メッシュの各境界進入リンクに到る全経路を求め、(2)同様に、前記第１メッシュの各境界脱出リンクについて該境界脱出リンクから前記第２メッシュの各境界進入リンクに到る全経路を求め、(3)前記各経路を構成するリンクが属するメッシュを特定することにより、前記第１、第２メッシュの組み合わせに応じた探索範囲情報を作成する。

(Ａ)本発明の概要
図１は本発明の地図データに含まれる道路情報の説明図である。詳細度に応じて複数のレベル(レベル１〜レベル４)を設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報RI1〜RI4と、経路探索に際して利用する探索範囲データSRDとで道路情報を構成する。
レベル1は誘導経路対象道路と非誘導経路対象道路の地図情報を特定する部分、レベル2は誘導経路対象道路の道路情報を特定する部分、レベル３は主要道路の地図情報を特定する部分、レベル４は更に主要な道路(県道、国道、高速道路)の地図情報を特定する部分である。
探索範囲データSRDは、図２に示すように、所定レベル(例えばレベル３)における任意の２つのメッシュM1,M2の組み合わせ毎に、一方のメッシュM1から他方のメッシュM2に到る経路を探索する際に使用するメッシュ(太枠線内のメッシュ)を特定するデータを探索範囲データとして地図データに含める。
この探索範囲データSRDは、例えば、以下のように作成する。(１)各メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成し、(２)任意の２つのメッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクから他方のメッシュの各境界進入リンクに到る全経路PT1，PT2，…を探索し、(３)探索された各経路を構成するリンクが属するメッシュを特定するデータにより、該２つのメッシュの組み合わせに応じた探索範囲データとし、全てのメッシュの組み合わせについて探索範囲データを作成する。

図３はメッシュの一例の説明図である。地図はカバーするエリアの広さからレベル４のメッシュ，レベル３のメッシュ、レベル３のメッシュ、レベル２のメッシュ、レベル１のメッシュと階層化されている。レベル４のメッシュに相当する領域Ｒ４は、複数(図では４つ)のレベル３メッシュの領域Ｒ３で構成され、同様に、レベル３のメッシュに相当する領域Ｒ３は、４つのレベル２メッシュの領域Ｒ２で構成され、レベル２のメッシュに相当する領域Ｒ２は、４つのレベル１メッシュの領域Ｒ１で構成されている。

図４は道路情報に含まれるリンクレコードの構成説明図である。リンクとは交差点から交差点までの道路部分であり、リンクレコードは、（Ａ）に示すように(1)リンクID、(2)道路種別、(3)リンク距離、(4)車線数、(5)リンク形状を特定する形状情報(始点ノード、中間のノード、終点ノードの位置データ)を有している。各リンクレコードはメッシュ番号に対応させて地図に含まれており、リンクが属するメッシュのメッシュ番号がわかるようになっている。また、レベル４のリンクはレベル３領域Ｒ３をまたがらないように形成されており、該レベル４のリンクレコードには図４(Ｂ)に示すようにレベル３領域のメッシュ番号が含まれている。
図５はレベル４のリンクがレベル３領域をまたがらないように形成することを説明する説明図であり、交差点Ｎ１，Ｎ２を始点、終点とするリンクLKがレベル３領域R3a，R3bを横切っている。かかる場合、リンクLKをレベル３領域Ｒ３の境界線で二分し、二分された２つのリンクLK1（N1−NB），LK2（NB−N2）をレベル４のリンクとし、夫々についてリンクレコードを作成し、それぞれにレベル３領域R3a．R3bのメッシュ番号を持たせる。

（Ｂ）探索データ作成
図６は本発明の地図作成装置の要部構成図、図７は本発明の地図作成処理説明図である。
リンクデータ入力部１はレベル３メッシュのリンクレコードをリスト作成部２と経路探索部３に入力する。リスト作成部２は、レベル３メッシュのリンクレコードを参照し、全レベル３メッシュについて、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成する。図７（A）は、境界脱出リンクの説明図であり、レベル３メッシュの着目領域R3から隣接メッシュへ移動する際に通る境界リンクS1〜S6が境界脱出リンクである。図７（B）は、境界進入リンクの説明図であり、隣接メッシュからレベル３メッシュの着目領域R3へ進入する際に通る境界リンクE1〜E6が境界進入リンクである
経路探索部３は、任意の２つのレベル３メッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクS1〜S6から他方のメッシュの各境界進入リンクE1〜E6に到る全経路を所定の経路探索方法により、例えばダイクストラ法により探索する。すなわち、図7(C),(D)に示すように経路探索部３は、
・境界脱出リンクS1から各境界進入リンクE1〜E6に到る全経路、
・境界脱出リンクS2から各境界進入リンクE1〜E6に到る全経路、
・境界脱出リンクS3から各境界進入リンクE1〜E6に到る全経路、
・・・・・・・
・境界脱出リンクS6から各境界進入リンクE1〜E6に到る全経路、
を探索する。

探索範囲データ作成部４は、経路探索部３により探索された上記の各経路を構成するレベル３リンクが属するレベル３メッシュのメッシュ番号を記憶することにより、任意の2つのレベル3メッシュの組み合わせに対応させて探索範囲データを作成してメモリ５に保存する。なお、探索範囲データを保存するために、任意の２つのメッシュの組み合わせに対応させてメモリ５にKバイトを用意し、Kバイトの各ビットにより上記経路を構成するリンクが所定のメッシュに含まれているか否かを記録する。すなわち、Kバイトの第1ビット〜第8×Kビットをメッシュ番号１〜メッシュ番号8×Kに対応させ、上記経路を構成するリンクが所定のメッシュに属する場合には、該メッシュに対応するビットに”1”を記入し、これにより探索範囲データを作成して保存する。全てのメッシュの組み合わせに対して上記処理を行って、探索範囲データをメモリ５に保存する。
地図データ作成部６は各レベルの道路情報および前記作成された探索範囲データを用いて道路レイヤ情報を作成してたとえばDVD ７に記録する。

（C）経路探索法
・ダイクストラ法
図８はコストを距離とした場合のダイクストラ法の概略説明図で、道路を直線、交差点を直線の交点としてグラフ化したものである。各交差点間の距離は既知で、Ｐsは出発点(自車位置)、Ｐdは目的地である。ダイクストラ法では、出発地Ｐsに隣接する１次交差点Ａ₁〜Ａ₄を求め、各１次交差点Ａ₁〜Ａ₄に対応させて０次の交差点（出発点）及び出発点からの距離を記憶する。ついで、各１次交差点Ａ₁〜Ａ₄について２次交差点Ｂijを求め、各２次交差点に対応させて１次交差点を経由する出発点からの距離を求めて記憶する。例えば、１次交差点Ａ₁については３つの２次交差点Ｂ₁₁，Ｂ₁₂，Ｂ₁₃が求まり、各２次交差点Ｂ₁₁，Ｂ₁₂，Ｂ₁₃に対応させて、
Ｂ₁₁：１次交差点Ａ₁を経由する出発点からの距離d₁₁
Ｂ₁₂：１次交差点Ａ₁を経由する出発点からの距離d₁₂
Ｂ₁₃：１次交差点Ａ₁を経由する出発点からの距離d₁₃・・・・(a)
を記憶する。又、1次交差点Ａ₂について３つの２次交差点Ｂ₂₁，Ｂ₂₂，Ｂ₂₃が求まり、各２次交差点Ｂ₂₁，Ｂ₂₂，Ｂ₂₃に対応させて、
Ｂ₂₁：１次交差点Ａ₂を経由する出発点からの距離d₂₁・・・・（b）
Ｂ₂₂：１次交差点Ａ₂を経由する出発点からの距離d₂₂
Ｂ₂₃：１次交差点Ａ₂を経由する出発点からの距離d₂₃
を記憶し、他の１次交差点Ａ₃，Ａ₄についても同様に２次交差点を求めて所定のデータを記憶する。
ところで、交差点Ｂ₁₃とＢ₂₁は同一の交差点である。このように、データを記憶すべき交差点が重複すると、出発点からの距離d₁₃とd₂₁の大小を比較し、小さい方のデータのみを記憶する。たとえば、d₁₃＞ｄ₂₁であれば、交差点Ｂ₁₃（＝Ｂ₂₁)のデータとして(b)のデータが最終的に記憶される。
以後、同様に、各２次交差点について３次交差点Ｃijを求め、各３次交差点に対応させて２次交差点を経由する出発点からの距離を求めて記憶し、一般に各第ｉ次交差点について第(i+1)次交差点を求め、各第(i+1)次交差点に対応させて第ｉ次交差点を経由する出発点からの累計距離を求めて記憶してゆけば、最終的に目的点Ｐｄに到達する。以上はノードに着目してダイクストラ法を説明したがリンクに着目して説明することもできる。

・ダイクストラ法を用いた経路探索処理
図９はダイクストラ法を用いた経路探索処理のフローであり、距離をコストとする場合であり、目的地が存在するメッシュを目的側メッシュ、出発地が存在するメッシュを出発側メッシュという。
所定の出発側メッシュの第j境界脱出リンクを選択し、該リンクの検索次数nを１にし（１→ｎ、ステップ１０１）、第ｎ次リンクに接続するリンクが存在するか調べる（ステップ１０２）。１次リンクは出発点Ｐsに接続するリンクである。第次ｎリンクLnに接続するリンク(隣接リンクという)が存在すれば、出発点Ｐsから第ｎ次リンクLnを経由して隣接リンクL_ajの終端までの累計距離Ｄを計算する（ステップ１０３）。
出発点から第ｎ次リンクの終点までの距離ｄ_nは後述するように、該第次ｎリンクに対応させて記憶に記憶してあり、また隣接リンクL_ajの距離d_ajはリンクレコードに記憶してあるから、次式
ｄ_n＋ｄ_aj→Ｄ
により出発点Ｐsから隣接リンクL_ajの終点までの累計距離Ｄが求まる。
ついで、隣接リンクL_ajの検索次数が(n+1)かチェックし（ステップ１０４）、(n+1)でなければ、隣接リンクL_ajに対応させて、以下のデータ
(1) 現在着目している第ｎ次リンクのシ−ケンシャル番号、
(2) 出発点から当該隣接リンクL_ajの終点までの累計距離Ｄ、
(3) 当該隣接リンクL_aj の検索次数として(n+1)、
(4) メッシュ３番号
(5) リンクL_ajのリンク番号
を記憶部に記憶し（ステップ１０５）、以後、ステップ１０２に戻り、着目している第ｎ次リンクに接続するリンクが、なお残存するか調べて以降の処理を繰り返す。
一方、ステップ１０４において、隣接リンクの次数が(n+1)の場合には、換言すれば、該隣接リンクが別の第ｎ次リンクに隣接するリンクとして参照されていれば（ステップ１０５で既に上記(1)〜(5) のデータが記憶されていれば）、該隣接リンクに対応して記憶してある出発点からの距離D′とステップ１０３で求めた距離Dの大小を比較する（ステップ１０６）。D＜D′であれば、当該隣接リンクL_ajに対応して記憶部に記憶してある、第ｎ次リンクのシ−ケンシャル番号を現在着目している第ｎ次リンクのシ−ケンシャル番号で置き換えると共に、累計距離Ｄ′をＤで書き替え（Ｄ→Ｄ′，ステップ１０７）、以後、ステップ１０２に戻り、着目している第ｎ次リンクに接続するリンクが、なお残存するか調べて以降の処理を繰り返す。又、D≧D′の場合には、当該隣接リンクに対応して記憶部に記憶してある内容を変更せずステップ１０２に戻る。

ステップ１０２において、着目している第ｎ次リンクに接続するリンクが存在しなくなれば、別の第ｎ次リンクが存在するか調べ（ステップ１０８）、存在すれば、該別の第ｎ次リンクを新たに第ｎ次リンクとして（ステップ１０９）、ステップ１０２以降の処理を繰り返す。ステップ１０８において、別の第ｎ次リンクが存在しなければ、目的側メッシュの進入リンクに到達したかチェックし(ステップ１１０)、到達していなければ検索次数を１つ歩進し（ｎ＋１→ｎ，ステップ１１１）、ステップ１０２以降の処理を繰り返す。しかし、目的側メッシュの進入リンクに到達していれば、探索処理を終了する。以上では、距離をコストとみなした場合であるが、コストが距離以外の要素をも含む場合には距離の代わりにコストＣを用いることができる。
以上により、探索処理が完了後、目的側メッシュにおける所定の境界進入リンクに着目し、
(1)該境界進入リンク（M次のリンクとする）→(2)該境界進入リンクに対応させて記憶してある（M−１）次のリンク→(3)該（M−１）次のリンクに対応させて記憶してある（M−２）次のリンク→・・・→(4)2次のリンクに対応させて記憶してある１次リンク（第i目的側メッシュの第j境界脱出リンク）
と順次接続することにより、１次リンクである第i目的側メッシュの第j境界脱出リンクから目的側メッシュにおける所定の境界進入リンクに到るコスト(距離)最小の経路をもとめることができる。
なお、後述する図１０の探索範囲データ作成処理フローのステップ２０８では、上記求めた経路を構成するリンクのメッシュ３番号に対応するビットを“１”にして探索範囲データを作成する。
また、図１１の第２の探索範囲データ作成処理フローのステップ３０３の探索処理では、上記ステップ１１０において探索枝を延ばせるか判別し、探索枝を延ばせれば検索次数を１つ歩進し（ｎ＋１→ｎ，ステップ１１１）、ステップ１０２以降の処理を繰り返す。しかし、探索枝を延ばせず、探索が不可能になれば探索処理を終了する。

（D）探索範囲データの作成処理
・第１の探索範囲データ作成処理
図１０は本発明の第１の探索範囲データ作成処理フローである。
まず、レベル３メッシュのリンクレコードを参照し、全レベル３メッシュについて、メッシュ毎に該メッシュから隣接メッシュへ脱出する境界脱出リンクのリストを作成し(ステップ２０１)、ついで、該メッシュに隣接メッシュから進入する境界進入リンクのリストを作成する(ステップ２０２)。
ついで、出発側メッシュ番号を示すi、目的側メッシュ番号を示すk、出発側メッシュにおける境界脱出リンク番号を示すj、目的側メッシュにおける境界進入リンク番号を示すmをすべて１に初期化する(ステップ２０３〜２０６)。
ついで、第i出発側メッシュの第j境界脱出リンクから第k目的側メッシュの第m境界進入リンクまでの経路を探索する(ステップ２０７)。なお、i=kの場合にはステップ２０７以降の処理を行わない。
経路探索処理が終了すれば、第m境界進入リンクから逆方向にたどって第j境界脱出リンクに至る経路が通過するメッシュのメッシュ対応ビットを“1”にする(ステップ２０８)。しかる後、第k目的側メッシュの全境界進入リンクまでの経路探索が完了したかチェックし(ステップ２０９)、完了してなければmを歩進して(m＝m+1,ステップ２１０)、ステップ２０７以降の処理を繰り返す。
ステップ２０９において、第k目的側メッシュの全境界進入リンクまでの経路探索が完了すれば、第i出発側メッシュの全境界脱出リンクからの経路探索が完了したかチェックし(ステップ２１１)、完了してなければｊを歩進して(ｊ＝ｊ+1,ステップ２１２)、ステップ２０６以降の処理を繰り返す。ステップ２１１において、第i出発側メッシュの全境界脱出リンクからの経路探索が完了すれば、メッシュ番号(i,k)の組み合わせに対応する探索範囲データの作成が完了する。
ついで、全目的側メッシュについて上記処理が終了したかチェックし(ステップ２１３)、終了してなければkを歩進して(k＝k+1,ステップ２１４)、ステップ２０５以降の処理を繰り返す。ステップ２１３において、全目的側メッシュについて上記処理が終了すれば、第i出発側メッシュから他の全目的側メッシュに対する探索範囲データの作成が完了する。
しかる後、全出発側メッシュについて上記処理が終了したかチェックし(ステップ２１５)、終了してなければiを歩進して(i＝i+1,ステップ２１６)、ステップ２０４以降の処理を繰り返す。ステップ２１５において、全出発側メッシュについて上記処理が終了すれば、探索範囲データの作成が完了する。

・第２の探索範囲データ作成処理
図１１は本発明の第２の探索範囲データ作成処理フローである。なお、各メッシュの境界脱出リンクおよび境界進入リンクのリストの作成は完了しているものとする。
まず、出発側メッシュ番号を示すi、出発側メッシュにおける境界脱出リンク番号を示すjを１に初期化する(ステップ３０１〜３０２)。
ついで、第i出発側メッシュの第j境界脱出リンクからダイクストラ法を用いて経路探索処理を探索が不可能となるまで、すなわち、探索枝を延ばせなくなるまで行う(ステップ３０３)。探索終了後、目的側メッシュ番号を示すk、目的側メッシュにおける境界進入リンク番号を示す番号mをそれぞれ１に初期化する(ステップ３０４〜３０５)。
ついで、第k目的側メッシュの第m境界進入リンクから逆方向にたどって第i出発側メッシュの第j境界脱出リンクに至る経路が通過するメッシュのメッシュ対応ビットを“1”にする(ステップ３０６)。しかる後、第k目的側メッシュの全境界進入リンクについてステップ３０６の処理が完了したかチェックし(ステップ３０７)、完了してなければmを歩進して(m＝m+1,ステップ３０８)、ステップ３０６以降の処理を繰り返す。
ステップ３０７において、第k目的側メッシュの全境界進入リンクについてステップ３０６の処理が完了すれば、全目的側メッシュについて上記処理が終了したかチェックし(ステップ３０９)、終了してなければkを歩進して(k＝k+1,ステップ３１０)、ステップ３０５以降の処理を繰り返す。
ステップ３０９において、全目的側メッシュについて上記処理が終了すれば、第i出発側メッシュの第ｊ境界脱出リンクから全目的側メッシュの全境界脱出リンクに至る探索範囲データの作成が完了する。ついで、第i出発側メッシュの全境界脱出リンクについて上記処理が完了したかチェックし(ステップ３１１)、完了してなければｊを歩進して(ｊ＝ｊ+1,ステップ３１２)、ステップ３０３以降の処理を繰り返す。
ステップ３１１において、第i出発側メッシュの全境界脱出リンクからの経路探索が完了すれば、メッシュ番号iのメッシュと他のすべてのメッシュとの組み合わせに対応する探索範囲データの作成が完了する。
ついで、全出発側メッシュについて上記処理が終了したかチェックし(ステップ３１３)、終了してなければiを歩進して(i＝i+1,ステップ３１４)、ステップ３０２以降の処理を繰り返す。ステップ３１３において、全出発側メッシュについて上記処理が終了すれば、探索範囲データの作成が完了する。

（E）ナビゲーション装置
図１２は本発明のナビゲーション装置の構成図である。
地図記録媒体(CD-ROM、DVDなど）１１には図６の地図作成装置が作成した地図データが記録されており、必要に応じて読み取られるようになっている。操作部１２はナビゲーション制御装置１０を操作するものでリモコン、操作用のハードキーなどを有している。GPS受信機１３はGPS衛星から送られてくるGPS信号を受信し、車両の絶対的現在位置(GPS位置)や進行方向を算出し、自立航法センサー部１４は、所定時間毎に進行方向変化および走行距離を検出してナビゲーション制御装置１０に入力する。
タッチパネル式ディスプレイ装置１５はナビゲーション制御装置１０からの指示に従って車両周辺地図、誘導経路、メニュー、車両位置マーク等を表示する。また、タッチパネル式ディスプレイ装置１５は、スクリーンに表示したソフトキーが押下されたとき所定のコマンドをナビゲーション制御装置１０に入力するようになっている。
ナビゲーション制御装置１０において、位置推定制御部２０はGPS受信機１３及び自立航法センサー部１４からの信号に基づいて車両位置を推定してナビゲーション制御部２２に入力する。地図バッファ２１は地図記録媒体から読み取った地図データを保存する。ナビゲーション制御部２２は、図示しないが、入力される各種情報、コマンドに基づいて、車両位置周辺の地図データを地図バッファ２１に読み出す地図読み出し制御部、誘導経路探索制御及び経路誘導制御を実行する誘導経路制御部、各種操作画面、車両マークの発生制御を実行する操作画面発生制御部などを有している。
地図描画部２３は地図バッファ２１に読み出された地図データを用いて地図画像を生成してVRAM ２４に書込み、画像読み出し部２５は制御部２２からの指示に従ってVRAM ２４から所定の画像部分を切り取って画像合成部２６に入力する。
誘導経路メモリ２７は、制御部２２の誘導経路制御部により探索された目的地までの誘導経路情報、すなわち、誘導経路を構成する全リンクデータを出発地から目的地まで記録する。誘導経路描画部２８は誘導経路情報を用いて誘導経路画像を発生して画像合成部２６に入力し、描画地図上に強調表示する。操作画面発生部２９は各種メニュー画面(操作画面)を生成して画像合成部２６に入力し、マーク発生部３０は車両位置マークやカーソル等の各種マークを生成して画像合成部26に入力する。画像合成部２６は、VRAM ２４から読み出した地図画像に各種マークや誘導経路画像を重ね合わせてスクリーン全体に表示する。

（F）誘導経路探索
図１３は出発地と目的地が特定された際の本発明の誘導経路探索処理フローである。
レベル１メッシュの出発地からレベル４のメッシュのリンクまでの経路を探索する(ステップ４０１)。同様に、レベル１メッシュの目的地からレベル４のメッシュのリンクまでの経路を探索する(ステップ４０２)。ついで、レベル４メッシュの出発側リンクおよびレベル４メッシュの目的側リンクがそれぞれ存在するレベル３メッシュ番号を求める(ステップ４０３)。この求めたレベル３メッシュの組み合わせにより、経路探索に際してどの探索範囲データを使用するかがわかる。
しかる後、該探索範囲データを参照しつつ、レベル４の道路情報(リンクレコード)を用いて出発地から目的地までの経路を探索する(ステップ４０４)。すなわち、経路探索に際して、レベル４リンクのリンクレコードに含まれるレベル３メッシュ番号に対応する探索範囲データのビット位置を参照し(図１４参照)、“１”(オン)であれば、該レベル４リンクは経路探索対象リンクであるとみなして該リンクを用いて経路探索処理を行い、“０”(オフ)であれば、該レベル４リンクは経路探索対象リンクでないとみなして経路探索に使用しない。
ステップ４０１においてレベル１の出発地からレベル４メッシュのリンクまでの経路は複数見つかるから、夫々について出発地から目的地までの経路を探索し、最小コストの経路を誘導経路として取得する(ステップ４０５)。
以上本発明によれば階層型探索において、探索範囲を経路品位に影響する事無く絞り込む事が出来て、探索時間を削減する事が出来る。

本発明の地図データに含まれる道路情報の説明図である。探索範囲データSRDの説明図である。図３はメッシュの一例説明図である。道路情報に含まれるリンクレコードの構成説明図である。レベル４のリンクがレベル３領域をまたがらないように形成することを説明する説明図である。本発明の地図作成装置の要部構成図である。本発明の地図作成処理説明図である。コストを距離とした場合のダイクストラ法の概略説明図である。ダイクストラ法を用いた経路探索処理のフローである。本発明の第１の探索範囲データ作成処理フローである。本発明の第２の探索範囲データ作成処理フローである。本発明のナビゲーション装置の構成図である。出発地と目的地が入力された際の本発明の誘導経路探索処理フローである。レベル４リンクを経路探索に使用するか否かを判断する説明図である。第１従来技術説明図である。第２従来技術説明図である。第２従来技術の問題点説明図である。

符号の説明

１リンクデータ入力部
２リスト作成部
３経路探索部
４探索範囲データ作成部
５メモリ
６地図データ作成部
７ DVD

Claims

詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成方法において、
所定レベルにおける任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用する該レベルのメッシュを特定するデータを探索範囲情報として地図データに含めて地図を作成する際、
メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成し、
任意の２つのメッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクから他方のメッシュの各境界進入リンクに到る全経路を探索し、探索された各経路を構成するリンクが属するメッシュを特定するデータにより前記探索範囲情報を作成する、
ことを特徴とする地図データ作成方法。
詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成方法において、
所定レベルにおける任意の２つのメッシュの組み合わせ毎に、一方のメッシュから他方のメッシュに到る経路を探索する際に使用する該レベルのメッシュを特定するデータを探索範囲情報として地図データに含めて地図を作成する際、
メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成し、
任意の第１メッシュの境界脱出リンクから探索が不可能となるまで探索を行い、探索終了後、探索結果を参照し、前記第１メッシュの境界脱出リンクから任意の第２メッシュの各境界進入リンクに到る全経路を求め、
同様に、前記第１メッシュの各境界脱出リンクについて該境界脱出リンクから前記第２メッシュの各境界進入リンクに到る全経路を求め、
前記各経路を構成するリンクが属するメッシュを特定することにより、前記第１、第２メッシュの組み合わせに応じた探索範囲情報を作成する、
ことを特徴とする地図データ作成方法。
前記所定レベルは最上位レベルの次のレベル(準最上位レベル)であり、最上位レベルの道路情報を構成するリンクは前記準最上位レベルのメッシュをまたがらないようにし、かつ、該リンクのリンクレコードに該リンクが存在する前記準最上位レベルのメッシュの識別データを含ませることを特徴とする請求項１または２記載の地図データ作成方法。
詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成装置において、
メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成するリンクリスト作成部、
任意の２つのメッシュの組み合わせ毎に、一方のメッシュの各境界脱出リンクから他方のメッシュの各境界進入リンクに到る全経路を探索する探索部、
探索された各経路を構成するリンクが属するメッシュを特定するデータにより前記一方のメッシュから他方のメッシュに到る経路を探索する際に使用するメッシュを特定する探索範囲情報を作成する探索範囲情報作成部、
を備えたことを特徴とする地図データ作成装置。
詳細度に応じて複数のレベルを設けると共に各レベルにおけるメッシュを階層化し、各レベルのメッシュ毎の道路情報を有する地図データを作成するナビゲーション用の地図データ作成装置において、
メッシュの道路情報を参照し、メッシュ毎に該メッシュから脱出する境界脱出リンクのリストと、該メッシュに進入する境界進入リンクのリストを作成するリンクリスト作成部、
任意の第１メッシュの境界脱出リンクから探索が不可能となるまで探索を行い、探索終了後、探索結果を参照して前記第１メッシュの境界脱出リンクから任意の第２メッシュの各境界進入リンクに到る全経路を求め、同様に、前記第１メッシュの各境界脱出リンクについて該境界脱出リンクから前記第２メッシュの各境界進入リンクに到る全経路を求める経路探索部、
前記各経路を構成するリンクが属するメッシュを特定するデータにより、前記第１のメッシュから第２のメッシュに到る経路を探索する際に使用するメッシュを特定する探索範囲情報を作成する探索範囲情報作成部、
を備えたことを特徴とする地図データ作成装置。