JP5142151B2

JP5142151B2 - 地図情報処理装置、地図情報処理方法、およびプログラム

Info

Publication number: JP5142151B2
Application number: JP2008328405A
Authority: JP
Inventors: 琢磨瀬川
Original assignee: 株式会社ミックウェア
Priority date: 2008-12-24
Filing date: 2008-12-24
Publication date: 2013-02-13
Anticipated expiration: 2028-12-24
Also published as: JP2010151539A

Description

本発明は、始点から目的地点までの最短経路を出力する地図情報処理装置等に関するものである。

従来、ダイクストラ法 (Dijkstra's Algorithm)と呼ばれる最短経路を決定するアルゴリズムがあった（例えば、非特許文献１参照）。ダイクストラ法は、始点から放射状に距離の短い順に距離を計算しながら最短ルートをチェックしていく方法である。また、ダイクストラ法は、目的地点へたどり着いた時点でその経路が最短ルートとなるアルゴリズムである。さらに、ダイクストラ法において、必要なメモリ量と処理時間が、リンクやノードの数に比例して増加する。なお、ノードとは、地図上の地点のことである。リンクとは、ノードとノードを接続する線である。

また、従来、Ａ＊アルゴリズムと呼ばれる最短経路を決定するアルゴリズムがあった（例えば、非特許文献２参照）。Ａ＊アルゴリズムは、各頂点ｎからゴールまでの距離の推定値ｈ^＊（ｎ）を知っていた場合に対して、最短経路問題を効率的に解くアルゴリズムである。Ａ＊アルゴリズムは、ダイクストラ法に予測距離を加えた考えで、ダイクストラ法に比べて目的地点までの到達ステップが短くなる。また、Ａ＊アルゴリズムにおいて、予測距離が含まれる為、目的地点へたどり着いた時点でその経路が最短ルートとならない可能性がある。また、Ａ＊アルゴリズムにおいて、目的地までたどり着く事を優先させ、メモリ容量と処理時間を抑えることができる。
"ダイクストラ法（最短経路問題）"、［online］、［平成２０年１２月３日検索］、インターネット<URL： http://www.deqnotes.net/acmicpc/dijkstra/> "Ａ＊"［online］、［平成２０年１２月３日検索］、インターネット<URL： http://ja.wikipedia.org/wiki/A*%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0>

しかしながら、従来の地図情報処理装置においては、短時間で、精度高く、始点から目的地点までの最短経路を出力することが困難であった。

本第一の発明の地図情報処理装置は、地点の位置を示す情報である位置情報を２以上有する地図情報を格納し得る地図情報格納部と、始点を特定する始点情報および目的地点を特定する目的地点情報を受け付ける受付部と、前記地図情報に対応する領域を２以上の部分領域に分割した領域であるメッシュに関する情報であり、当該２以上の各メッシュを代表する１以上の地点に関する情報であるメッシュ情報を２以上格納し得るメッシュ情報格納部と、前記２以上のメッシュ情報を用いて、前記始点情報に対応する始点を含むメッシュから前記目的地点情報に対応する目的地点を含むメッシュであり、前記始点から前記目的地点までの最短経路を含む２以上のメッシュを選択するメッシュ選択部と、前記メッシュ選択部により選択された２以上のメッシュ内の地点の位置情報を、前記地図情報格納部から取得し、当該２以上のメッシュ内の地点の位置情報を用いて、前記始点から前記目的地点に進行する際の最短経路に関する情報である最短経路情報を取得する最短経路情報取得部と、前記最短経路情報取得部が取得した最短経路情報を出力する最短経路情報出力部を具備する地図情報処理装置である。

かかる構成により、短時間で、精度高く、始点から目的地点までの最短経路を出力することができる。

また、本第二の発明の地図情報処理装置は、第一の発明に対して、前記地図情報を２以上のメッシュに分割し、当該２以上の各メッシュに対応するメッシュ情報を２以上取得するメッシュ情報取得部をさらに具備し、前記メッシュ情報格納部のメッシュ情報は、前記メッシュ情報取得部が取得したメッシュ情報である地図情報処理装置である。

また、本第三の発明の地図情報処理装置は、第一、第二いずれかの発明に対して、前記メッシュ情報取得部は、前記地図情報に対応する領域を２以上の部分領域であるメッシュに分割するメッシュ分割手段と、当該２以上のメッシュごとに、メッシュの各辺上の１以上の地点の位置を示す位置情報である１以上の辺上地点情報を、前記地図情報格納部から取得する辺上地点情報取得手段とを具備し、前記メッシュ選択部は、前記２以上のメッシュ間の２以上の辺上地点情報を用いて、前記２以上のメッシュの各辺の間の距離である２以上の辺間距離を算出する辺間距離算出手段と、前記２以上の辺間距離を用いて、前記始点情報に対応する始点を含むメッシュから前記目的地点情報に対応する目的地点を含むメッシュであり、前記始点から前記目的地点までの最短経路を含む２以上のメッシュを選択するメッシュ選択手段とを具備する地図情報処理装置である。

また、本第四の発明の地図情報処理装置は、第一、第二いずれかの発明に対して、前記メッシュ情報取得部は、前記地図情報に対応する領域を２以上の部分領域であるメッシュに分割するメッシュ分割手段と、当該２以上のメッシュごとに、メッシュの重心に最も近い地点の位置を示す位置情報である重心地点情報を、前記地図情報格納部から取得する重心地点情報取得手段とを具備し、前記メッシュ選択部は、前記２以上のメッシュ間の２以上の重心地点情報を用いて、前記２以上のメッシュの間の距離である２以上の重心距離を算出する重心距離算出手段と、前記２以上の重心距離を用いて、前記始点情報に対応する始点を含むメッシュから前記目的地点情報に対応する目的地点を含むメッシュであり、前記始点から前記目的地点までの最短経路を含む２以上のメッシュを選択するメッシュ選択手段とを具備する地図情報処理装置である。

かかる構成により、より短時間で、精度高く、始点から目的地点までの最短経路を出力することができる。

また、本第五の発明の地図情報処理装置は、第一から第四いずれかの発明に対して、前記最短経路情報取得部は、前記メッシュ選択部により選択された２以上のメッシュごとに、当該メッシュ内の２以上の地点の位置情報を、前記地図情報格納部から取得するメッシュ内位置情報取得手段と、前記２以上の地点の位置情報を用いて、前記始点から前記目的地点までの最短経路に関する情報である最短経路情報を取得する最短経路情報取得手段とを具備する地図情報処理装置である。

また、本第六の発明の地図情報処理装置は、第一から第四いずれかの発明に対して、前記最短経路情報取得部は、前記メッシュ選択部により選択された２以上の各メッシュが仮想的に直線上に並ぶように、前のメッシュに対して上および下に存在するメッシュ、または前のメッシュに対して左および右に存在するメッシュを回転し、仮想的な直線のメッシュ群の情報を取得するメッシュ直線化手段と、前記仮想的な直線のメッシュ群の情報に含まれる２以上の地点の位置情報を用いて、前記始点から前記目的地点までの最短経路の情報を取得する最短経路情報取得手段とを具備し、前記最短経路情報出力部は、前記最短経路情報取得手段が取得した最短経路の情報を出力する地図情報処理装置である。

かかる構成により、開始位置と目的位置の位置関係に関係なく、同じ探索結果が選ばれる。

また、本第七の発明の地図情報処理装置は、第五、第六いずれかの発明に対して、前記最短経路情報取得手段は、前記２以上の地点の位置情報を用いて、ダイクストラ法により、前記始点から前記目的地点までの最短経路の情報を取得する地図情報処理装置である。

かかる構成により、既存のアルゴリズムを効果的に利用できる。

また、本第八の発明の地図情報処理装置は、第一から第七いずれかの発明に対して、前記地図情報は、前記位置情報と、当該位置情報に対応する地点が存在する道路の種類を示す道路種類情報とを対に有する地点情報を２以上有し、前記メッシュ選択部は、一の道路種類情報と対になる位置情報が示す地点を含むメッシュ、または一の道路種類情報と対にならない位置情報が示す地点を含むメッシュを、他のメッシュと比較して優先して選択する地図情報処理装置である。

かかる構成により、道路の種類を考慮した、より適切な最短経路を出力することができる。

また、本第九の発明の地図情報処理装置は、第八の発明に対して、一の道路種類情報を受け付ける受付部をさらに具備し、前記メッシュ選択部は、前記受付部が受け付けた一の道路種類情報と対になる位置情報が示す地点を含むメッシュ、または前記受付部が受け付けた一の道路種類情報と対にならない位置情報が示す地点を含むメッシュを、他のメッシュと比較して優先して選択する地図情報処理装置である。

かかる構成により、道路の種類を、ユーザから受け付けることができる。

本発明による地図情報処理装置によれば、短時間で、精度高く、始点から目的地点までの最短経路を出力することができる。

以下、地図情報処理装置等の実施形態について図面を参照して説明する。なお、実施の形態において同じ符号を付した構成要素は同様の動作を行うので、再度の説明を省略する場合がある。

（実施の形態１）
本実施の形態において、短時間で、精度高く、始点から目的地点までの最短経路を出力する地図情報処理装置について説明する。また、地図情報処理装置において、メッシュ列を選択する第１ステップ、メッシュ内の各点を用いて、最短経路を決定する第２ステップの、大きく２段階に処理が分かれる。また、地図情報処理装置において、一の道路種類（例えば、高速道路）を受け付け、当該道路を優先して、最短経路を決定する。また、地図情報処理装置において、一の道路種類（例えば、高速道路）を受け付け、当該道路以外の道路を優先して、最短経路を決定しても良い。なお、第１ステップにおいて、メッシュごとに、一の代表点を用いて、メッシュ列を選択することは好適である。

図１は、本実施の形態における地図情報処理装置１のブロック図である。地図情報処理装置１は、受付部１１、地図情報格納部１２、メッシュ情報格納部１３、メッシュ情報取得部１４、メッシュ選択部１５、最短経路情報取得部１６、最短経路情報出力部１７を具備する。メッシュ情報取得部１４は、メッシュ分割手段１４１、辺上地点情報取得手段１４２を具備する。メッシュ選択部１５は、辺間距離算出手段１５１、メッシュ選択手段１５２を具備する。最短経路情報取得部１６は、メッシュ内位置情報取得手段１６１、最短経路情報取得手段１６２を具備する。

受付部１１は、始点を特定する始点情報および目的地点を特定する目的地点情報を受け付ける。受付部１１は、目的地点情報を含む指示であり、始点から目的地点までの最短経路を出力する指示である最短経路出力指示を受け付けても良い。最短経路出力指示は、始点情報と目的地点情報を有することは好適である。また、最短経路出力指示は、一の道路種類情報を有しても良い。つまり、受付部１１は、一の道路種類情報も受け付けても良い。ここで、始点情報とは、例えば、（緯度，経度）の位置情報、地名などである。始点情報は、スタート地点を示す情報であれば良い。また、始点情報は、図示しないナビゲーション装置または、図示しないＧＰＳ受信機から受け付けた現在位置を示す情報でも良い。目的地点情報とは、例えば、（緯度，経度）の位置情報、地名など、目的地点を示す情報であれば良い。また、「受け付ける」とは、ナビゲーション装置のタッチパネルを利用したユーザ入力の受け付け、キーボードやマウスなどの入力手段からの受け付け、外部装置からの受信、記録媒体からの読み出しなどである。道路種類情報とは、地点が存在する道路の種類を示す情報である。道路種類情報とは、「高速道路」「一般道路」などである。始点情報および目的地点情報等の入力手段は、キーボードやマウスやテンキーやメニュー画面によるもの等、何でも良い。受付部１１は、キーボード等の入力手段のデバイスドライバーや、メニュー画面の制御ソフトウェア等で実現され得る。

地図情報格納部１２は、地図情報を格納し得る。地図情報は、地図に関する情報であり、地点の位置を示す情報である位置情報を２以上有する。地図情報は、通常、地図の図柄情報を含む。図柄情報は、地図自体の情報であり、ビットマップ、ベクターデータ等、問わない。つまり、地図情報のフォーマット等は問わない。また、地図情報は、通常、位置情報と、当該位置情報に対応する地点が存在する道路の種類を示す道路種類情報とを対に有する地点情報を２以上有する。また、地図情報は、位置情報が示す地点の間のスコアを有する。スコアとは、地点間の距離や地点間の通行のし易さ、または通行のし難さを示す情報である。地図情報格納部１２は、不揮発性の記録媒体が好適であるが、揮発性の記録媒体でも実現可能である。地図情報格納部１２に地図情報が記憶される過程は問わない。例えば、記録媒体を介して地図情報が地図情報格納部１２で記憶されるようになってもよく、通信回線等を介して送信された地図情報が地図情報格納部１２で記憶されるようになってもよく、あるいは、入力デバイスを介して入力された地図情報が地図情報格納部１２で記憶されるようになってもよい。

メッシュ情報格納部１３は、メッシュ情報を２以上格納し得る。メッシュ情報とは、メッシュに関する情報である。メッシュ情報とは、メッシュを代表する１以上の地点に関する情報である。メッシュ情報は、通常、メッシュを代表する１以上の地点の位置情報である。また、メッシュとは、地図情報に対応する領域（例えば、「全体領域」という。）を２以上の部分領域に分割した領域である。メッシュは、通常、矩形領域である。メッシュは、例えば、１２ｋｍ×１０ｋｍの矩形領域である。ただし、メッシュは、他の形状の領域でも良い。メッシュ情報格納部１３は、不揮発性の記録媒体が好適であるが、揮発性の記録媒体でも実現可能である。メッシュ情報格納部１３にメッシュ情報が記憶される過程は問わない。例えば、記録媒体を介してメッシュ情報がメッシュ情報格納部１３で記憶されるようになってもよく、通信回線等を介して送信されたメッシュ情報がメッシュ情報格納部１３で記憶されるようになってもよく、あるいは、入力デバイスを介して入力されたメッシュ情報がメッシュ情報格納部１３で記憶されるようになってもよい。

メッシュ情報取得部１４は、地図情報格納部１２の地図情報から、２以上のメッシュ情報を取得する。つまり、メッシュ情報取得部１４は、通常、地図情報格納部１２の地図情報を２以上のメッシュに分割し、２以上の各メッシュに対応するメッシュ情報を２以上取得する。メッシュ情報取得部１４は、取得した２以上のメッシュ情報をメッシュ情報格納部１３に蓄積する。メッシュ情報取得部１４は、通常、ＭＰＵやメモリ等から実現され得る。メッシュ情報取得部１４の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。

メッシュ分割手段１４１は、地図情報に対応する領域を２以上の部分領域であるメッシュに分割する。ここで、分割するとは、通常、分割されたメッシュを特定する情報を取得することである。メッシュを特定する情報は、例えば、メッシュの左上座標と右下座標の情報や、メッシュＩＤなどである。なお、座標情報は、例えば、（緯度，経度）の情報である。また、座標情報は、例えば、平面上の座標情報(ｘ，ｙ)でも良い。メッシュ分割手段１４１は、通常、ＭＰＵやメモリ等から実現され得る。メッシュ分割手段１４１の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。

辺上地点情報取得手段１４２は、２以上のメッシュごとに、１以上の辺上地点情報を、地図情報格納部１２から取得する。辺上地点情報は、メッシュの各辺上の１以上の地点の位置を示す位置情報を有する。また、通常、辺上地点情報は、辺上地点の間のスコアも有する。なお、辺上地点情報取得手段１４２は、各メッシュの辺ごとに、一つの辺上地点情報（一つの点の情報）を取得することは好適である。経路を決定する際の計算量を少なくするためである。辺上地点情報は、例えば、（緯度，経度）の位置情報などであり、そのデータ形式は問わない。辺上地点情報取得手段１４２は、他のメッシュに対して取得した辺上地点情報と同じ辺上地点情報を、再度、取得する必要はない。辺上地点情報取得手段１４２は、通常、ＭＰＵやメモリ等から実現され得る。辺上地点情報取得手段１４２の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。

メッシュ選択部１５は、始点から目的地点までの最短経路を含む２以上のメッシュを選択する。メッシュ選択部１５は、２以上のメッシュ情報を用いて、始点情報に対応する始点を含むメッシュから目的地点情報に対応する目的地点を含むメッシュであり、始点から目的地点までの最短経路を含む２以上のメッシュを選択する。ここでの最短経路は、地図情報処理装置１が最短経路であると判断すれば良く、実際に最短経路で無い場合もあり得る。また、ここでの最短経路は、２以上のメッシュ情報を用いて、最短であると判断され得る経路である。メッシュ選択部１５が取得する２以上のメッシュの情報は、通常、メッシュの連結の順序の情報も含む。メッシュ選択部１５が取得する２以上のメッシュの情報は、例えば、メッシュ識別子列などである。なお、通常、辺を共通に有するメッシュは２つであり、その一つは始点方向のメッシュ、他の一つは目的地点方向のメッシュである。また、メッシュ選択部１５は、一の道路種類情報と対になる位置情報が示す地点を含むメッシュ、または一の道路種類情報と対にならない位置情報が示す地点を含むメッシュを、他のメッシュと比較して優先して選択することは好適である。ここで、一の道路種類情報は、通常、受付部１１が受け付けた一の道路種類情報である。また、最短経路とは、地図情報処理装置１が最短経路であると判断すれば良く、実際に最短経路で無い場合もあり得る。メッシュ選択部１５は、通常、ＭＰＵやメモリ等から実現され得る。メッシュ選択部１５の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。

辺間距離算出手段１５１は、２以上のメッシュ間の２以上の辺上地点情報を用いて、２以上のメッシュの各辺の間の距離である２以上の辺間距離を算出する。ここで、辺間距離算出手段１５１は、すべての辺間の距離を算出する必要はない。辺間距離算出手段１５１は、始点から目的地点までのルートを含む複数のメッシュを決定できれば良い。また、始点から辺上地点情報が示す辺上地点までの距離も辺間距離である、と考える。さらに、目的地点から辺上地点情報が示す辺上地点までの距離も辺間距離である、と考える。ここでも距離とは、上記のスコアと同意義である、と考えて良い。また、辺間距離の算出とは、辺間距離の取得でも良い。つまり、辺間距離の算出とは、結果として、辺間距離が得られれば良い。辺間距離算出手段１５１は、通常、ＭＰＵやメモリ等から実現され得る。辺間距離算出手段１５１の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。

メッシュ選択手段１５２は、辺間距離算出手段１５１が算出した２以上の辺間距離を用いて、始点情報に対応する始点を含むメッシュから目的地点情報に対応する目的地点を含む始点から目的地点までの最短経路を含む２以上のメッシュを選択する。メッシュ選択手段１５２は、通常、以下のようにして、２以上のメッシュを選択する。第一に、メッシュ選択手段１５２は、２以上の辺間距離を用いて、始点から目的地点までの、辺上地点を通過する最短経路を取得する。そして、メッシュ選択手段１５２は、ここで言う最短経路を構成する、始点情報、１以上の辺上地点情報、目的地点情報を取得する。かかる場合のアルゴリズムは、例えば、ダイクストラ法である。第二に、メッシュ選択手段１５２は、最短経路が通過するメッシュに関する情報を取得する。メッシュに関する情報とは、例えば、メッシュの識別情報である。メッシュ選択手段１５２は、通常、ＭＰＵやメモリ等から実現され得る。メッシュ選択手段１５２の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。

最短経路情報取得部１６は、メッシュ選択部１５により選択された２以上のメッシュ内の地点の位置情報を、地図情報格納部１２から取得し、当該２以上のメッシュ内の地点の位置情報を用いて、始点から目的地点に進行する際の最短経路に関する情報である最短経路情報を取得する。なお、最短経路情報取得部１６は、メッシュ選択部１５により選択された２以上のメッシュ内の地点（例えば、位置情報とスコアなど）情報を取得することは好適である。さらに、最短経路情報取得部１６は、メッシュ選択部１５により選択された２以上のメッシュ内のすべての地点のみを利用して、始点から目的地点に進行する際の最短経路に関する情報である最短経路情報を取得することは好適である。また、最短経路情報取得部１６は、２以上の位置情報からダイクストラ法を用いて、始点から目的地点までの最短経路の情報を取得しても良いし、Ａ＊（エー・スター法）を用いて、始点から目的地点までの最短経路の情報を取得しても良い。

なお、最短経路情報取得部１６は、メッシュ選択部１５により選択された２以上の各メッシュに対して、メッシュ内最短経路情報を取得しても良い。メッシュ内最短経路情報とは、メッシュ内の最短経路の情報である。メッシュ内最短経路情報は、以下の３つの場合があり得る。第一は、始点から、始点を含むメッシュと次のメッシュとの境界辺に進行する際の最短経路に関する情報である。つまり、第一は、始点から辺上地点への最短経路に関する情報である。第二は、前のメッシュとの境界辺から次のメッシュとの境界辺に進行する際の最短経路に関する情報である。つまり、第二は、辺上地点から辺上地点への最短経路に関する情報である。第三は、目的地点を含むメッシュと前のメッシュとの境界辺から目的地点に進行する際の最短経路に関する情報である。つまり、第三は、辺上地点から目的地点への最短経路に関する情報である。最短経路情報取得部１６は、通常、ＭＰＵやメモリ等から実現され得る。最短経路情報取得部１６の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。

メッシュ内位置情報取得手段１６１は、メッシュ選択部１５により選択された２以上のメッシュごとに、メッシュ内の２以上の地点の情報（例えば、位置情報とスコア）を、地図情報格納部１２から取得する。ここで、２以上の位置情報とは、通常、地図情報が有する、メッシュ内のすべての位置情報であるが、選択的に取得された一部の位置情報でも良い趣旨である。メッシュ内位置情報取得手段１６１は、一の道路種類情報と対になる位置情報、または一の道路種類情報と対にならない位置情報を、他の位置情報と比較して優先して選択することは好適である。メッシュ内位置情報取得手段１６１は、通常、ＭＰＵやメモリ等から実現され得る。メッシュ内位置情報取得手段１６１の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。

最短経路情報取得手段１６２は、メッシュ内位置情報取得手段１６１が取得した地点の情報を用いて、始点から目的地点に進行する際の最短経路に関する情報である最短経路情報を取得する。最短経路情報取得手段１６２は、２以上の位置情報を用いて、メッシュ内最短経路情報を、２以上の各メッシュごとに取得しても良い。２以上の位置情報は、メッシュ内位置情報取得手段１６１が取得した位置情報である。メッシュ内最短経路情報は、前のメッシュとの境界辺から次のメッシュとの境界辺に進行する際の最短経路に関する情報など、上述した３種類の態様があり得る。また、最短経路情報取得手段１６２は、２以上の位置情報からダイクストラ法を用いて、始点から目的地点までの最短経路の情報を取得しても良いし、Ａ＊（エー・スター法）を用いて、始点から目的地点までの最短経路の情報を取得しても良い。最短経路情報取得手段１６２は、通常、ＭＰＵやメモリ等から実現され得る。最短経路情報取得手段１６２の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。

最短経路情報出力部１７は、最短経路情報取得部１６が取得した２以上のメッシュ内最短経路情報を出力する。つまり、最短経路情報出力部１７は、始点から目的地点までの最短経路を出力する。ここで、出力とは、ディスプレイへの表示、プロジェクターを用いた投影、プリンタへの印字、音出力、外部の装置への送信、記録媒体への蓄積、他の処理装置や他のプログラム等への処理結果の引渡し等を含む概念である。最短経路情報出力部１７は、ディスプレイやスピーカー等の出力デバイスを含むと考えても含まないと考えても良い。最短経路情報出力部１７は、出力デバイスのドライバーソフトまたは、出力デバイスのドライバーソフトと出力デバイス等で実現され得る。

次に、地図情報処理装置の動作について図２のフローチャートを用いて説明する。なお、図２のフローチャートの動作開始前に、メッシュ情報取得部１４は、地図情報格納部１２の地図情報から、２以上のメッシュ情報を取得した、とする。そして、メッシュ情報取得部１４は、当該２以上のメッシュ情報を、メッシュ情報格納部１３に格納した、とする。

（ステップＳ２０１）受付部１１は、始点情報および目的地点情報を有する最短経路出力指示を受け付けたか否かを判断する。最短経路出力指示を受け付ければステップＳ２０２に行き、最短経路出力指示を受け付けなければステップＳ２０１に戻る。

（ステップＳ２０２）メッシュ選択部１５は、始点から目的地点までの最短経路を含む２以上のメッシュを選択する。このメッシュ選択処理の詳細について、図３のフローチャートを用いて説明する。

（ステップＳ２０４）最短経路情報取得部１６は、最短経路情報を取得する。最短経路情報取得処理について、図４のフローチャートを用いて説明する。

（ステップＳ２０４）最短経路情報出力部１７は、最短経路情報取得部１６が取得した２以上の最短経路情報を出力する。ここで、最短経路情報の出力態様は問わない。最短経路情報出力部１７は、現在の位置（例えば、図示しないナビゲーション装置から与えられる自動車の現在走行位置）を含んで表示されている地図上の道路であり、最短経路情報が示す道路の一部を出力しても良い。ステップＳ２０１に戻る。

なお、図２のフローチャートにおいて、電源オフや処理終了の割り込みにより処理は終了する。

次に、ステップＳ２０２のメッシュ選択処理の詳細について、図３のフローチャートを用いて説明する。

（ステップＳ３０１）メッシュ選択部１５は、カウンタｉに１を代入する。

（ステップＳ３０２）メッシュ選択部１５は、メッシュ情報格納部１３に格納されているメッシュ情報に対応するｉ番目のメッシュが存在するか否かを判断する。ｉ番目のメッシュが存在すればステップＳ３０３に行き、ｉ番目のメッシュが存在しなければステップＳ３０７に行く。

（ステップＳ３０３）メッシュ選択部１５は、ステップＳ２０１で受付部１１が受け付けた最短経路出力指示の中に、道路種類情報が含まれるか否かを判断する。道路種類情報が含まれればステップＳ３０４に行き、道路種類情報が含まれなければステップＳ３０５に行く。

（ステップＳ３０４）メッシュ選択部１５の辺間距離算出手段１５１は、ｉ番目のメッシュの辺上地点情報であり、道路種類情報に対応する辺上地点情報を取得する。なお。ここで、辺間距離算出手段１５１は、既に取得された辺の上の辺上地点情報は取得しない。また、道路種類情報に対応する辺上地点情報が存在しない場合、辺間距離算出手段１５１は、道路種類情報に対応しない辺上地点情報を取得する。つまり、ここでは、辺間距離算出手段１５１は、道路種類情報に対応する辺上地点情報を優先して取得する。ステップＳ３０６に行く。

（ステップＳ３０５）辺間距離算出手段１５１は、ｉ番目のメッシュの辺上地点情報をすべて取得する。なお、辺間距離算出手段１５１は、（ｉ−１）番目のメッシュの辺上地点情報に対応する道路種類情報と同一の道路種類情報と対になるｉ番目のメッシュの辺上地点情報のみを取得することは好適である。

（ステップＳ３０６）メッシュ選択部１５は、カウンタｉを１、インクリメントする。ステップＳ３０２に戻る。

（ステップＳ３０７）辺間距離算出手段１５１は、すべてのメッシュの各々に対して、メッシュ内の辺間距離を算出し、少なくとも一時蓄積する。辺間距離とは、メッシュ内の辺上地点と辺上地点の間の距離であり、道路で繋がっている辺上地点と辺上地点の間の距離である。また、始点を含むメッシュに関して、辺間距離とは、始点からメッシュの各辺の辺上地点までの間の距離であり、始点と道路で繋がっている辺上地点との間の距離である。また、目的地点を含むメッシュに関して、辺間距離とは、メッシュの各辺の辺上地点から目的地点までの間の距離であり、目的地点と道路で繋がっている辺上地点との間の距離である。さらに、辺間距離とは、同一の辺の地点間の距離である場合もある。

（ステップＳ３０８）メッシュ選択手段１５２は、ステップＳ３０７で蓄積された複数の辺間距離を用いて、始点から目的地点までの最短経路を決定する。この最短経路は、始点、目的地点、辺上地点のみを用いて算出された最短経路であり、ここでは、仮最短経路という。

（ステップＳ３０９）メッシュ選択手段１５２は、ステップＳ３０８で決定した仮最短経路が通過するすべてのメッシュの識別情報を取得し、少なくとも一時蓄積する。なお、メッシュの識別情報とは、メッシュ情報格納部１３に格納されているメッシュ情報の識別子でも良いし、メッシュ（例えば、矩形）を特定する左上点の座標値と右下点の座標値でも良いし、メッシュ内の地点の情報（例えば、メッシュ内の辺上地点情報の集合）でも良い。メッシュの識別情報とは、メッシュを識別できる情報であれば良い。また、メッシュの識別情報がメッシュ内の辺上地点情報の集合である場合、ステップＳ３１０の処理は不要となる。

（ステップＳ３１０）メッシュ選択手段１５２は、仮最短経路における各メッシュの辺上地点情報の集合を、少なくとも一時蓄積する。上位処理にリターンする。

次に、ステップＳ２０５のメッシュ内最短経路情報を取得する処理例の詳細について、図４のフローチャートを用いて説明する。

（ステップＳ４０１）最短経路情報取得部１６は、カウンタｉに１を代入する。

（ステップＳ４０２）メッシュ内位置情報取得手段１６１は、は、ステップＳ２０２で選択されたメッシュの中に、ｉ番目のメッシュが存在するか否かを判断する。ｉ番目のメッシュが存在すればステップＳ４０３に行き、ｉ番目のメッシュが存在しなければステップＳ４０５に行く。

（ステップＳ４０３）メッシュ内位置情報取得手段１６１は、は、ｉ番目のメッシュのメッシュ内の地点の情報（例えば、位置情報とスコア）を取得する。

（ステップＳ４０４）最短経路情報取得部１６は、カウンタｉを１、インクリメントする。ステップＳ４０２に戻る。

（ステップＳ４０５）最短経路情報取得手段１６２は、始点情報および目的地点情報（通常、位置情報）を取得する。

（ステップＳ４０６）最短経路情報取得手段１６２は、始点情報が示す始点から終点情報が示す終点までの最短経路の情報を、ステップＳ４０３で取得された地点の情報、およびステップＳ４０５で取得された始点情報および目的地点情報を用いて取得する。ここで、最短経路情報取得手段１６２は、ダイクストラ法を用いて、始点から目的地点までの最短経路の情報を取得することが好適であるが、Ａ＊（エー・スター法）を用いて、始点から目的地点までの最短経路の情報を取得しても良い。上位処理にリターンする。

以下、本実施の形態における地図情報処理装置１の具体的な動作について説明する。まず、地図情報処理装置１の動作の概念について説明する。

今、始点（Ｓ）から目的地点（Ｇ）までの最短経路を出力する場合を考える。上述したダイクストラ法で、経路探索を行うと、膨大なメモリ容量が必要になり、不都合が大きい。また、ダイクストラ法では、膨大な経路探索時間が必要になる。また、上述したＡ＊法で目的地にたどり着くまで探索を行うと、図５に示すように、常に直線的に経路を決定するため、最適な経路にならない場合がある。つまり、Ａ＊法では、経路５１を最短経路と決定する。一方、実際の最適な経路（最短経路）は、経路５２である。なお、始点（Ｓ）は神戸であり、目的地点（Ｇ）は知多半島のある地点である。

地図情報処理装置１は、かかる従来の経路決定のアルゴリズムの課題を解決するものである。

地図情報処理装置１において、地図情報から、その部分領域である複数のメッシュを作成する。そして、地図情報処理装置１では、第一ステップとして、メッシュを１ノードとしたデータを作成し、詳細に探索するメッシュを限定して、決定する。ここで、第１ステップでは、例えば、ダイクストラ法を用いて、詳細に探索するメッシュを決定することは好適である。ただし、第一ステップにおいて、Ａ＊法などの他のアルゴリズムを用いても良い。地図情報処理装置１は、第１ステップにおいて、図６の地図の網掛けのメッシュを選択する。なお、図６において、各矩形はメッシュである。ここで、図６のメッシュは、例えば、約１２ｋｍ×１０ｋｍの矩形である。そして、図６における地図情報内には５００３のメッシュが存在している。また、図６は、すべてのメッシュを表示しているわけではなく、概念図である。

次に、地図情報処理装置１では、第２ステップとして、選択されたメッシュ内の各点を用いて、始点から目的地点までの最短経路を決定する。第２ステップでは、例えば、ダイクストラ法を用いて、メッシュ内の最短経路を決定することは好適である。ただし、第２ステップにおいて、Ａ＊法などの他のアルゴリズムを用いても良い。地図情報処理装置１は、第２ステップにおいて、図５の経路５２を選択し、出力する。なお、第２ステップにおいて、さらに、各メッシュをさらに分割し、サブメッシュを構成し、サブメッシュを選択し（ここまでは、上記の第１ステップの処理）、各サブメッシュに対して、ダイクストラ法やＡ＊法などを用いて、最短経路を決定しても良い。つまり、メッシュに分割して、メッシュを選択する処理（第１ステップの処理）を２回以上、再帰的に行っても良い。そして、選択されたメッシュ（サブメッシュや、さらに細かいメッシュでも良い）の各地点の情報を用いて、始点から目的地点までの最短経路を取得するようにしても良い（この処理は第２ステップの処理）。

以下、地図情報処理装置１の具体的な動作の詳細について説明する。図７は、地図情報格納部１２が保持している地図情報を構成する地点情報管理表である。地点情報管理表は、１以上の地点情報を保持している。地点情報管理表は、「ＩＤ」「地点情報」を有するレコードを１以上保持している。「ＩＤ」は、地点情報を識別する情報である。「地点情報」は、「位置情報」「道路種類情報」「接続地点ＩＤ」を有する。「位置情報」は、地図上の地点の位置を識別する情報である。「位置情報」は、例えば、（緯度，経度）である。また、「位置情報」は、例えば、（地図上のＸ座標値，地図上のＹ座標値）である。その他、「位置情報」のフォーマット等は問わない。「道路種類情報」は、地点が存在する道路の種類を識別する情報である。ここでは、「道路種類情報」が「１」の場合、その道路の種類は「高速道路」である。また、「道路種類情報」が「０」の場合、その道路の種類は「一般道路」である。なお、ここでは、道路種類情報は、２種類であるが、３種類以上に分類する情報であっても良い。例えば、道路種類情報は、高速道路「１」、国道「２」、県道「３」、その他の一般道路「４」などでも良い。「接続地点ＩＤ」は、その地点と直接に繋がっている地点（地点情報で識別される地点）のＩＤを示す。「接続地点ＩＤ」は、３以上の地点ＩＤを有し得る、交差点の中心部の地点は、例えば、４つの接続地点ＩＤを有する。したがって、図７の地点情報管理表は、非正規のデータベースになっている。また、地図情報格納部１２が格納している地図情報は、通常、図５等に示すような地図の図柄情報を有する。図柄情報は、ベクターでもビットマップでもよく、そのデータ構造は問わない。また、ここでの地図情報は一例であり、地図情報のデータ構造は問わないことは言うまでもない。さらに、地点情報管理表は、地点間のコストを含むことは好適である。

また、図８は、メッシュ情報格納部１３に格納されているメッシュ区分情報管理表である。メッシュ区分情報管理表は、各メッシュの領域を識別する情報（「メッシュ領域識別情報」という）を管理している。メッシュ区分情報管理表は、「メッシュＩＤ」「左上地点」「右下地点」を有するレコードを1以上保持している。「メッシュＩＤ」は、メッシュを識別する情報である。「メッシュＩＤ」の「１Ａ」は、図６の左上のメッシュを示す。ここでは、「メッシュＩＤ」は、地図をメッシュに区分した際の縦のアドレス（数値）と、横のアドレス（大文字のアルファベット）で示されている。「左上地点」は、メッシュの左上隅の地点を識別する情報である。「右下地点」は、メッシュの右下隅の地点を識別する情報である。「左上地点」および「右下地点」は、ここでは、（緯度，経度）である。

また、図９は、メッシュ情報格納部１３に格納されているメッシュ情報管理表である。メッシュ情報管理表は、１以上のメッシュ情報を管理している。メッシュ情報管理表は、「メッシュＩＤ」と「メッシュ情報」を有する。「メッシュ情報」は、メッシュの各辺上の地点を示す辺上地点ＩＤを有する。「メッシュ情報」は、ここでは「上辺の辺上地点ＩＤ」「下辺の辺上地点ＩＤ」「左辺の辺上地点ＩＤ」「右辺の辺上地点ＩＤ」を有する。「上辺の辺上地点ＩＤ」は、メッシュの上部の辺上に存在する地点ＩＤである。「下辺の辺上地点ＩＤ」は、メッシュの下部の辺上に存在する地点ＩＤである。「左辺の辺上地点ＩＤ」は、メッシュの左部の辺上に存在する地点ＩＤである。「右辺の辺上地点ＩＤ」は、メッシュの右部の辺上に存在する地点ＩＤである。「上辺の辺上地点ＩＤ」「下辺の辺上地点ＩＤ」「左辺の辺上地点ＩＤ」「右辺の辺上地点ＩＤ」内のデータは、一つの地点ＩＤでも良いし、複数の地点ＩＤでも良い。なお、図９において、重複して同一の地点ＩＤを保持していなくても良い。

なお、図８のメッシュ区分情報管理表、および図９のメッシュ情報管理表は、メッシュ情報取得部１４が、地図情報格納部１２の地図情報から、構成した情報である。つまり、メッシュ情報取得部１４は、予め決められたルールに従ってメッシュＩＤを生成する。そして、メッシュ情報取得部１４は、地図情報格納部１２の地図情報を予め決められたサイズ、形状の部分領域に分割し、分割した各部分領域（メッシュ）の左上地点の（緯度，経度）を取得し、かつ、各部分領域（メッシュ）の右下地点の（緯度，経度）を取得する。そして、各メッシュの左上地点の（緯度，経度）、右下地点の（緯度，経度）、および対応するメッシュＩＤを対にして、メッシュ区分情報管理表に書き込む。

次に、メッシュ情報取得部１４は、各メッシュごとに、４つの各辺の上に存在する地点ＩＤを地図情報（図７参照）から取得し、図９のメッシュ情報管理表に書き込む。なお、地点ＩＤは、図７の「ＩＤ」である。また、メッシュの左上地点および右下地点の情報が分かっているので、メッシュ情報取得部１４は、メッシュの４辺（４つの線）の情報（始点、終点の情報）は取得できる。また、４辺（４つの線）の情報が取得され得るので、メッシュ情報取得部１４が、その辺上に存在する地点ＩＤを、図７の地点情報管理表から取得することは容易である。かかる技術は公知技術であるので、詳細な説明を省略する。

かかる状況において、ユーザは、目的地点を地図情報処理装置１に入力した、とする。そして、ユーザは、地図情報処理装置１に対して、最短経路出力の指示を入力した、とする。なお、ユーザが入力する目的地点は、地名でも良いし、（緯度，経度）でも良いし、住所等でも良い。

次に、図示しないナビゲーション装置が、現在位置の情報である始点情報（緯度，経度）を取得し、地図情報処理装置１に渡した、とする。

次に、地図情報処理装置１の受付部１１は、始点情報および目的地点情報を有する最短経路出力指示を受け付ける。なお、受付部１１は、ユーザが入力した目的地点を（緯度，経度）に変換する、とする。

次に、メッシュ選択部１５は、始点から目的地点までの最短経路を含む２以上のメッシュを、以下のように選択する。

つまり、まず、メッシュ選択部１５の辺間距離算出手段１５１は、すべての辺間（辺上の隣接する地点の間であり、道路で繋がっている地点の間）の距離を算出する。そして、辺間距離算出手段１５１は、概念的には、図１０に示すようなノード（地点）間のリンクと、リンクの距離（辺間距離）を得て、辺間距離と、リンクの始点の情報（辺上地点情報）と、終点の情報（辺上地点情報）とを対にして、メモリ等の記憶媒体に蓄積する。なお、図１０において、リンクの距離については、一部の値のみを記載している。なお、辺間の距離は、一の辺上の２地点間の距離である場合もある。また、上述したように、辺間の距離は、始点からメッシュの各辺の辺上地点までの間の距離である場合もある。さらに、上述したように、辺間の距離は、メッシュの各辺の辺上地点から目的地点までの間の距離である場合もある。また、辺間距離算出手段１５１は、予め格納されている地点間のコストを読み出して、辺間距離としても良い。

次に、メッシュ選択手段１５２は、記憶媒体に蓄積した複数の辺間距離を用いて、始点から目的地点までの仮最短経路を決定する。図１１において、この仮最短経路は、太線で示している。

次に、メッシュ選択手段１５２は、決定した仮最短経路が通過するすべてのメッシュの識別情報を取得し、少なくとも一時蓄積する。メッシュ選択手段１５２が取得したメッシュの概念図を、図１２に示す。図１２において、網掛けのメッシュが、選択されたメッシュである。そして、メッシュ選択手段１５２は、図１３に示すように、少なくとも一時的に、メモリ等の記憶媒体に、メッシュ識別子の集合を記録する。なお、メッシュ識別子の集合は格納されている順序が、始点から目的地点に向かうメッシュの順序である。ここで、メッシュ選択手段１５２は、１３のメッシュを選択したこととなる。

次に、１番目から１３番目までの各メッシュに対して、最短経路情報取得部１６は、メッシュ内最短経路情報を取得する。

つまり、まず、最短経路情報取得部１６のメッシュ内位置情報取得手段１６１は、最短経路出力指示に含まれる始点情報を取得する。

次に、メッシュ内位置情報取得手段１６１は、１番目から１３番目までのメッシュ内のすべての地点の位置情報、または地点間の距離を示す距離情報（コストとも言う。）を取得し、少なくとも一時蓄積する。

そして、次に、最短経路情報取得手段１６２は、始点情報および目的地点情報を取得する。

そして、最短経路情報取得手段１６２は、始点情報が示す始点から終点情報が示す終点までの最短経路の情報を、取得された１３のメッシュ内の地点の情報、および始点情報と目的地点情報を用いて取得する。ここで、最短経路情報取得手段１６２は、ダイクストラ法を用いて、始点から目的地点までの最短経路の情報を取得し、記憶媒体に蓄積する。

次に、最短経路情報出力部１７は、最短経路情報取得部１６が取得し、記憶媒体に蓄積した最短経路情報を出力する。その結果、ユーザは、例えば、図１４に示す最短経路の情報を得る。

以上、本実施の形態によれば、地図情報処理装置１は、始点から目的地点までの最短経路を出力する際に、各メッシュの代表地点（ここでは、辺上地点情報）を用いて、メッシュ列を選択する第１ステップ、メッシュ内の各点を用いて、最短経路を決定する第２ステップの、大きく２段階に処理を分けて実行する。その結果、短時間で、精度高く、始点から目的地点までの最短経路を出力することができる。

なお、本実施の形態において、上述したメッシュ列を選択する処理のアルゴリズムは一例であり、問わないことは言うまでもない。また、本実施の形態において、上述したメッシュ内の最短経路を取得する処理のアルゴリズムは一例であり、問わないことは言うまでもない。

また、本実施の形態の具体例によれば、道路種類情報は考慮しなかった。しかし、受付部１１が道路種類情報を受け付けた場合、当該道路種類情報で識別される道路を優先して、メッシュ選択部１５がメッシュを選択したり、最短経路情報取得部１６がメッシュ内最短経路を取得したりする。または、受付部１１が道路種類情報を受け付けた場合、当該道路種類情報で識別される道路以外の道路を優先して、メッシュ選択部１５がメッシュを選択したり、最短経路情報取得部１６がメッシュ内最短経路を取得したりしても良い。

また、本実施の形態において、第１ステップにおいて、メッシュの各辺間の連結の距離を算出し、距離が短い辺を有するメッシュ列を選択するアルゴリズムであった。しかし、実施の形態２で説明するアルゴリズムなど、他のアルゴリズムでも良い。メッシュの選択アルゴリズムは問わないことは、他の実施の形態でも同様である。

また、本実施の形態において、第２ステップにおけるアルゴリズムについても、実施の形態２で説明するアルゴリズムなど、他のアルゴリズムでも良い。かかることも、他の実施の形態でも同様である。

さらに、本実施の形態における処理は、ソフトウェアで実現しても良い。そして、このソフトウェアをソフトウェアダウンロード等により配布しても良い。また、このソフトウェアをＣＤ−ＲＯＭなどの記録媒体に記録して流布しても良い。なお、このことは、本明細書における他の実施の形態においても該当する。なお、本実施の形態における地図情報処理装置を実現するソフトウェアは、以下のようなプログラムである。つまり、このプログラムは、記憶媒体に、地点の位置を示す情報である位置情報を２以上有する地図情報と、地図情報に対応する領域を２以上の部分領域に分割した領域であるメッシュに関するメッシュ情報とが格納されており、コンピュータを、始点を特定する始点情報および目的地点を特定する目的地点情報を受け付ける受付部と、前記２以上のメッシュ情報を用いて、前記始点情報に対応する始点を含むメッシュから前記目的地点情報に対応する目的地点を含むメッシュであり、前記始点から前記目的地点までの最短経路を含む２以上のメッシュを選択するメッシュ選択部と、前記メッシュ選択部により選択された２以上のメッシュ内の地点の位置情報を、前記地図情報格納部から取得し、当該２以上のメッシュ内の地点の位置情報を用いて、前記始点から前記目的地点に進行する際の最短経路に関する情報である最短経路情報を取得する最短経路情報取得部と、前記最短経路情報取得部が取得した２以上のメッシュ内最短経路情報を出力する最短経路情報出力部として機能させるためのプログラム、である。

また、上記プログラムにおいて、コンピュータを、前記地図情報を２以上のメッシュに分割し、当該２以上の各メッシュに対応するメッシュ情報を２以上取得するメッシュ情報取得部としてさらに機能させ、前記メッシュ情報は、前記メッシュ情報取得部が取得したメッシュ情報であるプログラムであることは好適である。

また、上記プログラムにおいて、前記メッシュ情報取得部は、前記地図情報に対応する領域を２以上の部分領域であるメッシュに分割するメッシュ分割手段と、当該２以上のメッシュごとに、メッシュの各辺上の１以上の地点の位置を示す位置情報である１以上の辺上地点情報を、前記地図情報格納部から取得する辺上地点情報取得手段とを具備し、前記メッシュ選択部は、前記２以上のメッシュ間の２以上の辺上地点情報を用いて、前記２以上のメッシュの各辺の間の距離である２以上の辺間距離を算出する辺間距離算出手段と、前記２以上の辺間距離を用いて、前記始点情報に対応する始点を含むメッシュから前記目的地点情報に対応する目的地点を含むメッシュであり、前記始点から前記目的地点までの最短経路を含む２以上のメッシュを選択するメッシュ選択手段とを具備するものとして、コンピュータを機能させるためのプログラムであることは好適である。

また、上記プログラムにおいて、前記最短経路情報取得部は、前記メッシュ選択部により選択された２以上のメッシュごとに、当該メッシュ内の２以上の地点の位置情報を、前記地図情報格納部から取得するメッシュ内位置情報取得手段と、前記２以上の地点の位置情報を用いて、前記始点から前記目的地点までの最短経路に関する情報である最短経路情報を取得する最短経路情報取得手段とを具備するものとして、コンピュータを機能させるためのプログラムであることは好適である。

また、上記プログラムにおいて、前記最短経路情報取得手段は、前記２以上の位置情報からダイクストラ法を用いて、前記始点から前記目的地点までの最短経路の情報を取得するものとて、コンピュータを、機能させるためのプログラムであることは好適である。

また、上記プログラムにおいて、前記地図情報は、前記位置情報と、当該位置情報に対応する地点が存在する道路の種類を示す道路種類情報とを対に有する地点情報を２以上有し、前記メッシュ選択部は、一の道路種類情報と対になる位置情報が示す地点を含むメッシュ、または一の道路種類情報と対にならない位置情報が示す地点を含むメッシュを、他のメッシュと比較して優先して選択するものとして、コンピュータを機能させるためのプログラムであることは好適である。

さらに、上記プログラムにおいて、一の道路種類情報を受け付ける受付部として、コンピュータをさらに機能させ、前記メッシュ選択部は、前記受付部が受け付けた一の道路種類情報と対になる位置情報が示す地点を含むメッシュ、または前記受付部が受け付けた一の道路種類情報と対にならない位置情報が示す地点を含むメッシュを、他のメッシュと比較して優先して選択するものとして、コンピュータを機能させるためのプログラムであることは好適である。

（実施の形態２）
本実施の形態において、短時間で、精度高く、始点から目的地点までの最短経路を出力する地図情報処理装置について説明する。また、地図情報処理装置において、メッシュ列を選択する第１ステップ、メッシュ内の各点を用いて、最短経路を決定する第２ステップの、大きく２段階に処理が分かれる。また、地図情報処理装置において、一の道路種類（例えば、高速道路）を受け付け、当該道路を優先して、最短経路を決定する。

また、特に、本実施の形態において、第１ステップにおいて、メッシュの重心に近い点をメッシュの代表点として、距離が短いメッシュ列を選択するアルゴリズムを説明する。また、本実施の形態において、第２ステップにおいて、選択されたメッシュを直線的に並べた後に、メッシュ内の全点を用いて、経路探索し、距離が短い経路を出力するアルゴリズムを説明する。

図１５は、本実施の形態における地図情報処理装置２のブロック図である。地図情報処理装置２は、受付部１１、地図情報格納部１２、メッシュ情報格納部１３、メッシュ情報取得部２４、メッシュ選択部２５、最短経路情報取得部２６、最短経路情報出力部１７を具備する。

メッシュ情報取得部２４は、メッシュ分割手段１４１、重心地点情報取得手段２４２を具備する。メッシュ選択部２５は、重心距離算出手段２５１、メッシュ選択手段２５２を具備する。最短経路情報取得部２６は、メッシュ直線化手段２６１、最短経路情報取得手段２６２を具備する。

メッシュ情報取得部２４は、地図情報格納部１２の地図情報から、２以上のメッシュ情報を取得する。つまり、メッシュ情報取得部１４は、通常、地図情報格納部１２の地図情報を２以上のメッシュに分割し、２以上の各メッシュに対応するメッシュ情報を２以上取得する。ここで、メッシュ情報は、当該メッシュの重心に最も近い地点の位置を示す位置情報である重心地点情報を含む。メッシュ情報取得部２４は、通常、ＭＰＵやメモリ等から実現され得る。メッシュ情報取得部２４の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。

重心地点情報取得手段２４２は、２以上のメッシュごとに、メッシュの重心に最も近い地点の位置を示す位置情報である重心地点情報を、地図情報格納部１２から取得する。重心地点情報取得手段２４２は、２以上のメッシュごとに、目的地点に向かう方向の点であり、メッシュの重心に最も近い地点の位置を示す位置情報である重心地点情報を、地図情報格納部１２から取得しても良い。なお、始点を含むメッシュの場合は、通常、重心地点情報取得手段２４２は、始点情報を重心地点情報として取得する。また、目的地点を含むメッシュの場合は、通常、重心地点情報取得手段２４２は、目的地点情報を重心地点情報として取得する。重心地点情報取得手段２４２は、メッシュの内部の一点（辺上の点ではない一点）を取得すれば良い。重心地点情報取得手段２４２は、通常、ＭＰＵやメモリ等から実現され得る。重心地点情報取得手段２４２の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。

重心距離算出手段２５１は、２以上のメッシュ間の２以上の重心地点情報を用いて、２以上のメッシュの間の距離である２以上の重心距離を算出する。メッシュ間の距離は、すべての重心地点間の距離でも良いし、一部の重心地点間の距離でも良い。また、重心距離算出手段２５１は、直接または間接的に繋がっている重心地点間の距離のみを算出することは好適である。重心距離算出手段２５１は、始点から目的地点までのルートを含む複数のメッシュを決定できるように、重心地点間の距離を算出すれば良い。２つの重心地点の距離を算出するアルゴリズムは、例えば、以下である。つまり、２つの重心地点の一方を始点、他方を終点とする。そして、始点から終点までの距離を、地図情報格納部１２の地図情報に含まれる位置情報を用いて算出する。この算出アルゴリズムは、例えば、Ａ＊法やダイクストラ法である。重心距離算出手段２５１は、通常、ＭＰＵやメモリ等から実現され得る。重心距離算出手段２５１の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。

メッシュ選択手段２５２は、２以上の重心距離を用いて、始点情報に対応する始点を含むメッシュから目的地点情報に対応する目的地点を含む始点から目的地点までの最短経路を含む２以上のメッシュを選択する。メッシュ選択手段２５２は、通常、ＭＰＵやメモリ等から実現され得る。メッシュ選択手段２５２の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。

メッシュ直線化手段２６１は、メッシュ選択部２５により選択された２以上の各メッシュが仮想的に直線上に並ぶように、前のメッシュに対して上および下に存在するメッシュ、または前のメッシュに対して左および右に存在するメッシュを回転、または移動し、仮想的な直線のメッシュ群の情報を取得する。メッシュが矩形である場合、通常、回転の角度は９０度である。ここで、メッシュの回転や移動とは、メッシュ内の地点の位置情報を座標変換し、変換後の位置情報を取得する処理である。また、メッシュ群の情報とは、回転や移動させたメッシュ内の地点については座標変換後の位置情報であり、他のメッシュ内の地点については、そのまま位置情報である。なお、メッシュ直線化手段２６１が行う処理を直列化処理という。また、一のメッシュを回転または移動する処理をメッシュ移動処理という。メッシュ直線化手段２６１は、通常、ＭＰＵやメモリ等から実現され得る。メッシュ直線化手段２６１の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。

最短経路情報取得手段２６２は、仮想的な直線のメッシュ群の情報に含まれる２以上の地点の位置情報を用いて、始点から目的地点までの最短経路の情報を取得する。最短経路情報取得手段２６２は、２以上の地点の位置情報からダイクストラ法を用いて、始点から目的地点までの最短経路の情報を取得することは好適である。ここで、位置情報とは、座標変換された位置情報を含む。また、最短経路の情報とは、例えば、位置情報の集合である。また、最短経路の情報に含まれる位置情報は、座標変換された位置情報ではなく、元に戻された位置情報である。つまり、最短経路情報取得手段２６２は、座標変換されている位置情報を、元に戻す（例えば、逆に９０度回転させる等）処理を行う。また、最短経路情報取得手段２６２は、通常、仮想的な直線のメッシュ群の情報に含まれる２以上の地点の位置情報とコスト（距離情報）を用いて、始点から目的地点までの最短経路の情報を取得する。最短経路情報取得手段２６２は、通常、ＭＰＵやメモリ等から実現され得る。最短経路情報取得手段２６２の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。

次に、地図情報処理装置の動作について、図１６のフローチャートを用いて説明する。図１６のフローチャートにおいて、図２のフローチャートと同一の処理について、説明を省略する。

（ステップＳ１６０１）メッシュ選択部２５は、メッシュ選択処理を行う。メッシュ選択処理について、図１７のフローチャートを用いて説明する。

（ステップＳ１６０２）メッシュ直線化手段２６１は、ｉ番目のメッシュを移動（回転を含む）する必要があるか否かを判断する。移動する必要があればステップＳ１６０３に行き、移動する必要がなければステップＳ２０６に行く。ここで、メッシュ直線化手段２６１は、以前に移動を行ったメッシュがあれば、次のメッシュも移動する必要があると判断する。また、メッシュ直線化手段２６１は、以前に移動を行ったメッシュがない場合でも、ｉ番目のメッシュが前のメッシュに対して、目的地点を含むメッシュと方向が異なる（一直線で結べない）場合には、移動する必要があると判断する。

（ステップＳ１６０３）メッシュ直線化手段２６１は、ｉ番目のメッシュを移動（回転を含む）する。例えば、横に（例えば、左から右に）メッシュを並べている場合は、メッシュ直線化手段２６１は、ｉ番目のメッシュを、横に並ぶように回転させる。かかる場合、メッシュ直線化手段２６１は、メッシュ内のすべての地点情報が有する位置情報を回転させる。また、例えば、横にメッシュを並べている場合は、メッシュ直線化手段２６１は、ｉ番目のメッシュを、平行移動する。かかる場合、メッシュ直線化手段２６１は、メッシュ内のすべての地点情報が有する位置情報を平行移動させる。かかる処理は、公知技術（自明）であるので、詳細な説明を省略する。

（ステップＳ１６０４）メッシュ直線化手段２６１が座標変換した位置情報を用いて、最短経路情報取得手段２６２は、始点から目的地点までの最短経路を取得する。かかる最短経路取得アルゴリズムは、ダイクストラ法が好適であるが、Ａ＊法など問わない。

（ステップＳ１６０５）最短経路情報取得手段２６２は、ステップＳ１６０４で得た最短経路を構成する地点情報の位置情報を、元に戻す処理を行う。なお、ステップＳ１６０４で得た最短経路を構成する地点情報が有する地点ＩＤを用いて、元の位置情報を検索して、取得するなどしても良い。ここで、最短経路情報が得られたこととなる。

（ステップＳ１６０６）最短経路情報出力部１７は、ステップＳ１６０５で得られた最短経路情報を出力する。ステップＳ２０１に戻る。

なお、図１６のフローチャートにおいて、電源オフや処理終了の割り込みにより処理は終了する。

次に、ステップＳ１６０１のメッシュ選択処理について、図１７のフローチャートを用いて説明する。図１７のフローチャートにおいて、図３のフローチャートと同一の処理について、説明を省略する。

（ステップＳ１７０１）重心地点情報取得手段２４２は、ｉ番目のメッシュの重心地点の情報（座標情報でも、緯度・経度の情報でも良い）を取得する。なお、矩形等の図形の重心地点の位置の情報を取得する処理は公知技術であるので、詳細な説明を省略する。

（ステップＳ１７０２）重心地点情報取得手段２４２は、ｉ番目のメッシュ内の地点情報であり、道路種類情報に対応する地点情報の中から、ステップＳ１７０１で取得した重心地点の情報を用いて、重心地点から最も近い地点情報を取得する。なお、道路種類情報に対応する地点情報が存在しない場合、他の道路種類情報に対応する地点情報も含めて、重心地点情報取得手段２４２は、重心地点から最も近い地点情報を取得する。

（ステップＳ１７０３）重心地点情報取得手段２４２は、ステップＳ１７０１で取得した重心地点の情報を用いて、ｉ番目のメッシュ内の地点情報であり、重心地点から最も近い地点情報（重心地点情報）を取得する。なお、ここで、重心地点情報取得手段２４２は、通常、（ｉ−１）番目のメッシュの重心地点情報と道路種類情報が同一の重心地点情報を、優先して取得することは好適である。

（ステップＳ１７０４）重心距離算出手段２５１は、各メッシュについて、隣接するメッシュとの重心距離を算出する。

（ステップＳ１７０５）メッシュ選択手段２５２は、ステップＳ１７０４で算出した重心距離を用いて、始点から目的地点までの最短経路（仮最短経路）を決定し、取得する。

なお、図１７のフローチャートにおいて、重心地点情報を取得したが、予め重心地点情報は取得されていても良い。かかる場合、道路種類情報ごとに、重心地点情報は取得されていることは好適である。

また、図１７のフローチャートにおいて、ステップＳ１７０４の重心距離算出処理も、予め行っており、図示しない記録媒体に蓄積していても良い。

以下、本実施の形態における地図情報処理装置２の具体的な動作について説明する。まず、地図情報処理装置２の動作の概念について、説明する。

地図情報処理装置２の動作において、地図情報処理装置１の動作と異なるのは、以下の２点である。第一に、メッシュ選択処理において、メッシュを代表する地点情報として、重心に最も近い地点情報を選択した点である。図１８に示すように、各メッシュの重心地点情報（図１８のドット）を決定し、重心地点情報が地点間の距離（重心距離）を算出する。そして、２以上の重心距離を用いて、仮最短経路を取得する。そして、仮最短経路が通過するメッシュを選択する。なお、図１８において、重心地点情報が示す位置は、概ね、メッシュの中央に見えるが、上述したように、メッシュの中央であるとは限らない。

第二に、メッシュ列が一直線にならぶように、メッシュを移動（回転も含む）させたことである。概念的には、図１９に示すように、メッシュを回転または平行移動させ、一直線に並べる。

以下、地図情報処理装置２の具体的な動作の詳細について説明する。今、地図情報格納部１２は、図７に示す地点情報管理表を保持している。また、メッシュ情報格納部１３は、図８に示すメッシュ区分情報管理表を保持している。

かかる状況において、ユーザは、目的地点を地図情報処理装置２に入力した、とする。そして、ユーザは、地図情報処理装置２に対して、最短経路出力の指示を入力した、とする。

次に、図示しないナビゲーション装置が、現在位置の情報である始点情報（緯度，経度）を取得し、地図情報処理装置２に渡した、とする。

次に、地図情報処理装置２の受付部１１は、始点情報および目的地点情報を有する最短経路出力指示を受け付ける。なお、受付部１１は、ユーザが入力した目的地点を（緯度，経度）に変換する、とする。

次に、メッシュ選択部２５は、始点から目的地点までの最短経路を含む２以上のメッシュを、以下のように選択する。

つまり、まず、重心地点情報取得手段２４２は、各メッシュの重心地点の情報を取得する。次に、重心地点情報取得手段２４２は、重心地点の情報を用いて、各メッシュ内の地点情報であり、重心地点から最も近い地点情報（重心地点情報）を取得する。この際、重心地点情報取得手段２４２は、地図情報が有する位置情報を参照する。そして、重心地点情報取得手段２４２は、図２０に示すような重心地点情報管理表を得る。

次に、重心距離算出手段２５１は、各メッシュについて、隣接するメッシュとの重心距離を算出する。なお、二地点の位置情報から距離を算出する処理は公知技術である。ここで、隣接するメッシュとは、上下左右のメッシュだけではなく、ここでは、斜め右前、斜め左前、斜め右下、斜め左下のメッシュも含む、とする。なお、図２１は、重心距離算出手段２５１が算出する重心距離の概念を示す図である。なお、重心距離算出手段２５１は、地図情報が地点間距離を含む場合、重心距離を地図情報管理表（地図情報格納部１２）から読み出しても良い。

次に、メッシュ選択手段２５２は、算出した重心距離を用いて、始点から目的地点までの最短経路（仮最短経路）を決定し、取得する。なお、重心地点情報をノードとし、ノード間の距離を取得しているので、最短経路を取得する処理は公知技術である。この公知技術とは、例えば、ダイクストラ法、Ａ＊法などである。

そして、メッシュ選択手段２５２は、仮最短経路が通過するメッシュの識別情報の列を、記録媒体に蓄積する。かかるメッシュの識別情報の列は、図１３である。

次に、図１３のメッシュ識別情報列から、メッシュ直線化手段２６１は、移動の必要のあるメッシュを移動し、一直線に並ぶメッシュ列を得る。かかる概念図は、図１９である。なお、メッシュ直線化手段２６１は、移動の必要のあるメッシュ内の地点情報が有する位置情報を変換し、一時格納する。

次に、メッシュ直線化手段２６１が座標変換した位置情報を用いて、最短経路情報取得手段２６２は、始点から目的地点までの最短経路を取得する。かかる最短経路取得アルゴリズムは、ダイクストラ法、Ａ＊法などである。そして、最短経路情報取得手段２６２は、最短経路を構成する地点ＩＤの列を得る。

最短経路情報出力部１７は、得られた地点ＩＤの列から、最短経路情報を出力する。地点ＩＤの列から、最短経路情報を出力する処理は以下である。地点ＩＤをキーとして、図７に示す地点情報管理表を検索し、経路を構成する地点の位置情報を得る。そして、当該経路を、視覚的に、他の道路と比較して、目立つような態様で出力する。かかる出力例は、図１４である。

以上、本実施の形態によれば、直線に並べ替えたデータに対して探索を実施するので、開始位置と目的位置の位置関係に関係なく、同じ探索結果が選ばれる。また、本実施の形態によれば、短時間で、精度高く、始点から目的地点までの最短経路を出力することができる。

なお、本実施の形態における直列化処理を、実施の形態１の地図情報処理装置に適用しても良いことは言うまでもない。

さらに、本実施の形態における地図情報処理装置を実現するソフトウェアは、以下のようなプログラムである。つまり、このプログラムは、記憶媒体に、地点の位置を示す情報である位置情報を２以上有する地図情報と、地図情報に対応する領域を２以上の部分領域に分割した領域であるメッシュに関するメッシュ情報とが格納されており、コンピュータを、始点を特定する始点情報および目的地点を特定する目的地点情報を受け付ける受付部と、前記２以上のメッシュ情報を用いて、前記始点情報に対応する始点を含むメッシュから前記目的地点情報に対応する目的地点を含むメッシュであり、前記始点から前記目的地点までの最短経路を含む２以上のメッシュを選択するメッシュ選択部と、前記メッシュ選択部により選択された２以上の各メッシュに対して、始点から始点を含むメッシュと次のメッシュとの境界辺に進行する際の最短経路に関する情報であるメッシュ内最短経路情報、または前のメッシュとの境界辺から次のメッシュとの境界辺に進行する際の最短経路に関する情報であるメッシュ内最短経路情報、または目的地点を含むメッシュと前のメッシュとの境界辺から目的地点に進行する際の最短経路に関する情報であるメッシュ内最短経路情報を取得する最短経路情報取得部と、前記最短経路情報取得部が取得した２以上のメッシュ内最短経路情報を出力する最短経路情報出力部として機能させるためのプログラム、である。

また、上記プログラムにおいて、前記メッシュ情報取得部は、前記地図情報に対応する領域を２以上の部分領域であるメッシュに分割するメッシュ分割手段と、当該２以上のメッシュごとに、メッシュの重心に最も近い地点の位置を示す位置情報である重心地点情報を、前記地図情報格納部から取得する重心地点情報取得手段とを具備し、前記メッシュ選択部は、前記２以上のメッシュ間の２以上の重心地点情報を用いて、前記２以上のメッシュの間の距離である２以上の重心距離を算出する重心距離算出手段と、前記２以上の重心距離を用いて、前記始点情報に対応する始点を含むメッシュから前記目的地点情報に対応する目的地点を含むメッシュであり、前記始点から前記目的地点までの最短経路を含む２以上のメッシュを選択するメッシュ選択手段とを具備するものとして、コンピュータを機能させるためのプログラムであることは好適である。

また、上記プログラムにおいて、前記最短経路情報取得部は、前記メッシュ選択部により選択された２以上の各メッシュが仮想的に直線上に並ぶように、前のメッシュに対して上および下に存在するメッシュ、または前のメッシュに対して左および右に存在するメッシュを回転し、仮想的な直線のメッシュ群の情報を取得するメッシュ直線化手段と、前記仮想的な直線のメッシュ群の情報に含まれる２以上の位置情報を用いて、前記始点から前記目的地点までの最短経路の情報を取得する最短経路情報取得手段とを具備し、前記最短経路情報出力部は、前記最短経路情報取得手段が取得した最短経路の情報を出力するものとして、コンピュータを機能させるためのプログラムであることは好適である。

また、上記プログラムにおいて、前記最短経路情報取得手段は、前記２以上の位置情報からダイクストラ法を用いて、前記始点から前記目的地点までの最短経路の情報を取得するものとして、コンピュータを機能させるためのプログラムであることは好適である。

また、図２２は、本明細書で述べたプログラムを実行して、上述した実施の形態の地図情報処理装置等を実現するコンピュータの外観を示す。上述の実施の形態は、コンピュータハードウェア及びその上で実行されるコンピュータプログラムで実現され得る。図２２は、このコンピュータシステム３４０の概観図であり、図２３は、コンピュータシステム３４０のブロック図である。

図２２において、コンピュータシステム３４０は、ＦＤドライブ、ＣＤ−ＲＯＭドライブを含むコンピュータ３４１と、キーボード３４２と、マウス３４３と、モニタ３４４とを含む。

図２３において、コンピュータ３４１は、ＦＤドライブ３４１１、ＣＤ−ＲＯＭドライブ３４１２に加えて、ＭＰＵ３４１３と、ＣＤ−ＲＯＭドライブ３４１２及びＦＤドライブ３４１１に接続されたバス３４１４と、ブートアッププログラム等のプログラムを記憶するためのＲＯＭ３４１５と、ＭＰＵ３４１３に接続され、アプリケーションプログラムの命令を一時的に記憶するとともに一時記憶空間を提供するためのＲＡＭ３４１６と、アプリケーションプログラム、システムプログラム、及びデータを記憶するためのハードディスク３４１７とを含む。ここでは、図示しないが、コンピュータ３４１は、さらに、ＬＡＮへの接続を提供するネットワークカードを含んでも良い。

コンピュータシステム３４０に、上述した実施の形態の地図情報処理装置等の機能を実行させるプログラムは、ＣＤ−ＲＯＭ３５０１、またはＦＤ３５０２に記憶されて、ＣＤ−ＲＯＭドライブ３４１２またはＦＤドライブ３４１１に挿入され、さらにハードディスク３４１７に転送されても良い。これに代えて、プログラムは、図示しないネットワークを介してコンピュータ３４１に送信され、ハードディスク３４１７に記憶されても良い。プログラムは実行の際にＲＡＭ３４１６にロードされる。プログラムは、ＣＤ−ＲＯＭ３５０１、ＦＤ３５０２またはネットワークから直接、ロードされても良い。

プログラムは、コンピュータ３４１に、上述した実施の形態の地図情報処理装置等の機能を実行させるオペレーティングシステム（ＯＳ）、またはサードパーティープログラム等は、必ずしも含まなくても良い。プログラムは、制御された態様で適切な機能（モジュール）を呼び出し、所望の結果が得られるようにする命令の部分のみを含んでいれば良い。コンピュータシステム３４０がどのように動作するかは周知であり、詳細な説明は省略する。

また、上記プログラムを実行するコンピュータは、単数であってもよく、複数であってもよい。すなわち、集中処理を行ってもよく、あるいは分散処理を行ってもよい。

また、上記各実施の形態において、一の装置に存在する２以上の通信手段（端末情報送信部、端末情報受信部など）は、物理的に一の媒体で実現されても良いことは言うまでもない。

また、上記各実施の形態において、各処理（各機能）は、単一の装置（システム）によって集中処理されることによって実現されてもよく、あるいは、複数の装置によって分散処理されることによって実現されてもよい。

本発明は、以上の実施の形態に限定されることなく、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。

以上のように、本発明にかかる地図情報処理装置は、短時間で、精度高く、始点から目的地点までの最短経路を出力することができるという効果を有し、ナビゲーション装置等として有用である。

実施の形態１における地図情報処理装置のブロック図同地図情報処理装置の動作について説明するフローチャート同メッシュ選択処理の動作について説明するフローチャート同処理例の動作について説明するフローチャート同従来のアルゴリズムの課題を説明する図同地図情報処理装置が選択したメッシュを示す図同地点情報管理表を示す図同メッシュ区分情報管理表を示す図同メッシュ情報管理表を示す図同辺間距離算出手段の処理を説明する図同仮最短経路を示す図同メッシュ選択手段が取得したメッシュを示す図同メッシュ識別子の集合を示す図同最短経路の出力例を示す図実施の形態２における地図情報処理装置のブロック図同地図情報処理装置の動作について説明するフローチャート同メッシュ選択処理の動作について説明するフローチャート同選択されたメッシュを示す図同メッシュを回転または平行移動する概念を説明する図同重心地点情報管理表を示す図同重心距離算出手段が算出する重心距離の概念を示す図同コンピュータシステムの概観図同コンピュータシステムのブロック図

符号の説明

１、２地図情報処理装置
１１受付部
１２地図情報格納部
１３メッシュ情報格納部
１４、２４メッシュ情報取得部
１５、２５メッシュ選択部
１６、２６最短経路情報取得部
１７最短経路情報出力部
１４１メッシュ分割手段
１４２辺上地点情報取得手段
１５１辺間距離算出手段
１５２、２５２メッシュ選択手段
１６１メッシュ内位置情報取得手段
１６２、２６２最短経路情報取得手段
２４２重心地点情報取得手段
２５１重心距離算出手段
２６１メッシュ直線化手段

Claims

地点の位置を示す情報である位置情報を２以上有する地図情報を格納し得る地図情報格納部と、
始点を特定する始点情報および目的地点を特定する目的地点情報を受け付ける受付部と、
前記地図情報に対応する領域を２以上の部分領域に分割した領域であるメッシュに関する情報であり、当該２以上の各メッシュを代表する１以上の地点に関する情報であるメッシュ情報を２以上格納し得るメッシュ情報格納部と、
前記２以上のメッシュ情報を用いて、前記始点情報に対応する始点を含むメッシュから前記目的地点情報に対応する目的地点を含むメッシュであり、前記始点から前記目的地点までの最短経路を含む２以上のメッシュを選択するメッシュ選択部と、
前記メッシュ選択部により選択された２以上のメッシュ内の地点の位置情報を、前記地図情報格納部から取得し、当該２以上のメッシュ内の地点の位置情報を用いて、前記始点から前記目的地点に進行する際の最短経路に関する情報である最短経路情報を取得する最短経路情報取得部と、
前記最短経路情報取得部が取得した最短経路情報を出力する最短経路情報出力部を具備し、
前記メッシュ情報格納部に格納されている２以上のメッシュ情報に対応する２メッシュごとに、メッシュの重心に最も近い地点の位置を示す位置情報である重心地点情報を、前記地図情報格納部から取得する重心地点情報取得手段をさらに具備し、
前記メッシュ選択部は、
前記２以上のメッシュ間の２以上の重心地点情報を用いて、前記２以上のメッシュの間の距離である２以上の重心距離を算出する重心距離算出手段と、
前記２以上の重心距離を用いて、前記始点情報に対応する始点を含むメッシュから前記目的地点情報に対応する目的地点を含むメッシュであり、前記始点から前記目的地点までの最短経路を含む２以上のメッシュを選択するメッシュ選択手段とを具備する地図情報処理装置。
前記最短経路情報取得部は、
前記メッシュ選択部により選択された２以上のメッシュごとに、当該メッシュ内の２以上の地点の位置情報を、前記地図情報格納部から取得するメッシュ内位置情報取得手段と、
前記２以上の地点の位置情報を用いて、前記始点から前記目的地点までの最短経路に関する情報である最短経路情報を取得する最短経路情報取得手段とを具備する請求項１記載の地図情報処理装置。
前記最短経路情報取得部は、
前記メッシュ選択部により選択された２以上の各メッシュが仮想的に直線上に並ぶように、前のメッシュに対して上および下に存在するメッシュ、または前のメッシュに対して左および右に存在するメッシュを回転し、仮想的な直線のメッシュ群の情報を取得するメッシュ直線化手段と、
前記仮想的な直線のメッシュ群の情報に含まれる２以上の地点の位置情報を用いて、前記始点から前記目的地点までの最短経路の情報を取得する最短経路情報取得手段とを具備し、
前記最短経路情報出力部は、
前記最短経路情報取得手段が取得した最短経路の情報を出力する請求項１記載の地図情報処理装置。
地点の位置を示す情報である位置情報を２以上有する地図情報を格納し得る地図情報格納部と、
始点を特定する始点情報および目的地点を特定する目的地点情報を受け付ける受付部と、
前記地図情報に対応する領域を２以上の部分領域に分割した領域であるメッシュに関する情報であり、当該２以上の各メッシュを代表する１以上の地点に関する情報であるメッシュ情報を２以上格納し得るメッシュ情報格納部と、
前記２以上のメッシュ情報を用いて、前記始点情報に対応する始点を含むメッシュから前記目的地点情報に対応する目的地点を含むメッシュであり、前記始点から前記目的地点までの最短経路を含む２以上のメッシュを選択するメッシュ選択部と、
前記メッシュ選択部により選択された２以上のメッシュ内の地点の位置情報を、前記地図情報格納部から取得し、当該２以上のメッシュ内の地点の位置情報を用いて、前記始点から前記目的地点に進行する際の最短経路に関する情報である最短経路情報を取得する最短経路情報取得部と、
前記最短経路情報取得部が取得した最短経路情報を出力する最短経路情報出力部を具備し、
前記最短経路情報取得部は、
前記メッシュ選択部により選択された２以上の各メッシュが仮想的に直線上に並ぶように、前のメッシュに対して上および下に存在するメッシュ、または前のメッシュに対して左および右に存在するメッシュを回転し、仮想的な直線のメッシュ群の情報を取得するメッシュ直線化手段と、
前記仮想的な直線のメッシュ群の情報に含まれる２以上の地点の位置情報を用いて、前記始点から前記目的地点までの最短経路の情報を取得する最短経路情報取得手段とを具備し、
前記最短経路情報出力部は、
前記最短経路情報取得手段が取得した最短経路の情報を出力する地図情報処理装置。
前記最短経路情報取得手段は、
前記２以上の地点の位置情報を用いて、Ａ＊法により、前記始点から前記目的地点までの最短経路の情報を取得する請求項４記載の地図情報処理装置。
前記地図情報は、
前記位置情報と、当該位置情報に対応する地点が存在する道路の種類を示す道路種類情報とを対に有する地点情報を２以上有し、
前記メッシュ選択部は、
一の道路種類情報と対になる位置情報が示す地点を含むメッシュ、または一の道路種類情報と対にならない位置情報が示す地点を含むメッシュを、他のメッシュと比較して優先して選択する請求項１から請求項５いずれか記載の地図情報処理装置。
一の道路種類情報を受け付ける受付部をさらに具備し、
前記メッシュ選択部は、
前記受付部が受け付けた一の道路種類情報と対になる位置情報が示す地点を含むメッシュ、または前記受付部が受け付けた一の道路種類情報と対にならない位置情報が示す地点を含むメッシュを、他のメッシュと比較して優先して選択する請求項６記載の地図情報処理装置。
地図情報格納部、受付部、メッシュ情報格納部、メッシュ情報格納部、重心地点情報取得手段、メッシュ選択部、最短経路情報取得部、および最短経路情報出力部により実現される地図情報処理方法であって、
地図情報格納部に、地点の位置を示す情報である位置情報を２以上有する地図情報を格納しており、
メッシュ情報格納部に、前記地図情報に対応する領域を２以上の部分領域に分割した領域であるメッシュに関する情報であり、当該２以上の各メッシュを代表する１以上の地点に関する情報であるメッシュ情報を２以上格納しており、
前記受付部により、始点を特定する始点情報および目的地点を特定する目的地点情報を受け付ける受付ステップと、メッシュ選択部により、始点から目的地点までの最短経路を含む２以上のメッシュを選択するメッシュ選択ステップと、
前記最短経路情報取得部により、前記メッシュ選択部により選択された２以上のメッシュ内の地点の位置情報を、前記地図情報格納部から取得し、当該２以上のメッシュ内の地点の位置情報を用いて、前記始点から前記目的地点に進行する際の最短経路に関する情報である最短経路情報を取得する最短経路情報取得ステップと、
前記最短経路情報出力部により、最短経路情報取得部が取得した２以上のメッシュ内最短経路情報を出力する最短経路情報出力ステップを具備し、
し、
前記重心地点情報取得手段が、前記メッシュ情報格納部に格納されている２以上のメッシュ情報に対応する２メッシュごとに、メッシュの重心に最も近い地点の位置を示す位置情報である重心地点情報を、前記地図情報格納部から取得する重心地点情報取得ステップをさらに具備し、
前記メッシュ選択ステップは、
前記２以上のメッシュ間の２以上の重心地点情報を用いて、前記２以上のメッシュの間の距離である２以上の重心距離を算出する重心距離算出ステップと、
前記２以上の重心距離を用いて、前記始点情報に対応する始点を含むメッシュから前記目的地点情報に対応する目的地点を含むメッシュであり、前記始点から前記目的地点までの最短経路を含む２以上のメッシュを選択するメッシュ選択ステップとを具備する地図情報処理方法。
前記最短経路情報取得ステップは、
前記メッシュ選択ステップにより選択された２以上の各メッシュが仮想的に直線上に並ぶように、前のメッシュに対して上および下に存在するメッシュ、または前のメッシュに対して左および右に存在するメッシュを回転し、仮想的な直線のメッシュ群の情報を取得するメッシュ直線化ステップと、
前記仮想的な直線のメッシュ群の情報に含まれる２以上の地点の位置情報を用いて、前記始点から前記目的地点までの最短経路の情報を取得する最短経路情報取得ステップとを具備し、
前記最短経路情報出力ステップは、
前記最短経路情報取得ステップで取得された最短経路の情報を出力する請求項８記載の地図情報処理方法。
地図情報格納部、受付部、メッシュ情報格納部、メッシュ情報格納部、メッシュ選択部、最短経路情報取得部、および最短経路情報出力部により実現される地図情報処理方法であって、
地図情報格納部に、地点の位置を示す情報である位置情報を２以上有する地図情報を格納しており、
メッシュ情報格納部に、前記地図情報に対応する領域を２以上の部分領域に分割した領域であるメッシュに関する情報であり、当該２以上の各メッシュを代表する１以上の地点に関する情報であるメッシュ情報を２以上格納しており、
前記受付部により、始点を特定する始点情報および目的地点を特定する目的地点情報を受け付ける受付ステップと、メッシュ選択部により、始点から目的地点までの最短経路を含む２以上のメッシュを選択するメッシュ選択ステップと、
前記最短経路情報取得部により、前記メッシュ選択部により選択された２以上のメッシュ内の地点の位置情報を、前記地図情報格納部から取得し、当該２以上のメッシュ内の地点の位置情報を用いて、前記始点から前記目的地点に進行する際の最短経路に関する情報である最短経路情報を取得する最短経路情報取得ステップと、
前記最短経路情報出力部により、最短経路情報取得部が取得した２以上のメッシュ内最短経路情報を出力する最短経路情報出力ステップを具備し、
前記最短経路情報取得ステップは、
前記メッシュ選択ステップにより選択された２以上の各メッシュが仮想的に直線上に並ぶように、前のメッシュに対して上および下に存在するメッシュ、または前のメッシュに対して左および右に存在するメッシュを回転し、仮想的な直線のメッシュ群の情報を取得するメッシュ直線化ステップと、
前記仮想的な直線のメッシュ群の情報に含まれる２以上の地点の位置情報を用いて、前記始点から前記目的地点までの最短経路の情報を取得する最短経路情報取得ステップとを具備し、
前記最短経路情報出力ステップは、
前記最短経路情報取得ステップで取得された最短経路の情報を出力する地図情報処理方法。
記憶媒体に、地点の位置を示す情報である位置情報を２以上有する地図情報と、地図情報に対応する領域を２以上の部分領域に分割した領域であるメッシュに関するメッシュ情報とが格納されており、
コンピュータを、
始点を特定する始点情報および目的地点を特定する目的地点情報を受け付ける受付部と、
前記２以上のメッシュ情報を用いて、前記始点情報に対応する始点を含むメッシュから前記目的地点情報に対応する目的地点を含むメッシュであり、前記始点から前記目的地点までの最短経路を含む２以上のメッシュを選択するメッシュ選択部と、
前記メッシュ選択部により選択された２以上のメッシュ内の地点の位置情報を、前記地図情報格納部から取得し、当該２以上のメッシュ内の地点の位置情報を用いて、前記始点から前記目的地点に進行する際の最短経路に関する情報である最短経路情報を取得する最短経路情報取得部と、
前記最短経路情報取得部が取得した２以上のメッシュ内最短経路情報を出力する最短経路情報出力部として機能させるためのプログラムであって、
コンピュータを、
前記記憶媒体に格納されている２以上のメッシュ情報に対応する２メッシュごとに、メッシュの重心に最も近い地点の位置を示す位置情報である重心地点情報を、前記記憶媒体から取得する重心地点情報取得手段としてさらに機能させ、
前記メッシュ選択部は、
前記２以上のメッシュ間の２以上の重心地点情報を用いて、前記２以上のメッシュの間の距離である２以上の重心距離を算出する重心距離算出手段と、
前記２以上の重心距離を用いて、前記始点情報に対応する始点を含むメッシュから前記目的地点情報に対応する目的地点を含むメッシュであり、前記始点から前記目的地点までの最短経路を含む２以上のメッシュを選択するメッシュ選択手段とを具備するものとして、コンピュータを機能させるためのプログラム。
記憶媒体に、地点の位置を示す情報である位置情報を２以上有する地図情報と、前記地図情報に対応する領域を２以上の部分領域に分割した領域であるメッシュに関する情報であり、当該２以上の各メッシュを代表する１以上の地点に関する情報である２以上のメッシュ情報とが格納されており、
コンピュータを、
始点を特定する始点情報および目的地点を特定する目的地点情報を受け付ける受付部と、
前記２以上のメッシュ情報を用いて、前記始点情報に対応する始点を含むメッシュから前記目的地点情報に対応する目的地点を含むメッシュであり、前記始点から前記目的地点までの最短経路を含む２以上のメッシュを選択するメッシュ選択部と、
前記メッシュ選択部により選択された２以上のメッシュ内の地点の位置情報を、前記記憶媒体から取得し、当該２以上のメッシュ内の地点の位置情報を用いて、前記始点から前記目的地点に進行する際の最短経路に関する情報である最短経路情報を取得する最短経路情報取得部と、
前記最短経路情報取得部が取得した最短経路情報を出力する最短経路情報出力部として機能させ、
前記最短経路情報取得部は、
前記メッシュ選択部により選択された２以上の各メッシュが仮想的に直線上に並ぶように、前のメッシュに対して上および下に存在するメッシュ、または前のメッシュに対して左および右に存在するメッシュを回転し、仮想的な直線のメッシュ群の情報を取得するメッシュ直線化手段と、
前記仮想的な直線のメッシュ群の情報に含まれる２以上の地点の位置情報を用いて、前記始点から前記目的地点までの最短経路の情報を取得する最短経路情報取得手段とを具備するものとしてコンピュータ機能させ、
前記最短経路情報出力部は、
前記最短経路情報取得手段が取得した最短経路の情報を出力するものとして、コンピュータを機能させるためのプログラム。
記憶媒体に、地点の位置を示す情報である位置情報を２以上有する地図情報と、
前記地図情報に対応する領域を２以上の部分領域に分割した領域であるメッシュに関する情報であり、当該２以上の各メッシュを代表する１以上の地点に関する情報である２以上のメッシュ情報とを格納しており、
コンピュータを、
始点を特定する始点情報および目的地点を特定する目的地点情報を受け付ける受付部と、
前記２以上のメッシュ情報を用いて、前記始点情報に対応する始点を含むメッシュから前記目的地点情報に対応する目的地点を含むメッシュであり、前記始点から前記目的地点までの最短経路を含む２以上のメッシュを選択するメッシュ選択部と、
前記メッシュ選択部により選択された２以上のメッシュ内の地点の位置情報を、前記記憶媒体から取得し、当該２以上のメッシュ内の地点の位置情報を用いて、前記始点から前記目的地点に進行する際の最短経路に関する情報である最短経路情報を取得する最短経路情報取得部と、
前記最短経路情報取得部が取得した最短経路情報を出力する最短経路情報出力部として機能させるためのプログラムであって、
前記最短経路情報取得部は、
前記メッシュ選択部により選択された２以上の各メッシュが仮想的に直線上に並ぶように、前のメッシュに対して上および下に存在するメッシュ、または前のメッシュに対して左および右に存在するメッシュを回転し、仮想的な直線のメッシュ群の情報を取得するメッシュ直線化手段と、
前記仮想的な直線のメッシュ群の情報に含まれる２以上の地点の位置情報を用いて、前記始点から前記目的地点までの最短経路の情報を取得する最短経路情報取得手段とを具備し、
前記最短経路情報出力部は、
前記最短経路情報取得手段が取得した最短経路の情報を出力するものとして、コンピュータを機能させるためのプログラム。