JP2011227053A - 経路探索システム - Google Patents

Abstract

【課題】 ネットワークデータから離れた出発地、経由地および目的地に対して、適切な経路探索を実現する。
【解決手段】 ナビゲーション装置は、道路をリンク、ノードで表したネットワークデータを用いて経路探索を行う。目的地として指定した地物Ｈ２がネットワークのリンクＬ２から離れた地点である場合は、その地物からいずれかの道路をたどってネットワーク上にたどり着いた点を到着地点ＧＨとし、到着地点ＧＨを終点とする経路探索を行う。到着地点は、道路を描画するためのポリゴンデータを用いて探索することができる。到着地点が複数存在する場合には、出発点から到着地点までのコスト、および到着地点から目的地までのコスト等に基づいて、最適な到着地点を選択する。
このように到着地点を終点として経路探索することにより、無用な大回りなどをしなくてもよい適切な経路を探索することができる。
【選択図】 図３

Description

本発明は、指定された目的地に向かう経路を探索する経路探索システムに関する。

道路をリンク、およびノードで表したネットワークデータを用いて、指定された出発地から目的地までの経路を探索し、案内するナビゲーションシステムが普及している。ネットワークデータは、全ての道路に対して整備されている訳ではないため、経路探索の際には、ネットワーク上のリンク、ノードから離れた地点が目的地として指定されることもある。

特許文献１は、リンク、ノードから離れた地点が目的地として指定された場合、２種類のネットワークデータを利用して経路探索を行う技術を開示する。まず、目的地から最寄りのノードを求め、このノードを終点とする経路探索を行う。そして、終点から目的地までは、別途得られる補完データを用いて経路探索を行うのである。

特許文献２は、ネットワークデータから外れた領域を特定エリアと称し、ネットワークデータが整備された主要道路からその特定エリアに至る接続道路を求め、主要道路と接続道路との交点を案内ポイントとして経路探索する技術を開示する。

特開２００６−８４２５６号公報 特許第３３８５９７５号公報

従来技術では、リンクから離れた目的地が指定された場合に、必ずしも適切な経路が得られないという課題があった。
図１は、従来技術における経路探索例を示す説明図である。
図中の領域では、道路ＲＷ１〜ＲＷ４に対しては、リンクＬＷ１〜ＬＷ４、ノードＮ１２、Ｎ２３、Ｎ３４、Ｎ４１からなるネットワークデータが整備されており、道路ＲＮにはネットワークデータが整備されていない。領域内には建物ＨＡ〜ＨＪが存在する。
経路探索の目的地として、建物ＨＢ内の点ＤＥ１が指定された場合を考える。点ＤＥ１は、ネットワークから外れた地点である。

特許文献１記載の技術によれば、指定された点ＤＥ１の最寄りのノードＮ２３を終点とする経路探索が行われる。しかし、地点ＤＥ１に向かうには、道路ＲＮを使う必要があるから、ノードＮ１２またはＮ４１を終点とする経路探索が行われるべきである。ノードＮ２３を終点とする経路探索では、ノードＮ１２、Ｎ４１を通過してノードＮ２３に向かう経路が得られるおそれがあり、不適切な経路となってしまうおそれがある。

特許文献２記載の技術によれば、例えば、図中の破線で示すように特定エリアＳＡを設け、特定エリアＳＡに対する案内ポイントＣＰを終点とする経路探索を行うことになる。しかし、この技術では、例えば、道路ＲＷ４から矢印ＡＨＣに示すように入るよう建てられている建物ＨＣが目的地として指定された場合も、案内ポイントＣＰに対する経路探索が行われてしまうことになり、必ずしも適切な経路が得られるとは言えない。

本発明は、これらの課題に鑑み、ネットワークから外れた地点が目的地に指定された場合でも、目的地の周囲の道路状況や、目的地として指定された建物等の構造を考慮した経路探索を行うことを目的とする。

本発明は、指定された目的地までの経路を探索する経路探索システムとして構成することができる。経路探索システムは、地図データベース記憶部、入力部、到着地点取得部、および経路探索部を備える。
地図データベース記憶部は、道路をノード、リンクで表したネットワークデータと、道路および建物を含む地物を描画するポリゴンを記憶する地物データとを格納する。ネットワークデータは、通行規制も踏まえて自動車の経路探索に使用可能な主ネットワークと、経路探索に使用可能ではあるが通行規制の整備が完全とは言えない準ネットワークなどを混在して用意してもよい。
地図データベース記憶部は、また到着地点に関するデータも記憶している。このデータは、地物データの一部として記憶させてもよいし、地物データと関連づけられた個別のデータとして用意してもよい。到着地点とは、上述の主ネットワーク、つまり自動車が通行可能な道路としてネットワークデータが整備された道路上の点であって、目的地に対応する地物からいずれかの道路を通行して到着できる点である。
以下、地図データベース記憶部に記憶された上述のデータ全体を地図データベースと称することもある。
入力部は、出発地および目的地を入力する。出発地は、ユーザの現在位置を自動的に入力するようにしてもよい。目的地は、地物データに含まれる特定の建物等を指定してもよいし、地図上で座標値を指定してもよい。
到着地点取得部は、目的地として地物が指定されたとき、地図データベース記憶部に記憶された地図データベースを参照して、当該地物に対応する到着地点を取得する。
そして、経路探索部は、ネットワークデータを参照して、出発地から到着地点までの経路探索を行う。

本発明の経路探索システムによれば、指定された目的地の最寄りのノードではなく、到着地点を用いて経路探索を行う。到着地点は、目的地に対応する地物からいずれかの道路を通行して到達できる主ネットワーク上の点であるから、逆に言えば、主ネットワークから目的地にいずれかの道路を通行して向かうのに適した点となる。また、到着地点は、特許文献２にいう特定エリアのように地域に対して設定される点ではなく、それぞれの地物に対して得られる点であるから、各地物の構造を踏まえて適した点を得ることができる。従って、この到着地点を用いた経路探索を行うことにより、本発明は、目的地周辺の道路状況や、目的地の構造等を考慮した好適な経路を探索することが可能となる。

本発明において、到着地点は、地物データの一部として、または地物データと関連づけられた状態で建物等の地物ごとに設定されているから、到着地点取得部は、目的地として指定された地物に対応する到着地点のデータを読み込めば済む。目的地が座標値で指定された場合には、到着地点取得部は、指定された座標が対応する地物を特定し、その地物に対応する到着地点のデータを読み込めばよい。

他の態様として、次に示すように、到着地点を予め用意しない構成とすることもできる。まず、地物データに、地物への出入口に面した道路上の点を指定する出入口点を記憶しておく。そして、到着地点取得部は、出入口点を探索開始点としてネットワークデータおよび地物データの少なくとも一方を用いた経路探索によって到着地点を得るのである。経
路探索には、上述の通り、通行規制の整備が完全とは言えない準ネットワークや、ネットワークが一切整備されてはいない道路も用いることができる。ネットワークが整備されていない道路については、地物データに含まれる道路のポリゴンデータの連結具合をネットワークデータとして扱うことにより経路探索の対象とすることができる。
仮に、到着地点を予め地物データとして整備しておくと、ネットワークが更新された場合に従前の到着地点がネットワークから外れてしまうことが生じたり、従前の到着地点よりも地物に近い点を到着地点とできるのに、こうした点が利用できないなどの支障が生じるおそれがある。これに対し、上述のように、経路探索によって到着地点を求める態様によれば、これらの支障を回避し、その時々のネットワークデータに基づいて好適な到着地点を得ることができる。

到着地点は、目的地に対応する地物について一つに限る必要はなく、複数を取得してもよい。本発明において地図データベース記憶部に予め複数の到着地点を地物データとして格納しておいてもよい。また、到着地点を経路探索によって求める他の態様においては、経路探索によって複数の到着地点を求める方法をとってもよい。さらに、両者を併用し、地物データに到着地点を格納しておくとともに、経路探索によって追加の到着地点を求めるようにしてもよい。
このように複数の到着地点が取得される場合には、経路探索部は、経路探索の結果または目的地と到着地点との位置関係に基づく所定の抽出条件によって複数の到着地点の一つを選択すればよい。例えば、次に示す抽出条件を用いることができる。コストとは、経路探索で用いられる評価値であり、コストが小さいほど、経路として適していることを表す値である。
（１）出発地からそれぞれの到着地点までの経路探索によるコスト（以下、「経路コスト」という）が最小となる到着地点を選択する。
（２）経路コストと、目的地からそれぞれの到着地点までのコスト（以下、「到着地点コスト」という）の和が最小となる到着地点を選択する。
（３）到着地点コストが最小となる到着地点を選択する。
（４）出発地と目的地とを結ぶ線分までの距離が最短の到着地点を選択する。
（５）到着地点から目的地までの移動手段が車の場合には、車での出入りに適した出入口線に対応する到着地点を選択する。
抽出条件は、これらの組合せであってもよいし、この他の条件を用いることもできる。

