経路探索装置及び経路探索用データ生成方法

【課題】面的な空間を含む経路の探索、点・線・面混在方式による探索経路の出力を可能にする。
【解決手段】座標を有する点データ、点列を有する線データ及び境界を回る点列を有する面データの組み合わせからなる幾何図形データを含む点・線・面混在型データ１と、幾何図形データと合成され面データに代表点を設定して双方向にネットワークを形成する線データの組み合わせからなる経路探索用データ２と、経路探索用データに基づき経路探索を行う経路探索手段３、４と、経路探索手段により探索された経路を幾何図形データに基づき点・線・面混在方式による経路を描画し出力する経路出力手段５とを備え、目的地までの最適経路を探索して出力する。

【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、目的地までの最適経路を探索して出力する経路探索装置及び経路探索用データ生成方法に関する。
【背景技術】
【０００２】
最適経路探索は、従来、車両用ナビゲーション装置において、道路を示す線、並びにその端点及び交差点を示す点の集まりで表現される道路ネットワークを使って行われてきた（例えば、特許文献１、２参照）。
【特許文献１】特開平１０−２３９０８０号公報
【特許文献２】特開２００４−２８８４６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかし、従来のナビゲーション装置における最適経路探索の方式は、広場や公園などの面的な空間において、移動体の自由な行動を保証するものではなく、特に歩行や車椅子による移動にとっては、不便となる場合がある。この問題を解決するためには、道路を互いに連結する複数の面の集まりとして捉え、その上を利用者の自由意志で移動できるようにすればよい。しかし郊外、山間部及び細街路まで面によって表現すると、データ作成のためのコストが実現への障壁となる。そこで、都市の中心部など歩行者等が多い空間は面とするが、その他は線及び点によってモデル化し、点・線・面混在型のデータを使って歩行者を誘導することが考えられる。しかし、これまでそのような方式はない。
【課題を解決するための手段】
【０００４】
本発明は、上記課題を解決するものであって、面的な空間を含む経路の探索、点・線・面混在方式による探索経路の出力を可能にするものである。
【０００５】
そのために本発明は、目的地までの最適経路を探索して出力する経路探索装置として、座標を有する点データ、点列を有する線データ及び境界を回る点列を有する面データの組み合わせからなる幾何図形データを含む点・線・面混在型データと、前記幾何図形データと合成され面データに代表点を設定して双方向にネットワークを形成する線データの組み合わせからなる経路探索用データと、前記経路探索用データに基づき経路探索を行う経路探索手段と、前記経路探索手段により探索された経路を前記幾何図形データに基づき点・線・面混在方式による経路を描画し出力する経路出力手段とを備えたことを特徴とする。
【０００６】
目的地までの最適経路を探索するための経路探索用データを生成する方法として、点データ、線データ及び面データからなる幾何図形データ、前記点、線及び面に対応するノード、エッジ及びフェイスデータからなり幾何図形同士の隣接関係のみを表現する位相複体データ、幾何図形の各レコード及び位相複体データの各レコードの１対１関係を示す幾何位相関連データを入力として、前記幾何図形データの面データに対応する位相複体データのフェイスデータを新たにノードに置換してノードデータとエッジデータによりネットワークデータを経路探索基本データとして生成し、前記経路探索基本データ、幾何図形データ及び幾何位相関連データからなる経路探索用データを生成することを特徴とする。
【発明の効果】
【０００７】
本発明によれば、面的な空間を含む経路を探索する場合においても、通常の最適経路探索法によって、これが可能となる。つまり、点・線・面混在型データを経路探索用データに自動的に変換することによって、データ量が多くなる面データを直接処理対象とすることなく経路探索を可能にするとともに、経路探索用データが元の点・線・面混在型データと関連をもつことによって、より現実的な表示を可能とするものである。
【発明を実施するための最良の形態】
【０００８】
以下、本発明の実施の形態を図面を参照しつつ説明する。図１は本発明に係る経路探索装置の実施の形態を示す図、図２は幾何図形データの構成例を示す図、図３は経路探索用データの構成例を示す図、図４は探索経路の出力例を示す図である。図中、１は幾何図形データ、２は経路探索用データ、３は地点入力部、４は経路探索部、５は経路出力部を示す。
【０００９】
図１において、幾何図形データ１は、座標を有する点データ、点列を有する線データ及び境界を回る点列を有する面データからなる。例えば図２に示すように点データは、２次元の座標をもつ点レコードの集まりであり、点レコードはそれぞれの点の識別子、ｘ座標及びｙ座標の組である。線データは、点の列をもつ線レコードの集まりであり、線レコードは線の識別子及び点の列の組である。ここで、点列の第１点を始点、最終の点を終点という。面データは、その境界を左回りに廻る点の列をもつ面レコードの集まりであり、面レコードは面の識別子及び点列の組である。ここで、隣接する点列の端点は一致しなければならない。
【００１０】
経路探索用データ２は、図３に示すように幾何図形データの面データｓ１、ｓ２に代表点を設定してその代表点ｃｐ１、ｃｐ２を線データｖ１、ｖ４、ｖ９に付加し、その代表点を含む点列により経路探索のために双方向にネットワークを形成する線データｃｖ１１、ｃｖ１１１、ｃｖ１２、ｃｖ１２１、……を定義したものである。例えば図２に示す幾何図形データでは、面データｓ１、ｓ２があって、その面を回る線データｖ２、ｖ３、ｖ７〜ｖ１０が設定されているが、経路探索用データ２では、図３に示すように代表点ｃｐ１、ｃｐ２の設定に伴い、ネットワークを形成する線データとして、例えばｖ１に対応するｃｖ１１（ｃｖ１１１）、ｖ４に対応するｃｖ４（ｃｖ４１）、ｃｖ１０（ｃｖ１０１）、ｃｖ１２（ｃｖ１２１）が設定される。
【００１１】
地点入力部３は、経路探索を行う際の現在地や出発地、目的地、経由地などの地点を入力し、さらには最短距離経路、車道優先経路、歩道優先経路など好みの探索条件を入力するものであり、経路探索部４は、地点入力部３の入力に基づき経路探索用データ２を読み出して最適経路を探索し、経路出力部５は、その探索された経路を面データを有する幾何図形データ１を読み出して、図４（Ａ）に示すような点・線方式ではなく、図４（Ｂ）に示すような点・線・面混在方式で表示して出力するものである。
【００１２】
次に、経路探索用データを生成する装置、アルゴリズムについて説明する。図５は経路探索用データ生成装置のモジュール構成例を示す図、図６は位相複体データの構成例を示す図、図７は幾何位相関連データの構成例を示す図、図８は双対データの構成例を示す図、図９は経路探索基本データの構成例を示す図である。図中、１１は点・線・面混在型データ、１２は双対データ生成モジュール、１３は経路探索基本データ生成モジュール、１４は幾何データ合成モジュールを示す。
【００１３】
図５において、双対データ生成モジュール１２は、点・線・面混在型データ１１から双対データを生成して中間データ１として出力し、経路探索基本データ生成モジュール１３は、双対データ生成モジュール１で生成された双対データと点・線・面混在型データ１１から経路探索基本データを生成して中間データ２として出力し、幾何データ合成モジュール１４は、経路探索基本データ生成モジュール１３で生成された経路探索基本データと点・線・面混在型データ１１から経路探索用データを生成するものである。
【００１４】
点・線・面混在型データ１１は、３つのデータからなり、その１は幾何図形データ、その２は位相複体データ、そしてその３は幾何位相関連データである。位相複体データは、幾何図形同士の隣接関係のみを表現するデータであり、図６に示すようなフェイスデータ、エッジデータ及びノードデータからなる。隣接関係は、図形及びその境界、並びに境界及びその境界が囲む図形の関係で表現する。前者の関係は境界関係、後者の関係は双対境界関係という。例えば、線の境界は始点と終点であり、始点及び終点の双対境界はその点から出る線及びその点に入る線である。また、面の境界は線の集まりであり、線の双対境界は左右にある面である。なお、点の境界はなく、面の双対境界はない。位相複体データにおいて、点・線・面という用語を使用すると、幾何図形と混同されるので、それぞれに対応するものとしてここではノード、エッジ及びフェイスという用語を使う。
【００１５】
ノードデータは、双対境界となる出入りするエッジを示すノードレコードの集まりであり、ノードレコードはノードの識別子、出るエッジ、入るエッジの組である。エッジデータは、境界である始終ノード及び双対境界である左右フェイスをもつエッジレコードの集まりであり、エッジレコードはエッジの識別子、始点ノード、終点ノード、左側フェイス及び右側フェイスの組である。フェイスデータは、境界となるエッジ列をもつフェイスレコードの集まりであり、フェイスレコードはフェイスの識別子及びエッジ列の組である。ここで、フェイスの境界は左側にフェイスの内部が来るように、左回りでエッジを並べるものとする。また、エッジの始点から終点の方向がこのエッジの順序と反対になる場合は負号をエッジにつけて表現する。例えば、フェイス識別子ｆｌにおいてｅ６は右側にｆ１を見る方向になっているので、エッジ列の中では負号をつけて表現する。なお、位相複体データの外側を１つのフェイスとして扱い、これをユニバーサルフェイスと呼ぶ。ユニバーサルフェイスの境界は位相複体データ全体の境界となる。
【００１６】
幾何位相関連データは、図７に示すような幾何図形の各レコード及び位相複体データの各レコードの１対１関係を示す幾何位相関連レコードの集まりであり、幾何位相関連レコードは、幾何要素の識別子及びそれに対応する位相要素の識別子の組である。このデータによって、位相要素のグラフィックな表現が可能になる。なお、位相要素からそれに関連する幾何要素を求めることを、ここでは幾何実現という。
【００１７】
双対データ生成モジュール１２は、点・線・面混在型データ１１を例えば外部ファイルから入力して、双対データを中間データ１として、例えばＲＡＭに出力するモジュールである。双対データ生成モジュール１２のアルゴリズムは、図６に示すように
１）位相複体データにおいて、各フェイスｆ１、ｆ２に対応する新たなノードを生成する。ただし、ユニバーサルフェイスｕの場合は作らない。
２）２つのフェイスがエッジを境界上で共有するときこれに対応する新たなエッジをつくる。ただし、両側ともにユニバーサルフェイスのときは対応する新たなエッジは作らない。
３）新たにできるエッジはもとのエッジの左側から右側を向く。また、新たなエッジの始点及び終点ノードはもとのフェイスから新たにできたノードとする。このようにして新たにできた位相要素は、もとの位相要素が保持していた幾何実現を引き継ぐ。
４）この処理の結果得られる双対データを中間データ１として例えばＲＡＭに出力する。双対データは、位相複体データからフェイスデータを除いた仕様に従う。また、エッジレコードから左・右のフェイスを示す項目も削除するので、エッジレコードはエッジ識別子、始点ノード及び終点ノードの組となる。双対データでは、例えば図８に示すように、フェイスｆｌ、ｆ２がそれぞれ新たなノードｄｎｌ、ｄｎ２になり、両フェイスの境界は新たなエッジｄｅ１０になる。また、ｄｎｌ、ｄｎ２の幾何実現は図２に示したｓｌ、ｓ２になる。ｄｅ１０の幾何実現はｖ１０である。
【００１８】
経路探索基本データ生成モジュール１３は、双対データの中間データ１を入力して、経路探索基本データを中間データ２として、例えばＲＡＭに出力するモジュールである。このモジュールは、中間データ１として出力された面同士の隣接関係を示す双対データ及び、元の位相複体データ中のノード・エツジデータを結合する働きをもつ。以下、出力する中間データ２の仕様、及びモジュールが実現するアルゴリズムを説明する。
【００１９】
中間データ２（経路探索基本データ）の仕様は、中間データ１に、元からあったノード・エッジ及び、このモジュールで生成されるエッジを追加することによってできあがるものであり、新たな種類のデータ項目が追加されるわけではないので、その仕様は中間データ１と同じである。
【００２０】
経路探索用基本データの生成アルゴリズムは、図９に示すように
１）もとの位相複体データの中にあるノードそれぞれについて、出入りするエッジ全てがユニバーサルフェイスの境界となる場合は、そのノードのコピーを作成し（図６におけるｎｌ、ｎ４、ｎ５、ｎ６、ｎ１０）、これをノードデータに追加する。
【００２１】
２）もとの位相複体データの中にあるエッジの中で、左右がユニバーサルフェイスとなるものをエッジデータにコピーし（図６におけるｅｌ、ｅ３、ｅ４、ｅ５、ｅ８）、以下の処理を行う。
２）−１．始点及び終点が接するフェイス集合を求める（図６ではｅ１の終点がｆ１及びｆ２、ｅ３の始点がｆｌ、ｅ８の始点がｆ２、ｅｌの始点及び、ｅ４、ｅ５、ｅ８の終点がユニバーサルフェイスに接する）。
２）−２．それらのフェイス集合の中にユニバーサルフェイスがある場合は、除去する（ｅｌの始点、ｅ４、ｅ５、ｅ８の終点におけるｕ）。
２）−３．始点と接するフェイス集合に要素がないときは、ノードデータにある、この始点と同じ識別子をもったノードを始点ノードとする（ｅｌの始点はｎｌ）。
２）−４．終点と接するフェイス集合に要素がないときは、ノードデータにある、この終点と同じ識別子をもったノードを終点ノードとする（ｅ４、ｅ５、ｅ８についてはそれぞれｎ５、ｎ６、ｎ１０）。
２）−５．始点と接するフェイス集合に要素が１つ以上あるときは、ノードデータにある、そのフェイスから生成されたノードの集合を新たな始点集合として生成する（ｅ３、ｅ８の始点はそれぞれｄｎｌ、ｄｎ２）。
２）−６．終点と接するフェイス集合に要素が１つ以上あるときは、ノードデータにある、フェィスから生成されたノードの集合を新たな終点集合とする（ｅｌの終点はｄｎｌ、ｄｎ２）。
２）−７．上記２）−３．から２）−６．の手続きで求められた始点集合（ｅｌの場合はｎｌ）と終点集合（ｅｌの場合はｄｎｌ、ｄｎ２）の組み合わせを新たなエッジ集合とし、その要素全てをエッジデータに追加し、もとのエッジを削除する（ｅｌの場合は、新たにｎ１を始点、ｄｎｌを終点とするｄｅｌｌ及びｎ１を始点、ｄｎ２を終点とするｄｅｌ２が生成され、ｅｌは除かれる）。ただし、もとのエッジの幾何実現は新たなエッジに継承する（ｅｌの場合は、ｖｌがｄｅｌｌ及びｄｅｌ２の幾何実現となる）。
【００２２】
３）両方向のナビゲーションができるように、全てのエッジについて、逆方向のエッジを追加する（ｄｅｌｌｌ、ｄｅｌ２１、ｄｅｌ０１、ｄｅ３１、ｅ４１、ｅ５１、ｅ８１）。このとき、新たにできるエッジの幾何実現は、もとのエッジの幾何実現である曲線を逆方向にしたものを関連させることになる（例えばｄｅｌｌｌの場合は、−ｖｌ）。
この手順でできるネットワークデータが経路探索基本データである。
【００２３】
幾何図形データ合成モジュール１４は、中間データ２を入力して、これに幾何図形データ及び幾何位相関連データを追加して、経路探索用データとして外部記憶装置に出力するモジュールである。このモジュールは、中間データ２として出力されたネットワーク及び点・線・面混在型データ中の幾何図形データを使い、経路探索で重要な働きをするノード間の距離を求める曲線の形状を合成する働きをもつ。以下、経路探索用データの仕様、及びモジュールが実現するアルゴリズムを説明する。
【００２４】
経路探索用データの仕様は、経路探索基本データ、幾何図形データ及び幾何位相関連データからなる。幾何図形データは、点・線・面混合型データの中にある幾何図形データにおける点データ及び線データの組み合わせになる。幾何位相関連データの仕様は変わらない。
【００２５】
幾何図形データ合成のアルゴリズムは、図３に示すように以下の手順で行われる。
【００２６】
１）経路探索基本データ中の全てのエッジについて、以下のアルゴリズムを適用する。
１）−１．エッジの幾何実現としての曲線の始点について、その座標がエッジの始点ノードに一致しないときは、この曲線のはじめに始点ノードの位置を挿入する。始点ノードの幾何的な位置は、始点ノードの幾何実現としての曲面の中にある代表点を求めることによって得られる（例えば図９中、ｄｅ３の幾何実現はｖ４でありｐ１０が始点であったが、この操作により始点としてｃｐｌが追加され、幾何実現はｃｖ４になる。同様の処理はｄｅ８でも行われｃｖ９ができる）。代表点の位置は、曲面の重心を求めることによって定まるが、曲面の形状が凹の場合にはその位置が曲面の外に出ることがあるので、別の方式を用いることができる。例えば曲面の境界の内部にある点で、境界から最も遠い位置にある点（三角形では垂心に相当する）を求め、これを代表点として使うことも可能である。１）−２．エッジの幾何実現としての曲線の終点について、その位置がエッジの終点ノードに位置しないときは、この曲線の終わりに終点ノードの位置を追加する。終点ノードの幾何的な位置は、終点ノードの幾何実現としての曲面の中にある代表点を求めることによって得られる（例えば図９中、ｄｅｌｌの幾何実現はｖ１でありｐ５が終点であったが、この操作によりｃｐｌが終点として追加され、ｃｖ１１になる。同様の処理がｄｅｌ２でも行われｃｖｌ２ができる）。
【００２７】
図１０は経路探索及びその結果を表示する装置の実施の形態を示す図、図１１は最適経路探索のアルゴリズムを説明する図である。本実施形態により生成された経路探索用データを使った経路探索では、経路探索用データを外部記憶装置から入力し、経路探索用データ中の各エッジの延長（重量）を計算し、その結果並びに出発地及び到着地の地点を示す始点・終点データを入力して、その間の最適経路を求め、経路探索用データ中の幾何図形データを使ってディスプレイに表示する。この装置は、例えば図１０に示すような重量計算モジュール２１、最短経路探索モジュール２２及び表示モジュール２３からなる。
【００２８】
重量計算モジュール２１は、経路探索用データを入力して、経路探索基本データ中の各エッジに、その幾何実現としての曲線の延長を追加するモジュールである。また、曲線のうち、曲面の内部に位置する部分曲線には一定の係数（曲面係数）を延長に掛けて重量を求めることも可能である。これによって広場における歩行者の挙動が普通の道路と異なることに起因する歩行速度の違いを表現することができる。なお、経路探索用の重量は、曲線の延長に限るものではないので、特殊な重量を与える場合は、エッジ識別子及び重量を組にしたレコードの集合としての重量データをこのモジュールに入力して、各エッジに重量を割り振ることもできる。以下、重量計算モジュールが出力する重量付き経路探索用データの仕様及び重量計算のアルゴリズムを説明する。
【００２９】
重量付き経路探索用データの仕様は、経路探索用データ中の経路探索基本データにあるエッジデータの各エッジレコードに重量項目を付加したものである。従って、エッジレコードは、エッジ識別子、始点ノード、終点ノード及び重量の組になる。
【００３０】
重量計算のアルゴリズムは、
１）全てのエッジレコードについて、以下の処理を行う。
２）同一のエッジ識別子をもつレコードを幾何位相関連データから抽出し、対応する曲線レコードの識別子を得る。
３）曲線識別子をキーにして、曲線データから点列を得る。
４）点列の延長（重量）を求める。ただし、始点又は終点が曲面内にあるときは、その直後又は直前の点との距離に曲面係数を掛ける。指示がないとき、係数は１である。
５）重量を追加したエッジレコードを出力する。
【００３１】
なお、曲線の延長以外のパラメタを重量として採用する場合は、全てのエッジレコードについて、以下の処理を行う。
１）エッジ識別子及び重量でできるレコードの集合としての重量データを入力する。
２）エッジレコード及び重量データの中で同一のエッジ識別子をもつものを選び、エッジレコードに重量を追加する。
３）重量を追加したエッジレコードを出力する。
【００３２】
最短経路探索モジュール２２では、出発点・到着点データ及び重量付き経路探索用データを入力し、出発点位置から到着点位置までの最短経路を求め、最短経路データを例えばＲＡＭに出力する。以下、出発点・到着点データの仕様及び最短経路探索のアルゴリズムを説明する。
【００３３】
出発点・到着点データの仕様は、出発点レコード及び到着点レコードの組みである。両者ともに、経路探索用データにある幾何図形データの点データ中の点レコードと同じ仕様であり、点の識別子は点データ中に存在するものの中から選ばれる。
【００３４】
最短経路データの仕様は、出発点ノードから到着点ノードに至るエッジレコードの列であり、エッジデータと同じ仕様で作成される。
【００３５】
最短経路探索アルゴリズムは、図１１に示すように経路探索用データ中のネットワークデータを用い、以下の手順で行われる。
１）出発地に対応するノードを得る。これを出発点ノードとする。
２）出発点ノードに特別なラベル（＊、０）をつけ、それ以外のノードにはラベル（φ、∞）をつける。ここでφはそのノードへの最短経路が未定義であることを示す。
３）ラベル付き・未探索のノードがなければ５）にゆく。そうでなければ、そのようなノードｎを選びステップ４）にゆく。
４）ノードｎを探索する。すなわち、ノードから出るエッジｅに対してｐ（ｅの終点ノード）＞ｐ（ｎ）＋ｄ（ｅ）ならば、ｅの終点ノードにラベル（ｅ、ｐ（ｎ）＋ｄ（ｅ））をつけてｅの終点ノードを未探索の状態にする。またノードｎは既探索として３）に戻る。ここでｐは、ラベルの右側の項目であり、その出発点からそのノードまでの総重量（距離）を示す。また、ｄはそのエッジの重量（延長）である。
５）到着地に対応するノードを得る。これを到着点ノードとする。
６）到着点ノードのラベルにある直前エッジｅの識別子を得る。
７）このエッジの始点ノードのラベルにある直前エッジの識別子を得る。
８）７）の処理を、始点ノードが到着点ノードと一致するまで続ける。
９）ここまでの結果として、到着点ノードから出発点ノードまでのエッジ列が求められるので、これを逆順にすることによって、出発点から到着点までのエッジ列、つまり最短経路データが出力される。
図中の”ループ”は４）の処理の結果を示す。この例では５回の繰り返しで、ｄｎｌがらすべてのノードへの最短経路を求めている。また、到着地をｎ１０とすると、６）から８）の処理によって、エッジ列（ｄｅ８、ｄｅ１０）を求めることができ、その逆の列として、（ｄｅ１０、ｄｅ８）がｄｎｌからｎ１０への最短経路となる。
【００３６】
なお、ここで示した最短経路探索アルゴリズムは、ラベル修正法（伊理正夫監修、計算幾何学と地理情報処理、共立出版、１９８６、ｐｐｌ５２）と呼ばれる方法であるが、これ以外にも様々な方式が提案されているので、別のアルゴリズムを使う場合は、必要に応じてモジュールを入れ替えればよい。
【００３７】
表示モジュール２３は、最短経路データ及び経路探索用データ中にある幾何図形データを入力し、最短経路を示す幾何図形をディスプレイに表示する。以下、表示のためのアルゴリズムを説明する。
【００３８】
表示のアルゴリズムは、
１）最短経路データ中の全てのエッジレコードについて、以下の処理を行う。
２）エッジの始点ノードについて、幾何実現が曲面のときは、その曲面を表示する。
３）エッジの幾何実現としての曲線を表示する。
４）２）、３）の処理を全てのエッジについて繰り返す。
５）最後のエッジの終点ノードの幾何実現が曲面のときは、その曲面を表示する。
【００３９】
なお、本発明は、上記実施の形態に限定されるものではなく、種々の変形が可能である。例えば上記実施の形態では、歩行者のための経路探索用として説明したが、車両用その他の経路探索用としても同様に適用してもよい。つまり、本発明による方式は、人間、自動車及びロボットを含む移動体の誘導全てについて用いることができる。
【図面の簡単な説明】
【００４０】
【図１】本発明に係る経路探索装置の実施の形態を示す図である。
【図２】幾何図形データの構成例を示す図である。
【図３】経路探索用データの構成例を示す図である。
【図４】探索経路の出力例を示す図である。
【図５】経路探索用データ生成装置のモジュール構成例を示す図である。
【図６】位相複体データの構成例を示す図である。
【図７】幾何位相関連データの構成例を示す図である。
【図８】双対データの構成例を示す図である。
【図９】経路探索基本データの構成例を示す図である。
【図１０】経路探索及びその結果を表示する装置の実施の形態を示す図である。
【図１１】最適経路探索のアルゴリズムを説明する図である。
【符号の説明】
【００４１】
１…幾何図形データ、２…経路探索用データ、３…地点入力部、４…経路探索部、５…経路出力部

