地図データのデータ構造
【課題】本発明は、上り車線と下り車線とに分けて規定されたリンクを適切に取り扱うことが可能な技術を提供する。
【解決手段】地図上に道路を表現するための地図データ８０のデータ構造は、道路上の基準点を示す複数のノードを規定したノードデータ８１０と、ノードデータ８１０に規定された複数のノード間を接続する複数のリンクを規定したリンクデータ８２０と、リンクデータ８２０に規定された複数のリンクのうち、同一の道路に含まれる上り車線と下り車線とをそれぞれ表現するリンク同士を関連付けた上下線ペアデータ８３０とを備える。
【解決手段】地図上に道路を表現するための地図データ８０のデータ構造は、道路上の基準点を示す複数のノードを規定したノードデータ８１０と、ノードデータ８１０に規定された複数のノード間を接続する複数のリンクを規定したリンクデータ８２０と、リンクデータ８２０に規定された複数のリンクのうち、同一の道路に含まれる上り車線と下り車線とをそれぞれ表現するリンク同士を関連付けた上下線ペアデータ８３０とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地図表示装置等で表示される地図上に道路を表現するために用いられる地図データのデータ構造に関する。
【背景技術】
【０００２】
地図上に道路を表現するための地図データは、コンピュータで利用可能に電子化され、車載用や携帯用のナビゲーション装置、ウェブサーバ、パーソナルコンピュータなどの装置で利用される。一般的な地図データは、道路上の基準点を示す複数のノードを規定したノードデータと、これら複数のノード間を接続する複数のリンクを規定したリンクデータとを備える。地図データを利用する装置は、地図データに規定されたノードおよびリンクを組み合わせて地図上に道路を表現することによって、道路地図の表示、現在地の表示、経路の探索、経路の案内などの処理を実行する。
【０００３】
地図データにおけるリンクは、一つの道路を一つのリンクで規定した上下線非分離リンクと、一つの道路に設けられた上り車線と下り車線とを別々のリンクで規定した上下線分離リンクとを含む。例えば、縮尺が比較的に小さい地図上に道路を表現するために用いられるリンクや、中央分離帯で車線が分離されていない道路を表現するために用いられるリンクは、上下線非分離リンクとして規定される場合が多い。また、例えば、縮尺が比較的に大きい地図上に上下線分離道路を表現するために用いられるリンクは、上下線分離リンクとして規定される場合が多い。
【０００４】
下記特許文献１には、同一の道路に含まれる上り車線と下り車線とをそれぞれ表現する上下線分離リンクを一つの道路として地図上に表現するために、並行する二つのリンクを、一つの道路に設けられた上り車線と下り車線とを別々のリンクで規定したものであると判断し、これら並行する二つのリンクを、一つの道路を表現するデータとして取り扱う技術が開示されている。
【０００５】
【特許文献１】特許第３２２８２４０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、特許文献１の技術では、並行する二つのリンクを、一つの道路を表現するデータとして画一的に取り扱うことから、実際に並行している二つの道路をそれぞれ規定した二つのリンクを、一つの道路を表現するデータとして誤った取り扱いをしてしまうという問題があった。
【０００７】
本発明は、上記した課題を踏まえ、上り車線と下り車線とに分けて規定されたリンクを適切に取り扱うことが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、上述の課題の少なくとも一部を解決するためになされたものであり、以下の実施の形態として実現することが可能である。
【０００９】
本発明における地図データのデータ構造は、地図上に道路を表現するための地図データのデータ構造であって、道路上の基準点を示す複数のノードを規定したノードデータと、前記ノードデータに規定された複数のノード間を接続する複数のリンクを規定したリンクデータと、前記リンクデータに規定された複数のリンクのうち、同一の道路に含まれる上り車線と下り車線とをそれぞれ表現するリンク同士を関連付けた上下線ペアデータとを備えることを特徴とする。本発明における地図データのデータ構造によれば、同一の道路に含まれる上り車線と下り車線とをそれぞれ表現するリンク同士を上下線ペアデータによって特定することができるため、上り車線と下り車線とに分けて規定されたリンクを適切に取り扱うことができる。
【００１０】
本発明の形態は、データ構造に限るものではなく、例えば、ナビゲーションシステム、ナビゲーション装置、ナビゲーション装置の制御方法、ナビゲーション装置を制御する機能をコンピュータに実現させるためのプログラムなどの他の形態に適用することもできる。また、本発明は、前述の形態に何ら限定されるものではなく、本発明の趣旨を逸脱しない範囲内において様々な形態で実施し得ることは勿論である。
【発明を実施するための最良の形態】
【００１１】
以上説明した本発明の構成および作用を一層明らかにするために、以下本発明を適用した地図表示システムについて説明する。
【００１２】
Ａ．地図表示システム１０の構成：
図１は、地図表示システム１０の構成を示す説明図である。地図表示システム１０は、端末装置２０と、地図サーバ５０と、記憶装置６０とを備える。地図表示システム１０は、記憶装置６０に記憶されている地図データ８０に基づくデータを地図サーバ５０から端末装置２０に配信することによって、端末装置２０において道路地図の表示、現在地の表示、経路の探索、経路の案内などを実行するナビゲーションシステムである。
【００１３】
地図表示システム１０の端末装置２０は、携帯用のナビゲーション装置であり、本実施例では、ナビゲーション装置としての機能を有する携帯電話機である。端末装置２０は、ＣＰＵ（Central Processing Unit）２１０と、メモリ２２０と、ディスプレイ２３０と、入力ボタン２４０と、無線通信部２５０と、ＧＰＳ受信部２６０とを備える。
【００１４】
端末装置２０のＣＰＵ２１０は、端末装置２０の各部を制御する。端末装置２０のメモリ２２０は、ＣＰＵ２１０の動作を規定したプログラムや、ＣＰＵ２１０によって取り扱われる種々のデータを記憶する。端末装置２０のディスプレイ２３０は、ＣＰＵ２１０の指示に基づいて道路地図を含む種々の画像を表示する。端末装置２０の入力ボタン２４０は、端末装置２０を操作するユーザからのデータの入力を受け付ける。
【００１５】
端末装置２０の無線通信部２５０は、地図サーバ５０とのデータのやり取りを無線通信で行う。本実施例では、端末装置２０の無線通信部２５０が携帯電話網の基地局装置３０と無線通信を行うことによって、端末装置２０は、地図サーバ５０に接続されたネットワーク４０に接続する。ネットワーク４０は、インターネット，ＷＡＮ(Wide Area Network)，ＬＡＮ(Local Area Network)，携帯電話網，固定電話網，光通信網などを含むとしても良い。
【００１６】
端末装置２０のＧＰＳ受信部２５０は、測地衛星９０から送信されるＧＰＳ（Global Positioning System）信号を受信する。ＧＰＳ受信部２５０によって受信されたＧＰＳ信号を解析することによって、端末装置２０の現在位置を検知することができる。
【００１７】
地図表示システム１０の地図サーバ５０は、ＣＰＵ５１０と、メモリ５２０とを備えるサーバコンピュータである。地図サーバ５０のＣＰＵ５１０は、地図サーバ５０の各部を制御する。地図サーバ５０のメモリ５２０は、ＣＰＵ５１０の動作を規定したプログラムや、ＣＰＵ５１０によって取り扱われる種々のデータを記憶する。地図サーバ５０は、ＣＰＵ５１０およびメモリ５２０の他、ネットワーク４０および記憶装置６０の各々とデータのやり取りを行うインタフェース（図示しない）を備える。地図サーバ５０の動作についての詳細は後述する。
【００１８】
地図表示システム１０の記憶装置６０は、地図データ８０を記憶可能な記憶容量を有する記憶装置である。本実施例では、記憶装置６０は、地図サーバ５０の外部記憶装置として構成されたハードディスクドライブ(Hard Disk Drive、以下、ＨＤＤという)であるが、他の実施形態において、記憶装置６０は、地図サーバ５０に内蔵されても良いし、半導体メモリやＤＶＤ(Digital Versatile Disk)，ＣＤ(Compact Disk)を用いた記憶装置であっても良い。
【００１９】
記憶装置６０に記憶されている地図データ８０は、ノードデータ８１０と、リンクデータ８２０と、上下線ペアデータ８３０と、同一交差点データ８４０とを備える。地図データ８０のノードデータ８１０は、道路上の基準点を示す複数のノードを規定する。地図データ８０のリンクデータ８２０は、ノードデータ８１０に規定された複数のノード間を接続する複数のリンクを規定する。地図データ８０の上下線ペアデータ８３０は、リンクデータ８２０に規定された複数のリンクのうち、同一の道路に含まれる上り車線と下り車線とをそれぞれ表現するリンク同士を関連付ける。地図データ８０の同一交差点データ８４０は、リンクデータ８２０で規定された複数のリンクのうち、同一の交差点を表現するリンク同士を関連付ける。地図データ８０が備えるノードデータ８１０，リンクデータ８２０，上下線ペアデータ８３０，同一交差点データ８４０の構成についての詳細は後述する。
【００２０】
図２は、地図データ８０によって規定されたノードおよびリンクを模式的に例示する説明図である。以下の説明では、図中のノードを個別に示す場合には、英文字「Ｎ」の後に数字を付した符号を用い（例えば、Ｎ１，Ｎ２，Ｎ３，…）、図中のリンクを個別に示す場合には、英文字「Ｌ」の後に数字を付した符号を用いる（例えば、Ｌ１，Ｌ２，Ｌ３，…）。図２には、地図データ８０のノードデータ８１０によって規定された９個のノードＮ１〜Ｎ９が図示されており、地図データ８０のリンクデータ８２０によって規定された１１個のリンクＬ１〜Ｌ１１が図示されている。ノードＮ１〜Ｎ９は、道路や車線における特徴的な基準点、例えば、交差点，分岐点，幅員が変化する点などを表現する。リンクＬ１〜Ｌ１１は、ノードＮ１〜Ｎ９の間を接続する道路や車線を表現する。
【００２１】
図３は、地図データ８０におけるノードデータ８１０の詳細構成を示す説明図である。ノードデータ８１０は、ノード毎の属性を示すノード属性データ８１０２を備える。ノード属性データ８１０２に示されるノードの属性は、ノード番号と、位置座標と、ノード種別と、接続リンク数と、接続リンク番号と、リンク間規制情報とを含む。
【００２２】
ノード属性データ８１０２のノード番号は、ノードを識別するための符号を示す。ノード属性データ８１０２の位置座標は、地図上におけるノードの位置を示す。ノード属性データ８１０２のノード種別は、ノードが表現する基準点の種別を示す。ノード属性データ８１０２の接続リンク数は、ノードに接続するリンクの数を示す。ノード属性データ８１０２の接続リンク番号は、ノードに接続するリンクを識別するための符号を示す。図３に示す例では、ノード番号「Ｎ２」が割り当てられたノードＮ２に関するノード属性データ８１０２には、ノードＮ２が座標［Ｘｎ２（経度），Ｙｎ２（緯度）］上に位置し、ノードＮ２が「交差点」を表現し、ノードＮ２に接続するリンクの数が「４」であり、これらのリンク番号が「Ｌ１，Ｌ２，Ｌ４，Ｌ９」であることが示されている。
【００２３】
図４は、地図データ８０におけるリンクデータ８２０の詳細構成を示す説明図である。リンクデータ８２０は、リンク毎の属性を示すリンク属性データ８２０２を備える。リンク属性データ８２０２に示されるリンクの属性は、リンク番号と、始点ノードと、終点ノードと、道路種別と、補間点座標とを含み、その他、リンク長，幅員区分，車線数なども含む。
【００２４】
リンク属性データ８２０２のリンク番号は、リンクを識別するための符号を示す。リンク属性データ８２０２の始点ノードは、リンクが始点として接続するノードを識別するための符号を示す。リンク属性データ８２０２の終点ノードは、リンクが終点として接続するノードを識別するための符号を示す。リンク属性データ８２０２の道路種別は、リンクが表現する道路や車線の種別を示す。リンク属性データ８２０２の補間点座標は、リンクが始点ノードから終点ノードまで延びる軌跡の形状を示す。リンク属性データ８２０２のリンク長は、始点ノードから終点ノードまでのリンクの長さを示す。リンク属性データ８２０２の幅員区分は、リンクが表現する道路や車線の幅員を示す。リンク属性データ８２０２の車線数は、リンクが表現する道路や車線に含まれる車線の数を示す。図４に示す例では、リンク番号「Ｌ２」が割り当てられたリンクＬ２に関するリンク属性データ８２０２には、リンクＬ２が「始点ノードＮ２」から「終点ノードＮ３」へと接続し、リンクＬ２が表現する道路が「一般国道」であることが示されている。
【００２５】
図５は、地図データ８０における同一交差点データ８４０の詳細構成を示す説明図である。同一交差点データ８４０は、交差点毎の属性を示す交差点属性データ８４０２を備える。交差点属性データ８４０２に示される交差点の属性は、交差点番号と、構成リンク数と、構成リンク番号を含む。
【００２６】
交差点属性データ８４０２の交差点番号は、交差点を識別するための符号を示す。交差点属性データ８４０２の構成リンク数は、交差点を構成するリンクの数を示す。交差点属性データ８４０２の構成リンク番号は、交差点を構成するリンクを識別するための符号を示す。図５に示す例では、交差点番号「Ｃ１」が割り当てられた交差点Ｃ１に関する交差点属性データ８４０２には、交差点Ｃ１を構成するリンク数が「６」であり、これらのリンク番号が「Ｌ１ａ〜Ｌ１ｆ」であることが示されている。
【００２７】
図６は、同一交差点を模式的に例示する説明図である。図６には、図５の交差点属性データ８４０２によって規定された交差点Ｃ１が示されている。交差点Ｃ１は、６個のリンクＬ１ａ〜Ｌ１ｆで構成されている。交差点Ｃ１を構成するリンクＬ１ａ〜Ｌ１ｆは、リンクデータ８２０に規定されている。
【００２８】
交差点Ｃ１のリンクＬ１ａは、上り車線を表現するリンクＬ１７とリンクＬ１８との間を接続する交差点内リンクである。リンクＬ１７によって表現される上り車線は、リンクＬ１６によって表現される下り車線に対向して延びる車線であり、これらの車線は同じ道路に含まれる。リンクＬ１８によって表現される上り車線は、リンクＬ１５によって表現される下り車線に対向して延びる車線であり、これらの車線は同じ道路に含まれる。交差点Ｃ１のリンクＬ１ｂは、下り車線を表現するリンクＬ１５とリンクＬ１６との間を接続する交差点内リンクである。
【００２９】
交差点Ｃ１のリンクＬ１ｃは、上り車線を表現するリンクＬ１１とリンクＬ１２との間を接続する交差点内リンクである。リンクＬ１１によって表現される上り車線は、リンクＬ１４によって表現される下り車線に対向して延びる車線であり、これらの車線は同じ道路に含まれる。リンクＬ１２によって表現される上り車線は、リンクＬ１３によって表現される下り車線に対向して延びる車線であり、これらの車線は同じ道路に含まれる。交差点Ｃ１のリンクＬ１ｄは、下り車線を表現するリンクＬ１３とリンクＬ１４との間を接続する交差点内リンクである。
【００３０】
交差点Ｃ１のリンクＬ１ｅおよびリンクＬ１ｆは、交差点内におけるＵターン禁止を表現するために設けられたＵターンダミーリンクである。図６に示す例では、「リンクＬ１ａ−リンクＬ１ｃ−リンクＬ１ｂ」を介したリンクＬ１７からリンクＬ１６へのＵターンを禁止するために、リンクＬ１ａからリンクＬ１ｃへの進入が禁止されている。このままでは、リンクＬ１７からリンクＬ１２への右折ができないため、リンクＬ１７からリンクＬ１２へと接続するＵターンダミーリンクとしてリンクＬ１ｅを設けると共に、リンクＬ１ｅからリンクＬ１ｂへの進入を禁止することによって、リンクＬ１ｅを介してリンクＬ１７からリンクＬ１２への右折が可能になっている。リンクＬ１ｅは、リンクＬ１５からリンクＬ１８へのＵターンを禁止するためにも利用されている。また、リンクＬ１ｆは、リンクＬ１ｅと同様に、リンクＬ１１からリンクＬ１４へのＵターンと、リンクＬ１３からリンクＬ１２へのＵターンとを禁止するために設けられている。
【００３１】
図７は、地図データ８０における上下線ペアデータ８３０の詳細構成を示す説明図である。上下線ペアデータ８３０は、上下線ペアリンク毎の属性を示す上下線属性データ８３０２を備える。上下線ペアリンクは、上り車線を表現するリンクと下り車線を表現するリンクとの組み合わせであり、２個以上のリンクで構成されるものである。上下線属性データ８３０２に示される上下線ペアリンクの属性は、上下線ペア番号と、上り構成リンク数と、上り構成リンク番号と、下り構成リンク数と、下り構成リンク番号とを含む。
【００３２】
上下線属性データ８３０２の上下線ペア番号は、上下線ペアリンクを識別するための符号を示す。上下線属性データ８３０２の上り構成リンク数は、上下線ペアリンクを構成するリンクのうち上り線を構成するリンクの数を示す。上下線属性データ８３０２の上り構成リンク番号は、上下線ペアリンクを構成するリンクのうち上り線を構成するリンクを識別するための符号を示す。上下線属性データ８３０２の下り構成リンク数は、上下線ペアリンクを構成するリンクのうち下り線を構成するリンクの数を示す。上下線属性データ８３０２の下り構成リンク番号は、上下線ペアリンクを構成するリンクのうち下り線を構成するリンクを識別するための符号を示す。図７に示す例では、上下線ペア番号「Ｐ２」が割り当てられた上下線ペアリンクＰ２に関する上下線属性データ８３０２には、上下線ペアリンクＰ２における上り線を構成するリンク数が「２」であり、これらの構成リンク番号が「Ｌ２３，Ｌ２４」であることが示されている。また、上下線ペアリンクＰ２における下り線を構成するリンク数が「１」であり、この構成リンク番号が「Ｌ２２」であることも示されている。
【００３３】
図８は、第１形態における上下線ペアリンクを模式的に例示する説明図である。図８には、同一交差点Ｃ２１と同一交差点Ｃ２２との間に挟まれた上下線ペアリンクＰ２が示されている。上下線ペアリンクＰ２は、３個のリンクＬ２２，Ｌ２３，Ｌ２４で構成されており、これら３個のリンクＬ２２，Ｌ２３，Ｌ２４は、リンクデータ８２０に規定されている。上下線ペアリンクＰ２における下り線Ｄ２のリンクＬ２２は、同一交差点Ｃ２２から延びて同一交差点Ｃ２１に接続する。上り線Ｕ２のリンクＬ２３は、同一交差点Ｃ２１から延びてリンクＬ２４に接続し、上り線Ｕ２のリンクＬ２４は、リンクＬ２３から延びて同一交差点Ｃ２２に接続する。すなわち、リンクＬ２２は、リンクＬ２３，Ｌ２４に対向する方向に延びた車線である。同一交差点Ｃ２１，Ｃ２２は、同一交差点データ８４０によって規定されている。同一交差点Ｃ２１は、図６で示した同一交差点Ｃ１と同様に６個のリンクで構成されている。同一交差点Ｃ２２は、リンクＬ２４の一端とリンクＬ２２の一端とを接続する１個のリンクで構成されている。
【００３４】
図９は、第２形態における上下線ペアリンクを模式的に例示する説明図である。図９には、同一交差点Ｃ３１とノードＮ３１との間に挟まれた上下線ペアリンクＰ３が示されている。上下線ペアリンクＰ３は、３個のリンクＬ３２，Ｌ３３，Ｌ３４で構成されており、これら３個のリンクＬ３２，Ｌ３３，Ｌ３４は、リンクデータ８２０に規定されている。上下線ペアリンクＰ３における下り線Ｄ３のリンクＬ３２は、ノードＮ３１から延びて同一交差点Ｃ３１に接続する。上り線Ｕ３のリンクＬ３３は、同一交差点Ｃ３１から延びてリンクＬ３４に接続し、上り線Ｕ３のリンクＬ３４は、リンクＬ３３から延びてノードＮ３１に接続する。すなわち、リンクＬ３２は、リンクＬ３３，Ｌ３４に対向する方向に延びた車線である。同一交差点Ｃ３１は、同一交差点データ８４０によって規定されており、図６で示した同一交差点Ｃ１と同様に６個のリンクで構成されている。ノードＮ３１は、ノードデータ８１０に規定されており、上下線が分離されていない道路を表現するリンクＬ３５との接続地点である二条化開始終了点を表現する。
【００３５】
図１０は、第３形態における上下線ペアリンクを模式的に例示する説明図である。図１０には、同一交差点Ｃ４１とノードＮ４１，Ｎ４２との間に挟まれた上下線ペアリンクＰ４が示されている。上下線ペアリンクＰ４は、３個のリンクＬ４２，Ｌ４３，Ｌ４４で構成されており、これら３個のリンクＬ４２，Ｌ４３，Ｌ４４は、リンクデータ８２０に規定されている。上下線ペアリンクＰ４における下り線Ｄ４のリンクＬ４２は、ノードＮ４２から延びて同一交差点Ｃ４１に接続する。上り線Ｕ４のリンクＬ４３は、同一交差点Ｃ４１から延びてリンクＬ４４に接続し、上り線Ｕ４のリンクＬ４４は、リンクＬ４３から延びてノードＮ４１に接続する。すなわち、リンクＬ４２は、リンクＬ４３，Ｌ４４に対向する方向に延びた車線である。同一交差点Ｃ４１は、同一交差点データ８４０によって規定されており、図６で示した同一交差点Ｃ１と同様に６個のリンクで構成されている。ノードＮ４１，Ｎ４２は、ノードデータ８１０に規定されており、地図を区画するメッシュＭ４１の境界線上の基準点を表現する。
【００３６】
Ａ２．地図表示システム１０の動作：
Ａ２−１．交差点拡大処理：
図１１は、地図表示システム１０の地図サーバ５０が実行する交差点拡大処理（ステップＳ１１０）を示すフローチャートである。本実施例では、地図サーバ５０は、交差点を拡大表示した画像を端末装置２０から要求された場合に、図１１の交差点拡大処理（ステップＳ１１０）を実行する。本実施例では、図１１の交差点拡大処理（ステップＳ１１０）は、地図サーバ５０のＣＰＵ５１０がソフトウェアに基づいて動作することによって実現されるが、他の実施形態として、地図サーバ５０の電子回路がその物理的な回路構成に基づいて動作することによって実現されても良い。
【００３７】
地図サーバ５０は、図１１の交差点拡大処理（ステップＳ１１０）を開始すると、交差点を拡大表示した画像を要求するコマンドを端末装置２０から受信する（ステップＳ１１２）。その後、地図サーバ５０は、拡大表示される交差点に接続するリンクに、上下線ペアデータ８３０によって上下線ペアリンクとして規定されたリンクが含まれるか否かを判断する（ステップＳ１１４）。
【００３８】
拡大対象に上下線ペアリンクが含まれる場合（ステップＳ１１４：「ＹＥＳ」）、地図サーバ５０は、上下線ペアリンクとして規定されたリンクを一つの道路とし、同一交差点を一つの点に縮退した形式で、交差点拡大画像を描画する（ステップＳ１１５）。一方、拡大対象に上下線ペアリンクが含まれない場合（ステップＳ１１４：ＮＯ」）、地図サーバ５０は、リンクの各々を一つの道路として交差点拡大画像を描画する（ステップＳ１１６）。
【００３９】
交差点拡大画像が描画された後（ステップＳ１１５，Ｓ１１６）、地図サーバ５０は、交差点拡大画像を端末装置２０に配信する（ステップＳ１１７）。端末装置２０は、地図サーバ５０から交差点拡大画像を受信すると、その交差点拡大画像をディスプレイ２３０に表示する。
【００４０】
以上説明した図１１の交差点拡大処理（ステップＳ１１０）によれば、表示対象であるリンクが上下線分離道路か否かを、上下線ペアデータ８３０を参照することによって判断することができるため、上り車線と下り車線とが別々のリンクで規定されている場合であっても、一つの道路として実際の道路形状に即した道路地図を表示することができる。
【００４１】
Ａ２−２．探索済み道路の設定処理：
図１２は、地図表示システム１０の地図サーバ５０が実行する探索済み道路の設定処理（ステップＳ１２０）を示すフローチャートである。本実施例では、地図サーバ５０は、経路探索中にリンクが経路として選定された場合に、図１２の探索済み道路の設定処理（ステップＳ１２０）を実行する。本実施例では、図１２の探索済み道路の設定処理（ステップＳ１２０）は、地図サーバ５０のＣＰＵ５１０がソフトウェアに基づいて動作することによって実現されるが、他の実施形態として、地図サーバ５０の電子回路がその物理的な回路構成に基づいて動作することによって実現されても良い。
【００４２】
地図サーバ５０は、図１２の探索済み道路の設定処理（ステップＳ１２０）を開始すると、経路探索中に経路として選定した選定リンクを特定する（ステップＳ１２２）。その後、地図サーバ５０は、特定された選定リンクに、上下線ペアデータ８３０によって上下線ペアリンクとして規定されたリンクが含まれるか否かを判断する（ステップＳ１２４）。
【００４３】
選定リンクに上下線ペアリンクが含まれる場合（ステップＳ１２４：「ＹＥＳ」）、地図サーバ５０は、選定リンクと共に、その選定リンクと上下線ペアリンクの関係にあるリンクの双方を、探索経路で通過済みの通過リンクとして設定する（ステップＳ１２５）。一方、選定リンクに上下線ペアリンクが含まれない場合（ステップＳ１２４：「ＮＯ」）、地図サーバ５０は、探索経路で通過済みの通過リンクとして選定リンクを設定する（ステップＳ１２６）。
【００４４】
通過リンクが設定された後（ステップＳ１２５，Ｓ１２６）、地図サーバ５０は、経路探索を再開する。再開された経路探索において、地図サーバ５０は、図１２の探索済み道路の設定処理（ステップＳ１２０）で設定された通過リンクを参照しながら経路探索を実行する。
【００４５】
図１３は、通過リンクを参照した経路探索の一例を示す説明図である。図１３の例では、道路上におけるＧＰＳや無線通信システムの電波強度を調査する路上調査車両の調査経路を探索する様子が示されている。路上調査車両の経路探索では、重複経路を避けて出来るだけ多くの道路を経由することが求められる。上下線分離道路に含まれる一方の車線を通過した後、その上下線分離道路に含まれる他方の車線を通過すると、同じ道路を重複して通過することになるため、路上調査車両の経路探索では、上下線分離道路に含まれる上り車線および下り車線の双方を経由する重複経路を回避する必要がある。
【００４６】
図１３の例では、上下線ペアリンクＰ５１に含まれるリンクＬ５１が経路として選定されると、リンクＬ５１と上下線ペアリンクの関係にあるリンクＬ５２がリンクＬ５１と共に通過リンクとして設定される（図１２のステップＳ１２５）。その後の経路探索において、リンクＬ５１，Ｌ５２は、通過リンクとして取り扱われ、経路として選定される優先度が低くなる。また、上下線ペアリンクＰ５５に含まれるリンクＬ５６が経路として選定されると、リンクＬ５６と上下線ペアリンクの関係にあるリンクＬ５５がリンクＬ５６と共に通過リンクとして設定される（図１２のステップＳ１２５）。その後の経路探索において、リンクＬ５５，Ｌ５６は、通過リンクとして取り扱われ、経路として選定される優先度が低くなる。
【００４７】
図１４は、通過リンクを参照した経路探索の一例を示す説明図である。図１４の例では、複数の階層に分けて経路探索を実施する階層的経路探索を行う様子が示されている。階層的経路探索では、例えば、第１階層では一般道を含む全ての道路で構成された道路網で経路探索が実行される。第２階層では高速道路、有料道路、国道および県道で構成された道路網が経路探索される。第３階層では高速道および有料道路で構成された道路網で経路探索が実行される。図１４では、リンクＬ６１，Ｌ６２，Ｌ６３は、第１階層の道路網に含まれており、その他のリンクＬ６５，Ｌ６６，Ｌ６７，Ｌ６８などは、第２階層の道路網に含まれる。第２階層のリンクＬ６５，Ｌ６７は、上下線ペアリンクＰ６１として上下線ペアデータ８３０に規定されている。
【００４８】
図１４における地点Ａから地点Ｂまでの経路探索について説明する。従来例では、まず経路探索が開始されると、地点Ａに隣接する第１階層のリンクＬ６１が経路として選定される。その後、第１階層での経路探索にて、第１階層のリンクＬ６１から第２階層のリンクＬ６５への経路が選定されたとする。第１階層の経路探索で所定の回数だけ探索枝を延伸しても目的地点Ｂに到達しなかった場合、探索枝が到達し得た範囲内にある第２階層のノード（例えば、Ｎ６１）から階層遷移し、第２階層での経路探索が実行される。したがって、経路探索結果は、重複経路であるリンクＬ６５，Ｌ６７を含む、リンクＬ６１，Ｌ６５、Ｌ６６、Ｌ６７，Ｌ６８の順となる。
【００４９】
その一方で、本実施例では、第２階層のリンクＬ６５が経路として選定されると、リンクＬ６５と上下線ペアリンクの関係にあるリンクＬ６７がリンクＬ６５と共に通過リンクとして設定される（図１２のステップＳ１２５）。そのため、第１階層の経路探索にてリンクＬ６５が選定された後、第２階層の経路探索にてリンクＬ６７が選定された場合であっても、リンクＬ６５とリンクＬ６７とが重複経路の関係になることを判断することができる。したがって、重複経路を避けて経路を再探索することができる。つまり、経路探索結果は、重複経路であるリンクＬ６５，Ｌ６７が含まれない、リンクＬ６１，Ｌ６２，Ｌ６８の順となる。
【００５０】
以上説明した図１２の探索済み道路の設定処理（ステップＳ１２０）によれば、経路探索で選定されたリンクが上下線分離道路か否かを、上下線ペアデータ８３０を参照することによって判断することができるため、上り車線と下り車線とが別々のリンクで規定されている場合であっても、通過済みの道路であるか否かを判断することができる。
【００５１】
Ａ２−３．復路探索処理：
図１５は、地図表示システム１０の地図サーバ５０が実行する復路探索処理（ステップＳ１３０）を示すフローチャートである。本実施例では、地図サーバ５０は、復路の探索を端末装置２０から要求された場合に、図１５の復路探索処理（ステップＳ１３０）を実行する。本実施例では、図１５の復路探索処理（ステップＳ１３０）は、地図サーバ５０のＣＰＵ５１０がソフトウェアに基づいて動作することによって実現されるが、他の実施形態として、地図サーバ５０の電子回路がその物理的な回路構成に基づいて動作することによって実現されても良い。
【００５２】
地図サーバ５０は、図１５の復路探索処理（ステップＳ１３０）を開始すると、往路に含まれるリンクを特定する（ステップＳ１３２）。その後、地図サーバ５０は、往路と同じ経路で復路を作成するコマンドが選択されたか否かを判断する（ステップＳ１３４）。
【００５３】
往路と同じ経路で復路を作成する場合（ステップＳ１３４：「ＹＥＳ」）、地図サーバ５０は、往路と同じリンクおよび、往路に含まれるリンクと上下線ペアデータ８３０によって関連付けられたリンクを用いて、復路を探索する（ステップＳ１３５）。一方、往路と異なる経路で復路を作成する場合（ステップＳ１３４：「ＮＯ」）、地図サーバ５０は、往路と同じリンクおよび、往路に含まれるリンクと上下線ペアデータ８３０によって関連付けられたリンクを除いて、復路を探索する（ステップＳ１３６）。
【００５４】
以上説明した図１５の復路探索処理（ステップＳ１３０）によれば、往路に含まれる上下線分離道路を、上下線ペアデータ８３０を参照することによって容易に判断することができるため、往路と同じ経路の復路や、往路と異なる経路の復路を探索する速度を向上させることができる。
【００５５】
Ａ２−４．立寄経路探索処理：
図１６は、地図表示システム１０の地図サーバ５０が実行する立寄経路探索処理（ステップＳ１４０）を示すフローチャートである。本実施例では、地図サーバ５０は、立寄地点への経路探索を端末装置２０から要求された場合に、図１６の立寄経路探索処理（ステップＳ１４０）を実行する。本実施例では、図１６の立寄経路探索処理（ステップＳ１４０）は、地図サーバ５０のＣＰＵ５１０がソフトウェアに基づいて動作することによって実現されるが、他の実施形態として、地図サーバ５０の電子回路がその物理的な回路構成に基づいて動作することによって実現されても良い。
【００５６】
地図サーバ５０は、図１６の立寄経路探索処理（ステップＳ１４０）を開始すると、立寄地点に近隣するリンクである近隣リンクを特定する（ステップＳ１４２）。その後、地図サーバ５０は、上下線ペアデータ８３０によって近隣リンクに上下線ペアリンクとして関連付けられたリンクがあるか否かを判断する（ステップＳ１４４）。近隣リンクに上下線ペアリンクとして関連付けられたリンクがない場合（ステップＳ１４４：「ＮＯ」）、地図サーバ５０は、近隣リンクへの経路を探索する（ステップＳ１４７）。
【００５７】
一方、近隣リンクに上下線ペアリンクとして関連付けられたリンクがある場合（ステップＳ１４４：「ＹＥＳ」）、地図サーバ５０は、近隣リンクへの経路と、その近隣リンクに上下線ペアリンクとして関連付けられたリンクへの経路とを探索する（ステップＳ１４５）。その後、地図サーバ５０は、検索された双方のリンクからコストの低い経路を選定する（ステップＳ１４６）。なお、経路のコストとは、走行距離、走行時間、通行費用、渋滞状況など経路を走行するのに掛かる種々の負荷を数値化したものである。
【００５８】
図１７は、出発地Ｓから目的地Ｇまでの間に立寄地点Ｃを有する立寄経路探索処理（ステップＳ１４０）の一例を示す説明図である。図１７には、リンクＬ７１からリンクＬ７２を経てリンクＬ７３へと延びるリンク列と、このリンク列とは逆方向にリンクＬ７５からリンクＬ７４へと延びるリンク列とが示されている。従来例では、リンクＬ７１〜Ｌ７３とリンクＬ７４，Ｌ７５とで構成される道路は上下線ペアリンクとして関連付けられていない。また、リンクＬ７２は立寄地点Ｃに近隣することから、立寄経路探索処理（ステップＳ１４０）では、リンクＬ７２のみが近隣リンクとして特定される（図１６のステップＳ１４２）。そのため、出発地Ｓから立寄地点Ｃを経由して目的地Ｇまで走行する経路を探索する場合、経路探索結果は、リンクＬ７７，Ｌ７５，Ｌ７４、Ｌ７８，Ｌ７１，Ｌ７２，Ｌ７３，Ｌ７６，Ｌ７５、Ｌ７４，Ｌ７９の順となる。
【００５９】
一方、本実施例では、リンクＬ７１〜Ｌ７５は、上下線ペアデータ８３０によって上下線ペアリンクＰ７として関連付けられている。すなわち、立寄地点Ｃに近隣するリンクＬ７２は、上下線ペアリンクＰ７としてリンクＬ７４，Ｌ７５にも関連付けられていることから、図１７の状況では、立寄地点Ｃの隣接するリンクとしてリンクＬ７４，Ｌ７５も特定されることになる。したがって、リンクＬ７２，Ｌ７４，Ｌ７５の各々への経路探索が実行される（図１６のステップＳ１４５）。その後、リンクＬ７２，Ｌ７４，Ｌ７５の各々への経路のうち、コストの低い経路が選定される（図１２のステップＳ１４６）。つまり、経路探索結果は、リンクＬ７７，Ｌ７５，Ｌ７４、Ｌ７９の順となる。
【００６０】
以上説明した図１６の立寄経路探索処理（ステップＳ１４０）によれば、近隣リンクに上下線ペアリンクとして関連付けられたリンクを、上下線ペアデータ８３０を参照することによって容易に特定することができるため、立寄地点への経路を探索する速度を向上させることができる。
【００６１】
Ａ２−５．上下線構成処理：
図１８は、地図表示システム１０の地図サーバ５０が実行する上下線構成処理（ステップＳ１５０）を示すフローチャートである。本実施例では、地図サーバ５０は、道路地図を作成する際に、図１８の上下線構成処理（ステップＳ１５０）を実行する。本実施例では、図１８の上下線構成処理（ステップＳ１５０）は、地図サーバ５０のＣＰＵ５１０がソフトウェアに基づいて動作することによって実現されるが、他の実施形態として、地図サーバ５０の電子回路がその物理的な回路構成に基づいて動作することによって実現されても良い。
【００６２】
地図サーバ５０は、図１８の上下線構成処理（ステップＳ１５０）を開始すると、道路地図画像として表示する範囲内にあるリンクを特定する（ステップＳ１５２）。その後、地図サーバ５０は、上下線ペアデータ８３０を参照することによって、表示範囲内のリンクと上下線ペアリンクとして関連付けられたリンクが他のネットワークレベルにあるか否かを判断する（ステップＳ１５４）。本実施例では、地図データ８０は、第一次メッシュ（約６４００ｋｍ2）を基準に道路地図を表現した第一次ネットワークレベルと、第二次メッシュ（約１００ｋｍ2）を基準に道路地図を表現した第二次ネットワークレベルと、第三次メッシュ（約１ｋｍ2）を基準に道路地図を表現した第三次ネットワークレベルとを含む。例えば、第二次ネットワークレベルで道路地図画像を生成する場合、地図サーバ５０は、第一次ネットワークレベルに、表示範囲内のリンクと上下線ペアリンクとして関連付けられたリンクが存在するか否かを、上下線ペアデータ８３０を参照することによって判断する（ステップＳ１５４）。
【００６３】
表示範囲内のリンクと上下線ペアリンクとして関連付けられたリンクが他のネットワークレベルにある場合（ステップＳ１５４：「ＹＥＳ」）、地図サーバ５０は、他のネットワークレベルにおける上下線ペアリンクを道路地図画像として表示するリンクに追加する（ステップＳ１５６）。その後、地図サーバ５０は、表示範囲内のリンクと、他のネットワークレベルから追加されたリンクとを用いて、道路地図を作成する（ステップＳ１５７）。
【００６４】
以上説明した図１８の上下線構成処理（ステップＳ１５０）によれば、異なるネットワークレベル間で上り車線と下り車線との関係にある上下線分離道路であっても、上下線ペアデータ８３０を参照することによって、実際の上下線関係を道路地図に反映させることができる。
【００６５】
Ａ２−６．車線数算出処理：
図１９は、地図表示システム１０の地図サーバ５０が実行する車線数算出処理（ステップＳ１６０）を示すフローチャートである。本実施例では、地図サーバ５０は、道路の車線数を反映させた道路地図を作成するために道路の車線数を把握する必要がある場合に、図１９の車線数算出処理（ステップＳ１６０）を実行する。本実施例では、図１９の車線数算出処理（ステップＳ１６０）は、地図サーバ５０のＣＰＵ５１０がソフトウェアに基づいて動作することによって実現されるが、他の実施形態として、地図サーバ５０の電子回路がその物理的な回路構成に基づいて動作することによって実現されても良い。
【００６６】
地図サーバ５０は、図１９の車線数算出処理（ステップＳ１６０）を開始すると、道路の車線数を算出する対象区間を特定する（ステップＳ１６２）。その後、地図サーバ５０は、特定した算出対象区間に上下線ペアリンクとして関連付けられたリンクがあるか否かを、上下線ペアデータ８３０を参照することによって判断する（ステップＳ１６４）。上下線ペアリンクとして関連付けられたリンクがある場合（ステップＳ１６４：「ＹＥＳ」）、地図サーバ５０は、上下線ペアリンクとして関連付けられたリンク毎の車線数を合算した数を道路の総車線数として算出する（ステップＳ１６６）。一方、上下線ペアリンクとして関連付けられたリンクがある場合（ステップＳ１６４：「ＮＯ」）、地図サーバ５０は、算出対象区間にあるリンク毎の車線数を道路の総車線数として算出する（ステップＳ１６８）。
【００６７】
以上説明した図１９の車線数算出処理（ステップＳ１６０）によれば、上り車線と下り車線とで別々のリンクで規定された道路であっても、上下線ペアデータ８３０を参照することによって道路の総車線数を容易に算出することができる。
【００６８】
Ａ２−７．上位地図作成処理：
図２０は、地図表示システム１０の地図サーバ５０が実行する上位地図作成処理（ステップＳ１８０）を示すフローチャートである。本実施例では、地図サーバ５０は、地図データ８０に用意されていない縮尺による地図データが必要となった場合に、図２０の上位地図作成処理（ステップＳ１８０）を実行する。本実施例では、図２０の上位地図作成処理（ステップＳ１８０）は、地図サーバ５０のＣＰＵ５１０がソフトウェアに基づいて動作することによって実現されるが、他の実施形態として、地図サーバ５０の電子回路がその物理的な回路構成に基づいて動作することによって実現されても良い。
【００６９】
地図サーバ５０は、図２０の上位地図作成処理（ステップＳ１８０）を開始すると、記憶装置６０から地図データ８０を読み出す（ステップＳ１８２）。その後、地図サーバ５０は、読み出した地図データ８０における上下線ペアデータ８３０によって関連付けられたリンク同士を統合して新たな一つのリンクを構成する（ステップＳ１８４）。その後、地図サーバ５０は、統合した新たなリンクを用いて、読み出した地図データ８０よりも上位にあるネットワークレベルの地図データを作成する（ステップＳ１８６）。例えば、読み出した地図データ８０が、第二次メッシュ（約１００ｋｍ2）を基準に道路地図を表現した第二次ネットワークレベルの地図データである場合、図２０の上位地図作成処理（ステップＳ１８０）によって、第一次メッシュ（約６４００ｋｍ2）を基準に道路地図を表現した第一次ネットワークレベルの地図データを作成しても良い。
【００７０】
以上説明した図２０の上位地図作成処理（ステップＳ１８０）によれば、上下線ペアデータ８３０を参照することによって、他のネットワークレベルによる地図データ８０に基づいて、上位にあるネットワークレベルの地図データを容易に作成することができる。
【００７１】
Ａ３．効果
以上説明した地図表示システム１０によれば、同一の道路に含まれる上り車線と下り車線とをそれぞれ表現するリンク同士を上下線ペアデータ８３０によって特定することができるため、上り車線と下り車線とに分けて規定されたリンクを適切に取り扱うことができる。
【００７２】
Ｂ．その他の実施形態：
以上、本発明の実施の形態について説明したが、本発明はこうした実施の形態に何ら限定されるものではなく、本発明の趣旨を逸脱しない範囲内において様々な形態で実施し得ることは勿論である。例えば、本実施例では、地図表示システム１０の端末装置２０は、携帯電話機であるが、無線ローカルエリアネットワーク（Local Area Network, LAN）の端末装置であっても良いし、地図表示専用の携帯端末であっても良いし、車載のカーナビゲーション装置であっても良い。また、本実施例では、地図データ８０に基づくデータを地図サーバ５０が端末装置２０にネットワーク４０などを介して配信する構成としたが、他の実施形態において、端末装置２０に記憶装置６０を内蔵または外付けして、端末装置２０が地図データ８０を直接的に取り扱うとしても良い。
【図面の簡単な説明】
【００７３】
【図１】地図表示システムの構成を示す説明図である。
【図２】地図データによって規定されたノードおよびリンクを模式的に例示する説明図である。
【図３】地図データにおけるノードデータ８１０の詳細構成を示す説明図である。
【図４】地図データにおけるリンクデータ８２０の詳細構成を示す説明図である。
【図５】地図データにおける同一交差点データ８４０の詳細構成を示す説明図である。
【図６】同一交差点を模式的に例示する説明図である。
【図７】地図データにおける上下線ペアデータの詳細構成を示す説明図である。
【図８】第１形態における上下線ペアリンクを模式的に例示する説明図である。
【図９】第２形態における上下線ペアリンクを模式的に例示する説明図である。
【図１０】第３形態における上下線ペアリンクを模式的に例示する説明図である。
【図１１】地図表示システムの地図サーバが実行する交差点拡大処理を示すフローチャートである。
【図１２】地図表示システムの地図サーバが実行する探索済み道路の設定処理を示すフローチャートである。
【図１３】通過リンクを参照した経路探索の一例を示す説明図である。
【図１４】通過リンクを参照した経路探索の一例を示す説明図である。
【図１５】地図表示システムの地図サーバが実行する復路探索処理を示すフローチャートである。
【図１６】地図表示システムの地図サーバが実行する立寄経路探索処理を示すフローチャートである。
【図１７】立寄経路探索処理の一例を示す説明図である。
【図１８】地図表示システムの地図サーバが実行する上下線構成処理を示すフローチャートである。
【図１９】地図表示システムの地図サーバが実行する車線数算出処理を示すフローチャートである。
【図２０】地図表示システムの地図サーバが実行する上位地図作成処理を示すフローチャートである。
【符号の説明】
【００７４】
１０…地図表示システム
２０…端末装置
３０…基地局装置
４０…ネットワーク
５０…地図サーバ
６０…記憶装置
８０…地図データ
９０…測地衛星
２１０…ＣＰＵ
２２０…メモリ
２３０…ディスプレイ
２４０…入力ボタン
２５０…無線通信部
２６０…ＧＰＳ受信部
５１０…ＣＰＵ
５２０…メモリ
８１０…ノードデータ
８２０…リンクデータ
８３０…上下線ペアデータ
８４０…同一交差点データ
８１０２…ノード属性データ
８２０２…リンク属性データ
８３０２…上下線属性データ
８４０２…交差点属性データ
【技術分野】
【０００１】
本発明は、地図表示装置等で表示される地図上に道路を表現するために用いられる地図データのデータ構造に関する。
【背景技術】
【０００２】
地図上に道路を表現するための地図データは、コンピュータで利用可能に電子化され、車載用や携帯用のナビゲーション装置、ウェブサーバ、パーソナルコンピュータなどの装置で利用される。一般的な地図データは、道路上の基準点を示す複数のノードを規定したノードデータと、これら複数のノード間を接続する複数のリンクを規定したリンクデータとを備える。地図データを利用する装置は、地図データに規定されたノードおよびリンクを組み合わせて地図上に道路を表現することによって、道路地図の表示、現在地の表示、経路の探索、経路の案内などの処理を実行する。
【０００３】
地図データにおけるリンクは、一つの道路を一つのリンクで規定した上下線非分離リンクと、一つの道路に設けられた上り車線と下り車線とを別々のリンクで規定した上下線分離リンクとを含む。例えば、縮尺が比較的に小さい地図上に道路を表現するために用いられるリンクや、中央分離帯で車線が分離されていない道路を表現するために用いられるリンクは、上下線非分離リンクとして規定される場合が多い。また、例えば、縮尺が比較的に大きい地図上に上下線分離道路を表現するために用いられるリンクは、上下線分離リンクとして規定される場合が多い。
【０００４】
下記特許文献１には、同一の道路に含まれる上り車線と下り車線とをそれぞれ表現する上下線分離リンクを一つの道路として地図上に表現するために、並行する二つのリンクを、一つの道路に設けられた上り車線と下り車線とを別々のリンクで規定したものであると判断し、これら並行する二つのリンクを、一つの道路を表現するデータとして取り扱う技術が開示されている。
【０００５】
【特許文献１】特許第３２２８２４０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、特許文献１の技術では、並行する二つのリンクを、一つの道路を表現するデータとして画一的に取り扱うことから、実際に並行している二つの道路をそれぞれ規定した二つのリンクを、一つの道路を表現するデータとして誤った取り扱いをしてしまうという問題があった。
【０００７】
本発明は、上記した課題を踏まえ、上り車線と下り車線とに分けて規定されたリンクを適切に取り扱うことが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、上述の課題の少なくとも一部を解決するためになされたものであり、以下の実施の形態として実現することが可能である。
【０００９】
本発明における地図データのデータ構造は、地図上に道路を表現するための地図データのデータ構造であって、道路上の基準点を示す複数のノードを規定したノードデータと、前記ノードデータに規定された複数のノード間を接続する複数のリンクを規定したリンクデータと、前記リンクデータに規定された複数のリンクのうち、同一の道路に含まれる上り車線と下り車線とをそれぞれ表現するリンク同士を関連付けた上下線ペアデータとを備えることを特徴とする。本発明における地図データのデータ構造によれば、同一の道路に含まれる上り車線と下り車線とをそれぞれ表現するリンク同士を上下線ペアデータによって特定することができるため、上り車線と下り車線とに分けて規定されたリンクを適切に取り扱うことができる。
【００１０】
本発明の形態は、データ構造に限るものではなく、例えば、ナビゲーションシステム、ナビゲーション装置、ナビゲーション装置の制御方法、ナビゲーション装置を制御する機能をコンピュータに実現させるためのプログラムなどの他の形態に適用することもできる。また、本発明は、前述の形態に何ら限定されるものではなく、本発明の趣旨を逸脱しない範囲内において様々な形態で実施し得ることは勿論である。
【発明を実施するための最良の形態】
【００１１】
以上説明した本発明の構成および作用を一層明らかにするために、以下本発明を適用した地図表示システムについて説明する。
【００１２】
Ａ．地図表示システム１０の構成：
図１は、地図表示システム１０の構成を示す説明図である。地図表示システム１０は、端末装置２０と、地図サーバ５０と、記憶装置６０とを備える。地図表示システム１０は、記憶装置６０に記憶されている地図データ８０に基づくデータを地図サーバ５０から端末装置２０に配信することによって、端末装置２０において道路地図の表示、現在地の表示、経路の探索、経路の案内などを実行するナビゲーションシステムである。
【００１３】
地図表示システム１０の端末装置２０は、携帯用のナビゲーション装置であり、本実施例では、ナビゲーション装置としての機能を有する携帯電話機である。端末装置２０は、ＣＰＵ（Central Processing Unit）２１０と、メモリ２２０と、ディスプレイ２３０と、入力ボタン２４０と、無線通信部２５０と、ＧＰＳ受信部２６０とを備える。
【００１４】
端末装置２０のＣＰＵ２１０は、端末装置２０の各部を制御する。端末装置２０のメモリ２２０は、ＣＰＵ２１０の動作を規定したプログラムや、ＣＰＵ２１０によって取り扱われる種々のデータを記憶する。端末装置２０のディスプレイ２３０は、ＣＰＵ２１０の指示に基づいて道路地図を含む種々の画像を表示する。端末装置２０の入力ボタン２４０は、端末装置２０を操作するユーザからのデータの入力を受け付ける。
【００１５】
端末装置２０の無線通信部２５０は、地図サーバ５０とのデータのやり取りを無線通信で行う。本実施例では、端末装置２０の無線通信部２５０が携帯電話網の基地局装置３０と無線通信を行うことによって、端末装置２０は、地図サーバ５０に接続されたネットワーク４０に接続する。ネットワーク４０は、インターネット，ＷＡＮ(Wide Area Network)，ＬＡＮ(Local Area Network)，携帯電話網，固定電話網，光通信網などを含むとしても良い。
【００１６】
端末装置２０のＧＰＳ受信部２５０は、測地衛星９０から送信されるＧＰＳ（Global Positioning System）信号を受信する。ＧＰＳ受信部２５０によって受信されたＧＰＳ信号を解析することによって、端末装置２０の現在位置を検知することができる。
【００１７】
地図表示システム１０の地図サーバ５０は、ＣＰＵ５１０と、メモリ５２０とを備えるサーバコンピュータである。地図サーバ５０のＣＰＵ５１０は、地図サーバ５０の各部を制御する。地図サーバ５０のメモリ５２０は、ＣＰＵ５１０の動作を規定したプログラムや、ＣＰＵ５１０によって取り扱われる種々のデータを記憶する。地図サーバ５０は、ＣＰＵ５１０およびメモリ５２０の他、ネットワーク４０および記憶装置６０の各々とデータのやり取りを行うインタフェース（図示しない）を備える。地図サーバ５０の動作についての詳細は後述する。
【００１８】
地図表示システム１０の記憶装置６０は、地図データ８０を記憶可能な記憶容量を有する記憶装置である。本実施例では、記憶装置６０は、地図サーバ５０の外部記憶装置として構成されたハードディスクドライブ(Hard Disk Drive、以下、ＨＤＤという)であるが、他の実施形態において、記憶装置６０は、地図サーバ５０に内蔵されても良いし、半導体メモリやＤＶＤ(Digital Versatile Disk)，ＣＤ(Compact Disk)を用いた記憶装置であっても良い。
【００１９】
記憶装置６０に記憶されている地図データ８０は、ノードデータ８１０と、リンクデータ８２０と、上下線ペアデータ８３０と、同一交差点データ８４０とを備える。地図データ８０のノードデータ８１０は、道路上の基準点を示す複数のノードを規定する。地図データ８０のリンクデータ８２０は、ノードデータ８１０に規定された複数のノード間を接続する複数のリンクを規定する。地図データ８０の上下線ペアデータ８３０は、リンクデータ８２０に規定された複数のリンクのうち、同一の道路に含まれる上り車線と下り車線とをそれぞれ表現するリンク同士を関連付ける。地図データ８０の同一交差点データ８４０は、リンクデータ８２０で規定された複数のリンクのうち、同一の交差点を表現するリンク同士を関連付ける。地図データ８０が備えるノードデータ８１０，リンクデータ８２０，上下線ペアデータ８３０，同一交差点データ８４０の構成についての詳細は後述する。
【００２０】
図２は、地図データ８０によって規定されたノードおよびリンクを模式的に例示する説明図である。以下の説明では、図中のノードを個別に示す場合には、英文字「Ｎ」の後に数字を付した符号を用い（例えば、Ｎ１，Ｎ２，Ｎ３，…）、図中のリンクを個別に示す場合には、英文字「Ｌ」の後に数字を付した符号を用いる（例えば、Ｌ１，Ｌ２，Ｌ３，…）。図２には、地図データ８０のノードデータ８１０によって規定された９個のノードＮ１〜Ｎ９が図示されており、地図データ８０のリンクデータ８２０によって規定された１１個のリンクＬ１〜Ｌ１１が図示されている。ノードＮ１〜Ｎ９は、道路や車線における特徴的な基準点、例えば、交差点，分岐点，幅員が変化する点などを表現する。リンクＬ１〜Ｌ１１は、ノードＮ１〜Ｎ９の間を接続する道路や車線を表現する。
【００２１】
図３は、地図データ８０におけるノードデータ８１０の詳細構成を示す説明図である。ノードデータ８１０は、ノード毎の属性を示すノード属性データ８１０２を備える。ノード属性データ８１０２に示されるノードの属性は、ノード番号と、位置座標と、ノード種別と、接続リンク数と、接続リンク番号と、リンク間規制情報とを含む。
【００２２】
ノード属性データ８１０２のノード番号は、ノードを識別するための符号を示す。ノード属性データ８１０２の位置座標は、地図上におけるノードの位置を示す。ノード属性データ８１０２のノード種別は、ノードが表現する基準点の種別を示す。ノード属性データ８１０２の接続リンク数は、ノードに接続するリンクの数を示す。ノード属性データ８１０２の接続リンク番号は、ノードに接続するリンクを識別するための符号を示す。図３に示す例では、ノード番号「Ｎ２」が割り当てられたノードＮ２に関するノード属性データ８１０２には、ノードＮ２が座標［Ｘｎ２（経度），Ｙｎ２（緯度）］上に位置し、ノードＮ２が「交差点」を表現し、ノードＮ２に接続するリンクの数が「４」であり、これらのリンク番号が「Ｌ１，Ｌ２，Ｌ４，Ｌ９」であることが示されている。
【００２３】
図４は、地図データ８０におけるリンクデータ８２０の詳細構成を示す説明図である。リンクデータ８２０は、リンク毎の属性を示すリンク属性データ８２０２を備える。リンク属性データ８２０２に示されるリンクの属性は、リンク番号と、始点ノードと、終点ノードと、道路種別と、補間点座標とを含み、その他、リンク長，幅員区分，車線数なども含む。
【００２４】
リンク属性データ８２０２のリンク番号は、リンクを識別するための符号を示す。リンク属性データ８２０２の始点ノードは、リンクが始点として接続するノードを識別するための符号を示す。リンク属性データ８２０２の終点ノードは、リンクが終点として接続するノードを識別するための符号を示す。リンク属性データ８２０２の道路種別は、リンクが表現する道路や車線の種別を示す。リンク属性データ８２０２の補間点座標は、リンクが始点ノードから終点ノードまで延びる軌跡の形状を示す。リンク属性データ８２０２のリンク長は、始点ノードから終点ノードまでのリンクの長さを示す。リンク属性データ８２０２の幅員区分は、リンクが表現する道路や車線の幅員を示す。リンク属性データ８２０２の車線数は、リンクが表現する道路や車線に含まれる車線の数を示す。図４に示す例では、リンク番号「Ｌ２」が割り当てられたリンクＬ２に関するリンク属性データ８２０２には、リンクＬ２が「始点ノードＮ２」から「終点ノードＮ３」へと接続し、リンクＬ２が表現する道路が「一般国道」であることが示されている。
【００２５】
図５は、地図データ８０における同一交差点データ８４０の詳細構成を示す説明図である。同一交差点データ８４０は、交差点毎の属性を示す交差点属性データ８４０２を備える。交差点属性データ８４０２に示される交差点の属性は、交差点番号と、構成リンク数と、構成リンク番号を含む。
【００２６】
交差点属性データ８４０２の交差点番号は、交差点を識別するための符号を示す。交差点属性データ８４０２の構成リンク数は、交差点を構成するリンクの数を示す。交差点属性データ８４０２の構成リンク番号は、交差点を構成するリンクを識別するための符号を示す。図５に示す例では、交差点番号「Ｃ１」が割り当てられた交差点Ｃ１に関する交差点属性データ８４０２には、交差点Ｃ１を構成するリンク数が「６」であり、これらのリンク番号が「Ｌ１ａ〜Ｌ１ｆ」であることが示されている。
【００２７】
図６は、同一交差点を模式的に例示する説明図である。図６には、図５の交差点属性データ８４０２によって規定された交差点Ｃ１が示されている。交差点Ｃ１は、６個のリンクＬ１ａ〜Ｌ１ｆで構成されている。交差点Ｃ１を構成するリンクＬ１ａ〜Ｌ１ｆは、リンクデータ８２０に規定されている。
【００２８】
交差点Ｃ１のリンクＬ１ａは、上り車線を表現するリンクＬ１７とリンクＬ１８との間を接続する交差点内リンクである。リンクＬ１７によって表現される上り車線は、リンクＬ１６によって表現される下り車線に対向して延びる車線であり、これらの車線は同じ道路に含まれる。リンクＬ１８によって表現される上り車線は、リンクＬ１５によって表現される下り車線に対向して延びる車線であり、これらの車線は同じ道路に含まれる。交差点Ｃ１のリンクＬ１ｂは、下り車線を表現するリンクＬ１５とリンクＬ１６との間を接続する交差点内リンクである。
【００２９】
交差点Ｃ１のリンクＬ１ｃは、上り車線を表現するリンクＬ１１とリンクＬ１２との間を接続する交差点内リンクである。リンクＬ１１によって表現される上り車線は、リンクＬ１４によって表現される下り車線に対向して延びる車線であり、これらの車線は同じ道路に含まれる。リンクＬ１２によって表現される上り車線は、リンクＬ１３によって表現される下り車線に対向して延びる車線であり、これらの車線は同じ道路に含まれる。交差点Ｃ１のリンクＬ１ｄは、下り車線を表現するリンクＬ１３とリンクＬ１４との間を接続する交差点内リンクである。
【００３０】
交差点Ｃ１のリンクＬ１ｅおよびリンクＬ１ｆは、交差点内におけるＵターン禁止を表現するために設けられたＵターンダミーリンクである。図６に示す例では、「リンクＬ１ａ−リンクＬ１ｃ−リンクＬ１ｂ」を介したリンクＬ１７からリンクＬ１６へのＵターンを禁止するために、リンクＬ１ａからリンクＬ１ｃへの進入が禁止されている。このままでは、リンクＬ１７からリンクＬ１２への右折ができないため、リンクＬ１７からリンクＬ１２へと接続するＵターンダミーリンクとしてリンクＬ１ｅを設けると共に、リンクＬ１ｅからリンクＬ１ｂへの進入を禁止することによって、リンクＬ１ｅを介してリンクＬ１７からリンクＬ１２への右折が可能になっている。リンクＬ１ｅは、リンクＬ１５からリンクＬ１８へのＵターンを禁止するためにも利用されている。また、リンクＬ１ｆは、リンクＬ１ｅと同様に、リンクＬ１１からリンクＬ１４へのＵターンと、リンクＬ１３からリンクＬ１２へのＵターンとを禁止するために設けられている。
【００３１】
図７は、地図データ８０における上下線ペアデータ８３０の詳細構成を示す説明図である。上下線ペアデータ８３０は、上下線ペアリンク毎の属性を示す上下線属性データ８３０２を備える。上下線ペアリンクは、上り車線を表現するリンクと下り車線を表現するリンクとの組み合わせであり、２個以上のリンクで構成されるものである。上下線属性データ８３０２に示される上下線ペアリンクの属性は、上下線ペア番号と、上り構成リンク数と、上り構成リンク番号と、下り構成リンク数と、下り構成リンク番号とを含む。
【００３２】
上下線属性データ８３０２の上下線ペア番号は、上下線ペアリンクを識別するための符号を示す。上下線属性データ８３０２の上り構成リンク数は、上下線ペアリンクを構成するリンクのうち上り線を構成するリンクの数を示す。上下線属性データ８３０２の上り構成リンク番号は、上下線ペアリンクを構成するリンクのうち上り線を構成するリンクを識別するための符号を示す。上下線属性データ８３０２の下り構成リンク数は、上下線ペアリンクを構成するリンクのうち下り線を構成するリンクの数を示す。上下線属性データ８３０２の下り構成リンク番号は、上下線ペアリンクを構成するリンクのうち下り線を構成するリンクを識別するための符号を示す。図７に示す例では、上下線ペア番号「Ｐ２」が割り当てられた上下線ペアリンクＰ２に関する上下線属性データ８３０２には、上下線ペアリンクＰ２における上り線を構成するリンク数が「２」であり、これらの構成リンク番号が「Ｌ２３，Ｌ２４」であることが示されている。また、上下線ペアリンクＰ２における下り線を構成するリンク数が「１」であり、この構成リンク番号が「Ｌ２２」であることも示されている。
【００３３】
図８は、第１形態における上下線ペアリンクを模式的に例示する説明図である。図８には、同一交差点Ｃ２１と同一交差点Ｃ２２との間に挟まれた上下線ペアリンクＰ２が示されている。上下線ペアリンクＰ２は、３個のリンクＬ２２，Ｌ２３，Ｌ２４で構成されており、これら３個のリンクＬ２２，Ｌ２３，Ｌ２４は、リンクデータ８２０に規定されている。上下線ペアリンクＰ２における下り線Ｄ２のリンクＬ２２は、同一交差点Ｃ２２から延びて同一交差点Ｃ２１に接続する。上り線Ｕ２のリンクＬ２３は、同一交差点Ｃ２１から延びてリンクＬ２４に接続し、上り線Ｕ２のリンクＬ２４は、リンクＬ２３から延びて同一交差点Ｃ２２に接続する。すなわち、リンクＬ２２は、リンクＬ２３，Ｌ２４に対向する方向に延びた車線である。同一交差点Ｃ２１，Ｃ２２は、同一交差点データ８４０によって規定されている。同一交差点Ｃ２１は、図６で示した同一交差点Ｃ１と同様に６個のリンクで構成されている。同一交差点Ｃ２２は、リンクＬ２４の一端とリンクＬ２２の一端とを接続する１個のリンクで構成されている。
【００３４】
図９は、第２形態における上下線ペアリンクを模式的に例示する説明図である。図９には、同一交差点Ｃ３１とノードＮ３１との間に挟まれた上下線ペアリンクＰ３が示されている。上下線ペアリンクＰ３は、３個のリンクＬ３２，Ｌ３３，Ｌ３４で構成されており、これら３個のリンクＬ３２，Ｌ３３，Ｌ３４は、リンクデータ８２０に規定されている。上下線ペアリンクＰ３における下り線Ｄ３のリンクＬ３２は、ノードＮ３１から延びて同一交差点Ｃ３１に接続する。上り線Ｕ３のリンクＬ３３は、同一交差点Ｃ３１から延びてリンクＬ３４に接続し、上り線Ｕ３のリンクＬ３４は、リンクＬ３３から延びてノードＮ３１に接続する。すなわち、リンクＬ３２は、リンクＬ３３，Ｌ３４に対向する方向に延びた車線である。同一交差点Ｃ３１は、同一交差点データ８４０によって規定されており、図６で示した同一交差点Ｃ１と同様に６個のリンクで構成されている。ノードＮ３１は、ノードデータ８１０に規定されており、上下線が分離されていない道路を表現するリンクＬ３５との接続地点である二条化開始終了点を表現する。
【００３５】
図１０は、第３形態における上下線ペアリンクを模式的に例示する説明図である。図１０には、同一交差点Ｃ４１とノードＮ４１，Ｎ４２との間に挟まれた上下線ペアリンクＰ４が示されている。上下線ペアリンクＰ４は、３個のリンクＬ４２，Ｌ４３，Ｌ４４で構成されており、これら３個のリンクＬ４２，Ｌ４３，Ｌ４４は、リンクデータ８２０に規定されている。上下線ペアリンクＰ４における下り線Ｄ４のリンクＬ４２は、ノードＮ４２から延びて同一交差点Ｃ４１に接続する。上り線Ｕ４のリンクＬ４３は、同一交差点Ｃ４１から延びてリンクＬ４４に接続し、上り線Ｕ４のリンクＬ４４は、リンクＬ４３から延びてノードＮ４１に接続する。すなわち、リンクＬ４２は、リンクＬ４３，Ｌ４４に対向する方向に延びた車線である。同一交差点Ｃ４１は、同一交差点データ８４０によって規定されており、図６で示した同一交差点Ｃ１と同様に６個のリンクで構成されている。ノードＮ４１，Ｎ４２は、ノードデータ８１０に規定されており、地図を区画するメッシュＭ４１の境界線上の基準点を表現する。
【００３６】
Ａ２．地図表示システム１０の動作：
Ａ２−１．交差点拡大処理：
図１１は、地図表示システム１０の地図サーバ５０が実行する交差点拡大処理（ステップＳ１１０）を示すフローチャートである。本実施例では、地図サーバ５０は、交差点を拡大表示した画像を端末装置２０から要求された場合に、図１１の交差点拡大処理（ステップＳ１１０）を実行する。本実施例では、図１１の交差点拡大処理（ステップＳ１１０）は、地図サーバ５０のＣＰＵ５１０がソフトウェアに基づいて動作することによって実現されるが、他の実施形態として、地図サーバ５０の電子回路がその物理的な回路構成に基づいて動作することによって実現されても良い。
【００３７】
地図サーバ５０は、図１１の交差点拡大処理（ステップＳ１１０）を開始すると、交差点を拡大表示した画像を要求するコマンドを端末装置２０から受信する（ステップＳ１１２）。その後、地図サーバ５０は、拡大表示される交差点に接続するリンクに、上下線ペアデータ８３０によって上下線ペアリンクとして規定されたリンクが含まれるか否かを判断する（ステップＳ１１４）。
【００３８】
拡大対象に上下線ペアリンクが含まれる場合（ステップＳ１１４：「ＹＥＳ」）、地図サーバ５０は、上下線ペアリンクとして規定されたリンクを一つの道路とし、同一交差点を一つの点に縮退した形式で、交差点拡大画像を描画する（ステップＳ１１５）。一方、拡大対象に上下線ペアリンクが含まれない場合（ステップＳ１１４：ＮＯ」）、地図サーバ５０は、リンクの各々を一つの道路として交差点拡大画像を描画する（ステップＳ１１６）。
【００３９】
交差点拡大画像が描画された後（ステップＳ１１５，Ｓ１１６）、地図サーバ５０は、交差点拡大画像を端末装置２０に配信する（ステップＳ１１７）。端末装置２０は、地図サーバ５０から交差点拡大画像を受信すると、その交差点拡大画像をディスプレイ２３０に表示する。
【００４０】
以上説明した図１１の交差点拡大処理（ステップＳ１１０）によれば、表示対象であるリンクが上下線分離道路か否かを、上下線ペアデータ８３０を参照することによって判断することができるため、上り車線と下り車線とが別々のリンクで規定されている場合であっても、一つの道路として実際の道路形状に即した道路地図を表示することができる。
【００４１】
Ａ２−２．探索済み道路の設定処理：
図１２は、地図表示システム１０の地図サーバ５０が実行する探索済み道路の設定処理（ステップＳ１２０）を示すフローチャートである。本実施例では、地図サーバ５０は、経路探索中にリンクが経路として選定された場合に、図１２の探索済み道路の設定処理（ステップＳ１２０）を実行する。本実施例では、図１２の探索済み道路の設定処理（ステップＳ１２０）は、地図サーバ５０のＣＰＵ５１０がソフトウェアに基づいて動作することによって実現されるが、他の実施形態として、地図サーバ５０の電子回路がその物理的な回路構成に基づいて動作することによって実現されても良い。
【００４２】
地図サーバ５０は、図１２の探索済み道路の設定処理（ステップＳ１２０）を開始すると、経路探索中に経路として選定した選定リンクを特定する（ステップＳ１２２）。その後、地図サーバ５０は、特定された選定リンクに、上下線ペアデータ８３０によって上下線ペアリンクとして規定されたリンクが含まれるか否かを判断する（ステップＳ１２４）。
【００４３】
選定リンクに上下線ペアリンクが含まれる場合（ステップＳ１２４：「ＹＥＳ」）、地図サーバ５０は、選定リンクと共に、その選定リンクと上下線ペアリンクの関係にあるリンクの双方を、探索経路で通過済みの通過リンクとして設定する（ステップＳ１２５）。一方、選定リンクに上下線ペアリンクが含まれない場合（ステップＳ１２４：「ＮＯ」）、地図サーバ５０は、探索経路で通過済みの通過リンクとして選定リンクを設定する（ステップＳ１２６）。
【００４４】
通過リンクが設定された後（ステップＳ１２５，Ｓ１２６）、地図サーバ５０は、経路探索を再開する。再開された経路探索において、地図サーバ５０は、図１２の探索済み道路の設定処理（ステップＳ１２０）で設定された通過リンクを参照しながら経路探索を実行する。
【００４５】
図１３は、通過リンクを参照した経路探索の一例を示す説明図である。図１３の例では、道路上におけるＧＰＳや無線通信システムの電波強度を調査する路上調査車両の調査経路を探索する様子が示されている。路上調査車両の経路探索では、重複経路を避けて出来るだけ多くの道路を経由することが求められる。上下線分離道路に含まれる一方の車線を通過した後、その上下線分離道路に含まれる他方の車線を通過すると、同じ道路を重複して通過することになるため、路上調査車両の経路探索では、上下線分離道路に含まれる上り車線および下り車線の双方を経由する重複経路を回避する必要がある。
【００４６】
図１３の例では、上下線ペアリンクＰ５１に含まれるリンクＬ５１が経路として選定されると、リンクＬ５１と上下線ペアリンクの関係にあるリンクＬ５２がリンクＬ５１と共に通過リンクとして設定される（図１２のステップＳ１２５）。その後の経路探索において、リンクＬ５１，Ｌ５２は、通過リンクとして取り扱われ、経路として選定される優先度が低くなる。また、上下線ペアリンクＰ５５に含まれるリンクＬ５６が経路として選定されると、リンクＬ５６と上下線ペアリンクの関係にあるリンクＬ５５がリンクＬ５６と共に通過リンクとして設定される（図１２のステップＳ１２５）。その後の経路探索において、リンクＬ５５，Ｌ５６は、通過リンクとして取り扱われ、経路として選定される優先度が低くなる。
【００４７】
図１４は、通過リンクを参照した経路探索の一例を示す説明図である。図１４の例では、複数の階層に分けて経路探索を実施する階層的経路探索を行う様子が示されている。階層的経路探索では、例えば、第１階層では一般道を含む全ての道路で構成された道路網で経路探索が実行される。第２階層では高速道路、有料道路、国道および県道で構成された道路網が経路探索される。第３階層では高速道および有料道路で構成された道路網で経路探索が実行される。図１４では、リンクＬ６１，Ｌ６２，Ｌ６３は、第１階層の道路網に含まれており、その他のリンクＬ６５，Ｌ６６，Ｌ６７，Ｌ６８などは、第２階層の道路網に含まれる。第２階層のリンクＬ６５，Ｌ６７は、上下線ペアリンクＰ６１として上下線ペアデータ８３０に規定されている。
【００４８】
図１４における地点Ａから地点Ｂまでの経路探索について説明する。従来例では、まず経路探索が開始されると、地点Ａに隣接する第１階層のリンクＬ６１が経路として選定される。その後、第１階層での経路探索にて、第１階層のリンクＬ６１から第２階層のリンクＬ６５への経路が選定されたとする。第１階層の経路探索で所定の回数だけ探索枝を延伸しても目的地点Ｂに到達しなかった場合、探索枝が到達し得た範囲内にある第２階層のノード（例えば、Ｎ６１）から階層遷移し、第２階層での経路探索が実行される。したがって、経路探索結果は、重複経路であるリンクＬ６５，Ｌ６７を含む、リンクＬ６１，Ｌ６５、Ｌ６６、Ｌ６７，Ｌ６８の順となる。
【００４９】
その一方で、本実施例では、第２階層のリンクＬ６５が経路として選定されると、リンクＬ６５と上下線ペアリンクの関係にあるリンクＬ６７がリンクＬ６５と共に通過リンクとして設定される（図１２のステップＳ１２５）。そのため、第１階層の経路探索にてリンクＬ６５が選定された後、第２階層の経路探索にてリンクＬ６７が選定された場合であっても、リンクＬ６５とリンクＬ６７とが重複経路の関係になることを判断することができる。したがって、重複経路を避けて経路を再探索することができる。つまり、経路探索結果は、重複経路であるリンクＬ６５，Ｌ６７が含まれない、リンクＬ６１，Ｌ６２，Ｌ６８の順となる。
【００５０】
以上説明した図１２の探索済み道路の設定処理（ステップＳ１２０）によれば、経路探索で選定されたリンクが上下線分離道路か否かを、上下線ペアデータ８３０を参照することによって判断することができるため、上り車線と下り車線とが別々のリンクで規定されている場合であっても、通過済みの道路であるか否かを判断することができる。
【００５１】
Ａ２−３．復路探索処理：
図１５は、地図表示システム１０の地図サーバ５０が実行する復路探索処理（ステップＳ１３０）を示すフローチャートである。本実施例では、地図サーバ５０は、復路の探索を端末装置２０から要求された場合に、図１５の復路探索処理（ステップＳ１３０）を実行する。本実施例では、図１５の復路探索処理（ステップＳ１３０）は、地図サーバ５０のＣＰＵ５１０がソフトウェアに基づいて動作することによって実現されるが、他の実施形態として、地図サーバ５０の電子回路がその物理的な回路構成に基づいて動作することによって実現されても良い。
【００５２】
地図サーバ５０は、図１５の復路探索処理（ステップＳ１３０）を開始すると、往路に含まれるリンクを特定する（ステップＳ１３２）。その後、地図サーバ５０は、往路と同じ経路で復路を作成するコマンドが選択されたか否かを判断する（ステップＳ１３４）。
【００５３】
往路と同じ経路で復路を作成する場合（ステップＳ１３４：「ＹＥＳ」）、地図サーバ５０は、往路と同じリンクおよび、往路に含まれるリンクと上下線ペアデータ８３０によって関連付けられたリンクを用いて、復路を探索する（ステップＳ１３５）。一方、往路と異なる経路で復路を作成する場合（ステップＳ１３４：「ＮＯ」）、地図サーバ５０は、往路と同じリンクおよび、往路に含まれるリンクと上下線ペアデータ８３０によって関連付けられたリンクを除いて、復路を探索する（ステップＳ１３６）。
【００５４】
以上説明した図１５の復路探索処理（ステップＳ１３０）によれば、往路に含まれる上下線分離道路を、上下線ペアデータ８３０を参照することによって容易に判断することができるため、往路と同じ経路の復路や、往路と異なる経路の復路を探索する速度を向上させることができる。
【００５５】
Ａ２−４．立寄経路探索処理：
図１６は、地図表示システム１０の地図サーバ５０が実行する立寄経路探索処理（ステップＳ１４０）を示すフローチャートである。本実施例では、地図サーバ５０は、立寄地点への経路探索を端末装置２０から要求された場合に、図１６の立寄経路探索処理（ステップＳ１４０）を実行する。本実施例では、図１６の立寄経路探索処理（ステップＳ１４０）は、地図サーバ５０のＣＰＵ５１０がソフトウェアに基づいて動作することによって実現されるが、他の実施形態として、地図サーバ５０の電子回路がその物理的な回路構成に基づいて動作することによって実現されても良い。
【００５６】
地図サーバ５０は、図１６の立寄経路探索処理（ステップＳ１４０）を開始すると、立寄地点に近隣するリンクである近隣リンクを特定する（ステップＳ１４２）。その後、地図サーバ５０は、上下線ペアデータ８３０によって近隣リンクに上下線ペアリンクとして関連付けられたリンクがあるか否かを判断する（ステップＳ１４４）。近隣リンクに上下線ペアリンクとして関連付けられたリンクがない場合（ステップＳ１４４：「ＮＯ」）、地図サーバ５０は、近隣リンクへの経路を探索する（ステップＳ１４７）。
【００５７】
一方、近隣リンクに上下線ペアリンクとして関連付けられたリンクがある場合（ステップＳ１４４：「ＹＥＳ」）、地図サーバ５０は、近隣リンクへの経路と、その近隣リンクに上下線ペアリンクとして関連付けられたリンクへの経路とを探索する（ステップＳ１４５）。その後、地図サーバ５０は、検索された双方のリンクからコストの低い経路を選定する（ステップＳ１４６）。なお、経路のコストとは、走行距離、走行時間、通行費用、渋滞状況など経路を走行するのに掛かる種々の負荷を数値化したものである。
【００５８】
図１７は、出発地Ｓから目的地Ｇまでの間に立寄地点Ｃを有する立寄経路探索処理（ステップＳ１４０）の一例を示す説明図である。図１７には、リンクＬ７１からリンクＬ７２を経てリンクＬ７３へと延びるリンク列と、このリンク列とは逆方向にリンクＬ７５からリンクＬ７４へと延びるリンク列とが示されている。従来例では、リンクＬ７１〜Ｌ７３とリンクＬ７４，Ｌ７５とで構成される道路は上下線ペアリンクとして関連付けられていない。また、リンクＬ７２は立寄地点Ｃに近隣することから、立寄経路探索処理（ステップＳ１４０）では、リンクＬ７２のみが近隣リンクとして特定される（図１６のステップＳ１４２）。そのため、出発地Ｓから立寄地点Ｃを経由して目的地Ｇまで走行する経路を探索する場合、経路探索結果は、リンクＬ７７，Ｌ７５，Ｌ７４、Ｌ７８，Ｌ７１，Ｌ７２，Ｌ７３，Ｌ７６，Ｌ７５、Ｌ７４，Ｌ７９の順となる。
【００５９】
一方、本実施例では、リンクＬ７１〜Ｌ７５は、上下線ペアデータ８３０によって上下線ペアリンクＰ７として関連付けられている。すなわち、立寄地点Ｃに近隣するリンクＬ７２は、上下線ペアリンクＰ７としてリンクＬ７４，Ｌ７５にも関連付けられていることから、図１７の状況では、立寄地点Ｃの隣接するリンクとしてリンクＬ７４，Ｌ７５も特定されることになる。したがって、リンクＬ７２，Ｌ７４，Ｌ７５の各々への経路探索が実行される（図１６のステップＳ１４５）。その後、リンクＬ７２，Ｌ７４，Ｌ７５の各々への経路のうち、コストの低い経路が選定される（図１２のステップＳ１４６）。つまり、経路探索結果は、リンクＬ７７，Ｌ７５，Ｌ７４、Ｌ７９の順となる。
【００６０】
以上説明した図１６の立寄経路探索処理（ステップＳ１４０）によれば、近隣リンクに上下線ペアリンクとして関連付けられたリンクを、上下線ペアデータ８３０を参照することによって容易に特定することができるため、立寄地点への経路を探索する速度を向上させることができる。
【００６１】
Ａ２−５．上下線構成処理：
図１８は、地図表示システム１０の地図サーバ５０が実行する上下線構成処理（ステップＳ１５０）を示すフローチャートである。本実施例では、地図サーバ５０は、道路地図を作成する際に、図１８の上下線構成処理（ステップＳ１５０）を実行する。本実施例では、図１８の上下線構成処理（ステップＳ１５０）は、地図サーバ５０のＣＰＵ５１０がソフトウェアに基づいて動作することによって実現されるが、他の実施形態として、地図サーバ５０の電子回路がその物理的な回路構成に基づいて動作することによって実現されても良い。
【００６２】
地図サーバ５０は、図１８の上下線構成処理（ステップＳ１５０）を開始すると、道路地図画像として表示する範囲内にあるリンクを特定する（ステップＳ１５２）。その後、地図サーバ５０は、上下線ペアデータ８３０を参照することによって、表示範囲内のリンクと上下線ペアリンクとして関連付けられたリンクが他のネットワークレベルにあるか否かを判断する（ステップＳ１５４）。本実施例では、地図データ８０は、第一次メッシュ（約６４００ｋｍ2）を基準に道路地図を表現した第一次ネットワークレベルと、第二次メッシュ（約１００ｋｍ2）を基準に道路地図を表現した第二次ネットワークレベルと、第三次メッシュ（約１ｋｍ2）を基準に道路地図を表現した第三次ネットワークレベルとを含む。例えば、第二次ネットワークレベルで道路地図画像を生成する場合、地図サーバ５０は、第一次ネットワークレベルに、表示範囲内のリンクと上下線ペアリンクとして関連付けられたリンクが存在するか否かを、上下線ペアデータ８３０を参照することによって判断する（ステップＳ１５４）。
【００６３】
表示範囲内のリンクと上下線ペアリンクとして関連付けられたリンクが他のネットワークレベルにある場合（ステップＳ１５４：「ＹＥＳ」）、地図サーバ５０は、他のネットワークレベルにおける上下線ペアリンクを道路地図画像として表示するリンクに追加する（ステップＳ１５６）。その後、地図サーバ５０は、表示範囲内のリンクと、他のネットワークレベルから追加されたリンクとを用いて、道路地図を作成する（ステップＳ１５７）。
【００６４】
以上説明した図１８の上下線構成処理（ステップＳ１５０）によれば、異なるネットワークレベル間で上り車線と下り車線との関係にある上下線分離道路であっても、上下線ペアデータ８３０を参照することによって、実際の上下線関係を道路地図に反映させることができる。
【００６５】
Ａ２−６．車線数算出処理：
図１９は、地図表示システム１０の地図サーバ５０が実行する車線数算出処理（ステップＳ１６０）を示すフローチャートである。本実施例では、地図サーバ５０は、道路の車線数を反映させた道路地図を作成するために道路の車線数を把握する必要がある場合に、図１９の車線数算出処理（ステップＳ１６０）を実行する。本実施例では、図１９の車線数算出処理（ステップＳ１６０）は、地図サーバ５０のＣＰＵ５１０がソフトウェアに基づいて動作することによって実現されるが、他の実施形態として、地図サーバ５０の電子回路がその物理的な回路構成に基づいて動作することによって実現されても良い。
【００６６】
地図サーバ５０は、図１９の車線数算出処理（ステップＳ１６０）を開始すると、道路の車線数を算出する対象区間を特定する（ステップＳ１６２）。その後、地図サーバ５０は、特定した算出対象区間に上下線ペアリンクとして関連付けられたリンクがあるか否かを、上下線ペアデータ８３０を参照することによって判断する（ステップＳ１６４）。上下線ペアリンクとして関連付けられたリンクがある場合（ステップＳ１６４：「ＹＥＳ」）、地図サーバ５０は、上下線ペアリンクとして関連付けられたリンク毎の車線数を合算した数を道路の総車線数として算出する（ステップＳ１６６）。一方、上下線ペアリンクとして関連付けられたリンクがある場合（ステップＳ１６４：「ＮＯ」）、地図サーバ５０は、算出対象区間にあるリンク毎の車線数を道路の総車線数として算出する（ステップＳ１６８）。
【００６７】
以上説明した図１９の車線数算出処理（ステップＳ１６０）によれば、上り車線と下り車線とで別々のリンクで規定された道路であっても、上下線ペアデータ８３０を参照することによって道路の総車線数を容易に算出することができる。
【００６８】
Ａ２−７．上位地図作成処理：
図２０は、地図表示システム１０の地図サーバ５０が実行する上位地図作成処理（ステップＳ１８０）を示すフローチャートである。本実施例では、地図サーバ５０は、地図データ８０に用意されていない縮尺による地図データが必要となった場合に、図２０の上位地図作成処理（ステップＳ１８０）を実行する。本実施例では、図２０の上位地図作成処理（ステップＳ１８０）は、地図サーバ５０のＣＰＵ５１０がソフトウェアに基づいて動作することによって実現されるが、他の実施形態として、地図サーバ５０の電子回路がその物理的な回路構成に基づいて動作することによって実現されても良い。
【００６９】
地図サーバ５０は、図２０の上位地図作成処理（ステップＳ１８０）を開始すると、記憶装置６０から地図データ８０を読み出す（ステップＳ１８２）。その後、地図サーバ５０は、読み出した地図データ８０における上下線ペアデータ８３０によって関連付けられたリンク同士を統合して新たな一つのリンクを構成する（ステップＳ１８４）。その後、地図サーバ５０は、統合した新たなリンクを用いて、読み出した地図データ８０よりも上位にあるネットワークレベルの地図データを作成する（ステップＳ１８６）。例えば、読み出した地図データ８０が、第二次メッシュ（約１００ｋｍ2）を基準に道路地図を表現した第二次ネットワークレベルの地図データである場合、図２０の上位地図作成処理（ステップＳ１８０）によって、第一次メッシュ（約６４００ｋｍ2）を基準に道路地図を表現した第一次ネットワークレベルの地図データを作成しても良い。
【００７０】
以上説明した図２０の上位地図作成処理（ステップＳ１８０）によれば、上下線ペアデータ８３０を参照することによって、他のネットワークレベルによる地図データ８０に基づいて、上位にあるネットワークレベルの地図データを容易に作成することができる。
【００７１】
Ａ３．効果
以上説明した地図表示システム１０によれば、同一の道路に含まれる上り車線と下り車線とをそれぞれ表現するリンク同士を上下線ペアデータ８３０によって特定することができるため、上り車線と下り車線とに分けて規定されたリンクを適切に取り扱うことができる。
【００７２】
Ｂ．その他の実施形態：
以上、本発明の実施の形態について説明したが、本発明はこうした実施の形態に何ら限定されるものではなく、本発明の趣旨を逸脱しない範囲内において様々な形態で実施し得ることは勿論である。例えば、本実施例では、地図表示システム１０の端末装置２０は、携帯電話機であるが、無線ローカルエリアネットワーク（Local Area Network, LAN）の端末装置であっても良いし、地図表示専用の携帯端末であっても良いし、車載のカーナビゲーション装置であっても良い。また、本実施例では、地図データ８０に基づくデータを地図サーバ５０が端末装置２０にネットワーク４０などを介して配信する構成としたが、他の実施形態において、端末装置２０に記憶装置６０を内蔵または外付けして、端末装置２０が地図データ８０を直接的に取り扱うとしても良い。
【図面の簡単な説明】
【００７３】
【図１】地図表示システムの構成を示す説明図である。
【図２】地図データによって規定されたノードおよびリンクを模式的に例示する説明図である。
【図３】地図データにおけるノードデータ８１０の詳細構成を示す説明図である。
【図４】地図データにおけるリンクデータ８２０の詳細構成を示す説明図である。
【図５】地図データにおける同一交差点データ８４０の詳細構成を示す説明図である。
【図６】同一交差点を模式的に例示する説明図である。
【図７】地図データにおける上下線ペアデータの詳細構成を示す説明図である。
【図８】第１形態における上下線ペアリンクを模式的に例示する説明図である。
【図９】第２形態における上下線ペアリンクを模式的に例示する説明図である。
【図１０】第３形態における上下線ペアリンクを模式的に例示する説明図である。
【図１１】地図表示システムの地図サーバが実行する交差点拡大処理を示すフローチャートである。
【図１２】地図表示システムの地図サーバが実行する探索済み道路の設定処理を示すフローチャートである。
【図１３】通過リンクを参照した経路探索の一例を示す説明図である。
【図１４】通過リンクを参照した経路探索の一例を示す説明図である。
【図１５】地図表示システムの地図サーバが実行する復路探索処理を示すフローチャートである。
【図１６】地図表示システムの地図サーバが実行する立寄経路探索処理を示すフローチャートである。
【図１７】立寄経路探索処理の一例を示す説明図である。
【図１８】地図表示システムの地図サーバが実行する上下線構成処理を示すフローチャートである。
【図１９】地図表示システムの地図サーバが実行する車線数算出処理を示すフローチャートである。
【図２０】地図表示システムの地図サーバが実行する上位地図作成処理を示すフローチャートである。
【符号の説明】
【００７４】
１０…地図表示システム
２０…端末装置
３０…基地局装置
４０…ネットワーク
５０…地図サーバ
６０…記憶装置
８０…地図データ
９０…測地衛星
２１０…ＣＰＵ
２２０…メモリ
２３０…ディスプレイ
２４０…入力ボタン
２５０…無線通信部
２６０…ＧＰＳ受信部
５１０…ＣＰＵ
５２０…メモリ
８１０…ノードデータ
８２０…リンクデータ
８３０…上下線ペアデータ
８４０…同一交差点データ
８１０２…ノード属性データ
８２０２…リンク属性データ
８３０２…上下線属性データ
８４０２…交差点属性データ
【特許請求の範囲】
【請求項１】
地図上に道路を表現するための地図データのデータ構造であって、
道路上の基準点を示す複数のノードを規定したノードデータと、
前記ノードデータに規定された複数のノード間を接続する複数のリンクを規定したリンクデータと、
前記リンクデータに規定された複数のリンクのうち、同一の道路に含まれる上り車線と下り車線とをそれぞれ表現するリンク同士を関連付けた上下線ペアデータと
を備える地図データのデータ構造。
【請求項１】
地図上に道路を表現するための地図データのデータ構造であって、
道路上の基準点を示す複数のノードを規定したノードデータと、
前記ノードデータに規定された複数のノード間を接続する複数のリンクを規定したリンクデータと、
前記リンクデータに規定された複数のリンクのうち、同一の道路に含まれる上り車線と下り車線とをそれぞれ表現するリンク同士を関連付けた上下線ペアデータと
を備える地図データのデータ構造。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【公開番号】特開２０１０−５４７５４（Ｐ２０１０−５４７５４Ａ）
【公開日】平成２２年３月１１日（２０１０．３．１１）
【国際特許分類】
【出願番号】特願２００８−２１９０４０（Ｐ２００８−２１９０４０）
【出願日】平成２０年８月２８日（２００８．８．２８）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
【公開日】平成２２年３月１１日（２０１０．３．１１）
【国際特許分類】
【出願日】平成２０年８月２８日（２００８．８．２８）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
[ Back to top ]