本発明は、経路案内システムに限らず、種々の態様で構成可能である。
例えば、上述のネットワークデータ、地物データを備えるコンピュータによって地図データベースを生成する地図データベース生成方法として構成してもよい。
この方法では、まず、地物について出入口点の指定を入力する。指定された出入口点は地物データに格納してもよいし、地図データベースの生成が完了したら消去してもよい。
次に、出入口点を探索開始点とする経路探索によって、到着地点を求める。この経路探索には、先に説明したように、準ネットワークや道路ポリゴンを用いることができる。
そして、得られた到着地点を地物データに格納するのである。
この方法によれば、地物の出入口点を指定すれば、適した到着地点を自動的に得ることができる。従って、ネットワークを更新した場合でも、比較的軽い負荷で到着地点の整備が可能である。

本発明は、その他、コンピュータを用いた経路探索方法として構成してもよいし、かかる経路探索をコンピュータに実行させるためのコンピュータプログラムとして構成してもよい。また、かかるコンピュータプログラムを記録したコンピュータが読み取り可能な記録媒体として構成してもよい。記録媒体としては、フレキシブルディスクやＣＤ−ＲＯＭ、光磁気ディスク、ＩＣカード、ＲＯＭカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ）および外部記憶装置等、コンピュータが読取り可能な種々の媒体を利用できる。

従来技術における駐車場の探索方法を示す説明図である。 経路案内システムの構成を示す説明図である。 地図データベースの構造を示す説明図である。 到着地点の設定について示す説明図である。 地物データ整備処理のフローチャートである。 経路案内処理のフローチャートである。 到着地点取得処理のフローチャートである。 案内対象交差点設定処理のフローチャートである。 案内対象交差点設定例（１）を示す説明図である。 案内対象交差点設定例（２）を示す説明図である。 実施例２における出発地点、到着地点の設定について示す説明図である。 実施例２および実施例３における地物データのデータ構造を示す説明図である。 実施例２および実施例３における地物データのデータ構造の例を示す説明図である。 実施例２における経路案内処理のフローチャートである。 実施例３における経路案内処理のフローチャートである。

本発明の実施例１、実施例２および実施例３について以下の順序で説明する。
＜実施例１＞
Ａ．システム構成：
Ｂ．データ構造：
Ｂ１．ネットワークデータ：
Ｂ２．文字データ：
Ｂ３．地物データ：
Ｂ４．到着地点の設定：
Ｃ．地物データの整備：
Ｄ．経路案内処理：
Ｄ１．全体処理：
Ｄ２．到着地点取得処理：
Ｄ３．案内対象交差点設定処理：
Ｄ４．案内例：
Ｅ．変形例：
＜実施例２＞
＜実施例３＞

＜実施例１＞
Ａ．システム構成：
図２は、案内システムの構成を示す説明図である。案内システムは、ナビゲーション装置１００として構成される。本実施例では、ナビゲーション装置１００は、地図データ等を提供するサーバ２００とネットワークＮＥ１で接続されており、サーバ２００から地図データベースの更新を受けられるものとした。ナビゲーション装置１００は、スタンドアロンで稼働する構成としてもよいし、その機能の一部をサーバ２００等で実行する構成としてもよい。
サーバ２００は、データベース生成装置としてのパーソナルコンピュータ３００とネットワークＮＥ２を介して接続されている。データベース生成装置３００は、オペレータの指示に従って、サーバ２００に格納されるデータベースの生成および更新を行うための装置である。

サーバ２００は、地図データベース記憶部２１０、送受信部２０１、およびデータベース管理部２０２を備えている。送受信部２０１、データベース管理部２０２は、ハードウェア的に構成してもよいが、本実施例では、これらの機能を実現するコンピュータプログラムをインストールすることによって、ソフトウェア的に構成するものとした。

送受信部２０１は、ナビゲーション装置１００およびデータベース生成装置３００とネットワークＮＥ１、ＮＥ２を介した通信を行う。本実施例では、地図データベース記憶部２１０のデータや、その提供・格納に関するコマンド等が通信される。
データベース管理部２０２は、ナビゲーション装置１００、データベース生成装置３００から要求された地図情報を、地図データベース記憶部２１０から読み出したり、データベース生成装置３００で生成された地図データを地図データベース記憶部２１０に格納する。
地図データベース記憶部２１０には、地物データ２１１、文字データ２１２、およびネットワークデータ２１３が格納されている。地物データ２１１は、道路や建物など地図に描画すべき地物のポリゴンデータである。文字データ２１２は、地図上に表示すべき文字情報である。例えば、建物の名称や地名などの文字情報が含まれる。ネットワークデータ２１３は、道路をノード、リンクのつながりで表したデータである。本実施例のネットワークデータ２１３には、主ネットワークデータと準ネットワークが含まれる。主ネットワークデータとは、現地調査によって通行規制が十分に整備されたデータであり、車両の経路探索に支障なく用いることができるデータとなっている。準ネットワークデータとは、通行規制の整備が十分とは言えないデータであり、車両の経路探索では、使用しない方が好ましいデータである。

ナビゲーション装置１００には、主制御部１０１の下で稼働する種々の機能ブロックが構成されている。本実施例では、主制御部１０１および各機能ブロックは、それぞれの機能を実現するソフトウェアをインストールすることによって構成したが、その一部または全部をハードウェア的に構成してもよい。
送受信部１０２は、サーバ２００とのネットワークＮＥ１を介した通信を行う。本実施例では、地図データベースおよびその提供を受けるためのコマンドの送受信が主として行われる。
コマンド入力部１０３は、ナビゲーション装置１００に設けられたボタン、レバー、タッチパネル等の操作を通じて、ユーザからの指示を入力する。本実施例における指示としては、経路探索の出発地、目的地の指定などが挙げられる。
ＧＰＳ入力部１０４は、ＧＰＳ（Global
Positioning System）を用いてユーザの現在位置を入力する。
地図データベース記憶部１０５は、サーバ２００から提供された地図データベースを格納する。本実施例では、サーバ２００が備える地図データベース記憶部２１０に記憶された地図データベースの全体をナビゲーション装置１００内の地図データベース記憶部１０５にも格納するものとしたが、経路探索や地図表示に必要となる部分のみを、その都度、サーバ２００から取得するものとしてもよい。
経路探索部１０７は、地図データベース記憶部１０５を参照して、経路探索を行う。
表示制御部１０６は、地図データベース記憶部１０５を用いてナビゲーション装置１００のディスプレイに地図および探索された経路等の案内を表示する。

データベース生成装置３００には、主制御部３０１の下で稼働する種々の機能ブロックが構成されている。本実施例では、主制御部３０１および各機能ブロックは、それぞれの機能を実現するソフトウェアをインストールすることによって構成したが、その一部または全部をハードウェア的に構成してもよい。
送受信部３０２は、サーバ２００とのネットワークＮＥ２を介した通信を行う。本実施例では、地図データベースおよびその管理のためのコマンドの送受信が主として行われる。
コマンド入力部３０３は、キーボードやマウスなどの操作を介してオペレータによる指示を入力する。
表示制御部３０４は、データベース生成装置３００のディスプレイに地図等を表示する。
地図データベース記憶部３０５は、サーバ２００の地図データベース記憶部２１０に記憶されている地図データベースを格納する。本実施例では、サーバ２００の地図データベース全体を格納するものとしたが、処理に必要な部分のみを格納するようにしてもよい。
到着地点算出部３０７は、地図データベース記憶部３０５に格納された地物に対して、到着地点を求める。到着地点とは、地物から道路をたどって主ネットワークデータ、つまり経路探索に使用できるネットワークデータが整備された道路まで到達した地点を言う。
データベース整備部３０６は、到着地点算出部３０７によって得られた到着地点を地図データベース記憶部３０５に格納し、サーバ２００の地図データベース記憶部２１０に記憶されている地図データベースを更新する。

