経路探索システム
【課題】 ネットワークデータから離れた目的地に対して、適切な経路探索を実現する。
【解決手段】 ナビゲーション装置は、道路をリンク、ノードで表したネットワークデータを用いて経路探索を行う。目的地となるべき地物Ｈ２がネットワークのリンクＬ２から離れた地点である場合は、その地物からいずれかの道路をたどってネットワーク上にたどり着いた点を到着地点ＧＨとし、到着地点ＧＨを終点とする経路探索を行う。到着地点は、道路を描画するためのポリゴンデータを用いて探索することができる。到着地点が複数存在する場合には、出発点から到着地点までのコスト、および到着地点から目的地までのコスト等に基づいて、最適な到着地点を選択する。
このように到着地点を終点として経路探索することにより、無用な大回りなどをしなくてもよい適切な経路を探索することができる。
【解決手段】 ナビゲーション装置は、道路をリンク、ノードで表したネットワークデータを用いて経路探索を行う。目的地となるべき地物Ｈ２がネットワークのリンクＬ２から離れた地点である場合は、その地物からいずれかの道路をたどってネットワーク上にたどり着いた点を到着地点ＧＨとし、到着地点ＧＨを終点とする経路探索を行う。到着地点は、道路を描画するためのポリゴンデータを用いて探索することができる。到着地点が複数存在する場合には、出発点から到着地点までのコスト、および到着地点から目的地までのコスト等に基づいて、最適な到着地点を選択する。
このように到着地点を終点として経路探索することにより、無用な大回りなどをしなくてもよい適切な経路を探索することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、指定された目的地に向かう経路を探索する経路探索システムに関する。
【背景技術】
【０００２】
道路をリンク、およびノードで表したネットワークデータを用いて、指定された出発地から目的地までの経路を探索し、案内するナビゲーションシステムが普及している。ネットワークデータは、全ての道路に対して整備されている訳ではないため、経路探索の際には、ネットワーク上のリンク、ノードから離れた地点が目的地として指定されることもある。
【０００３】
特許文献１は、リンク、ノードから離れた地点が目的地として指定された場合、２種類のネットワークデータを利用して経路探索を行う技術を開示する。まず、目的地から最寄りのノードを求め、このノードを終点とする経路探索を行う。そして、終点から目的地までは、別途得られる補完データを用いて経路探索を行うのである。
【０００４】
特許文献２は、ネットワークデータから外れた領域を特定エリアと称し、ネットワークデータが整備された主要道路からその特定エリアに至る接続道路を求め、主要道路と接続道路との交点を案内ポイントとして経路探索する技術を開示する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−８４２５６号公報
【特許文献２】特許第３３８５９７５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来技術では、リンクから離れた目的地が指定された場合に、必ずしも適切な経路が得られないという課題があった。
図１は、従来技術における経路探索例を示す説明図である。
図中の領域では、道路ＲＷ１〜ＲＷ４に対しては、リンクＬＷ１〜ＬＷ４、ノードＮ１２、Ｎ２３、Ｎ３４、Ｎ４１からなるネットワークデータが整備されており、道路ＲＮにはネットワークデータが整備されていない。領域内には建物ＨＡ〜ＨＪが存在する。
経路探索の目的地として、建物ＨＢ内の点ＤＥ１が指定された場合を考える。点ＤＥ１は、ネットワークから外れた地点である。
【０００７】
特許文献１記載の技術によれば、指定された点ＤＥ１の最寄りのノードＮ２３を終点とする経路探索が行われる。しかし、地点ＤＥ１に向かうには、道路ＲＮを使う必要があるから、ノードＮ１２またはＮ４１を終点とする経路探索が行われるべきである。ノードＮ２３を終点とする経路探索では、ノードＮ１２、Ｎ４１を通過してノードＮ２３に向かう経路が得られるおそれがあり、不適切な経路となってしまうおそれがある。
【０００８】
特許文献２記載の技術によれば、例えば、図中の破線で示すように特定エリアＳＡを設け、特定エリアＳＡに対する案内ポイントＣＰを終点とする経路探索を行うことになる。しかし、この技術では、例えば、道路ＲＷ４から矢印ＡＨＣに示すように入るよう建てられている建物ＨＣが目的地として指定された場合も、案内ポイントＣＰに対する経路探索が行われてしまうことになり、必ずしも適切な経路が得られるとは言えない。
【０００９】
本発明は、これらの課題に鑑み、ネットワークから外れた地点が目的地に指定された場合でも、目的地の周囲の道路状況や、目的地として指定された建物等の構造を考慮した経路探索を行うことを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、指定された目的地までの経路を探索する経路探索システムとして構成することができる。経路探索システムは、地図データベース記憶部、入力部、到着地点取得部、および経路探索部を備える。
地図データベース記憶部は、ノードおよび走行レーンごとに独立して表現されたリンクで構成された道路のネットワークデータと、道路および建物を含む地物を描画するポリゴンを記憶する地物データとを格納する。ネットワークデータは、通行規制も踏まえて自動車の経路探索に使用可能な主ネットワークと、経路探索に使用可能ではあるが通行規制の整備が完全とは言えない準ネットワークなどを混在して用意してもよい。
【００１１】
地図データベース記憶部は、また到着地点に関するデータも記憶している。このデータは、地物データの一部として記憶させてもよいし、地物データと関連づけられた個別のデータとして用意してもよい。到着地点とは、上述の主ネットワーク、つまり自動車が通行可能な道路としてネットワークデータが整備された走行レーン上の点もしくはリンク上の点であって、目的地に対応する地物からいずれかの走行レーンを通行して到着できる点である。
以下、地図データベース記憶部に記憶された上述のデータ全体を地図データベースと称することもある。
入力部は、出発地および目的地を入力する。出発地は、ユーザの現在位置を自動的に入力するようにしてもよい。目的地は、地物データに含まれる特定の建物等を指定してもよいし、地図上で座標値を指定してもよい。
到着地点取得部は、地図データベース記憶部に記憶された地図データベースを参照して、目的地に対応する到着地点を取得する。
そして、経路探索部は、ネットワークデータを参照して、出発地から到着地点までの経路探索を行う。
【００１２】
本発明の経路探索システムによれば、指定された目的地の最寄りのノードではなく、到着地点を用いて経路探索を行う。到着地点は、目的地に対応する地物からいずれかの走行レーンを通行して到達できる主ネットワーク上の点であるから、逆に言えば、主ネットワークから目的地にいずれかの走行レーンを通行して向かうのに適した点となる。また、到着地点は、特許文献２にいう特定エリアのように地域に対して設定される点ではなく、それぞれの地物に対して得られる点であるから、各地物の構造を踏まえて適した点を得ることができる。従って、この到着地点を用いた経路探索を行うことにより、本発明は、目的地周辺の道路状況や、目的地の構造等を考慮した好適な経路を探索することが可能となる。
【００１３】
本発明において、到着地点は、地物データの一部として、または地物データと関連づけられた状態で建物等の地物ごとに設定されているから、到着地点取得部は、目的地として指定された地物に対応する到着地点のデータを読み込めば済む。目的地が座標値で指定された場合には、到着地点取得部は、指定された座標が対応する地物を特定し、その地物に対応する到着地点のデータを読み込めばよい。
【００１４】
他の態様として、次に示すように、到着地点を予め用意しない構成とすることもできる。
まず、地物データに、地物への出入口に面した道路上の点を指定する出入口点を記憶しておく。そして、到着地点取得部は、出入口点を探索開始点としてネットワークデータおよび地物データの少なくとも一方を用いた経路探索によって到着地点を得るのである。経路探索には、上述の通り、通行規制の整備が完全とは言えない準ネットワークや、ネットワークが一切整備されてはいない道路も用いることができる。ネットワークが整備されていない道路については、地物データに含まれる道路のポリゴンデータの連結具合をネットワークデータとして扱うことにより経路探索の対象とすることができる。
仮に、到着地点を予め地物データとして整備しておくと、ネットワークが更新された場合に従前の到着地点がネットワークから外れてしまうことが生じたり、従前の到着地点よりも地物に近い点を到着地点とできるのに、こうした点が利用できないなどの支障が生じるおそれがある。これに対し、上述のように、経路探索によって到着地点を求める態様によれば、これらの支障を回避し、その時々のネットワークデータに基づいて好適な到着地点を得ることができる。
【００１５】
到着地点は、目的地に対応する地物について一つに限る必要はなく、複数を取得してもよい。本発明において地図データベース記憶部に予め複数の到着地点を地物データとして格納しておいてもよい。また、到着地点を経路探索によって求める他の態様においては、経路探索によって複数の到着地点を求める方法をとってもよい。さらに、両者を併用し、地物データに到着地点を格納しておくとともに、経路探索によって追加の到着地点を求めるようにしてもよい。
このように複数の到着地点が取得される場合には、経路探索部は、経路探索の結果または目的地と到着地点との位置関係に基づく所定の抽出条件によって複数の到着地点の一つを選択すればよい。例えば、次に示す抽出条件を用いることができる。コストとは、経路探索で用いられる評価値であり、コストが小さいほど、経路として適していることを表す値である。（１）出発地からそれぞれの到着地点までの経路探索によるコスト（以下、「経路コスト」という）が最小となる到着地点を選択する。（２）経路コストと、目的地からそれぞれの到着地点までのコスト（以下、「到着地点コスト」という）の和が最小となる到着地点を選択する。（３）到着地点コストが最小となる到着地点を選択する。（４）出発地と目的地とを結ぶ線分までの距離が最短の到着地点を選択する。（５）到着地点から目的地までの移動手段が車の場合には、車での出入りに適した出入口線に対応する到着地点を選択する。
抽出条件は、これらの組合せであってもよいし、この他の条件を用いることもできる。
【００１６】
本発明は、経路案内システムに限らず、種々の態様で構成可能である。
例えば、上述のネットワークデータ、地物データを備えるコンピュータによって地図データベースを生成する地図データベース生成方法として構成してもよい。
この方法では、まず、地物について出入口点の指定を入力する。指定された出入口点は、地物データに格納してもよいし、地図データベースの生成が完了したら消去してもよい。
次に、出入口点を探索開始点とする経路探索によって、到着地点を求める。この経路探索には、先に説明したように、準ネットワークや道路ポリゴンを用いることができる。
そして、得られた到着地点を地物データに格納するのである。
この方法によれば、地物の出入口点を指定すれば、適した到着地点を自動的に得ることができる。従って、ネットワークを更新した場合でも、比較的軽い負荷で到着地点の整備が可能である。
【００１７】
本発明は、その他、コンピュータを用いた経路探索方法として構成してもよいし、かかる経路探索をコンピュータに実行させるためのコンピュータプログラムとして構成してもよい。また、かかるコンピュータプログラムを記録したコンピュータが読み取り可能な記録媒体として構成してもよい。記録媒体としては、フレキシブルディスクやＣＤ−ＲＯＭ、光磁気ディスク、ＩＣカード、ＲＯＭカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ）および外部記憶装置等、コンピュータが読取り可能な種々の媒体を利用できる。
【図面の簡単な説明】
【００１８】
【図１】従来技術における駐車場の探索方法を示す説明図である。
【図２】経路案内システムの構成を示す説明図である。
【図３】地図データベースの構造を示す説明図である。
【図４】到着地点の設定について示す説明図である。
【図５】地物データ整備処理のフローチャートである。
【図６】経路案内処理のフローチャートである。
【図７】到着地点取得処理のフローチャートである。
【図８】案内対象交差点設定処理のフローチャートである。
【図９】案内対象交差点設定例（１）を示す説明図である。
【図１０】案内対象交差点設定例（２）を示す説明図である。
【図１１】レーンネットワークの説明図である。
【図１２】レーンネットワークの説明図である。
【図１３】到着地点の説明図である。
【図１４】到着地点の説明図である。
【発明を実施するための形態】
【００１９】
本発明の実施例について以下の順序で説明する。
Ａ．システム構成：
Ｂ．データ構造：
Ｂ１．ネットワークデータ：
Ｂ２．文字データ：
Ｂ３．地物データ：
Ｂ４．到着地点の設定：
Ｃ．地物データの整備：
Ｄ．経路案内処理：
Ｄ１．全体処理：
Ｄ２．到着地点取得処理：
Ｄ３．案内対象交差点設定処理：
Ｄ４．案内例：
Ｅ．変形例：
【実施例１】
【００２０】
Ａ．システム構成：
図２は、案内システムの構成を示す説明図である。案内システムは、ナビゲーション装置１００として構成される。本実施例では、ナビゲーション装置１００は、地図データ等を提供するサーバ２００とネットワークＮＥ１で接続されており、サーバ２００から地図データベースの更新を受けられるものとした。ナビゲーション装置１００は、スタンドアロンで稼働する構成としてもよいし、その機能の一部をサーバ２００等で実行する構成としてもよい。
サーバ２００は、データベース生成装置としてのパーソナルコンピュータ３００とネットワークＮＥ２を介して接続されている。データベース生成装置３００は、オペレータの指示に従って、サーバ２００に格納されるデータベースの生成および更新を行うための装置である。
【００２１】
サーバ２００は、地図データベース記憶部２１０、送受信部２０１、およびデータベース管理部２０２を備えている。送受信部２０１、データベース管理部２０２は、ハードウェア的に構成してもよいが、本実施例では、これらの機能を実現するコンピュータプログラムをインストールすることによって、ソフトウェア的に構成するものとした。
【００２２】
送受信部２０１は、ナビゲーション装置１００およびデータベース生成装置３００とネットワークＮＥ１、ＮＥ２を介した通信を行う。本実施例では、地図データベース記憶部２１０のデータや、その提供・格納に関するコマンド等が通信される。
データベース管理部２０２は、ナビゲーション装置１００、データベース生成装置３００から要求された地図情報を、地図データベース記憶部２１０から読み出したり、データベース生成装置３００で生成された地図データを地図データベース記憶部２１０に格納する。
地図データベース記憶部２１０には、地物データ２１１、文字データ２１２、およびネットワークデータ２１３が格納されている。地物データ２１１は、道路や建物など地図に描画すべき地物のポリゴンデータである。文字データ２１２は、地図上に表示すべき文字情報である。例えば、建物の名称や地名などの文字情報が含まれる。ネットワークデータ２１３は、道路をノード、リンクのつながりで表したデータである。本実施例のネットワークデータ２１３には、主ネットワークデータと準ネットワークが含まれる。主ネットワークデータとは、現地調査によって通行規制が十分に整備されたデータであり、車両の経路探索に支障なく用いることができるデータとなっている。準ネットワークデータとは、通行規制の整備が十分とは言えないデータであり、車両の経路探索では、使用しない方が好ましいデータである。
【００２３】
ナビゲーション装置１００には、主制御部１０１の下で稼働する種々の機能ブロックが構成されている。本実施例では、主制御部１０１および各機能ブロックは、それぞれの機能を実現するソフトウェアをインストールすることによって構成したが、その一部または全部をハードウェア的に構成してもよい。
送受信部１０２は、サーバ２００とのネットワークＮＥ１を介した通信を行う。本実施例では、地図データベースおよびその提供を受けるためのコマンドの送受信が主として行われる。
コマンド入力部１０３は、ナビゲーション装置１００に設けられたボタン、レバー、タッチパネル等の操作を通じて、ユーザからの指示を入力する。本実施例における指示としては、経路探索の出発地、目的地の指定などが挙げられる。
ＧＰＳ入力部１０４は、ＧＰＳ（Global
Positioning System）を用いてユーザの現在位置を入力する。
地図データベース記憶部１０５は、サーバ２００から提供された地図データベースを格納する。本実施例では、サーバ２００が備える地図データベース記憶部２１０に記憶された地図データベースの全体をナビゲーション装置１００内の地図データベース記憶部１０５にも格納するものとしたが、経路探索や地図表示に必要となる部分のみを、その都度、サーバ２００から取得するものとしてもよい。
経路探索部１０７は、地図データベース記憶部１０５を参照して、経路探索を行う。
表示制御部１０６は、地図データベース記憶部１０５を用いてナビゲーション装置１００のディスプレイに地図および探索された経路等の案内を表示する。
【００２４】
データベース生成装置３００には、主制御部３０１の下で稼働する種々の機能ブロックが構成されている。本実施例では、主制御部３０１および各機能ブロックは、それぞれの機能を実現するソフトウェアをインストールすることによって構成したが、その一部または全部をハードウェア的に構成してもよい。
送受信部３０２は、サーバ２００とのネットワークＮＥ２を介した通信を行う。本実施例では、地図データベースおよびその管理のためのコマンドの送受信が主として行われる。
コマンド入力部３０３は、キーボードやマウスなどの操作を介してオペレータによる指示を入力する。
【００２５】
表示制御部３０４は、データベース生成装置３００のディスプレイに地図等を表示する。
地図データベース記憶部３０５は、サーバ２００の地図データベース記憶部２１０に記憶されている地図データベースを格納する。本実施例では、サーバ２００の地図データベース全体を格納するものとしたが、処理に必要な部分のみを格納するようにしてもよい。
到着地点算出部３０７は、地図データベース記憶部３０５に格納された地物に対して、到着地点を求める。到着地点とは、地物から道路をたどって主ネットワークデータ、つまり経路探索に使用できるネットワークデータが整備された道路まで到達した地点を言う。
データベース整備部３０６は、到着地点算出部３０７によって得られた到着地点を地図データベース記憶部３０５に格納し、サーバ２００の地図データベース記憶部２１０に記憶されている地図データベースを更新する。
【００２６】
Ｂ．データ構造：
図３は、地図データベースの構造を示す説明図である。地物データ、文字データ、ネットワークデータに格納される情報の概要を示した。
【００２７】
Ｂ１．ネットワークデータ：
ネットワークデータとは、道路をリンク、ノードで表したデータである。本実施例では、ネットワークデータとして主ネットワークデータと、準ネットワークデータの２種類が用意されている。図中に実線で示したリンクＬ１〜Ｌ４およびノードＮ１、Ｎ２が主ネットワークデータであり、破線で示したリンクＬ１１〜Ｌ１３およびノードＮ１１、Ｎ１２が準ネットワークデータである。
【００２８】
主ネットワークデータおよび準ネットワークデータともに、それぞれに属するリンクデータおよびノードデータを格納している。リンクデータは、それぞれのリンクを形成する点列の座標、国道・県道等の種別、車線数その他の属性情報や通行規制情報などを記録している。ノードデータは、座標値、通行規制などを記録している。
ただし、主ネットワークデータは、現地調査によって通行規制が十分に整備されたデータであり、車両の経路探索に支障なく用いることができるデータとなっている。これに対し、準ネットワークデータは、通行規制の整備が十分とは言えないデータであり、車両の経路探索では、使用しない方が好ましいデータである。本実施例でも、経路探索は原則として主ネットワークデータを用いて行うものとしている。
【００２９】
図１１に示すように、ネットワークデータには、実際の道路レーンに対応するレーンネットワークデータが対応付けられている。
リンクＬ１０１〜リンクＬ１０４に対応する道路がいずれも片側一車線である場合を例としてレーンネットワークデータのデータ構造について説明する。
レーンネットワークデータは、道路中心線ＬＣ１〜ＬＣ８に関するデータと交差点内走行線ＩＲ（図１１、図１２に示す点線１１０内に存在するすべての線）に関するデータとで構成される。
【００３０】
図１１に示すように、道路中心線ＬＣ１，ＬＣ２はネットワークデータのリンクＬ１０１に関連づけられている。同様に、道路中心線ＬＣ３，ＬＣ４はネットワークデータのリンクＬ１０２に関連づけられている。
また、交差点内走行線ＩＲは何れもネットワークデータのノードＮ１０１に関連づけられている。これらレーンネットワークデータを構成する道路中心線ＬＣ１〜ＬＣ８と交差点内走行線ＩＲとに関するデータは、地図データベース記憶部２１０に格納されている。各レーンネットワークデータには、固有のＩＤが付与されている。
本実施例では、到着地点には、このレーンネットワークデータを構成する道路中心線および交差点内走行線の上の所定位置が対応付けられている。
【００３１】
交差点内走行線は、１の道路におけるレーン（道路中心線）から進入可能な他の道路におけるレーン（道路中心線）にのみ接続されている。例えば、リンクＬ１０２に対応する道路の道路中心線ＬＣ４から進入可能な道路中心線は、道路中心線ＬＣ１，ＬＣ５，ＬＣ７である。従って、道路中心線ＬＣ４と接続関係にある交差点内走行線は、これら道路中心線ＬＣ１，ＬＣ５，ＬＣ７と接続されている交差点内走行線ＩＲ１〜ＩＲ３ということになる。
【００３２】
また、道路中心線および交差点内走行線に関するデータは何れも進行方向に関する属性情報を保持している。具体的には、図１２における道路中心線ＬＣ４，ＬＣ７は、図の右側から左側へ走行可能であることを示す属性情報を保持している。
図１２における交差点内走行線ＩＲ２は、道路中心線ＬＣ４から道路中心線ＬＣ７へ走行可能であることを示す属性情報を保持している。
なお、出発地から目的地までの経路を探索する際には、ネットワークデータ（リンク及びノード）を用い、レーンネットワークデータは目的地の到着地点を案内する際に用いるようにしてもよい。
【００３３】
Ｂ２．文字データ：
文字データ２１２は、地物の名称や地名などを表示する文字を規定するデータである。図中には、建物ＢＬＤの名称を表示するためのデータ例を示した。文字データは、内容、位置、地物、フォント、サイズなどの情報を格納する。
内容は、表示すべき文字列であり、図中の例では、「△△(株)」という会社名称である。
位置は、文字を表示する位置である。本実施例では、文字列の左下の点Ｐ５を基準点として、この座標値を指定するものとした。
地物は、文字が関連づけられる地物データのポリゴン名称である。
フォント、サイズは、表示する際のフォントおよびサイズの指定である。
この他、色、太字など、種々の属性を指定可能としてもよい。
【００３４】
Ｂ３．地物データ：
地物データ２１１について、建物Ｈ１を例にとって構造を示す。地物データ２１１は、建物、道路等の地物を描画するためのポリゴンデータであり、名称、形状、代表点、出入り口線、到着地点、属性などを格納している。
名称は、地物の名称である。ポリゴンに固有のＩＤを用いてもよい。
形状は、地物のポリゴンの頂点を示す座標の列である。図の例では、建物Ｈ１のポリゴンの頂点Ｐ１、Ｐ２、Ｐ３、Ｐ４の各座標が格納されている。
代表点は、地物の位置を表す地点Ｃの座標である。代表点は、地物の図心を用いることが多いが、任意に設定可能である。
出入口線は、地物と道路とを関連づけるための情報である。建物Ｈ１の場合、玄関から道路に出るための線分Ｄが出入口線として登録される。具体的には、線分Ｄの両端の座標が登録されることになる。出入口線は、線分Ｄのうち、道路上の端点のみを登録するものとしてもよい。また、出入口線は、建物や駐車場など、出入りを伴う地物に設定されるものであり、地物の全てに設定する必要はない。図の例では、建物ＢＬＤに対して正面の出入口線ＤＢ１および駐車場ＢＬＤＰ側の出入口線ＤＢ２、建物Ｈ２〜Ｈ４に対してそれぞれ出入口線ＤＨ２〜ＤＨ４、駐車場ＰＫに対して出入口線ＤＰＫが設定されている。出入口線に対して、人の出入りに使用する出入口、駐車場などの用途を示す情報を設定しておいてもよい。
【００３５】
到着地点Ｇは、地物の出入口線の道路上の端点から、いずれかの道路を経てたどりつけるネットワーク上の点である。道路を構成する走行レーン上の点ということもできる。建物Ｈ１の場合、図中に点線で示す通り、出入口線Ｄが関連づけられている道路Ｒ２１を経て、リンクＬ２に至ることができるため、リンクＬ２上に到着地点Ｇが設定されている。出入口線Ｄから道路Ｒ２１を図中右方向にたどり、ノードＮ１１で右折してノードＮ２に至る経路をとり、ノードＮ２を到着地点とすることもできる。本実施例では、建物Ｈ１からノードＮ２に至る道のりよりも、到着地点Ｇに至る道のりの方が短いから、このように設定した。到着地点は、一つに限定する必要はないから、ノードＮ２も到着地点に設定してもよい。
図の例では、建物Ｈ２〜Ｈ４に対する到着地点は点ＧＨと設定されている。建物ＢＬＤに対しては、点ＧＨおよび点ＧＢＬＤ２と設定されている。到着地点は、出入口線と同様、駐車場にも設定でき、図の例では、駐車場ＰＫに対して到着地点ＧＰＫが設定されている。駐車場ＰＫは、リンクＬ２に面しているため、出入口線ＤＰＫの端点と到着地点ＧＰＫが一致した状態となっている。
【００３６】
Ｂ４．到着地点の設定：
図４は、到着地点の設定について示す説明図である。建物ＢＬＤ１の出入口線ＤＢを対象とする到着地点について示した。
建物ＢＬＤ１の周辺の主ネットワークデータとしては、リンクＬ７、ノードＮ７およびリンクＬ５、Ｌ６およびノードＮ５、Ｎ６が存在する。準ネットワークデータとしては、破線で示したリンクＬ１４が存在する。
建物ＢＬＤ１の出入口線ＤＢからいずれかの道路を経て主ネットワークにたどりつく経路としては、図中に点線で示した３通りがあげられる。道路Ｒ２４を経てリンクＬ７にたどりつく経路、道路Ｒ２５を経てたリンクＬ６およびリンクＬ５にそれぞれたどりつく経路である。これらの各経路がリンクＬ７、Ｌ６、Ｌ５にたどりつく点が到着地点Ｇ７、Ｇ６、Ｇ５となる。
【００３７】
これらの到着地点は、経路探索によって求めることができる。本実施例では、それぞれの地物は、出入口線によって、いずれかの道路に関連づけられているから、出入口点、つまり地物への出入口に面した道路上の端点を始点とする経路探索によって到着地点を求めればよい。
この経路探索は、主ネットワークデータ、準ネットワークデータおよび道路のポリゴンの全てを用いてもよい。道路のポリゴンは、リンク、ノードで構成されている訳ではないが、隣接するポリゴンを指定するデータは持っているから、ポリゴン同士のつながり関係は規定されており、リンク、ノードと同様に、経路探索に使用することが可能である。出入口点を起点とする経路探索の結果、主ネットワークデータにたどり着いた点を到着地点とすればよい。
【００３８】
図の例のように、到着地点がＧ７、Ｇ６、Ｇ５の３点見いだされる場合、これらの３点を建物ＢＬＤ１の到着地点として用いてもよいし、例えば、地物からの道のりが最短の地点、地物からの距離が最短の地点、地物から到着地点までの経路と準ネットワークデータとの重複部分が多い点、地物から出発点に向かう方角に近い点などの基準で選択してもよい。
図の例においては、地物からの道のりや距離を基準として選べば、建物ＢＬＤ１に最も近い点Ｇ５が到着地点となる。準ネットワークデータとの重複部分を基準として選べば、点Ｇ６が到着地点となる。出発地が図の左端方向にある場合には、出発地の方角を基準として選べば、点Ｇ７が到着地点となる。
【００３９】
本実施例では、上述の手順で、到着地点を設定し、地物データ２１１に予め設定しておくものとした。到着地点は、予め設定しておくのではなく、経路探索などの処理の過程で求めるものとしてもよい。
【００４０】
Ｃ．地物データの整備：
図５は、地物データ整備処理のフローチャートである。データベース生成装置３００のデータベース整備部３０６、到着地点算出部３０７が主として実行する処理であり、ハードウェア的には、データベース生成装置３００のＣＰＵが実行する処理である。
【００４１】
ＣＰＵは、オペレータから指定された範囲の地図データを地図データベース記憶部３０５から読み込み、ディスプレイに地図を表示する（ステップＳ１０）。
ＣＰＵは、処理対象となる地物に対して、名称、地物のポリゴン形状、代表点、属性などの指示を入力する（ステップＳ１１）。既存の地物に対して処理を行う際には、これらの情報は、既に地物データに格納されているから、要更新箇所のみを修正すればよい。
また、ＣＰＵは、出入口線および用途の指定を入力する（ステップＳ１２）。出入口線は、地物と道路とを関連づけるための情報である。地物に対して複数の出入口線を設定してもよい。用途は、出入口線ごとに設定することができる。例えば、人の出入りに使用する出入口、駐車場などの形式で指定する。人の出入りに使用する出入口を、玄関、裏口などに細分化して設定してもよい。
【００４２】
ＣＰＵは、到着地点探索処理を行って、地物のそれぞれの出入口線に対応する到着地点を求める（ステップＳ１３）。この処理は、図４で説明した出入口点を始点とする経路探索である。
この経路探索は、主ネットワークデータ、準ネットワークデータおよび道路のポリゴンの全てを用いてもよい。道路のポリゴンは、リンク、ノードで構成されている訳ではないが、隣接するポリゴンを指定するデータは持っているから、ポリゴン同士のつながり関係は規定されており、リンク、ノードと同様に、経路探索に使用することが可能である。出入口点を起点とする経路探索の結果、主ネットワークデータに対応するレーンネットワークにたどり着いた点を到着地点とすればよい。
到着地点は、それぞれの出入口点に対して複数探索されることがある。このような場合、いずれかの到着地点に絞り込んで地物データに登録するようにしてもよいが、本実施例では、探索された到着地点は全て登録しておくものとした。こうすることにより、後述する経路探索における到着地点の選択肢が増え、より適した経路を提示できる可能性が増えるからである。
【００４３】
ＣＰＵは、以上の処理を踏まえ、名称、地物ポリゴン形状、代表点、属性、出入口線、用途、および到着地点のデータを地物データに格納し、地物データを更新する（ステップＳ１４）。
処理対象となるべき地物が他にもある場合には、オペレータの指示に従って、この処理を繰り返し実行する。
【００４４】
Ｄ．経路案内処理：Ｄ１．全体処理：
図６は、経路案内処理のフローチャートである。ナビゲーション装置１００の経路探索部１０７および表示制御部１０６が主として実行する処理であり、ハードウェア的にはナビゲーション装置１００のＣＰＵが実行する処理である。
【００４５】
ナビゲーション装置１００は、出発地および目的地を入力する（ステップＳ２０）。出発地は、ユーザが指定してもよいし、ＧＰＳなどで取得した現在位置を出発地に設定してもよい。
目的地は、地物を指定してもよいし、座標値で指定してもよい。
【００４６】
次に、ナビゲーション装置１００は、指定された目的地に対する到着地点を取得する（ステップＳ３０）。到着地点は走行レーン上の位置に設定されている。すなわち、到着地点は、走行レーン上の所定位置に対応する緯度・経度情報で表される。本実施例では、到着地点は地物データ２１１に格納されている。従って、目的地となる地物が指定されている場合は、指定された地物に対応する地物データから到着地点を読み出せばよい。目的地が座標で指定されている場合には、当該座標がいずれのポリゴンに含まれるかを特定し、特定されたポリゴンの地物データに対応する到着地点を読み出せばよい。また、座標に最も近い位置に存在する道路における走行レーン上の到着地点を読み出してもよい。地物に対して複数の到着地点が得られる場合もある。
到着地点取得処理の内容は後述する。
【００４７】
ナビゲーション装置１００は、得られた到着地点を起点とする経路探索を行う（ステップＳ５０）。
到着地点が複数得られている場合には、ナビゲーション装置１００は、経路案内の対象とすべき到着地点および経路を選択する。到着地点および経路を地図上に表示して、ユーザに直接、選択させる方法をとってもよい。また、ナビゲーション装置１００が何らかの選択条件に従って自動的に選択するようにしてもよい。選択には、種々の選択条件を適用可能であるが、本実施例では、次に示す３つの条件から、ユーザが予め選択した条件を用いるものとした。
（１）出発地からそれぞれの到着地点までの経路探索によるコスト（以下、「経路コスト」という）が最小となる到着地点を選択する。
（２）経路コストと、目的地からそれぞれの到着地点までのコスト（以下、「到着地点コスト」という）の和が最小となる到着地点を選択する。
（３）出発地と目的地とを結ぶ線分までの距離が最短の到着地点を選択する。つまり、出発地と目的地とを結ぶ線分に対して到着地点から垂線をおろし、その距離で評価する条件である。線分に対して垂線を引くことができない位置関係にある到着地点については、目的地までの直線距離を用いるものとする。この条件は、出発地から目的地との間に位置する到着地点を選択すれば、経路コストと到着地点コストとの総和が低い経路が得られるとの考え方に基づくものである。
【００４８】
なお、到着地点コストが最小となる到着地点を選択するものとしてもよい。この態様によれば、到着地点から出入口までを徒歩で移動する場合に、徒歩の移動負荷が最も軽くなる経路を案内することができる。もっとも、到着地点コストは目的地となる地物が指定された時点で一義的に決まるものであるから、到着地点コストが最小という条件を用いる場合には、到着地点を起点とする経路探索（ステップＳ５０）を行う前に、この条件に基づいて経路探索に使用すべき到着地点を決定しておくことが望ましい。こうすれば、経路探索は決定された到着地点についてのみ行えば足りるから、経路探索の処理負荷を軽減することも可能となる。
【００４９】
次に、到着地点が複数得られている場合における他の選択例について説明する。
図１３に示すように、ある地物としての施設５０に複数の到着地点５１〜５３が設定されている。この例では、施設５０の駐車場５４，５５へ案内するために、各到着地点５１〜５３も当該駐車場５４，５５に接している道路に対応する道路中心線ＬＣ１１〜ＬＣ１３上の位置にそれぞれ存在している。また、図１３に示す例では、道路に中央分離帯５６が存在しているため、リンクＬ１１１に対応する道路中心線ＬＣ１４上には到着地点が設定されていない。なお、図１３においてはノードＮ１１１に対応しておりレーンネットワークを構成する交差点内走行線については便宜上図示せず、リンクに対応する道路中心線を図示する。
【００５０】
このように、到着地点がレーンネットワークを構成する道路中心線上の位置に設定されている。従って、経路を探索する際に、走行レーンを考慮しつつ出発地から目的地までの距離が最短となるような到着地点を選択したり、左折により進入することができる駐車場への到着地点を選択したりすることで、ユーザに対して最適な案内が可能となる。
また、到着地点がレーンネットワークを構成する道路中心線上の位置に設定されており、当該道路中心線と関連性を持たせることで、中央分離帯が存在しており右折進入することができないような経路が探索されるといった事態を回避することができる。
【００５１】
なお、１の道路の上下線のいずれにも到着地点を設定することができる場合には、当該道路に対応するリンク上の点を到着地点としてもよい。具体的には、図１３に示すように、１つのリンクＬ１１２対応している道路中心線ＬＣ１２，ＬＣ１３はいずれも到着地点が設定可能である。従って、このような場合には図１４に示すように、リンクＬ１１２上に対応する点の位置座標を到着地点５７と設定してもよい。一方、リンクＬ１１２に対応している道路中心線ＬＣ１４については、中央分離帯５６が存在しているため施設５０の到着地点が設定できない。従って、リンクＬ１１１上に対応する点の位置座標を到着地点として採用することはない。
【００５２】
そして、案内対象交差点設定処理を行う（ステップＳ６０）。本実施例では、ナビゲーション装置１００は、経路案内時に、右左折などの経路の案内に加えて、危険箇所の案内など、ユーザに対して通行を支援するための案内を行う。案内対象交差点設定処理は、この案内を行う対象となる交差点を設定する処理である。本実施例で案内対象としたのは、次の２種類の交差点である。
第１は、仮想交差点の案内である。ネットワークデータは、全ての道路に整備されている訳ではないので、ネットワークデータ上は交差点として構成されていない部分であっても、実際には道路が交差している箇所が存在する。このような箇所を、ネットワークデータから見ると仮想的な交差点という意味で、本実施例では、仮想交差点と称する。本実施例では、このような仮想交差点の中から案内対象交差点を選択し、交差点の存在などをユーザに対して案内する。
第２は、要注意交差点の案内である。住宅に面した道路と交差する交差点では、幼児を含め人の出入りがあり、時には飛び出しなどの危険もある。本実施例では、このような交差点を案内対象交差点として、ユーザに対し注意喚起を行う。
これらの案内を行う案内対象交差点の設定処理の具体的内容については、後述する。
【００５３】
こうして経路案内のために要する情報が揃うと、ナビゲーション装置１００は、次の手順で経路案内を行う。
ユーザの現在位置を取得し（ステップＳ９０）、探索された経路および現在位置をディスプレイに表示する（ステップＳ９２）。経路の表示と併せて、経路の音声案内を行っても良い。
また、ナビゲーション装置１００は、案内対象交差点では、通行案内を出力する（ステップＳ９４）。先に説明した通り、仮想交差点の存在等を示したり、要注意交差点の注意喚起をしたりするのである。
以上の処理を、ナビゲーション装置１００は、ユーザが目的地に到着するまで（ステップＳ９６）、繰り返し実行する。
【００５４】
Ｄ２．到着地点取得処理：
図７は、到着地点取得処理のフローチャートである。経路案内処理（図６）のステップＳ３０に相当する処理であり、指定された目的地に対応する到着地点を得る処理である。
ナビゲーション装置１００は、目的地に対応する地物データを読み込む（ステップＳ３２）。目的地が地物を指定している場合には、指定に該当する地物データを読み込めばよい。目的地が座標で指定されている場合には、その座標点を含む地物の地物データを読み込む。
地物データに到着地点が設定されている場合（ステップＳ３４）、ナビゲーション装置１００は、設定されている到着地点データを読み込む（ステップＳ３６）。
到着地点が設定されていない場合には（ステップＳ３４）、ナビゲーション装置１００は、出入口線データを読み込み（ステップＳ３８）、到着地点探索処理を行って到着地点を得る（ステップＳ４０）。到着地点探索処理は、地物データ整備処理（図５）のステップＳ１３で説明した処理と同じである。
【００５５】
そして、ナビゲーション装置１００は、経路探索モードに応じて到着地点を選択する。
到着地点から目的地までは徒歩で向かう旨の探索モードが指定されている場合は（ステップＳ４２）、ナビゲーション装置１００は、到着地点から目的地までのコスト、つまり到着地点コストが短い到着地点を優先する（ステップＳ４４）。コストは、経路探索において、各経路を評価するための評価値であり、距離や移動に要する時間などに基づいて設定することができる。上り／下り坂、階段など道路の構造などに基づく移動負荷を加味して設定してもよい。ステップＳ４４では、到着地点から徒歩で移動することを考慮し、距離が短いなど、移動に要する労力が低い到着地点を選択することを意味している。
「優先」には、一つの到着地点を選択する態様、および複数の到着地点に対して優先度を設定する態様などが含まれる。後者の場合には、ステップＳ４４の条件に基づいて優先度を設定しておき、経路案内処理（図６）のステップＳ５０の処理における選択条件を併せて考慮して、案内対象となる到着地点を選択するようにしてもよい。
【００５６】
到着地点から目的地まで車で移動する旨の探索モードが指定されている場合は（ステップＳ４２）、ナビゲーション装置１００は、出入口線の用途を参照し、駐車場の出入口線に対応する到着地点を優先する（ステップＳ４６）。到着地点から目的地までは、通行規制等の調査が十分になされていない道路なので、幅員が足りないなど、車の通行に適しない道路が含まれるおそれもある。しかし、駐車場に対応した到着地点であれば、それ以外の到着地点に比べて、到着地点から目的地までの経路も車の通行に適している可能性が高い。ステップＳ４６の態様によれば、目的地に到着した時に車を駐車できる出入口に案内できるだけでなく、目的地まで車で移動するのに適した到着地点を優先することができる。
【００５７】
Ｄ３．案内対象交差点設定処理：
図８は、経路案内交差点設定処理のフローチャートである。経路案内処理（図６）のステップＳ６０に相当する処理であり、仮想交差点および注意喚起の案内を行う地点を設定する処理である。
【００５８】
ナビゲーション装置１００は、経路上の到着地点を抽出し（ステップＳ６２）、未処理の到着地点を処理対象として選択する（ステップＳ６４）。
そして、この到着地点に対応する全ての地物を抽出する（ステップＳ６６）。到着地点は、地物からいずれかの道路をたどって主ネットワークに到達した点であるから、複数の地物に対する到着地点が同一の点となることもある。ステップＳ６６では、ナビゲーション装置１００は、地物データから、処理対象の到着地点に対応する地物を全て検索する。
【００５９】
検索された地物に駐車場がある場合（ステップＳ６８）、ナビゲーション装置１００は、駐車場の位置に基づき交差点形状を特定し（ステップＳ７０）、交差点となっている箇所について（ステップＳ７２）、仮想交差点に設定する（ステップＳ７４）。
【００６０】
ステップＳ７０〜Ｓ７４の処理内容について具体例で説明する。
図９は案内対象交差点設定例（１）を示す説明図である。リンクＬ６０の周辺に、駐車場Ｐ６１〜Ｐ６５が存在する例を示した。それぞれは代表点が点Ｃ６１〜Ｃ６５であり、到着地点Ｇ６１〜Ｇ６３、出入口線Ｄ６１〜Ｄ６５が設定されている。
駐車場Ｐ６１の場合、到着地点Ｇ６１はリンクＬ６０上に存在するが、リンクＬ６０に面しており、交差点とはなっていないため、仮想交差点には設定しない。リンクＬ６０を走行しているユーザから視認できる駐車場を案内対象とする必要はないからである。
交差点となっているか否かの判断は、種々の方法を用いることができる。本実施例では、出入口線Ｄ６１の端点が到着地点Ｇ６１と一致している場合には交差点ではないと判断し、案内対象から除外するものとした。駐車場Ｐ６１の代表点Ｃ６１とリンクＬ６０との距離が道路の幅員程度である場合に交差点でないと判断する方法をとることもできる。
【００６１】
到着地点Ｇ６２の場合には、リンクＬ６０の右側にのみ駐車場Ｐ６２が存在することが分かる。従って、ナビゲーション装置１００は、「三叉路」と判断する。
到着地点Ｇ６３の場合には、リンクＬ６０の右側に駐車場Ｐ６３、Ｐ６４が存在し、左側に駐車場Ｐ６５が存在する。従って、ナビゲーション装置１００は、「交差点」または「四叉路」と判断する。
このように、駐車場とリンクとの距離、およびリンクの左右いずれに駐車場が配置されているかに応じて、ナビゲーション装置１００は交差点形状を判断することができる。
なお、図９において到着地点Ｇ６１〜Ｇ６３はリンクＬ６０上に存在しているが、図１３に示すように、リンクに対応する道路の走行レーン上に存在する態様としてもよい。
【００６２】
駐車場に関する処理を終えると、ナビゲーション装置１００は、到着地点に対応する「住宅」の数が２以上の場合には（ステップＳ７６）、要注意交差点に設定する（ステップＳ７８）。
この処理について具体例で説明する。
図１０は案内対象交差点設定例（２）を示す説明図である。リンクＬ７０の周辺に、住宅Ｈ７１〜Ｈ７９が存在する例を示した。それぞれは代表点が点Ｃ７１〜Ｃ７９であり、到着地点Ｇ７１〜Ｇ７３、Ｇ７５、Ｇ７７、出入口線Ｄ７１〜Ｄ７９が設定されている。
【００６３】
到着地点Ｇ７１、Ｇ７２は、対応する住宅数が１軒であるため、ステップＳ７６の判断基準により、要注意交差点から除外される。到着地点Ｇ７１については、駐車場の場合と同様、住宅Ｈ７１がリンクＬ７０に面していると判断し、要注意交差点から除外するものとしてもよい。
到着地点Ｇ７３は、リンクＬ７０の右側に住宅Ｈ７３、Ｈ７４の２軒が存在する。到着地点Ｇ７４は、リンクＬ７０の右側に住宅Ｈ７５、左側に住宅Ｈ７６が存在する。到着地点Ｇ７７は、リンクＬ７０の右側に住宅Ｈ７７、Ｈ７８の２軒、左側に住宅Ｈ７９が存在する。従って、到着地点Ｇ７３、Ｇ７５、Ｇ７７は、それぞれ２軒以上の住宅が対応しているから、要注意交差点に設定される。
【００６４】
ナビゲーション装置１００は、以上の処理を経路上の全ての到着地点について行い、案内対象交差点を設定する。
このように、本実施例では、駐車場に対応する到着地点のうち交差点となっている地点、および２軒以上の住宅に対応している到着地点が案内対象交差点として設定されることになる。
【００６５】
Ｄ４．案内例：
図９を参照しながら、駐車場が存在する場合の案内対象交差点に対する案内例を説明する。
図９に示す通り、点Ｇ６２、Ｇ６３の部分に三叉路および四叉路が存在するが、リンクＬ６０にはこれらの点にノードは設けられていないから、リンクＬ６０を見る限り、点Ｇ６２、Ｇ６３の交差点は把握することができない。しかし、点Ｇ６２、Ｇ６３は、それぞれ駐車場に対する到着地点であるから、これらの地点は、車が出入りできる程度の道路と交差していることが分かる。実施例のナビゲーション装置１００は、このような状態を考慮して、点Ｇ６２、Ｇ６３の仮想交差点を案内対象交差点と設定し、交差点である旨の案内を行う。
【００６６】
具体的には、交差点Ｇ６２にさしかかるところで、「前方に三叉路があります」と案内したり、交差点Ｇ６３にさしかかるところで、「前方に交差点（または四叉路）があります」と案内することができる。これらの案内とともに、「車が出てくる可能性があります」と注意喚起をしてもよい。
また、図９の点Ｇ６２よりも先の交差点で右折する場合は、点Ｇ６２の三叉路を踏まえて、「この先、三叉路の次の交差点で右折です」のように案内することも可能である。こうすることにより、ユーザが誤って点Ｇ６２の交差点を右折してしまうことを回避することができる。
【００６７】
また、点Ｇ６２のように、進行方向に対して右側にのみ駐車場が位置する場合には、車が出てくることによる危険度は比較的低いと判断して通行上の注意喚起を省略してもよい。左側にのみ駐車場が位置する場合には、ユーザの進行する車線に近く危険度が認められると考えて、注意喚起をしてもよいし、左右双方に駐車場が位置する場合に比べれば危険度が低いと考えて、注意喚起を省略するようにしてもよい。
【００６８】
本実施例では、到着地点Ｇ６２を利用して、駐車場Ｐ６２までの経路案内をすることもできる。つまり、ネットワークデータを利用して到着地点Ｇ６２までの経路を探索し、到着地点Ｇ６２から駐車場Ｐ６２までの経路は、道路のポリゴンデータを用いて案内するのである。
このような場合、仮にネットワークデータだけを利用した案内を行おうとすれば、ネットワークデータ上は、点Ｇ６２は交差点と認識されてはいないから、せいぜい「目的地付近です」という程度の案内しかすることができない。
これに対し、本実施例では、点Ｇ６２を交差点と認識することができることを利用して、「次の交差点を右折です」という経路案内を行っても良い。こうすることにより、ユーザにより適切な情報を提示することが可能となる。
【００６９】
図１０を参照しながら、住宅が存在する場合の案内対象交差点に対する案内例を説明する。
住宅に対応する到着地点は、人が飛び出してくる可能性がある要注意交差点として案内を行う。従って、点Ｇ７３、Ｇ７５、Ｇ７７にさしかかるところで、「この先の交差点は、人の出入りがあるかも知れません。注意して下さい」のように案内することができる。
この案内に交差点の形状を反映させてもよい。
例えば、点Ｇ７３では、「右側から人が出てくるかも知れません」、点Ｇ７５、Ｇ７７では、「左右から人が出てくるかも知れません」のように、方向を示して注意を喚起することができる。
【００７０】
注意喚起の方法は、到着地点に対応する住宅数に応じて変化させてもよい。図１０の到着地点Ｇ７３、点Ｇ７５は２軒が対応しているのに対し、到着地点Ｇ７７は３軒が対応しているから危険度が高いと判断し、より強調した態様で注意喚起してもよい。例えば、注意喚起するメッセージの内容を変化させてもよいし、音声案内のトーンや音量、画面表示の明度、色などで強調してもよい。
【００７１】
実施例では、住宅数が２以上の交差点を注意喚起の対象としたが（図８のステップＳ７６）、この軒数は任意に設定可能であり、更に多くの軒数を判断基準値としてもよい。判断基準値を大きくすれば、案内が行われる頻度が下がるため、逆に、案内が行われた時のユーザの注意を効果的に喚起することができる。
【００７２】
要注意交差点での案内については、住宅に対応する到着地点が経路に沿って現れる密度を求め、その密度に応じて、注意喚起のための情報提示の内容を設定してもよい。
図１０に示す点Ｇ７７、Ｇ７５、Ｇ７３が比較的接近している場合、各交差点ごとに「人が出てくる可能性あります」という案内が行われると、ユーザはこうした案内に麻痺したようになってしまい、注意喚起の効果が低くなることがある。
そこで、このように所定の密度を超えて要注意交差点が存在する場合には、「しばらく飛び出しの危険がある地域を通行いたします」のように地域全体に対する注意喚起の態様をとってもよい。図１０のリンクＬ７０を下側から上側に向かって走行している場合には、点Ｇ７７にさしかかるところで、点Ｇ７７、Ｇ７５、Ｇ７３に対する総合的な案内として、上述のように地域全体に対する注意喚起を行うのである。
【００７３】
別の態様として、要注意交差点の密度が高い場合には、要注意交差点とするか否かの判断基準値（図８のステップＳ７６の値）を増大させ、判断基準を厳しくしてもよい。図１０の点Ｇ７７、Ｇ７５、Ｇ７３の地域に対しては、ナビゲーション装置１００は、例えば、判断基準値を３軒に変更するのである。こうすることで、点Ｇ７７のみが要注意交差点となるから、注意喚起が頻繁に行われる事態を回避することができる。具体的な処理態様としては、案内対象交差点設定処理（図８）を実行した後、要注意交差点の密度を算出し、密度が所定値を超える地域に対しては、ステップＳ７６の判断基準値を増大させた上で、再度、案内対象交差点設定処理（図８）を実行する方法をとることができる。
【００７４】
Ｅ．変形例：
実施例では、仮想交差点および要注意交差点の例を示したが、実施例の案内は、到着地点の種別に応じて種々の態様で適用することができる。例えば、到着地点がレストランや店舗に対応している場合、その密度に応じて、「右側にレストラン街があります」、「○○店街があります」のような案内を行っても良い。経路探索を行う際に、目的地に向かう途中で食事をとるなどの目的を設定した場合には、レストランに対応した到着地点を抽出し、経路案内の過程で、「右側にイタリアンレストランがあります」のように目的に応じた情報を提示してもよい。このように到着地点と関連づけた地物の種別に応じて情報を提示することにより、ユーザが目的地として選択していない地物について、経路から離れたところにある地物であってもユーザの意図に合致した情報を提示可能となる。
【００７５】
また実施例では、経路案内を行った上で種々の情報提示をする例を示したが、本発明は、経路案内を行わない場合でも適用可能である。
例えば、図１０において、リンクＬ７０上をユーザが走行している場合には、ユーザの現在位置を検出し、その前方にある到着点について、「人が出てくる可能性あります」などの注意喚起をすることができる。ユーザの経路がわかっていない場合であっても、現在位置の変化から進行方向は判断できるため、前方に位置する交差点か否かは容易に判断可能である。
音声で注意喚起を行う場合には、注意喚起の対象となる交差点をユーザがほぼ確実に通行すると判断できる時点まで待つようにしてもよい。例えば、図１０の点Ｇ７７からリンクＬ７０を上方に向かってユーザが走行している場合を考える。ユーザは、点Ｇ７５を通過して直進するかも知れないし、ここで右左折するかも知れない。このような状況で点Ｇ７３の注意喚起を行うと、かえってユーザを混乱させかねない。しかし、ユーザが点Ｇ７５を通過した後は、Ｕターンでもしない限り点Ｇ７３を通過することが明らかである。このように、ユーザの現在位置および進行方向を考慮して、通過が確実と判断されるまで案内を行うタイミングを遅らせる態様をとることにより、ユーザの混乱を回避することができる。
【００７６】
この判断は、ユーザの前方に位置する到着地点Ｇ７３、Ｇ７２、Ｇ７１について、ユーザの現在位置（例えば点Ｇ７５）との間に分岐または他の到着地点が存在するか否かに基づいて判断することができる。到着地点Ｇ７１、Ｇ７２と点Ｇ７７との間には、到着地点Ｇ７３が存在するのに対し、到着地点Ｇ７３と点Ｇ７５との間には分岐等は存在しない。このような場合には、到着地点Ｇ７３を通過する可能性が高いと判断し、注意喚起を行うようにすればよい。
注意喚起は、音声だけでなく表示によることもできる。例えば、到着地点Ｇ７３，Ｇ７２等を危険度に応じて赤などの目立つ色で表示する態様をとることができる。このように表示によって注意喚起する場合には、ユーザの混乱を招くおそれが低いから、現在位置から所定範囲内にある到着地点を対象としても
【００７７】
本発明は、必ずしも上述した実施例の全ての機能を備えている必要はなく、一部のみを実現するようにしてもよい。また、上述した内容に追加の機能を設けてもよい。
本発明は上述の実施例に限定されず、その趣旨を逸脱しない範囲で種々の構成を採ることができることはいうまでもない。例えば、実施例においてハードウェア的に構成されている部分は、ソフトウェア的に構成することもでき、その逆も可能である。
【００７８】
本発明は、以下に示す経路探索方法として構成してもよい。
道路をノード、リンクで表したネットワークデータと、道路を含む地物を描画するポリゴンを記憶する地物データと、自動車が通行可能な道路として前記ネットワークデータが整備された道路上の点であって、前記目的地に対応する地物からいずれかの道路を通行して到着できる点である到着地点に関するデータとを格納する地図データベースを有するコンピュータによって、指定された目的地までの経路を探索する経路探索方法であって、前記コンピュータが行うステップとして、出発地および目的地を入力しメモリに記憶する入力ステップと、前記地図データベースを参照して、前記目的地に対応する到着地点を取得しメモリに記憶する到着地点取得ステップと、前記ネットワークデータを参照して、前記出発地から前記到着地点までの経路探索を行う経路探索ステップとを備える経路探索方法である。
【００７９】
また以下に示すコンピュータプログラムとして構成してもよい。
道路をノード、リンクで表したネットワークデータと、道路を含む地物を描画するポリゴンを記憶する地物データと、自動車が通行可能な道路として前記ネットワークデータが整備された道路上の点であって、前記目的地に対応する地物からいずれかの道路を通行して到着できる点である到着地点に関するデータとを格納する地図データベースを有するコンピュータによって、指定された目的地までの経路を探索するためのコンピュータプログラムであって、出発地および目的地を入力しメモリに記憶する入力機能と、前記地図データベースを参照して、前記目的地に対応する到着地点を取得しメモリに記憶する到着地点取得機能と、前記ネットワークデータを参照して、前記出発地から前記到着地点までの経路探索を行う経路探索機能とをコンピュータに実現させるためのコンピュータプログラムである。
【００８０】
また以下に示す地図データベース生成方法として構成してもよい。
生成されるべき地図データベースの基礎データとして、自動車が通行可能な道路を表わしておりノード、リンクで構成されたネットワークデータと、道路および建物を含む地物を描画するための地物データと、各道路を構成する走行レーンごとに規定されており前記リンクと対応付けられているレーンネットワークデータとを備えるコンピュータによって、指定された目的地までの経路探索に用いられる地図データベースを生成する地図データベース生成方法であって、前記コンピュータが行うステップとして、オペレータによる前記地物データに格納された前記建物について、該建物への出入口に面した前記走行レーン上の点もしくは前記リンク上の点を指定する出入口点の指定を入力しメモリに記憶するステップと、前記出入口点を探索開始点として前記ネットワークデータおよび前記地物データの少なくとも一方を用いた経路探索によって、前記リンクに対応する点もしくは前記走行レーンに対応する点であって、前記出入口点からいずれかの道路を通行して到着できる点である到着地点を求め、メモリに記憶するステップと、前記到着地点を、前記地物に関連づけて前記地物データに格納するステップとを備える地図データベース生成方法。
【産業上の利用可能性】
【００８１】
本発明は、ネットワークから外れた目的地までの経路探索、およびネットワークから外れた地点の地物の存在を考慮した経路案内に利用可能である。
【符号の説明】
【００８２】
１００…ナビゲーション装置
１０１…主制御部
１０２…送受信部
１０３…コマンド入力部
１０４…ＧＰＳ入力部
１０５…地図データベース記憶部
１０６…表示制御部
１０７…経路探索部
２００…サーバ
２０１…送受信部
２０２…データベース管理部
２１０…地図データベース記憶部
２１１…地物データ
２１２…文字データ
２１３…ネットワークデータ
３００…データベース生成装置
３０１…主制御部
３０２…送受信部
３０３…コマンド入力部
３０４…表示制御部
３０５…地図データベース記憶部
３０６…データベース整備部
３０７…到着地点算出部
【技術分野】
【０００１】
本発明は、指定された目的地に向かう経路を探索する経路探索システムに関する。
【背景技術】
【０００２】
道路をリンク、およびノードで表したネットワークデータを用いて、指定された出発地から目的地までの経路を探索し、案内するナビゲーションシステムが普及している。ネットワークデータは、全ての道路に対して整備されている訳ではないため、経路探索の際には、ネットワーク上のリンク、ノードから離れた地点が目的地として指定されることもある。
【０００３】
特許文献１は、リンク、ノードから離れた地点が目的地として指定された場合、２種類のネットワークデータを利用して経路探索を行う技術を開示する。まず、目的地から最寄りのノードを求め、このノードを終点とする経路探索を行う。そして、終点から目的地までは、別途得られる補完データを用いて経路探索を行うのである。
【０００４】
特許文献２は、ネットワークデータから外れた領域を特定エリアと称し、ネットワークデータが整備された主要道路からその特定エリアに至る接続道路を求め、主要道路と接続道路との交点を案内ポイントとして経路探索する技術を開示する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−８４２５６号公報
【特許文献２】特許第３３８５９７５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来技術では、リンクから離れた目的地が指定された場合に、必ずしも適切な経路が得られないという課題があった。
図１は、従来技術における経路探索例を示す説明図である。
図中の領域では、道路ＲＷ１〜ＲＷ４に対しては、リンクＬＷ１〜ＬＷ４、ノードＮ１２、Ｎ２３、Ｎ３４、Ｎ４１からなるネットワークデータが整備されており、道路ＲＮにはネットワークデータが整備されていない。領域内には建物ＨＡ〜ＨＪが存在する。
経路探索の目的地として、建物ＨＢ内の点ＤＥ１が指定された場合を考える。点ＤＥ１は、ネットワークから外れた地点である。
【０００７】
特許文献１記載の技術によれば、指定された点ＤＥ１の最寄りのノードＮ２３を終点とする経路探索が行われる。しかし、地点ＤＥ１に向かうには、道路ＲＮを使う必要があるから、ノードＮ１２またはＮ４１を終点とする経路探索が行われるべきである。ノードＮ２３を終点とする経路探索では、ノードＮ１２、Ｎ４１を通過してノードＮ２３に向かう経路が得られるおそれがあり、不適切な経路となってしまうおそれがある。
【０００８】
特許文献２記載の技術によれば、例えば、図中の破線で示すように特定エリアＳＡを設け、特定エリアＳＡに対する案内ポイントＣＰを終点とする経路探索を行うことになる。しかし、この技術では、例えば、道路ＲＷ４から矢印ＡＨＣに示すように入るよう建てられている建物ＨＣが目的地として指定された場合も、案内ポイントＣＰに対する経路探索が行われてしまうことになり、必ずしも適切な経路が得られるとは言えない。
【０００９】
本発明は、これらの課題に鑑み、ネットワークから外れた地点が目的地に指定された場合でも、目的地の周囲の道路状況や、目的地として指定された建物等の構造を考慮した経路探索を行うことを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、指定された目的地までの経路を探索する経路探索システムとして構成することができる。経路探索システムは、地図データベース記憶部、入力部、到着地点取得部、および経路探索部を備える。
地図データベース記憶部は、ノードおよび走行レーンごとに独立して表現されたリンクで構成された道路のネットワークデータと、道路および建物を含む地物を描画するポリゴンを記憶する地物データとを格納する。ネットワークデータは、通行規制も踏まえて自動車の経路探索に使用可能な主ネットワークと、経路探索に使用可能ではあるが通行規制の整備が完全とは言えない準ネットワークなどを混在して用意してもよい。
【００１１】
地図データベース記憶部は、また到着地点に関するデータも記憶している。このデータは、地物データの一部として記憶させてもよいし、地物データと関連づけられた個別のデータとして用意してもよい。到着地点とは、上述の主ネットワーク、つまり自動車が通行可能な道路としてネットワークデータが整備された走行レーン上の点もしくはリンク上の点であって、目的地に対応する地物からいずれかの走行レーンを通行して到着できる点である。
以下、地図データベース記憶部に記憶された上述のデータ全体を地図データベースと称することもある。
入力部は、出発地および目的地を入力する。出発地は、ユーザの現在位置を自動的に入力するようにしてもよい。目的地は、地物データに含まれる特定の建物等を指定してもよいし、地図上で座標値を指定してもよい。
到着地点取得部は、地図データベース記憶部に記憶された地図データベースを参照して、目的地に対応する到着地点を取得する。
そして、経路探索部は、ネットワークデータを参照して、出発地から到着地点までの経路探索を行う。
【００１２】
本発明の経路探索システムによれば、指定された目的地の最寄りのノードではなく、到着地点を用いて経路探索を行う。到着地点は、目的地に対応する地物からいずれかの走行レーンを通行して到達できる主ネットワーク上の点であるから、逆に言えば、主ネットワークから目的地にいずれかの走行レーンを通行して向かうのに適した点となる。また、到着地点は、特許文献２にいう特定エリアのように地域に対して設定される点ではなく、それぞれの地物に対して得られる点であるから、各地物の構造を踏まえて適した点を得ることができる。従って、この到着地点を用いた経路探索を行うことにより、本発明は、目的地周辺の道路状況や、目的地の構造等を考慮した好適な経路を探索することが可能となる。
【００１３】
本発明において、到着地点は、地物データの一部として、または地物データと関連づけられた状態で建物等の地物ごとに設定されているから、到着地点取得部は、目的地として指定された地物に対応する到着地点のデータを読み込めば済む。目的地が座標値で指定された場合には、到着地点取得部は、指定された座標が対応する地物を特定し、その地物に対応する到着地点のデータを読み込めばよい。
【００１４】
他の態様として、次に示すように、到着地点を予め用意しない構成とすることもできる。
まず、地物データに、地物への出入口に面した道路上の点を指定する出入口点を記憶しておく。そして、到着地点取得部は、出入口点を探索開始点としてネットワークデータおよび地物データの少なくとも一方を用いた経路探索によって到着地点を得るのである。経路探索には、上述の通り、通行規制の整備が完全とは言えない準ネットワークや、ネットワークが一切整備されてはいない道路も用いることができる。ネットワークが整備されていない道路については、地物データに含まれる道路のポリゴンデータの連結具合をネットワークデータとして扱うことにより経路探索の対象とすることができる。
仮に、到着地点を予め地物データとして整備しておくと、ネットワークが更新された場合に従前の到着地点がネットワークから外れてしまうことが生じたり、従前の到着地点よりも地物に近い点を到着地点とできるのに、こうした点が利用できないなどの支障が生じるおそれがある。これに対し、上述のように、経路探索によって到着地点を求める態様によれば、これらの支障を回避し、その時々のネットワークデータに基づいて好適な到着地点を得ることができる。
【００１５】
到着地点は、目的地に対応する地物について一つに限る必要はなく、複数を取得してもよい。本発明において地図データベース記憶部に予め複数の到着地点を地物データとして格納しておいてもよい。また、到着地点を経路探索によって求める他の態様においては、経路探索によって複数の到着地点を求める方法をとってもよい。さらに、両者を併用し、地物データに到着地点を格納しておくとともに、経路探索によって追加の到着地点を求めるようにしてもよい。
このように複数の到着地点が取得される場合には、経路探索部は、経路探索の結果または目的地と到着地点との位置関係に基づく所定の抽出条件によって複数の到着地点の一つを選択すればよい。例えば、次に示す抽出条件を用いることができる。コストとは、経路探索で用いられる評価値であり、コストが小さいほど、経路として適していることを表す値である。（１）出発地からそれぞれの到着地点までの経路探索によるコスト（以下、「経路コスト」という）が最小となる到着地点を選択する。（２）経路コストと、目的地からそれぞれの到着地点までのコスト（以下、「到着地点コスト」という）の和が最小となる到着地点を選択する。（３）到着地点コストが最小となる到着地点を選択する。（４）出発地と目的地とを結ぶ線分までの距離が最短の到着地点を選択する。（５）到着地点から目的地までの移動手段が車の場合には、車での出入りに適した出入口線に対応する到着地点を選択する。
抽出条件は、これらの組合せであってもよいし、この他の条件を用いることもできる。
【００１６】
本発明は、経路案内システムに限らず、種々の態様で構成可能である。
例えば、上述のネットワークデータ、地物データを備えるコンピュータによって地図データベースを生成する地図データベース生成方法として構成してもよい。
この方法では、まず、地物について出入口点の指定を入力する。指定された出入口点は、地物データに格納してもよいし、地図データベースの生成が完了したら消去してもよい。
次に、出入口点を探索開始点とする経路探索によって、到着地点を求める。この経路探索には、先に説明したように、準ネットワークや道路ポリゴンを用いることができる。
そして、得られた到着地点を地物データに格納するのである。
この方法によれば、地物の出入口点を指定すれば、適した到着地点を自動的に得ることができる。従って、ネットワークを更新した場合でも、比較的軽い負荷で到着地点の整備が可能である。
【００１７】
本発明は、その他、コンピュータを用いた経路探索方法として構成してもよいし、かかる経路探索をコンピュータに実行させるためのコンピュータプログラムとして構成してもよい。また、かかるコンピュータプログラムを記録したコンピュータが読み取り可能な記録媒体として構成してもよい。記録媒体としては、フレキシブルディスクやＣＤ−ＲＯＭ、光磁気ディスク、ＩＣカード、ＲＯＭカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ）および外部記憶装置等、コンピュータが読取り可能な種々の媒体を利用できる。
【図面の簡単な説明】
【００１８】
【図１】従来技術における駐車場の探索方法を示す説明図である。
【図２】経路案内システムの構成を示す説明図である。
【図３】地図データベースの構造を示す説明図である。
【図４】到着地点の設定について示す説明図である。
【図５】地物データ整備処理のフローチャートである。
【図６】経路案内処理のフローチャートである。
【図７】到着地点取得処理のフローチャートである。
【図８】案内対象交差点設定処理のフローチャートである。
【図９】案内対象交差点設定例（１）を示す説明図である。
【図１０】案内対象交差点設定例（２）を示す説明図である。
【図１１】レーンネットワークの説明図である。
【図１２】レーンネットワークの説明図である。
【図１３】到着地点の説明図である。
【図１４】到着地点の説明図である。
【発明を実施するための形態】
【００１９】
本発明の実施例について以下の順序で説明する。
Ａ．システム構成：
Ｂ．データ構造：
Ｂ１．ネットワークデータ：
Ｂ２．文字データ：
Ｂ３．地物データ：
Ｂ４．到着地点の設定：
Ｃ．地物データの整備：
Ｄ．経路案内処理：
Ｄ１．全体処理：
Ｄ２．到着地点取得処理：
Ｄ３．案内対象交差点設定処理：
Ｄ４．案内例：
Ｅ．変形例：
【実施例１】
【００２０】
Ａ．システム構成：
図２は、案内システムの構成を示す説明図である。案内システムは、ナビゲーション装置１００として構成される。本実施例では、ナビゲーション装置１００は、地図データ等を提供するサーバ２００とネットワークＮＥ１で接続されており、サーバ２００から地図データベースの更新を受けられるものとした。ナビゲーション装置１００は、スタンドアロンで稼働する構成としてもよいし、その機能の一部をサーバ２００等で実行する構成としてもよい。
サーバ２００は、データベース生成装置としてのパーソナルコンピュータ３００とネットワークＮＥ２を介して接続されている。データベース生成装置３００は、オペレータの指示に従って、サーバ２００に格納されるデータベースの生成および更新を行うための装置である。
【００２１】
サーバ２００は、地図データベース記憶部２１０、送受信部２０１、およびデータベース管理部２０２を備えている。送受信部２０１、データベース管理部２０２は、ハードウェア的に構成してもよいが、本実施例では、これらの機能を実現するコンピュータプログラムをインストールすることによって、ソフトウェア的に構成するものとした。
【００２２】
送受信部２０１は、ナビゲーション装置１００およびデータベース生成装置３００とネットワークＮＥ１、ＮＥ２を介した通信を行う。本実施例では、地図データベース記憶部２１０のデータや、その提供・格納に関するコマンド等が通信される。
データベース管理部２０２は、ナビゲーション装置１００、データベース生成装置３００から要求された地図情報を、地図データベース記憶部２１０から読み出したり、データベース生成装置３００で生成された地図データを地図データベース記憶部２１０に格納する。
地図データベース記憶部２１０には、地物データ２１１、文字データ２１２、およびネットワークデータ２１３が格納されている。地物データ２１１は、道路や建物など地図に描画すべき地物のポリゴンデータである。文字データ２１２は、地図上に表示すべき文字情報である。例えば、建物の名称や地名などの文字情報が含まれる。ネットワークデータ２１３は、道路をノード、リンクのつながりで表したデータである。本実施例のネットワークデータ２１３には、主ネットワークデータと準ネットワークが含まれる。主ネットワークデータとは、現地調査によって通行規制が十分に整備されたデータであり、車両の経路探索に支障なく用いることができるデータとなっている。準ネットワークデータとは、通行規制の整備が十分とは言えないデータであり、車両の経路探索では、使用しない方が好ましいデータである。
【００２３】
ナビゲーション装置１００には、主制御部１０１の下で稼働する種々の機能ブロックが構成されている。本実施例では、主制御部１０１および各機能ブロックは、それぞれの機能を実現するソフトウェアをインストールすることによって構成したが、その一部または全部をハードウェア的に構成してもよい。
送受信部１０２は、サーバ２００とのネットワークＮＥ１を介した通信を行う。本実施例では、地図データベースおよびその提供を受けるためのコマンドの送受信が主として行われる。
コマンド入力部１０３は、ナビゲーション装置１００に設けられたボタン、レバー、タッチパネル等の操作を通じて、ユーザからの指示を入力する。本実施例における指示としては、経路探索の出発地、目的地の指定などが挙げられる。
ＧＰＳ入力部１０４は、ＧＰＳ（Global
Positioning System）を用いてユーザの現在位置を入力する。
地図データベース記憶部１０５は、サーバ２００から提供された地図データベースを格納する。本実施例では、サーバ２００が備える地図データベース記憶部２１０に記憶された地図データベースの全体をナビゲーション装置１００内の地図データベース記憶部１０５にも格納するものとしたが、経路探索や地図表示に必要となる部分のみを、その都度、サーバ２００から取得するものとしてもよい。
経路探索部１０７は、地図データベース記憶部１０５を参照して、経路探索を行う。
表示制御部１０６は、地図データベース記憶部１０５を用いてナビゲーション装置１００のディスプレイに地図および探索された経路等の案内を表示する。
【００２４】
データベース生成装置３００には、主制御部３０１の下で稼働する種々の機能ブロックが構成されている。本実施例では、主制御部３０１および各機能ブロックは、それぞれの機能を実現するソフトウェアをインストールすることによって構成したが、その一部または全部をハードウェア的に構成してもよい。
送受信部３０２は、サーバ２００とのネットワークＮＥ２を介した通信を行う。本実施例では、地図データベースおよびその管理のためのコマンドの送受信が主として行われる。
コマンド入力部３０３は、キーボードやマウスなどの操作を介してオペレータによる指示を入力する。
【００２５】
表示制御部３０４は、データベース生成装置３００のディスプレイに地図等を表示する。
地図データベース記憶部３０５は、サーバ２００の地図データベース記憶部２１０に記憶されている地図データベースを格納する。本実施例では、サーバ２００の地図データベース全体を格納するものとしたが、処理に必要な部分のみを格納するようにしてもよい。
到着地点算出部３０７は、地図データベース記憶部３０５に格納された地物に対して、到着地点を求める。到着地点とは、地物から道路をたどって主ネットワークデータ、つまり経路探索に使用できるネットワークデータが整備された道路まで到達した地点を言う。
データベース整備部３０６は、到着地点算出部３０７によって得られた到着地点を地図データベース記憶部３０５に格納し、サーバ２００の地図データベース記憶部２１０に記憶されている地図データベースを更新する。
【００２６】
Ｂ．データ構造：
図３は、地図データベースの構造を示す説明図である。地物データ、文字データ、ネットワークデータに格納される情報の概要を示した。
【００２７】
Ｂ１．ネットワークデータ：
ネットワークデータとは、道路をリンク、ノードで表したデータである。本実施例では、ネットワークデータとして主ネットワークデータと、準ネットワークデータの２種類が用意されている。図中に実線で示したリンクＬ１〜Ｌ４およびノードＮ１、Ｎ２が主ネットワークデータであり、破線で示したリンクＬ１１〜Ｌ１３およびノードＮ１１、Ｎ１２が準ネットワークデータである。
【００２８】
主ネットワークデータおよび準ネットワークデータともに、それぞれに属するリンクデータおよびノードデータを格納している。リンクデータは、それぞれのリンクを形成する点列の座標、国道・県道等の種別、車線数その他の属性情報や通行規制情報などを記録している。ノードデータは、座標値、通行規制などを記録している。
ただし、主ネットワークデータは、現地調査によって通行規制が十分に整備されたデータであり、車両の経路探索に支障なく用いることができるデータとなっている。これに対し、準ネットワークデータは、通行規制の整備が十分とは言えないデータであり、車両の経路探索では、使用しない方が好ましいデータである。本実施例でも、経路探索は原則として主ネットワークデータを用いて行うものとしている。
【００２９】
図１１に示すように、ネットワークデータには、実際の道路レーンに対応するレーンネットワークデータが対応付けられている。
リンクＬ１０１〜リンクＬ１０４に対応する道路がいずれも片側一車線である場合を例としてレーンネットワークデータのデータ構造について説明する。
レーンネットワークデータは、道路中心線ＬＣ１〜ＬＣ８に関するデータと交差点内走行線ＩＲ（図１１、図１２に示す点線１１０内に存在するすべての線）に関するデータとで構成される。
【００３０】
図１１に示すように、道路中心線ＬＣ１，ＬＣ２はネットワークデータのリンクＬ１０１に関連づけられている。同様に、道路中心線ＬＣ３，ＬＣ４はネットワークデータのリンクＬ１０２に関連づけられている。
また、交差点内走行線ＩＲは何れもネットワークデータのノードＮ１０１に関連づけられている。これらレーンネットワークデータを構成する道路中心線ＬＣ１〜ＬＣ８と交差点内走行線ＩＲとに関するデータは、地図データベース記憶部２１０に格納されている。各レーンネットワークデータには、固有のＩＤが付与されている。
本実施例では、到着地点には、このレーンネットワークデータを構成する道路中心線および交差点内走行線の上の所定位置が対応付けられている。
【００３１】
交差点内走行線は、１の道路におけるレーン（道路中心線）から進入可能な他の道路におけるレーン（道路中心線）にのみ接続されている。例えば、リンクＬ１０２に対応する道路の道路中心線ＬＣ４から進入可能な道路中心線は、道路中心線ＬＣ１，ＬＣ５，ＬＣ７である。従って、道路中心線ＬＣ４と接続関係にある交差点内走行線は、これら道路中心線ＬＣ１，ＬＣ５，ＬＣ７と接続されている交差点内走行線ＩＲ１〜ＩＲ３ということになる。
【００３２】
また、道路中心線および交差点内走行線に関するデータは何れも進行方向に関する属性情報を保持している。具体的には、図１２における道路中心線ＬＣ４，ＬＣ７は、図の右側から左側へ走行可能であることを示す属性情報を保持している。
図１２における交差点内走行線ＩＲ２は、道路中心線ＬＣ４から道路中心線ＬＣ７へ走行可能であることを示す属性情報を保持している。
なお、出発地から目的地までの経路を探索する際には、ネットワークデータ（リンク及びノード）を用い、レーンネットワークデータは目的地の到着地点を案内する際に用いるようにしてもよい。
【００３３】
Ｂ２．文字データ：
文字データ２１２は、地物の名称や地名などを表示する文字を規定するデータである。図中には、建物ＢＬＤの名称を表示するためのデータ例を示した。文字データは、内容、位置、地物、フォント、サイズなどの情報を格納する。
内容は、表示すべき文字列であり、図中の例では、「△△(株)」という会社名称である。
位置は、文字を表示する位置である。本実施例では、文字列の左下の点Ｐ５を基準点として、この座標値を指定するものとした。
地物は、文字が関連づけられる地物データのポリゴン名称である。
フォント、サイズは、表示する際のフォントおよびサイズの指定である。
この他、色、太字など、種々の属性を指定可能としてもよい。
【００３４】
Ｂ３．地物データ：
地物データ２１１について、建物Ｈ１を例にとって構造を示す。地物データ２１１は、建物、道路等の地物を描画するためのポリゴンデータであり、名称、形状、代表点、出入り口線、到着地点、属性などを格納している。
名称は、地物の名称である。ポリゴンに固有のＩＤを用いてもよい。
形状は、地物のポリゴンの頂点を示す座標の列である。図の例では、建物Ｈ１のポリゴンの頂点Ｐ１、Ｐ２、Ｐ３、Ｐ４の各座標が格納されている。
代表点は、地物の位置を表す地点Ｃの座標である。代表点は、地物の図心を用いることが多いが、任意に設定可能である。
出入口線は、地物と道路とを関連づけるための情報である。建物Ｈ１の場合、玄関から道路に出るための線分Ｄが出入口線として登録される。具体的には、線分Ｄの両端の座標が登録されることになる。出入口線は、線分Ｄのうち、道路上の端点のみを登録するものとしてもよい。また、出入口線は、建物や駐車場など、出入りを伴う地物に設定されるものであり、地物の全てに設定する必要はない。図の例では、建物ＢＬＤに対して正面の出入口線ＤＢ１および駐車場ＢＬＤＰ側の出入口線ＤＢ２、建物Ｈ２〜Ｈ４に対してそれぞれ出入口線ＤＨ２〜ＤＨ４、駐車場ＰＫに対して出入口線ＤＰＫが設定されている。出入口線に対して、人の出入りに使用する出入口、駐車場などの用途を示す情報を設定しておいてもよい。
【００３５】
到着地点Ｇは、地物の出入口線の道路上の端点から、いずれかの道路を経てたどりつけるネットワーク上の点である。道路を構成する走行レーン上の点ということもできる。建物Ｈ１の場合、図中に点線で示す通り、出入口線Ｄが関連づけられている道路Ｒ２１を経て、リンクＬ２に至ることができるため、リンクＬ２上に到着地点Ｇが設定されている。出入口線Ｄから道路Ｒ２１を図中右方向にたどり、ノードＮ１１で右折してノードＮ２に至る経路をとり、ノードＮ２を到着地点とすることもできる。本実施例では、建物Ｈ１からノードＮ２に至る道のりよりも、到着地点Ｇに至る道のりの方が短いから、このように設定した。到着地点は、一つに限定する必要はないから、ノードＮ２も到着地点に設定してもよい。
図の例では、建物Ｈ２〜Ｈ４に対する到着地点は点ＧＨと設定されている。建物ＢＬＤに対しては、点ＧＨおよび点ＧＢＬＤ２と設定されている。到着地点は、出入口線と同様、駐車場にも設定でき、図の例では、駐車場ＰＫに対して到着地点ＧＰＫが設定されている。駐車場ＰＫは、リンクＬ２に面しているため、出入口線ＤＰＫの端点と到着地点ＧＰＫが一致した状態となっている。
【００３６】
Ｂ４．到着地点の設定：
図４は、到着地点の設定について示す説明図である。建物ＢＬＤ１の出入口線ＤＢを対象とする到着地点について示した。
建物ＢＬＤ１の周辺の主ネットワークデータとしては、リンクＬ７、ノードＮ７およびリンクＬ５、Ｌ６およびノードＮ５、Ｎ６が存在する。準ネットワークデータとしては、破線で示したリンクＬ１４が存在する。
建物ＢＬＤ１の出入口線ＤＢからいずれかの道路を経て主ネットワークにたどりつく経路としては、図中に点線で示した３通りがあげられる。道路Ｒ２４を経てリンクＬ７にたどりつく経路、道路Ｒ２５を経てたリンクＬ６およびリンクＬ５にそれぞれたどりつく経路である。これらの各経路がリンクＬ７、Ｌ６、Ｌ５にたどりつく点が到着地点Ｇ７、Ｇ６、Ｇ５となる。
【００３７】
これらの到着地点は、経路探索によって求めることができる。本実施例では、それぞれの地物は、出入口線によって、いずれかの道路に関連づけられているから、出入口点、つまり地物への出入口に面した道路上の端点を始点とする経路探索によって到着地点を求めればよい。
この経路探索は、主ネットワークデータ、準ネットワークデータおよび道路のポリゴンの全てを用いてもよい。道路のポリゴンは、リンク、ノードで構成されている訳ではないが、隣接するポリゴンを指定するデータは持っているから、ポリゴン同士のつながり関係は規定されており、リンク、ノードと同様に、経路探索に使用することが可能である。出入口点を起点とする経路探索の結果、主ネットワークデータにたどり着いた点を到着地点とすればよい。
【００３８】
図の例のように、到着地点がＧ７、Ｇ６、Ｇ５の３点見いだされる場合、これらの３点を建物ＢＬＤ１の到着地点として用いてもよいし、例えば、地物からの道のりが最短の地点、地物からの距離が最短の地点、地物から到着地点までの経路と準ネットワークデータとの重複部分が多い点、地物から出発点に向かう方角に近い点などの基準で選択してもよい。
図の例においては、地物からの道のりや距離を基準として選べば、建物ＢＬＤ１に最も近い点Ｇ５が到着地点となる。準ネットワークデータとの重複部分を基準として選べば、点Ｇ６が到着地点となる。出発地が図の左端方向にある場合には、出発地の方角を基準として選べば、点Ｇ７が到着地点となる。
【００３９】
本実施例では、上述の手順で、到着地点を設定し、地物データ２１１に予め設定しておくものとした。到着地点は、予め設定しておくのではなく、経路探索などの処理の過程で求めるものとしてもよい。
【００４０】
Ｃ．地物データの整備：
図５は、地物データ整備処理のフローチャートである。データベース生成装置３００のデータベース整備部３０６、到着地点算出部３０７が主として実行する処理であり、ハードウェア的には、データベース生成装置３００のＣＰＵが実行する処理である。
【００４１】
ＣＰＵは、オペレータから指定された範囲の地図データを地図データベース記憶部３０５から読み込み、ディスプレイに地図を表示する（ステップＳ１０）。
ＣＰＵは、処理対象となる地物に対して、名称、地物のポリゴン形状、代表点、属性などの指示を入力する（ステップＳ１１）。既存の地物に対して処理を行う際には、これらの情報は、既に地物データに格納されているから、要更新箇所のみを修正すればよい。
また、ＣＰＵは、出入口線および用途の指定を入力する（ステップＳ１２）。出入口線は、地物と道路とを関連づけるための情報である。地物に対して複数の出入口線を設定してもよい。用途は、出入口線ごとに設定することができる。例えば、人の出入りに使用する出入口、駐車場などの形式で指定する。人の出入りに使用する出入口を、玄関、裏口などに細分化して設定してもよい。
【００４２】
ＣＰＵは、到着地点探索処理を行って、地物のそれぞれの出入口線に対応する到着地点を求める（ステップＳ１３）。この処理は、図４で説明した出入口点を始点とする経路探索である。
この経路探索は、主ネットワークデータ、準ネットワークデータおよび道路のポリゴンの全てを用いてもよい。道路のポリゴンは、リンク、ノードで構成されている訳ではないが、隣接するポリゴンを指定するデータは持っているから、ポリゴン同士のつながり関係は規定されており、リンク、ノードと同様に、経路探索に使用することが可能である。出入口点を起点とする経路探索の結果、主ネットワークデータに対応するレーンネットワークにたどり着いた点を到着地点とすればよい。
到着地点は、それぞれの出入口点に対して複数探索されることがある。このような場合、いずれかの到着地点に絞り込んで地物データに登録するようにしてもよいが、本実施例では、探索された到着地点は全て登録しておくものとした。こうすることにより、後述する経路探索における到着地点の選択肢が増え、より適した経路を提示できる可能性が増えるからである。
【００４３】
ＣＰＵは、以上の処理を踏まえ、名称、地物ポリゴン形状、代表点、属性、出入口線、用途、および到着地点のデータを地物データに格納し、地物データを更新する（ステップＳ１４）。
処理対象となるべき地物が他にもある場合には、オペレータの指示に従って、この処理を繰り返し実行する。
【００４４】
Ｄ．経路案内処理：Ｄ１．全体処理：
図６は、経路案内処理のフローチャートである。ナビゲーション装置１００の経路探索部１０７および表示制御部１０６が主として実行する処理であり、ハードウェア的にはナビゲーション装置１００のＣＰＵが実行する処理である。
【００４５】
ナビゲーション装置１００は、出発地および目的地を入力する（ステップＳ２０）。出発地は、ユーザが指定してもよいし、ＧＰＳなどで取得した現在位置を出発地に設定してもよい。
目的地は、地物を指定してもよいし、座標値で指定してもよい。
【００４６】
次に、ナビゲーション装置１００は、指定された目的地に対する到着地点を取得する（ステップＳ３０）。到着地点は走行レーン上の位置に設定されている。すなわち、到着地点は、走行レーン上の所定位置に対応する緯度・経度情報で表される。本実施例では、到着地点は地物データ２１１に格納されている。従って、目的地となる地物が指定されている場合は、指定された地物に対応する地物データから到着地点を読み出せばよい。目的地が座標で指定されている場合には、当該座標がいずれのポリゴンに含まれるかを特定し、特定されたポリゴンの地物データに対応する到着地点を読み出せばよい。また、座標に最も近い位置に存在する道路における走行レーン上の到着地点を読み出してもよい。地物に対して複数の到着地点が得られる場合もある。
到着地点取得処理の内容は後述する。
【００４７】
ナビゲーション装置１００は、得られた到着地点を起点とする経路探索を行う（ステップＳ５０）。
到着地点が複数得られている場合には、ナビゲーション装置１００は、経路案内の対象とすべき到着地点および経路を選択する。到着地点および経路を地図上に表示して、ユーザに直接、選択させる方法をとってもよい。また、ナビゲーション装置１００が何らかの選択条件に従って自動的に選択するようにしてもよい。選択には、種々の選択条件を適用可能であるが、本実施例では、次に示す３つの条件から、ユーザが予め選択した条件を用いるものとした。
（１）出発地からそれぞれの到着地点までの経路探索によるコスト（以下、「経路コスト」という）が最小となる到着地点を選択する。
（２）経路コストと、目的地からそれぞれの到着地点までのコスト（以下、「到着地点コスト」という）の和が最小となる到着地点を選択する。
（３）出発地と目的地とを結ぶ線分までの距離が最短の到着地点を選択する。つまり、出発地と目的地とを結ぶ線分に対して到着地点から垂線をおろし、その距離で評価する条件である。線分に対して垂線を引くことができない位置関係にある到着地点については、目的地までの直線距離を用いるものとする。この条件は、出発地から目的地との間に位置する到着地点を選択すれば、経路コストと到着地点コストとの総和が低い経路が得られるとの考え方に基づくものである。
【００４８】
なお、到着地点コストが最小となる到着地点を選択するものとしてもよい。この態様によれば、到着地点から出入口までを徒歩で移動する場合に、徒歩の移動負荷が最も軽くなる経路を案内することができる。もっとも、到着地点コストは目的地となる地物が指定された時点で一義的に決まるものであるから、到着地点コストが最小という条件を用いる場合には、到着地点を起点とする経路探索（ステップＳ５０）を行う前に、この条件に基づいて経路探索に使用すべき到着地点を決定しておくことが望ましい。こうすれば、経路探索は決定された到着地点についてのみ行えば足りるから、経路探索の処理負荷を軽減することも可能となる。
【００４９】
次に、到着地点が複数得られている場合における他の選択例について説明する。
図１３に示すように、ある地物としての施設５０に複数の到着地点５１〜５３が設定されている。この例では、施設５０の駐車場５４，５５へ案内するために、各到着地点５１〜５３も当該駐車場５４，５５に接している道路に対応する道路中心線ＬＣ１１〜ＬＣ１３上の位置にそれぞれ存在している。また、図１３に示す例では、道路に中央分離帯５６が存在しているため、リンクＬ１１１に対応する道路中心線ＬＣ１４上には到着地点が設定されていない。なお、図１３においてはノードＮ１１１に対応しておりレーンネットワークを構成する交差点内走行線については便宜上図示せず、リンクに対応する道路中心線を図示する。
【００５０】
このように、到着地点がレーンネットワークを構成する道路中心線上の位置に設定されている。従って、経路を探索する際に、走行レーンを考慮しつつ出発地から目的地までの距離が最短となるような到着地点を選択したり、左折により進入することができる駐車場への到着地点を選択したりすることで、ユーザに対して最適な案内が可能となる。
また、到着地点がレーンネットワークを構成する道路中心線上の位置に設定されており、当該道路中心線と関連性を持たせることで、中央分離帯が存在しており右折進入することができないような経路が探索されるといった事態を回避することができる。
【００５１】
なお、１の道路の上下線のいずれにも到着地点を設定することができる場合には、当該道路に対応するリンク上の点を到着地点としてもよい。具体的には、図１３に示すように、１つのリンクＬ１１２対応している道路中心線ＬＣ１２，ＬＣ１３はいずれも到着地点が設定可能である。従って、このような場合には図１４に示すように、リンクＬ１１２上に対応する点の位置座標を到着地点５７と設定してもよい。一方、リンクＬ１１２に対応している道路中心線ＬＣ１４については、中央分離帯５６が存在しているため施設５０の到着地点が設定できない。従って、リンクＬ１１１上に対応する点の位置座標を到着地点として採用することはない。
【００５２】
そして、案内対象交差点設定処理を行う（ステップＳ６０）。本実施例では、ナビゲーション装置１００は、経路案内時に、右左折などの経路の案内に加えて、危険箇所の案内など、ユーザに対して通行を支援するための案内を行う。案内対象交差点設定処理は、この案内を行う対象となる交差点を設定する処理である。本実施例で案内対象としたのは、次の２種類の交差点である。
第１は、仮想交差点の案内である。ネットワークデータは、全ての道路に整備されている訳ではないので、ネットワークデータ上は交差点として構成されていない部分であっても、実際には道路が交差している箇所が存在する。このような箇所を、ネットワークデータから見ると仮想的な交差点という意味で、本実施例では、仮想交差点と称する。本実施例では、このような仮想交差点の中から案内対象交差点を選択し、交差点の存在などをユーザに対して案内する。
第２は、要注意交差点の案内である。住宅に面した道路と交差する交差点では、幼児を含め人の出入りがあり、時には飛び出しなどの危険もある。本実施例では、このような交差点を案内対象交差点として、ユーザに対し注意喚起を行う。
これらの案内を行う案内対象交差点の設定処理の具体的内容については、後述する。
【００５３】
こうして経路案内のために要する情報が揃うと、ナビゲーション装置１００は、次の手順で経路案内を行う。
ユーザの現在位置を取得し（ステップＳ９０）、探索された経路および現在位置をディスプレイに表示する（ステップＳ９２）。経路の表示と併せて、経路の音声案内を行っても良い。
また、ナビゲーション装置１００は、案内対象交差点では、通行案内を出力する（ステップＳ９４）。先に説明した通り、仮想交差点の存在等を示したり、要注意交差点の注意喚起をしたりするのである。
以上の処理を、ナビゲーション装置１００は、ユーザが目的地に到着するまで（ステップＳ９６）、繰り返し実行する。
【００５４】
Ｄ２．到着地点取得処理：
図７は、到着地点取得処理のフローチャートである。経路案内処理（図６）のステップＳ３０に相当する処理であり、指定された目的地に対応する到着地点を得る処理である。
ナビゲーション装置１００は、目的地に対応する地物データを読み込む（ステップＳ３２）。目的地が地物を指定している場合には、指定に該当する地物データを読み込めばよい。目的地が座標で指定されている場合には、その座標点を含む地物の地物データを読み込む。
地物データに到着地点が設定されている場合（ステップＳ３４）、ナビゲーション装置１００は、設定されている到着地点データを読み込む（ステップＳ３６）。
到着地点が設定されていない場合には（ステップＳ３４）、ナビゲーション装置１００は、出入口線データを読み込み（ステップＳ３８）、到着地点探索処理を行って到着地点を得る（ステップＳ４０）。到着地点探索処理は、地物データ整備処理（図５）のステップＳ１３で説明した処理と同じである。
【００５５】
そして、ナビゲーション装置１００は、経路探索モードに応じて到着地点を選択する。
到着地点から目的地までは徒歩で向かう旨の探索モードが指定されている場合は（ステップＳ４２）、ナビゲーション装置１００は、到着地点から目的地までのコスト、つまり到着地点コストが短い到着地点を優先する（ステップＳ４４）。コストは、経路探索において、各経路を評価するための評価値であり、距離や移動に要する時間などに基づいて設定することができる。上り／下り坂、階段など道路の構造などに基づく移動負荷を加味して設定してもよい。ステップＳ４４では、到着地点から徒歩で移動することを考慮し、距離が短いなど、移動に要する労力が低い到着地点を選択することを意味している。
「優先」には、一つの到着地点を選択する態様、および複数の到着地点に対して優先度を設定する態様などが含まれる。後者の場合には、ステップＳ４４の条件に基づいて優先度を設定しておき、経路案内処理（図６）のステップＳ５０の処理における選択条件を併せて考慮して、案内対象となる到着地点を選択するようにしてもよい。
【００５６】
到着地点から目的地まで車で移動する旨の探索モードが指定されている場合は（ステップＳ４２）、ナビゲーション装置１００は、出入口線の用途を参照し、駐車場の出入口線に対応する到着地点を優先する（ステップＳ４６）。到着地点から目的地までは、通行規制等の調査が十分になされていない道路なので、幅員が足りないなど、車の通行に適しない道路が含まれるおそれもある。しかし、駐車場に対応した到着地点であれば、それ以外の到着地点に比べて、到着地点から目的地までの経路も車の通行に適している可能性が高い。ステップＳ４６の態様によれば、目的地に到着した時に車を駐車できる出入口に案内できるだけでなく、目的地まで車で移動するのに適した到着地点を優先することができる。
【００５７】
Ｄ３．案内対象交差点設定処理：
図８は、経路案内交差点設定処理のフローチャートである。経路案内処理（図６）のステップＳ６０に相当する処理であり、仮想交差点および注意喚起の案内を行う地点を設定する処理である。
【００５８】
ナビゲーション装置１００は、経路上の到着地点を抽出し（ステップＳ６２）、未処理の到着地点を処理対象として選択する（ステップＳ６４）。
そして、この到着地点に対応する全ての地物を抽出する（ステップＳ６６）。到着地点は、地物からいずれかの道路をたどって主ネットワークに到達した点であるから、複数の地物に対する到着地点が同一の点となることもある。ステップＳ６６では、ナビゲーション装置１００は、地物データから、処理対象の到着地点に対応する地物を全て検索する。
【００５９】
検索された地物に駐車場がある場合（ステップＳ６８）、ナビゲーション装置１００は、駐車場の位置に基づき交差点形状を特定し（ステップＳ７０）、交差点となっている箇所について（ステップＳ７２）、仮想交差点に設定する（ステップＳ７４）。
【００６０】
ステップＳ７０〜Ｓ７４の処理内容について具体例で説明する。
図９は案内対象交差点設定例（１）を示す説明図である。リンクＬ６０の周辺に、駐車場Ｐ６１〜Ｐ６５が存在する例を示した。それぞれは代表点が点Ｃ６１〜Ｃ６５であり、到着地点Ｇ６１〜Ｇ６３、出入口線Ｄ６１〜Ｄ６５が設定されている。
駐車場Ｐ６１の場合、到着地点Ｇ６１はリンクＬ６０上に存在するが、リンクＬ６０に面しており、交差点とはなっていないため、仮想交差点には設定しない。リンクＬ６０を走行しているユーザから視認できる駐車場を案内対象とする必要はないからである。
交差点となっているか否かの判断は、種々の方法を用いることができる。本実施例では、出入口線Ｄ６１の端点が到着地点Ｇ６１と一致している場合には交差点ではないと判断し、案内対象から除外するものとした。駐車場Ｐ６１の代表点Ｃ６１とリンクＬ６０との距離が道路の幅員程度である場合に交差点でないと判断する方法をとることもできる。
【００６１】
到着地点Ｇ６２の場合には、リンクＬ６０の右側にのみ駐車場Ｐ６２が存在することが分かる。従って、ナビゲーション装置１００は、「三叉路」と判断する。
到着地点Ｇ６３の場合には、リンクＬ６０の右側に駐車場Ｐ６３、Ｐ６４が存在し、左側に駐車場Ｐ６５が存在する。従って、ナビゲーション装置１００は、「交差点」または「四叉路」と判断する。
このように、駐車場とリンクとの距離、およびリンクの左右いずれに駐車場が配置されているかに応じて、ナビゲーション装置１００は交差点形状を判断することができる。
なお、図９において到着地点Ｇ６１〜Ｇ６３はリンクＬ６０上に存在しているが、図１３に示すように、リンクに対応する道路の走行レーン上に存在する態様としてもよい。
【００６２】
駐車場に関する処理を終えると、ナビゲーション装置１００は、到着地点に対応する「住宅」の数が２以上の場合には（ステップＳ７６）、要注意交差点に設定する（ステップＳ７８）。
この処理について具体例で説明する。
図１０は案内対象交差点設定例（２）を示す説明図である。リンクＬ７０の周辺に、住宅Ｈ７１〜Ｈ７９が存在する例を示した。それぞれは代表点が点Ｃ７１〜Ｃ７９であり、到着地点Ｇ７１〜Ｇ７３、Ｇ７５、Ｇ７７、出入口線Ｄ７１〜Ｄ７９が設定されている。
【００６３】
到着地点Ｇ７１、Ｇ７２は、対応する住宅数が１軒であるため、ステップＳ７６の判断基準により、要注意交差点から除外される。到着地点Ｇ７１については、駐車場の場合と同様、住宅Ｈ７１がリンクＬ７０に面していると判断し、要注意交差点から除外するものとしてもよい。
到着地点Ｇ７３は、リンクＬ７０の右側に住宅Ｈ７３、Ｈ７４の２軒が存在する。到着地点Ｇ７４は、リンクＬ７０の右側に住宅Ｈ７５、左側に住宅Ｈ７６が存在する。到着地点Ｇ７７は、リンクＬ７０の右側に住宅Ｈ７７、Ｈ７８の２軒、左側に住宅Ｈ７９が存在する。従って、到着地点Ｇ７３、Ｇ７５、Ｇ７７は、それぞれ２軒以上の住宅が対応しているから、要注意交差点に設定される。
【００６４】
ナビゲーション装置１００は、以上の処理を経路上の全ての到着地点について行い、案内対象交差点を設定する。
このように、本実施例では、駐車場に対応する到着地点のうち交差点となっている地点、および２軒以上の住宅に対応している到着地点が案内対象交差点として設定されることになる。
【００６５】
Ｄ４．案内例：
図９を参照しながら、駐車場が存在する場合の案内対象交差点に対する案内例を説明する。
図９に示す通り、点Ｇ６２、Ｇ６３の部分に三叉路および四叉路が存在するが、リンクＬ６０にはこれらの点にノードは設けられていないから、リンクＬ６０を見る限り、点Ｇ６２、Ｇ６３の交差点は把握することができない。しかし、点Ｇ６２、Ｇ６３は、それぞれ駐車場に対する到着地点であるから、これらの地点は、車が出入りできる程度の道路と交差していることが分かる。実施例のナビゲーション装置１００は、このような状態を考慮して、点Ｇ６２、Ｇ６３の仮想交差点を案内対象交差点と設定し、交差点である旨の案内を行う。
【００６６】
具体的には、交差点Ｇ６２にさしかかるところで、「前方に三叉路があります」と案内したり、交差点Ｇ６３にさしかかるところで、「前方に交差点（または四叉路）があります」と案内することができる。これらの案内とともに、「車が出てくる可能性があります」と注意喚起をしてもよい。
また、図９の点Ｇ６２よりも先の交差点で右折する場合は、点Ｇ６２の三叉路を踏まえて、「この先、三叉路の次の交差点で右折です」のように案内することも可能である。こうすることにより、ユーザが誤って点Ｇ６２の交差点を右折してしまうことを回避することができる。
【００６７】
また、点Ｇ６２のように、進行方向に対して右側にのみ駐車場が位置する場合には、車が出てくることによる危険度は比較的低いと判断して通行上の注意喚起を省略してもよい。左側にのみ駐車場が位置する場合には、ユーザの進行する車線に近く危険度が認められると考えて、注意喚起をしてもよいし、左右双方に駐車場が位置する場合に比べれば危険度が低いと考えて、注意喚起を省略するようにしてもよい。
【００６８】
本実施例では、到着地点Ｇ６２を利用して、駐車場Ｐ６２までの経路案内をすることもできる。つまり、ネットワークデータを利用して到着地点Ｇ６２までの経路を探索し、到着地点Ｇ６２から駐車場Ｐ６２までの経路は、道路のポリゴンデータを用いて案内するのである。
このような場合、仮にネットワークデータだけを利用した案内を行おうとすれば、ネットワークデータ上は、点Ｇ６２は交差点と認識されてはいないから、せいぜい「目的地付近です」という程度の案内しかすることができない。
これに対し、本実施例では、点Ｇ６２を交差点と認識することができることを利用して、「次の交差点を右折です」という経路案内を行っても良い。こうすることにより、ユーザにより適切な情報を提示することが可能となる。
【００６９】
図１０を参照しながら、住宅が存在する場合の案内対象交差点に対する案内例を説明する。
住宅に対応する到着地点は、人が飛び出してくる可能性がある要注意交差点として案内を行う。従って、点Ｇ７３、Ｇ７５、Ｇ７７にさしかかるところで、「この先の交差点は、人の出入りがあるかも知れません。注意して下さい」のように案内することができる。
この案内に交差点の形状を反映させてもよい。
例えば、点Ｇ７３では、「右側から人が出てくるかも知れません」、点Ｇ７５、Ｇ７７では、「左右から人が出てくるかも知れません」のように、方向を示して注意を喚起することができる。
【００７０】
注意喚起の方法は、到着地点に対応する住宅数に応じて変化させてもよい。図１０の到着地点Ｇ７３、点Ｇ７５は２軒が対応しているのに対し、到着地点Ｇ７７は３軒が対応しているから危険度が高いと判断し、より強調した態様で注意喚起してもよい。例えば、注意喚起するメッセージの内容を変化させてもよいし、音声案内のトーンや音量、画面表示の明度、色などで強調してもよい。
【００７１】
実施例では、住宅数が２以上の交差点を注意喚起の対象としたが（図８のステップＳ７６）、この軒数は任意に設定可能であり、更に多くの軒数を判断基準値としてもよい。判断基準値を大きくすれば、案内が行われる頻度が下がるため、逆に、案内が行われた時のユーザの注意を効果的に喚起することができる。
【００７２】
要注意交差点での案内については、住宅に対応する到着地点が経路に沿って現れる密度を求め、その密度に応じて、注意喚起のための情報提示の内容を設定してもよい。
図１０に示す点Ｇ７７、Ｇ７５、Ｇ７３が比較的接近している場合、各交差点ごとに「人が出てくる可能性あります」という案内が行われると、ユーザはこうした案内に麻痺したようになってしまい、注意喚起の効果が低くなることがある。
そこで、このように所定の密度を超えて要注意交差点が存在する場合には、「しばらく飛び出しの危険がある地域を通行いたします」のように地域全体に対する注意喚起の態様をとってもよい。図１０のリンクＬ７０を下側から上側に向かって走行している場合には、点Ｇ７７にさしかかるところで、点Ｇ７７、Ｇ７５、Ｇ７３に対する総合的な案内として、上述のように地域全体に対する注意喚起を行うのである。
【００７３】
別の態様として、要注意交差点の密度が高い場合には、要注意交差点とするか否かの判断基準値（図８のステップＳ７６の値）を増大させ、判断基準を厳しくしてもよい。図１０の点Ｇ７７、Ｇ７５、Ｇ７３の地域に対しては、ナビゲーション装置１００は、例えば、判断基準値を３軒に変更するのである。こうすることで、点Ｇ７７のみが要注意交差点となるから、注意喚起が頻繁に行われる事態を回避することができる。具体的な処理態様としては、案内対象交差点設定処理（図８）を実行した後、要注意交差点の密度を算出し、密度が所定値を超える地域に対しては、ステップＳ７６の判断基準値を増大させた上で、再度、案内対象交差点設定処理（図８）を実行する方法をとることができる。
【００７４】
Ｅ．変形例：
実施例では、仮想交差点および要注意交差点の例を示したが、実施例の案内は、到着地点の種別に応じて種々の態様で適用することができる。例えば、到着地点がレストランや店舗に対応している場合、その密度に応じて、「右側にレストラン街があります」、「○○店街があります」のような案内を行っても良い。経路探索を行う際に、目的地に向かう途中で食事をとるなどの目的を設定した場合には、レストランに対応した到着地点を抽出し、経路案内の過程で、「右側にイタリアンレストランがあります」のように目的に応じた情報を提示してもよい。このように到着地点と関連づけた地物の種別に応じて情報を提示することにより、ユーザが目的地として選択していない地物について、経路から離れたところにある地物であってもユーザの意図に合致した情報を提示可能となる。
【００７５】
また実施例では、経路案内を行った上で種々の情報提示をする例を示したが、本発明は、経路案内を行わない場合でも適用可能である。
例えば、図１０において、リンクＬ７０上をユーザが走行している場合には、ユーザの現在位置を検出し、その前方にある到着点について、「人が出てくる可能性あります」などの注意喚起をすることができる。ユーザの経路がわかっていない場合であっても、現在位置の変化から進行方向は判断できるため、前方に位置する交差点か否かは容易に判断可能である。
音声で注意喚起を行う場合には、注意喚起の対象となる交差点をユーザがほぼ確実に通行すると判断できる時点まで待つようにしてもよい。例えば、図１０の点Ｇ７７からリンクＬ７０を上方に向かってユーザが走行している場合を考える。ユーザは、点Ｇ７５を通過して直進するかも知れないし、ここで右左折するかも知れない。このような状況で点Ｇ７３の注意喚起を行うと、かえってユーザを混乱させかねない。しかし、ユーザが点Ｇ７５を通過した後は、Ｕターンでもしない限り点Ｇ７３を通過することが明らかである。このように、ユーザの現在位置および進行方向を考慮して、通過が確実と判断されるまで案内を行うタイミングを遅らせる態様をとることにより、ユーザの混乱を回避することができる。
【００７６】
この判断は、ユーザの前方に位置する到着地点Ｇ７３、Ｇ７２、Ｇ７１について、ユーザの現在位置（例えば点Ｇ７５）との間に分岐または他の到着地点が存在するか否かに基づいて判断することができる。到着地点Ｇ７１、Ｇ７２と点Ｇ７７との間には、到着地点Ｇ７３が存在するのに対し、到着地点Ｇ７３と点Ｇ７５との間には分岐等は存在しない。このような場合には、到着地点Ｇ７３を通過する可能性が高いと判断し、注意喚起を行うようにすればよい。
注意喚起は、音声だけでなく表示によることもできる。例えば、到着地点Ｇ７３，Ｇ７２等を危険度に応じて赤などの目立つ色で表示する態様をとることができる。このように表示によって注意喚起する場合には、ユーザの混乱を招くおそれが低いから、現在位置から所定範囲内にある到着地点を対象としても
【００７７】
本発明は、必ずしも上述した実施例の全ての機能を備えている必要はなく、一部のみを実現するようにしてもよい。また、上述した内容に追加の機能を設けてもよい。
本発明は上述の実施例に限定されず、その趣旨を逸脱しない範囲で種々の構成を採ることができることはいうまでもない。例えば、実施例においてハードウェア的に構成されている部分は、ソフトウェア的に構成することもでき、その逆も可能である。
【００７８】
本発明は、以下に示す経路探索方法として構成してもよい。
道路をノード、リンクで表したネットワークデータと、道路を含む地物を描画するポリゴンを記憶する地物データと、自動車が通行可能な道路として前記ネットワークデータが整備された道路上の点であって、前記目的地に対応する地物からいずれかの道路を通行して到着できる点である到着地点に関するデータとを格納する地図データベースを有するコンピュータによって、指定された目的地までの経路を探索する経路探索方法であって、前記コンピュータが行うステップとして、出発地および目的地を入力しメモリに記憶する入力ステップと、前記地図データベースを参照して、前記目的地に対応する到着地点を取得しメモリに記憶する到着地点取得ステップと、前記ネットワークデータを参照して、前記出発地から前記到着地点までの経路探索を行う経路探索ステップとを備える経路探索方法である。
【００７９】
また以下に示すコンピュータプログラムとして構成してもよい。
道路をノード、リンクで表したネットワークデータと、道路を含む地物を描画するポリゴンを記憶する地物データと、自動車が通行可能な道路として前記ネットワークデータが整備された道路上の点であって、前記目的地に対応する地物からいずれかの道路を通行して到着できる点である到着地点に関するデータとを格納する地図データベースを有するコンピュータによって、指定された目的地までの経路を探索するためのコンピュータプログラムであって、出発地および目的地を入力しメモリに記憶する入力機能と、前記地図データベースを参照して、前記目的地に対応する到着地点を取得しメモリに記憶する到着地点取得機能と、前記ネットワークデータを参照して、前記出発地から前記到着地点までの経路探索を行う経路探索機能とをコンピュータに実現させるためのコンピュータプログラムである。
【００８０】
また以下に示す地図データベース生成方法として構成してもよい。
生成されるべき地図データベースの基礎データとして、自動車が通行可能な道路を表わしておりノード、リンクで構成されたネットワークデータと、道路および建物を含む地物を描画するための地物データと、各道路を構成する走行レーンごとに規定されており前記リンクと対応付けられているレーンネットワークデータとを備えるコンピュータによって、指定された目的地までの経路探索に用いられる地図データベースを生成する地図データベース生成方法であって、前記コンピュータが行うステップとして、オペレータによる前記地物データに格納された前記建物について、該建物への出入口に面した前記走行レーン上の点もしくは前記リンク上の点を指定する出入口点の指定を入力しメモリに記憶するステップと、前記出入口点を探索開始点として前記ネットワークデータおよび前記地物データの少なくとも一方を用いた経路探索によって、前記リンクに対応する点もしくは前記走行レーンに対応する点であって、前記出入口点からいずれかの道路を通行して到着できる点である到着地点を求め、メモリに記憶するステップと、前記到着地点を、前記地物に関連づけて前記地物データに格納するステップとを備える地図データベース生成方法。
【産業上の利用可能性】
【００８１】
本発明は、ネットワークから外れた目的地までの経路探索、およびネットワークから外れた地点の地物の存在を考慮した経路案内に利用可能である。
【符号の説明】
【００８２】
１００…ナビゲーション装置
１０１…主制御部
１０２…送受信部
１０３…コマンド入力部
１０４…ＧＰＳ入力部
１０５…地図データベース記憶部
１０６…表示制御部
１０７…経路探索部
２００…サーバ
２０１…送受信部
２０２…データベース管理部
２１０…地図データベース記憶部
２１１…地物データ
２１２…文字データ
２１３…ネットワークデータ
３００…データベース生成装置
３０１…主制御部
３０２…送受信部
３０３…コマンド入力部
３０４…表示制御部
３０５…地図データベース記憶部
３０６…データベース整備部
３０７…到着地点算出部
【特許請求の範囲】
【請求項１】
指定された目的地までの経路を探索する経路探索システムであって、
自動車が通行可能な道路を表わしておりノード、リンクで構成されたネットワークデータと、道路および建物を含む地物を描画するための地物データと、各道路を構成する走行レーンごとに規定されており前記リンクと対応付けられているレーンネットワークデータと、前記リンクに対応する点もしくは前記走行レーンに対応する点であって、前記目的地に対応する地物からいずれかの道路を通行して到着できる点である到着地点に関するデータとを格納する地図データベース記憶部と、
出発地および目的地を入力する入力部と、
前記地図データベース記憶部を参照して、前記目的地に対応する到着地点を取得する到着地点取得部と、
前記ネットワークデータを参照して、前記出発地から前記到着地点までの経路探索を行う経路探索部と
を備える経路探索システム。
【請求項２】
請求項１記載の経路探索システムであって、
前記地物データベース記憶部は、前記地物について複数の前記到着地点を記憶可能であり、
前記到着地点取得部は、前記目的地に対応する地物について複数の到着地点を取得し、
前記経路探索部は、前記経路探索の結果または前記目的地と到着地点との位置関係に基づく所定の抽出条件によって前記複数の到着地点の一つを選択する経路探索システム。
【請求項１】
指定された目的地までの経路を探索する経路探索システムであって、
自動車が通行可能な道路を表わしておりノード、リンクで構成されたネットワークデータと、道路および建物を含む地物を描画するための地物データと、各道路を構成する走行レーンごとに規定されており前記リンクと対応付けられているレーンネットワークデータと、前記リンクに対応する点もしくは前記走行レーンに対応する点であって、前記目的地に対応する地物からいずれかの道路を通行して到着できる点である到着地点に関するデータとを格納する地図データベース記憶部と、
出発地および目的地を入力する入力部と、
前記地図データベース記憶部を参照して、前記目的地に対応する到着地点を取得する到着地点取得部と、
前記ネットワークデータを参照して、前記出発地から前記到着地点までの経路探索を行う経路探索部と
を備える経路探索システム。
【請求項２】
請求項１記載の経路探索システムであって、
前記地物データベース記憶部は、前記地物について複数の前記到着地点を記憶可能であり、
前記到着地点取得部は、前記目的地に対応する地物について複数の到着地点を取得し、
前記経路探索部は、前記経路探索の結果または前記目的地と到着地点との位置関係に基づく所定の抽出条件によって前記複数の到着地点の一つを選択する経路探索システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１１−２２７０４３（Ｐ２０１１−２２７０４３Ａ）
【公開日】平成２３年１１月１０日（２０１１．１１．１０）
【国際特許分類】
【出願番号】特願２０１０−２２２７８２（Ｐ２０１０−２２２７８２）
【出願日】平成２２年９月３０日（２０１０．９．３０）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
【公開日】平成２３年１１月１０日（２０１１．１１．１０）
【国際特許分類】
【出願日】平成２２年９月３０日（２０１０．９．３０）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
[ Back to top ]