【特許請求の範囲】
【請求項１】
目的地までの最適経路を探索して出力する経路探索装置であって、
座標を有する点データ、点列を有する線データ及び境界を回る点列を有する面データの組み合わせからなる幾何図形データを含む点・線・面混在型データと、
前記幾何図形データと合成され面データに代表点を設定して双方向にネットワークを形成する線データの組み合わせからなる経路探索用データと、
前記経路探索用データに基づき経路探索を行う経路探索手段と、
前記経路探索手段により探索された経路を前記幾何図形データに基づき点・線・面混在方式による経路を描画し出力する経路出力手段と
を備えたことを特徴とする経路探索装置。
【請求項２】
目的地までの最適経路を探索するための経路探索用データを生成する方法であって、
点データ、線データ及び面データからなる幾何図形データ、前記点、線及び面に対応するノード、エッジ及びフェイスデータからなり幾何図形同士の隣接関係のみを表現する位相複体データ、幾何図形の各レコード及び位相複体データの各レコードの１対１関係を示す幾何位相関連データを入力として、
前記幾何図形データの面データに対応する位相複体データのフェイスデータを新たにノードに置換してノードデータとエッジデータによりネットワークデータを経路探索基本データとして生成し、
前記経路探索基本データ、幾何図形データ及び幾何位相関連データからなる経路探索用データを生成することを特徴とする経路探索用データ生成方法。

【図１】