Ｂ．データ構造：
図３は、地図データベースの構造を示す説明図である。地物データ、文字データ、ネットワークデータに格納される情報の概要を示した。

Ｂ１．ネットワークデータ：
ネットワークデータとは、道路をリンク、ノードで表したデータである。本実施例では、ネットワークデータとして主ネットワークデータと、準ネットワークデータの２種類が用意されている。図中に実線で示したリンクＬ１〜Ｌ４およびノードＮ１、Ｎ２が主ネットワークデータであり、破線で示したリンクＬ１１〜Ｌ１３およびノードＮ１１、Ｎ１２が準ネットワークデータである。
主ネットワークデータおよび準ネットワークデータともに、それぞれに属するリンクデータおよびノードデータを格納している。リンクデータは、それぞれのリンクを形成する点列の座標、国道・県道等の種別、車線数その他の属性情報や通行規制情報などを記録している。ノードデータは、座標値、通行規制などを記録している。
ただし、主ネットワークデータは、現地調査によって通行規制が十分に整備されたデータであり、車両の経路探索に支障なく用いることができるデータとなっている。これに対し、準ネットワークデータは、通行規制の整備が十分とは言えないデータであり、車両の経路探索では、使用しない方が好ましいデータである。本実施例でも、経路探索は原則として主ネットワークデータを用いて行うものとしている。

Ｂ２．文字データ：
文字データ２１２は、地物の名称や地名などを表示する文字を規定するデータである。図中には、建物ＢＬＤの名称を表示するためのデータ例を示した。文字データは、内容、位置、地物、フォント、サイズなどの情報を格納する。
内容は、表示すべき文字列であり、図中の例では、「△△(株)」という会社名称である。
位置は、文字を表示する位置である。本実施例では、文字列の左下の点Ｐ５を基準点として、この座標値を指定するものとした。
地物は、文字が関連づけられる地物データのポリゴン名称である。
フォント、サイズは、表示する際のフォントおよびサイズの指定である。
この他、色、太字など、種々の属性を指定可能としてもよい。

Ｂ３．地物データ：
地物データ２１１について、建物Ｈ１を例にとって構造を示す。地物データ２１１は、建物、道路等の地物を描画するためのポリゴンデータであり、名称、形状、代表点、出入り口線、到着地点、属性などを格納している。
名称は、地物の名称である。ポリゴンに固有のＩＤを用いてもよい。
形状は、地物のポリゴンの頂点を示す座標の列である。図の例では、建物Ｈ１のポリゴンの頂点Ｐ１、Ｐ２、Ｐ３、Ｐ４の各座標が格納されている。
代表点は、地物の位置を表す地点Ｃの座標である。代表点は、地物の図心を用いることが多いが、任意に設定可能である。
出入口線は、地物と道路とを関連づけるための情報である。建物Ｈ１の場合、玄関から道路に出るための線分Ｄが出入口線として登録される。具体的には、線分Ｄの両端の座標が登録されることになる。出入口線は、線分Ｄのうち、道路上の端点のみを登録するものとしてもよい。また、出入口線は、建物や駐車場など、出入りを伴う地物に設定されるものであり、地物の全てに設定する必要はない。図の例では、建物ＢＬＤに対して正面の出入口線ＤＢ１および駐車場ＢＬＤＰ側の出入口線ＤＢ２、建物Ｈ２〜Ｈ４に対してそれぞれ出入口線ＤＨ２〜ＤＨ４、駐車場ＰＫに対して出入口線ＤＰＫが設定されている。出入口線に対して、人の出入りに使用する出入口、駐車場などの用途を示す情報を設定しておいてもよい。

到着地点Ｇは、地物の出入口線の道路上の端点から、いずれかの道路を経てたどりつけるネットワーク上の点である。建物Ｈ１の場合、図中に点線で示す通り、出入口線Ｄが関連づけられている道路Ｒ２１を経て、リンクＬ２に至ることができるため、リンクＬ２上に到着地点Ｇが設定されている。出入口線Ｄから道路Ｒ２１を図中右方向にたどり、ノードＮ１１で右折してノードＮ２に至る経路をとり、ノードＮ２を到着地点とすることもできる。本実施例では、建物Ｈ１からノードＮ２に至る道のりよりも、到着地点Ｇに至る道のりの方が短いから、このように設定した。到着地点は、一つに限定する必要はないから、ノードＮ２も到着地点に設定してもよい。
図の例では、建物Ｈ２〜Ｈ４に対する到着地点は点ＧＨと設定されている。建物ＢＬＤに対しては、点ＧＨおよび点ＧＢＬＤ２と設定されている。到着地点は、出入口線と同様、駐車場にも設定でき、図の例では、駐車場ＰＫに対して到着地点ＧＰＫが設定されている。駐車場ＰＫは、リンクＬ２に面しているため、出入口線ＤＰＫの端点と到着地点ＧＰＫが一致した状態となっている。

Ｂ４．到着地点の設定：
図４は、到着地点の設定について示す説明図である。建物ＢＬＤ１の出入口線ＤＢを対象とする到着地点について示した。
建物ＢＬＤ１の周辺の主ネットワークデータとしては、リンクＬ７、ノードＮ７およびリンクＬ５、Ｌ６およびノードＮ５、Ｎ６が存在する。準ネットワークデータとしては、破線で示したリンクＬ１４が存在する。
建物ＢＬＤ１の出入口線ＤＢからいずれかの道路を経て主ネットワークにたどりつく経路としては、図中に点線で示した３通りがあげられる。道路Ｒ２４を経てリンクＬ７にたどりつく経路、道路Ｒ２５を経てたリンクＬ６およびリンクＬ５にそれぞれたどりつく経路である。これらの各経路がリンクＬ７、Ｌ６、Ｌ５にたどりつく点が到着地点Ｇ７、Ｇ６、Ｇ５となる。

これらの到着地点は、経路探索によって求めることができる。本実施例では、それぞれの地物は、出入口線によって、いずれかの道路に関連づけられているから、出入口点、つまり地物への出入口に面した道路上の端点を始点とする経路探索によって到着地点を求めればよい。
この経路探索は、主ネットワークデータ、準ネットワークデータおよび道路のポリゴンの全てを用いてもよい。道路のポリゴンは、リンク、ノードで構成されている訳ではないが、隣接するポリゴンを指定するデータは持っているから、ポリゴン同士のつながり関係は規定されており、リンク、ノードと同様に、経路探索に使用することが可能である。出入口点を起点とする経路探索の結果、主ネットワークデータにたどり着いた点を到着地点とすればよい。

図の例のように、到着地点がＧ７、Ｇ６、Ｇ５の３点見いだされる場合、これらの３点を建物ＢＬＤ１の到着地点として用いてもよいし、例えば、地物からの道のりが最短の地点、地物からの距離が最短の地点、地物から到着地点までの経路と準ネットワークデータとの重複部分が多い点、地物から出発点に向かう方角に近い点などの基準で選択してもよい。
図の例においては、地物からの道のりや距離を基準として選べば、建物ＢＬＤ１に最も近い点Ｇ５が到着地点となる。準ネットワークデータとの重複部分を基準として選べば、点Ｇ６が到着地点となる。出発地が図の左端方向にある場合には、出発地の方角を基準として選べば、点Ｇ７が到着地点となる。

本実施例では、上述の手順で、到着地点を設定し、地物データ２１１に予め設定しておくものとした。到着地点は、予め設定しておくのではなく、経路探索などの処理の過程で求めるものとしてもよい。

Ｃ．地物データの整備：
図５は、地物データ整備処理のフローチャートである。データベース生成装置３００のデータベース整備部３０６、到着地点算出部３０７が主として実行する処理であり、ハードウェア的には、データベース生成装置３００のＣＰＵが実行する処理である。

ＣＰＵは、オペレータから指定された範囲の地図データを地図データベース記憶部３０５から読み込み、ディスプレイに地図を表示する（ステップＳ１０）。
ＣＰＵは、処理対象となる地物に対して、名称、地物のポリゴン形状、代表点、属性などの指示を入力する（ステップＳ１１）。既存の地物に対して処理を行う際には、これらの情報は、既に地物データに格納されているから、要更新箇所のみを修正すればよい。
また、ＣＰＵは、出入口線および用途の指定を入力する（ステップＳ１２）。出入口線は、地物と道路とを関連づけるための情報である。地物に対して複数の出入口線を設定してもよい。用途は、出入口線ごとに設定することができる。例えば、人の出入りに使用する出入口、駐車場などの形式で指定する。人の出入りに使用する出入口を、玄関、裏口などに細分化して設定してもよい。

ＣＰＵは、到着地点探索処理を行って、地物のそれぞれの出入口線に対応する到着地点を求める（ステップＳ１３）。この処理は、図４で説明した出入口点を始点とする経路探索である。
この経路探索は、主ネットワークデータ、準ネットワークデータおよび道路のポリゴンの全てを用いてもよい。道路のポリゴンは、リンク、ノードで構成されている訳ではないが、隣接するポリゴンを指定するデータは持っているから、ポリゴン同士のつながり関係は規定されており、リンク、ノードと同様に、経路探索に使用することが可能である。出入口点を起点とする経路探索の結果、主ネットワークデータにたどり着いた点を到着地点とすればよい。
到着地点は、それぞれの出入口点に対して複数探索されることがある。このような場合、いずれかの到着地点に絞り込んで地物データに登録するようにしてもよいが、本実施例では、探索された到着地点は全て登録しておくものとした。こうすることにより、後述する経路探索における到着地点の選択肢が増え、より適した経路を提示できる可能性が増えるからである。

ＣＰＵは、以上の処理を踏まえ、名称、地物ポリゴン形状、代表点、属性、出入口線、用途、および到着地点のデータを地物データに格納し、地物データを更新する（ステップＳ１４）。
処理対象となるべき地物が他にもある場合には、オペレータの指示に従って、この処理を繰り返し実行する。

Ｄ．経路案内処理：
Ｄ１．全体処理：
図６は、経路案内処理のフローチャートである。ナビゲーション装置１００の経路探索部１０７および表示制御部１０６が主として実行する処理であり、ハードウェア的にはナビゲーション装置１００のＣＰＵが実行する処理である。

ナビゲーション装置１００は、出発地および目的地を入力する（ステップＳ２０）。出発地は、ユーザが指定してもよいし、ＧＰＳなどで取得した現在位置を出発地に設定してもよい。
目的地は、地物を指定してもよいし、座標値で指定してもよい。

次に、ナビゲーション装置１００は、目的地として指定された地物に対応する到着地点を取得する（ステップＳ３０）。本実施例では、到着地点は地物データ２１１に格納されている。従って、目的地となる地物が指定されている場合は、指定された地物に対応する地物データから到着地点を読み出せばよい。目的地が座標で指定されている場合には、当該座標がいずれのポリゴンに含まれるかを特定し、特定されたポリゴンの地物データに対応する到着地点を読み出せばよい。地物に対して複数の到着地点が得られる場合もある。
到着地点取得処理の内容は後述する。

ナビゲーション装置１００は、得られた到着地点を起点とする経路探索を行う（ステップＳ５０）。
到着地点が複数得られている場合には、ナビゲーション装置１００は、経路案内の対象とすべき到着地点および経路を選択する。到着地点および経路を地図上に表示して、ユーザに直接、選択させる方法をとってもよい。また、ナビゲーション装置１００が何らかの選択条件に従って自動的に選択するようにしてもよい。選択には、種々の選択条件を適用可能であるが、本実施例では、次に示す３つの条件から、ユーザが予め選択した条件を用いるものとした。
（１）出発地からそれぞれの到着地点までの経路探索によるコスト（以下、「経路コスト」という）が最小となる到着地点を選択する。
（２）経路コストと、目的地からそれぞれの到着地点までのコスト（以下、「到着地点コスト」という）の和が最小となる到着地点を選択する。
（３）出発地と目的地とを結ぶ線分までの距離が最短の到着地点を選択する。つまり、出発地と目的地とを結ぶ線分に対して到着地点から垂線をおろし、その距離で評価する条件である。線分に対して垂線を引くことができない位置関係にある到着地点については、目的地までの直線距離を用いるものとする。この条件は、出発地から目的地との間に位置する到着地点を選択すれば、経路コストと到着地点コストとの総和が低い経路が得られるとの考え方に基づくものである。

なお、到着地点コストが最小となる到着地点を選択するものとしてもよい。この態様によれば、到着地点から出入口までを徒歩で移動する場合に、徒歩の移動負荷が最も軽くなる経路を案内することができる。もっとも、到着地点コストは目的地となる地物が指定された時点で一義的に決まるものであるから、到着地点コストが最小という条件を用いる場合には、到着地点を起点とする経路探索（ステップＳ５０）を行う前に、この条件に基づいて経路探索に使用すべき到着地点を決定しておくことが望ましい。こうすれば、経路探索は決定された到着地点についてのみ行えば足りるから、経路探索の処理負荷を軽減することも可能となる。

そして、案内対象交差点設定処理を行う（ステップＳ６０）。本実施例では、ナビゲーション装置１００は、経路案内時に、右左折などの経路の案内に加えて、危険箇所の案内など、ユーザに対して通行を支援するための案内を行う。案内対象交差点設定処理は、この案内を行う対象となる交差点を設定する処理である。本実施例で案内対象としたのは、次の２種類の交差点である。
第１は、仮想交差点の案内である。ネットワークデータは、全ての道路に整備されている訳ではないので、ネットワークデータ上は交差点として構成されていない部分であっても、実際には道路が交差している箇所が存在する。このような箇所を、ネットワークデータから見ると仮想的な交差点という意味で、本実施例では、仮想交差点と称する。本実施例では、このような仮想交差点の中から案内対象交差点を選択し、交差点の存在などをユーザに対して案内する。
第２は、要注意交差点の案内である。住宅に面した道路と交差する交差点では、幼児を含め人の出入りがあり、時には飛び出しなどの危険もある。本実施例では、このような交差点を案内対象交差点として、ユーザに対し注意喚起を行う。
これらの案内を行う案内対象交差点の設定処理の具体的内容については、後述する。

こうして経路案内のために要する情報が揃うと、ナビゲーション装置１００は、次の手順で経路案内を行う。
ユーザの現在位置を取得し（ステップＳ９０）、探索された経路および現在位置をディスプレイに表示する（ステップＳ９２）。経路の表示と併せて、経路の音声案内を行っても良い。
また、ナビゲーション装置１００は、案内対象交差点では、通行案内を出力する（ステップＳ９４）。先に説明した通り、仮想交差点の存在等を示したり、要注意交差点の注意喚起をしたりするのである。
以上の処理を、ナビゲーション装置１００は、ユーザが目的地に到着するまで（ステップＳ９６）、繰り返し実行する。

Ｄ２．到着地点取得処理：
図７は、到着地点取得処理のフローチャートである。経路案内処理（図６）のステップＳ３０に相当する処理であり、目的地として地物が指定されたとき、地図データベース記憶部を参照して当該地物に対応する到着地点を得る処理である。
ナビゲーション装置１００は、目的地に対応する地物データを読み込む（ステップＳ３２）。目的地が地物を指定している場合には、指定に該当する地物データを読み込めばよい。目的地が座標で指定されている場合には、その座標点を含む地物の地物データを読み込む。
地物データに到着地点が設定されている場合（ステップＳ３４）、ナビゲーション装置１００は、設定されている到着地点データを読み込む（ステップＳ３６）。
到着地点が設定されていない場合には（ステップＳ３４）、ナビゲーション装置１００は、出入口線データを読み込み（ステップＳ３８）、到着地点探索処理を行って到着地点を得る（ステップＳ４０）。到着地点探索処理は、地物データ整備処理（図５）のステップＳ１３で説明した処理と同じである。

そして、ナビゲーション装置１００は、経路探索モードに応じて到着地点を選択する。
到着地点から目的地までは徒歩で向かう旨の探索モードが指定されている場合は（ステップＳ４２）、ナビゲーション装置１００は、到着地点から目的地までのコスト、つまり到着地点コストが短い到着地点を優先する（ステップＳ４４）。コストは、経路探索において、各経路を評価するための評価値であり、距離や移動に要する時間などに基づいて設定することができる。上り／下り坂、階段など道路の構造などに基づく移動負荷を加味して設定してもよい。ステップＳ４４では、到着地点から徒歩で移動することを考慮し、距離が短いなど、移動に要する労力が低い到着地点を選択することを意味している。
「優先」には、一つの到着地点を選択する態様、および複数の到着地点に対して優先度を設定する態様などが含まれる。後者の場合には、ステップＳ４４の条件に基づいて優先度を設定しておき、経路案内処理（図６）のステップＳ５０の処理における選択条件を併せて考慮して、案内対象となる到着地点を選択するようにしてもよい。

到着地点から目的地まで車で移動する旨の探索モードが指定されている場合は（ステップＳ４２）、ナビゲーション装置１００は、出入口線の用途を参照し、駐車場の出入口線に対応する到着地点を優先する（ステップＳ４６）。到着地点から目的地までは、通行規制等の調査が十分になされていない道路なので、幅員が足りないなど、車の通行に適しない道路が含まれるおそれもある。しかし、駐車場に対応した到着地点であれば、それ以外の到着地点に比べて、到着地点から目的地までの経路も車の通行に適している可能性が高い。ステップＳ４６の態様によれば、目的地に到着した時に車を駐車できる出入口に案内できるだけでなく、目的地まで車で移動するのに適した到着地点を優先することができる。

Ｄ３．案内対象交差点設定処理：
図８は、経路案内交差点設定処理のフローチャートである。経路案内処理（図６）のステップＳ６０に相当する処理であり、仮想交差点および注意喚起の案内を行う地点を設定する処理である。

ナビゲーション装置１００は、経路上の到着地点を抽出し（ステップＳ６２）、未処理の到着地点を処理対象として選択する（ステップＳ６４）。
そして、この到着地点に対応する全ての地物を抽出する（ステップＳ６６）。到着地点は、地物からいずれかの道路をたどって主ネットワークに到達した点であるから、複数の地物に対する到着地点が同一の点となることもある。ステップＳ６６では、ナビゲーション装置１００は、地物データから、処理対象の到着地点に対応する地物を全て検索する。

検索された地物に駐車場がある場合（ステップＳ６８）、ナビゲーション装置１００は、駐車場の位置に基づき交差点形状を特定し（ステップＳ７０）、交差点となっている箇所について（ステップＳ７２）、仮想交差点に設定する（ステップＳ７４）。

ステップＳ７０〜Ｓ７４の処理内容について具体例で説明する。
図９は案内対象交差点設定例（１）を示す説明図である。リンクＬ６０の周辺に、駐車場Ｐ６１〜Ｐ６５が存在する例を示した。それぞれは代表点が点Ｃ６１〜Ｃ６５であり、到着地点Ｇ６１〜Ｇ６３、出入口線Ｄ６１〜Ｄ６５が設定されている。
駐車場Ｐ６１の場合、到着地点Ｇ６１はリンクＬ６０上に存在するが、リンクＬ６０に面しており、交差点とはなっていないため、仮想交差点には設定しない。リンクＬ６０を走行しているユーザから視認できる駐車場を案内対象とする必要はないからである。
交差点となっているか否かの判断は、種々の方法を用いることができる。本実施例では、出入口線Ｄ６１の端点が到着地点Ｇ６１と一致している場合には交差点ではないと判断し、案内対象から除外するものとした。駐車場Ｐ６１の代表点Ｃ６１とリンクＬ６０との距離が道路の幅員程度である場合に交差点でないと判断する方法をとることもできる。

到着地点Ｇ６２の場合には、リンクＬ６０の右側にのみ駐車場Ｐ６２が存在することが分かる。従って、ナビゲーション装置１００は、「三叉路」と判断する。
到着地点Ｇ６３の場合には、リンクＬ６０の右側に駐車場Ｐ６３、Ｐ６４が存在し、左側に駐車場Ｐ６５が存在する。従って、ナビゲーション装置１００は、「交差点」または「四叉路」と判断する。
このように、駐車場とリンクとの距離、およびリンクの左右いずれに駐車場が配置されているかに応じて、ナビゲーション装置１００は交差点形状を判断することができる。

駐車場に関する処理を終えると、ナビゲーション装置１００は、到着地点に対応する「住宅」の数が２以上の場合には（ステップＳ７６）、要注意交差点に設定する（ステップＳ７８）。
この処理について具体例で説明する。
図１０は案内対象交差点設定例（２）を示す説明図である。リンクＬ７０の周辺に、住宅Ｈ７１〜Ｈ７９が存在する例を示した。それぞれは代表点が点Ｃ７１〜Ｃ７９であり、到着地点Ｇ７１〜Ｇ７３、Ｇ７５、Ｇ７７、出入口線Ｄ７１〜Ｄ７９が設定されている。

到着地点Ｇ７１、Ｇ７２は、対応する住宅数が１軒であるため、ステップＳ７６の判断基準により、要注意交差点から除外される。到着地点Ｇ７１については、駐車場の場合と同様、住宅Ｈ７１がリンクＬ７０に面していると判断し、要注意交差点から除外するものとしてもよい。
到着地点Ｇ７３は、リンクＬ７０の右側に住宅Ｈ７３、Ｈ７４の２軒が存在する。到着地点Ｇ７４は、リンクＬ７０の右側に住宅Ｈ７５、左側に住宅Ｈ７６が存在する。到着地点Ｇ７７は、リンクＬ７０の右側に住宅Ｈ７７、Ｈ７８の２軒、左側に住宅Ｈ７９が存在する。従って、到着地点Ｇ７３、Ｇ７５、Ｇ７７は、それぞれ２軒以上の住宅が対応しているから、要注意交差点に設定される。

ナビゲーション装置１００は、以上の処理を経路上の全ての到着地点について行い、案内対象交差点を設定する。
このように、本実施例では、駐車場に対応する到着地点のうち交差点となっている地点、および２軒以上の住宅に対応している到着地点が案内対象交差点として設定されることになる。

Ｄ４．案内例：
図９を参照しながら、駐車場が存在する場合の案内対象交差点に対する案内例を説明する。
図９に示す通り、点Ｇ６２、Ｇ６３の部分に三叉路および四叉路が存在するが、リンクＬ６０にはこれらの点にノードは設けられていないから、リンクＬ６０を見る限り、点Ｇ６２、Ｇ６３の交差点は把握することができない。しかし、点Ｇ６２、Ｇ６３は、それぞれ駐車場に対する到着地点であるから、これらの地点は、車が出入りできる程度の道路と交差していることが分かる。本実施例のナビゲーション装置１００は、このような状態を考慮して、点Ｇ６２、Ｇ６３の仮想交差点を案内対象交差点と設定し、交差点である旨の案内を行う。

具体的には、交差点Ｇ６２にさしかかるところで、「前方に三叉路があります」と案内したり、交差点Ｇ６３にさしかかるところで、「前方に交差点（または四叉路）があります」と案内することができる。これらの案内とともに、「車が出てくる可能性があります」と注意喚起をしてもよい。
また、図９の点Ｇ６２よりも先の交差点で右折する場合は、点Ｇ６２の三叉路を踏まえて、「この先、三叉路の次の交差点で右折です」のように案内することも可能である。こうすることにより、ユーザが誤って点Ｇ６２の交差点を右折してしまうことを回避することができる。

また、点Ｇ６２のように、進行方向に対して右側にのみ駐車場が位置する場合には、車が出てくることによる危険度は比較的低いと判断して通行上の注意喚起を省略してもよい。左側にのみ駐車場が位置する場合には、ユーザの進行する車線に近く危険度が認められると考えて、注意喚起をしてもよいし、左右双方に駐車場が位置する場合に比べれば危険度が低いと考えて、注意喚起を省略するようにしてもよい。

本実施例では、到着地点Ｇ６２を利用して、駐車場Ｐ６２までの経路案内をすることもできる。つまり、ネットワークデータを利用して到着地点Ｇ６２までの経路を探索し、到着地点Ｇ６２から駐車場Ｐ６２までの経路は、道路のポリゴンデータを用いて案内するのである。
このような場合、仮にネットワークデータだけを利用した案内を行おうとすれば、ネットワークデータ上は、点Ｇ６２は交差点と認識されてはいないから、せいぜい「目的地付近です」という程度の案内しかすることができない。
これに対し、本実施例では、点Ｇ６２を交差点と認識することができることを利用して、「次の交差点を右折です」という経路案内を行っても良い。こうすることにより、ユーザにより適切な情報を提示することが可能となる。

図１０を参照しながら、住宅が存在する場合の案内対象交差点に対する案内例を説明する。
住宅に対応する到着地点は、人が飛び出してくる可能性がある要注意交差点として案内を行う。従って、点Ｇ７３、Ｇ７５、Ｇ７７にさしかかるところで、「この先の交差点は、人の出入りがあるかも知れません。注意して下さい」のように案内することができる。
この案内に交差点の形状を反映させてもよい。
例えば、点Ｇ７３では、「右側から人が出てくるかも知れません」、点Ｇ７５、Ｇ７７では、「左右から人が出てくるかも知れません」のように、方向を示して注意を喚起することができる。

注意喚起の方法は、到着地点に対応する住宅数に応じて変化させてもよい。図１０の到着地点Ｇ７３、点Ｇ７５は２軒が対応しているのに対し、到着地点Ｇ７７は３軒が対応しているから危険度が高いと判断し、より強調した態様で注意喚起してもよい。例えば、注意喚起するメッセージの内容を変化させてもよいし、音声案内のトーンや音量、画面表示の明度、色などで強調してもよい。

本実施例では、住宅数が２以上の交差点を注意喚起の対象としたが（図８のステップＳ７６）、この軒数は任意に設定可能であり、更に多くの軒数を判断基準値としてもよい。判断基準値を大きくすれば、案内が行われる頻度が下がるため、逆に、案内が行われた時のユーザの注意を効果的に喚起することができる。

要注意交差点での案内については、住宅に対応する到着地点が経路に沿って現れる密度を求め、その密度に応じて、注意喚起のための情報提示の内容を設定してもよい。
図１０に示す点Ｇ７７、Ｇ７５、Ｇ７３が比較的接近している場合、各交差点ごとに「人が出てくる可能性あります」という案内が行われると、ユーザはこうした案内に麻痺し
たようになってしまい、注意喚起の効果が低くなることがある。
そこで、このように所定の密度を超えて要注意交差点が存在する場合には、「しばらく飛び出しの危険がある地域を通行いたします」のように地域全体に対する注意喚起の態様をとってもよい。図１０のリンクＬ７０を下側から上側に向かって走行している場合には、点Ｇ７７にさしかかるところで、点Ｇ７７、Ｇ７５、Ｇ７３に対する総合的な案内として、上述のように地域全体に対する注意喚起を行うのである。

別の態様として、要注意交差点の密度が高い場合には、要注意交差点とするか否かの判断基準値（図８のステップＳ７６の値）を増大させ、判断基準を厳しくしてもよい。図１０の点Ｇ７７、Ｇ７５、Ｇ７３の地域に対しては、ナビゲーション装置１００は、例えば、判断基準値を３軒に変更するのである。こうすることで、点Ｇ７７のみが要注意交差点となるから、注意喚起が頻繁に行われる事態を回避することができる。具体的な処理態様としては、案内対象交差点設定処理（図８）を実行した後、要注意交差点の密度を算出し、密度が所定値を超える地域に対しては、ステップＳ７６の判断基準値を増大させた上で、再度、案内対象交差点設定処理（図８）を実行する方法をとることができる。

Ｅ．変形例：
本実施例では、仮想交差点および要注意交差点の例を示したが、本実施例の案内は、到着地点の種別に応じて種々の態様で適用することができる。例えば、到着地点がレストランや店舗に対応している場合、その密度に応じて、「右側にレストラン街があります」、「○○店街があります」のような案内を行っても良い。経路探索を行う際に、目的地に向かう途中で食事をとるなどの目的を設定した場合には、レストランに対応した到着地点を抽出し、経路案内の過程で、「右側にイタリアンレストランがあります」のように目的に応じた情報を提示してもよい。このように到着地点と関連づけた地物の種別に応じて情報を提示することにより、ユーザが目的地として選択していない地物について、経路から離れたところにある地物であってもユーザの意図に合致した情報を提示可能となる。

また本実施例では、経路案内を行った上で種々の情報提示をする例を示したが、本発明は、経路案内を行わない場合でも適用可能である。
例えば、図１０において、リンクＬ７０上をユーザが走行している場合には、ユーザの現在位置を検出し、その前方にある到着点について、「人が出てくる可能性あります」などの注意喚起をすることができる。ユーザの経路がわかっていない場合であっても、現在位置の変化から進行方向は判断できるため、前方に位置する交差点か否かは容易に判断可能である。
音声で注意喚起を行う場合には、注意喚起の対象となる交差点をユーザがほぼ確実に通行すると判断できる時点まで待つようにしてもよい。例えば、図１０の点Ｇ７７からリンクＬ７０を上方に向かってユーザが走行している場合を考える。ユーザは、点Ｇ７５を通過して直進するかも知れないし、ここで右左折するかも知れない。このような状況で点Ｇ７３の注意喚起を行うと、かえってユーザを混乱させかねない。しかし、ユーザが点Ｇ７５を通過した後は、Ｕターンでもしない限り点Ｇ７３を通過することが明らかである。このように、ユーザの現在位置および進行方向を考慮して、通過が確実と判断されるまで案内を行うタイミングを遅らせる態様をとることにより、ユーザの混乱を回避することができる。
この判断は、ユーザの前方に位置する到着地点Ｇ７３、Ｇ７２、Ｇ７１について、ユーザの現在位置（例えば点Ｇ７５）との間に分岐または他の到着地点が存在するか否かに基づいて判断することができる。到着地点Ｇ７１、Ｇ７２と点Ｇ７７との間には、到着地点Ｇ７３が存在するのに対し、到着地点Ｇ７３と点Ｇ７５との間には分岐等は存在しない。このような場合には、到着地点Ｇ７３を通過する可能性が高いと判断し、注意喚起を行うようにすればよい。
注意喚起は、音声だけでなく表示によることもできる。例えば、到着地点Ｇ７３，Ｇ７２等を危険度に応じて赤などの目立つ色で表示する態様をとることができる。このように表示によって注意喚起する場合には、ユーザの混乱を招くおそれが低いから、現在位置から所定範囲内にある到着地点を対象としても良い。

＜実施例２＞
実施例１は、目的地として指定された地物に対応する到着地点を、経路案内処理で用いるものであった。これに対し、実施例２においては、一つの地物に対して一以上設定された到着地点のうち、特に車で移動する旨の探索モードが指定されている場合に、交通規制情報等を考慮することで出発用に適した点と到着用に適した点とを区別する。具体的には、実施例２においては、ネットワークデータが整備された道路上の点であって、地物からいずれかの道路を通行して到着できる点を出発地点とし、ネットワークデータが整備された道路上の点であって、地物へいずれかの道路を通行して到着できる点を到着地点として、それぞれ定義するものとする。

実施例２において経路探索システムが出発地点および到着地点を設定するために用いる地図データは、ネットワークデータが整備されていない道路でも通行規制等の情報を備えている。実施例２においては、出発地点および到着地点は、地図製作会社等により予め設定されているものである。

実施例２の経路探索システムで使用するネットワークデータは、実施例１の経路探索システムで使用するネットワークデータと同様に、自動車の経路探索に使用可能な主ネットワークおよび通行規制の整備が完全とは言えない準ネットワークで構成される。また、地物データにはネットワークデータの存在しない道路のデータが含まれている。
このように、実施例２の経路探索システムで使用する地図データにおいて、全ての道路にネットワークデータを含めた通行規制情報等を整備していないのは、整備することによりデータ量が膨大になって経路探索効率が低下するためである。

図１１は、実施例２の経路探索システムが出発地点、到着地点の設定について示す説明図である。建物ＢＬＤ２の出入口線ＤＢを対象とする出発地点、到着地点について示した。
図１１において、建物ＢＬＤ２の周辺の主ネットワークデータとしては、リンクＬ７、ノードＮ７およびリンクＬ５、Ｌ６およびノードＮ５、Ｎ６が存在する。準ネットワークデータとしては、破線で示したリンクＬ１４が存在する。
また、道路Ｒ２５と道路Ｒ２６との交点に交点Ｋ１が設定されており、R２５には交点Ｋ１からノードＮ５に向けて一方通行とした交通規制があり、Ｒ２６にはノードＮ６から交点Ｋ１に向けて一方通行とした交通規制があるものとする。

この場合、車で移動して建物ＢＬＤ２の出入口線ＤＢからいずれかの道路を経て主ネットワークにたどりつく経路としては、２通りがあげられる。道路Ｒ２４を経てリンクＬ７にたどりつく経路および交点Ｋ１から道路Ｒ２５を経てリンクＬ５にそれぞれたどりつく経路である。これらの各経路がリンクＬ７、Ｌ５にたどりつく点が出発地点Ｇ７およびＧ５となる。
また、建物ＢＬＤ２の出入口線ＤＢへ、車で移動していずれかの道路を経て主ネットワークからたどりつく経路としては、２通りがあげられる。リンクＬ７から道路Ｒ２４を経て建物ＢＬＤ２の出入口線ＤＢへたどりつく経路およびリンクＬ６から道路Ｒ２６および交点Ｋ１を経て建物ＢＬＤ２の出入口線ＤＢへたどりつく経路である。これらの各経路の始点となるリンクＬ７、Ｌ６上の点が到着地点Ｇ７、Ｇ６となる。

出発地点および到着地点は地物データの属性として予め設定され、地図データベース記憶部に記憶されている。たとえば図１２のように、地物データと出発地点および到着地点の位置を表現する地点座標データとが関連付いた状態で地図データベース記憶部に記憶されている。地物データの属性には名称、地物ＩＤ、ポリゴン形状、中心座標、出発地点および到着地点のデータが含まれている。名称は地物の名称が記録され、ポリゴン形状には地物の形状を表現するポリゴンの頂点座標が記録され、中心座標は地物に対応するポリゴンの中心座標が記録され、出発地点および到着地点には地点座標データの地点ＩＤが記録されている。地点座標データには、地点ＩＤおよび座標が記録されている。
たとえば、地物Aには地物ＩＤ（図示せず）、ポリゴン形状（図示せず）、中心座標（ＬａｔＡ、ＬｏｎＡ）、出発地点U、到着地点U、V）が含まれている。
このようなデータ構造とすることで、地物Ａの場合、ネットワークデータが整備されていない領域において地点Ｖから地点Ｕへの移動はできるが、地点Ｕから地点Ｖへの移動はできないことがわかる。また、地物Ｂの場合、ネットワークデータが整備されていない領域において地点Ｘから地点Ｗへの移動はできるが、地点Ｗから地点Ｘへの移動はできないことがわかる。またさらに、地物Ｃの場合、ネットワークデータが整備されていない領域において地点Ｙおよび地点Ｚの間の移動はいずれの方向においてもできることがわかる。

なお、地物データのデータ構造は種々の形式があって良い。たとえば、図１３のように、地物データに関連付く到着地点のそれぞれに出発地点という属性または到着地点という属性が付与されていても良い。図１３における地物データは、地物Aに到着地点１（Ｌａｔ Ｕ、Ｌｏｎ Ｕ)、到着地点２（Ｌａｔ Ｖ、Ｌｏｎ Ｖ）が設定されている。到着地点１は出発地点の属性および到着地点の属性が付与されており、到着地点２は到着地点の属性が付与されている。

以下、実施例２の経路探索システムにおける経路案内処理について説明をおこなう。
図１４は、実施例２における経路案内処理のフローチャートである。ナビゲーション装置１００の経路探索部および表示制御部１０６が主として実行する処理であり、ハードウェア的にはナビゲーション装置１００のＣＰＵが実行する処理である。

まず、ナビゲーション装置１００は、出発地および目的地を入力する（ステップＳ４００）。出発地は、ユーザが指定してもよいし、ＧＰＳなどで取得した現在位置を出発地に設定してもよい。出発地および目的地は、地物を指定してもよいし、座標値、住所および電話番号等で指定してもよい。

ステップＳ４００が終了すると、ナビゲーション装置１００は、出発地および目的地として地物が指定されたとき、地図データベース記憶部２１０を参照して当該出発地および目的地に対応する出発地点および到着地点を取得する（ステップＳ４０１）。出発地および目的地が座標で指定されている場合には、ナビゲーション装置１００は地物データを参照し、当該座標が地物データのいずれのポリゴンに含まれるかを特定する。ナビゲーション装置１００は、特定された地物データに対応する出発地点および到着地点を読み出せばよい。また、当該座標がいずれのポリゴンにも含まれない場合は、ナビゲーション装置１００は指定した地点の最寄のポリゴンを特定しても良いし、指定した地点の最寄のリンクを特定しても良い。

たとえば、図１２のデータ構造において、地物Ａを出発地として、地物Bを目的地として指定した場合を考える。ナビゲーション装置１００は、出発地となる地物データＡの属性を参照し、出発地点Uの座標（ＬａｔＵ、ＬｏｎＵ)を取得する。また、ナビゲーション装置１００は、目的地となる地物Bの属性を参照し、到着地点Xの座標（ＬａｔＸ、ＬｏｎＸ)を取得する。なお、出発地点や到着地点が複数取得した場合の選択方法については、実施例１の経路探索システムと同様の方法でおこなうものとする。

ステップＳ４０１が終了すると、ナビゲーション装置１００は、ネットワークデータ２１３を参照して、出発地に対応する出発地点から目的地に対応する到着地点までの経路探索を行う（ステップＳ４０２）。具体的には、ナビゲーション装置１００は、出発地点Ｕの座標（ＬａｔＵ、ＬｏｎＵ)から到着地点Ｘの座標（ＬａｔＸ、ＬｏｎＸ)までの経路探索を行う。
ステップＳ４０２が終了すると、ナビゲーション装置１００は実施例１のステップＳ４０の案内対象交差点設定処理へ移行する。

このように、実施例２の経路探索システムにおいては、地物から到着できる点である出発地点と地物へ到着できる点である到着地点とを区別しており、指定した地物からいずれかの道路を通行して到着できる点を出発地点として設定するので、たとえばリンクから離れた地物を出発地として指定しても確実に到達できるネットワークデータ上の地点からルート案内を行える効果がある。また、交通規制を考慮した出発地点および到着地点が設定されることで、全ての道路やネットワークに交通規制を整備しなくても良いので、データ容量を削減する効果がある。

＜実施例３＞
実施例２は、出発地として指定された地物に対応する出発地点および目的地として指定された地物に対応する到着地点を、経路案内処理で用いる例であった。実施例３においては、出発地から目的地までの間に経由地が設定される例について説明する。なお経由地は１箇所設定されても良いし、複数個所設定されても良い。
以下、実施例３における経路案内処理について説明をおこなう。
図１５は、実施例２における経路案内処理のフローチャートである。ナビゲーション装置１００の経路探索部および表示制御部１０６が主として実行する処理であり、ハードウェア的にはナビゲーション装置１００のＣＰＵが実行する処理である。

まず、ナビゲーション装置１００は、出発地、目的地および一以上の経由地を入力する（ステップＳ５００）。出発地は、ユーザが指定してもよいし、ＧＰＳなどで取得した現在位置を出発地に設定してもよい。出発地、経由地および目的地は、地物を指定してもよいし、座標値、住所および電話番号等で指定してもよい。

ステップＳ５００が終了すると、ナビゲーション装置１００は、出発地、目的地および一以上の経由地として地物が指定されたとき、地図データベース記憶部２１０を参照して当該出発地、目的地および経由地のそれぞれに対応する出発地点および到着地点を取得する（ステップＳ５０１）。出発地、経由地および目的地が座標で指定されている場合には、ナビゲーション装置１００は地物データを参照し、当該座標が地物データのいずれのポリゴンに含まれるかを特定する。ナビゲーション装置１００は、特定された地物データに対応する出発地点および到着地点を読み出せばよい。また、当該座標がいずれのポリゴンにも含まれない場合は、ナビゲーション装置１００は指定した地点の最寄のポリゴンを特定しても良いし、指定した地点の最寄のリンクを特定しても良い。

たとえば、図１２のデータ構造において、地物Ａを出発地として、地物Bを経由地として、地物Ｃを目的地として指定した場合を考える。ナビゲーション装置１００は、出発地となる地物Ａの属性を参照し、出発地点Ｕの座標（ＬａｔＵ、ＬｏｎＵ)を取得する。また、ナビゲーション装置１００は、経由地となる地物Ｂの属性を参照し、到着地点Ｘの座標（ＬａｔＸ、ＬｏｎＸ)と出発地点Ｗの座標（ＬａｔＷ、ＬｏｎＷ）とを取得する。経由地は、目的地でもあり出発地でもあるので、経路探索において到着地点と出発地点との双方が設定される。また、ナビゲーション装置１００は、目的地となる建物Ｃの属性を参照し、到着地点ＹおよびＺの座標（ＬａｔＹ、ＬｏｎＹ)および（ＬａｔＺ、ＬｏｎＺ)を取得する。なお、出発地点や到着地点が複数取得した場合の選択方法については、実施例１と同様の方法でおこなうものとしても良いし、出発地点と到着地点との双方の属性を含む地点を優先的に選択しても良い。

ステップＳ５０１が終了すると、ナビゲーション装置１００は、ネットワークデータ２１３を参照して、出発地または該出発地に対応する出発地点から経由地または該経由地に対応する到着地点までの経路探索を行なうとともに、経由地または該経由地に対応する出発地点から目的地または該目的地に対応する到着地点までの経路探索を行う（ステップＳ５０２）。具体的には、ナビゲーション装置１００は、図１２の場合、出発地点Ｕの座標（ＬａｔＵ、ＬｏｎＵ)から到着地点Ｘの座標（ＬａｔＸ、ＬｏｎＸ)までの経路探索を行なうとともに、出発地点Ｗの座標（ＬａｔＷ、ＬｏｎＷ）から到着地点ＹおよびＺの座標（ＬａｔＹ、ＬｏｎＹ)および（ＬａｔＺ、ＬｏｎＺ)までの経路探索を行なう。
ステップＳ５０２が終了すると、ナビゲーション装置１００は実施例１のステップＳ４０の案内対象交差点設定処理へ移行する。

このように、実施例３では経由地に対応する到着地点までの経路探索と経由地に対応する出発地点からの経路探索とを行うので、経由する地物への最適なアクセスを考慮した経路探索を行える効果がある。

本発明は、必ずしも上述した実施例の全ての機能を備えている必要はなく、一部のみを実現するようにしてもよい。また、上述した内容に追加の機能を設けてもよい。
本発明は上述の実施例に限定されず、その趣旨を逸脱しない範囲で種々の構成を採ることができることはいうまでもない。例えば、実施例においてハードウェア的に構成されている部分は、ソフトウェア的に構成することもでき、その逆も可能である。

たとえば、実施例３において、経由地は複数個所入力され、複数の経由地間の経路探索を含む構成としても良い。具体的には、経由地から目的地への経路探索に経由地から他の経由地への経路探索が含まれることとなる。ナビゲーション装置１００は、ネットワークデータ２１３を参照して、出発地または該出発地に対応する出発地点から一以上の経由地または該経由地に対応する到着地点までの経路探索を行なうとともに、一以上の経由地または該経由地に対応する出発地点から他の経由地または他の経由地に対応する到着地点ならびに目的地または該目的地に対応する到着地点までの経路探索を行う。

本発明は、以下に示す経路探索方法として構成してもよい。
道路をノード、リンクで表したネットワークデータと、道路を含む地物を描画するポリゴンを記憶する地物データと、自動車が通行可能な道路として前記ネットワークデータが整備された道路上の点であって、前記目的地に対応する地物からいずれかの道路を通行して到着できる点である到着地点に関するデータとを格納する地図データベースを有するコンピュータによって、指定された目的地までの経路を探索する経路探索方法であって、
前記コンピュータが行うステップとして、
出発地および目的地を入力しメモリに記憶する入力ステップと、
前記地図データベースを参照して、前記目的地に対応する到着地点を取得しメモリに記憶する到着地点取得ステップと、
前記ネットワークデータを参照して、前記出発地から前記到着地点までの経路探索を行う経路探索ステップとを備える経路探索方法である。

また以下に示すコンピュータプログラムとして構成してもよい。
道路をノード、リンクで表したネットワークデータと、道路を含む地物を描画するポリゴンを記憶する地物データと、自動車が通行可能な道路として前記ネットワークデータが整備された道路上の点であって、前記目的地に対応する地物からいずれかの道路を通行して到着できる点である到着地点に関するデータとを格納する地図データベースを有するコンピュータによって、指定された目的地までの経路を探索するためのコンピュータプログラムであって、
出発地および目的地を入力しメモリに記憶する入力機能と、
前記地図データベースを参照して、前記目的地に対応する到着地点を取得しメモリに記憶する到着地点取得機能と、
前記ネットワークデータを参照して、前記出発地から前記到着地点までの経路探索を行う経路探索機能とをコンピュータに実現させるためのコンピュータプログラムである。

本発明は、ネットワークから外れた目的地までの経路探索、およびネットワークから外れた地点の地物の存在を考慮した経路案内に利用可能である。

１００…ナビゲーション装置
１０１…主制御部
１０２…送受信部
１０３…コマンド入力部
１０４…ＧＰＳ入力部
１０５…地図データベース記憶部
１０６…表示制御部
１０７…経路探索部
２００…サーバ
２０１…送受信部
２０２…データベース管理部
２１０…地図データベース記憶部
２１１…地物データ
２１２…文字データ
２１３…ネットワークデータ
３００…データベース生成装置
３０１…主制御部
３０２…送受信部
３０３…コマンド入力部
３０４…表示制御部
３０５…地図データベース記憶部
３０６…データベース整備部
３０７…到着地点算出部

Claims (3)

1. 指定された目的地までの経路を探索する経路探索システムであって、
   道路をノード、リンクで表したネットワークデータと、道路および建物を含む地物を描画するための地物データと、自動車が通行可能な道路として前記ネットワークデータが整備された道路上の点であって、前記目的地に対応する地物からいずれかの道路を通行して到着できる点である到着地点に関するデータとを格納する地図データベース記憶部と、
   出発地および目的地を入力する入力部と、
   前記目的地として前記地物が指定されたとき、前記地図データベース記憶部を参照して、該地物に対応する到着地点を取得する到着地点取得部と、
   前記ネットワークデータを参照して、前記出発地から前記到着地点までの経路探索を行う経路探索部とを備える経路探索システム。
2. 自動車が通行可能な道路をノード、リンクで表したネットワークデータと、道路および建物を含む地物を描画するための地物データと、前記ネットワークデータが整備された道路上の点であって前記地物からいずれかの道路を通行して到着できる点である出発地点に関するデータと、前記ネットワークデータが整備された道路上の点であって前記地物へいずれかの道路を通行して到着できる点である到着地点に関するデータとを格納する地図データベース記憶部と、
   出発地および目的地を入力する入力部と、
   前記出発地として前記地物が指定されたとき、前記地図データベース記憶部を参照して、該地物に対応する出発地点を取得する出発地点取得部と、
   前記目的地として前記地物が指定されたとき、前記地図データベース記憶部を参照して、該地物に対応する到着地点を取得する到着地点取得部と、
   前記ネットワークデータを参照して、前記出発地点から前記到着地点までの経路探索を行う経路探索部とを備える経路探索システム。
3. 自動車が通行可能な道路をノード、リンクで表したネットワークデータと、道路および建物を含む地物を描画するための地物データと、前記ネットワークデータが整備された道路上の点であって前記地物からいずれかの道路を通行して到着できる点である出発地点に関するデータと、前記ネットワークデータが整備された道路上の点であって前記地物へいずれかの道路を通行して到着できる点である到着地点に関するデータとを格納する地図データベース記憶部と、
   出発地、目的地および一以上の経由地を入力する入力部と、
   前記出発地または前記経由地として前記地物が指定されたとき、前記地図データベース記憶部を参照して、該地物に対応する出発地点を取得する出発地点取得部と、
   前記経由地または前記目的地として前記地物が指定されたとき、前記地図データベース記憶部を参照して、該地物に対応する到着地点を取得する到着地点取得部と、
   前記ネットワークデータを参照して、前記出発地または当該出発地に対応する出発地点から前記経由地または当該経由地に対応する到着地点までの経路探索を行うとともに、前記経由地または当該経由地に対応する出発地点から前記目的地または当該目的地に対応する到着地点までの経路探索を行う経路探索部とを備える経路探索システム。