路網図管理装置、路網図管理システム、路網図管理プログラムおよび路網図管理方法
【課題】装置は、ある場所の状況に応じて当該場所を経由する経路を検索されやすくしつつ、効率よい経路探索をすることが出来ない。
【解決手段】路網図管理装置は、階層化され、各層において一段上位層の路の閉路で囲まれた領域ごとに分割されている路網図が、閉路を構成する上位層の各路の両側に当該路を境界とする分割網が関連付けられて格納された路記憶部と、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている注目位置側の分割網Ｇを、当該Ｇに注目位置を含む路が存在まで一段下位層から取得して、各層に於いて、当該Ｇの境界を構成する路と注目位置間の分割経路をＧｄ内で探索して、Ｇｄを分割経路で複数の分割網ｇに分割して、各ｇを路記憶部に記憶し、分割経路を１段上位の層に追加する分割手段を備える。
【解決手段】路網図管理装置は、階層化され、各層において一段上位層の路の閉路で囲まれた領域ごとに分割されている路網図が、閉路を構成する上位層の各路の両側に当該路を境界とする分割網が関連付けられて格納された路記憶部と、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている注目位置側の分割網Ｇを、当該Ｇに注目位置を含む路が存在まで一段下位層から取得して、各層に於いて、当該Ｇの境界を構成する路と注目位置間の分割経路をＧｄ内で探索して、Ｇｄを分割経路で複数の分割網ｇに分割して、各ｇを路記憶部に記憶し、分割経路を１段上位の層に追加する分割手段を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、路網図管理装置、路網図管理システム、路網図管理プログラムおよび路網図管理方法に関する。
【背景技術】
【０００２】
特許文献１は、道路を複数の階層に分類し、各階層データが階層内の交差点及び上位階層の道路との交差点に関する情報、交差点間の道路に関する情報を備える地図データを用いたナビゲーションシステムを開示する。このシステムは、出発地と目的地からそれぞれ上位の所定の階層の道路の交差点までの経路探査を行い、その後所定階層内での経路探査を行う。この地図データに於いて、下位の階層は、例えば上位の階層の道路により囲まれた範囲毎に分けて記憶される。
【０００３】
特許文献２は、適切な経路を探索する為に、階層化された地図情報を更新する地図情報生成装置を開示する。この装置は、下位の階層に属す道路の移動コストが上位の階層に属す道路を利用するよりも低コストであるとき、この下位の階層に属す道路を上位の階層の地図情報へ追加する。この装置は、例えば県道であっても空いていて快適に走れるならば、国道と同じ階層の地図情報にこの県道を追加する。
【０００４】
特許文献３は、全国の地図データを読み込み、最上段階の選択基準の道路（例えば国道）を境界としてエリア分割する地図データ作成装置を開示する。この装置は、分割エリアをナビ用データに変換した状態でのデータサイズが上限値を超えている場合は、次段階の選択基準道路（例えば県道・市町村道）を境界として再分割する。
【０００５】
非特許文献１は、空間インデックスを管理する一般的なデータ構造の例であるR-Treesを開示する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平５−２７６７９号公報
【特許文献２】特開２００７−２４５１５号公報
【特許文献３】特開２００４−２２６７３０号公報
【非特許文献】
【０００７】
【非特許文献１】2006年、シュプリンガー、アールツリー：セオリー・アンド・アプリケーション (R-Trees: Theory and Applications, Springer, 2006)
【発明の概要】
【発明が解決しようとする課題】
【０００８】
カーナビゲーション装置などの経路探索において、ある場所の状況に応じて、当該場所を経由する経路を検索されやすくすることが好ましい場合がある。例えば、或る場所でユーザの関心が高いイベントが発生（祭りや博覧会の開催等）している期間中、移動途中のユーザが当該イベント会場に寄り道できるような経路を優先して探索出来れば好ましい。
【０００９】
階層構造を有する地図情報を利用して経路探索を行う装置がこのような探索を行う為には、当該イベント会場を経由する経路が上位層の地図情報に登録されていると良い。当該経路が主要でない経路であって、通常は下位層の地図情報にしか登録されていない場合は、イベントの開催に合わせて、カーナビゲーション装置などが動的に当該経路を上位層の地図情報に追加すると良い。
【００１０】
ところで、特許文献１に開示されるナビゲーションシステムのように、階層化された地図情報の下位層を上位層の道路により囲まれた範囲に分割して記憶している経路探索装置が存在する。このような経路探索装置は、経路探索に於いてメモリ上に読み込む下位層の地図情報のデータ量を減らすことが出来る為、効率的な経路探索が可能である。
【００１１】
しかしながら、このような装置は、特許文献２に開示されている装置のように、簡単に新たな経路を上位層に追加できない。その理由は、下位層が新たな経路に基づいて分割されていないからである。一方、特許文献２に開示された装置は、効率的な経路探索が出来ない。その理由は、下位層の分割が考慮されていないからである。
【００１２】
即ち、特許文献１と特許文献２に開示された装置は、何れも、経路探索において、ある場所の状況に応じて、当該場所を経由する経路を検索されやすくすることと、効率よい経路探索を両立することが出来ないという課題がある。特許文献３および非特許文献１に開示された技術もこの課題を解決しない。
【００１３】
本願発明の目的は、上記課題を解決する路網図管理装置、路網図管理システム、路網図管理プログラムおよび路網図管理方法を提供することにある。
【課題を解決するための手段】
【００１４】
本発明の一実施形態の路網図管理装置は、路網の詳細度に基づいて複数の層（２つの層間において詳細度が低い層を上位層、高い層を下位層と呼ぶ）に階層化され、各層において一段上位層の路の閉路で囲まれている領域ごとに分割網に分割されている路網図が、当該閉路を構成する上位層の各路の両側に当該路を境界とする２つの分割網を関連付けて格納された路記憶部と、最上位層から下位に向けて順次前記路網図の各層をアクセスして、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている前記注目位置側の前記分割網（Ｇｄ）を、当該Ｇｄに前記注目位置を含む前記路が存在するようになるまで一段下位層から取得して、最後に取得した前記Ｇｄが属する層から上位に向けて更新層の一段下位層まで順次各層をアクセスして、各層に於いて、当該Ｇｄの前記境界を構成する前記路の少なくとも２つと前記注目位置間の経路（分割経路）を前記Ｇｄ内で探索して、前記Ｇｄを前記分割経路で複数の分割網（ｇｄ）に分割して、前記Ｇｄを前記路記憶部から削除して、各前記ｇｄを前記路記憶部に記憶し、前記分割経路を１段上位の層に追加する分割手段を備える。
【００１５】
本発明の一実施形態の路網図管理プログラムは、路網の詳細度に基づいて複数の層（２つの層間において詳細度が低い層を上位層、高い層を下位層と呼ぶ）に階層化され、各層において一段上位層の路の閉路で囲まれている領域ごとに分割網に分割されている路網図が、当該閉路を構成する上位層の各路の両側に当該路を境界とする２つの分割網を関連付けて格納された路記憶部を備えたコンピュータに、最上位層から下位に向けて順次前記路網図の各層をアクセスして、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている前記注目位置側の前記分割網（Ｇｄ）を、当該Ｇｄに前記注目位置を含む前記路が存在するようになるまで一段下位層から取得して、最後に取得した前記Ｇｄが属する層から上位に向けて更新層の一段下位層まで順次各層をアクセスして、各層に於いて、当該Ｇｄの前記境界を構成する前記路の少なくとも２つと前記注目位置間の経路（分割経路）を前記Ｇｄ内で探索して、前記Ｇｄを前記分割経路で複数の分割網（ｇｄ）に分割して、前記Ｇｄを前記路記憶部から削除して、各前記ｇｄを前記路記憶部に記憶し、前記分割経路を１段上位の層に追加する分割処理を実行させる。
【００１６】
本発明の一実施形態の路網図管理方法は、路網の詳細度に基づいて複数の層（２つの層間において詳細度が低い層を上位層、高い層を下位層と呼ぶ）に階層化され、各層において一段上位層の路の閉路で囲まれている領域ごとに分割網に分割されている路網図が、当該閉路を構成する上位層の各路の両側に当該路を境界とする２つの分割網を関連付けて格納された路記憶部を備えたコンピュータが、最上位層から下位に向けて順次前記路網図の各層をアクセスして、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている前記注目位置側の前記分割網（Ｇｄ）を、当該Ｇｄに前記注目位置を含む前記路が存在するようになるまで一段下位層から取得して、最後に取得した前記Ｇｄが属する層から上位に向けて更新層の一段下位層まで順次各層をアクセスして、各層に於いて、当該Ｇｄの前記境界を構成する前記路の少なくとも２つと前記注目位置間の経路（分割経路）を前記Ｇｄ内で探索して、前記Ｇｄを前記分割経路で複数の分割網（ｇｄ）に分割して、前記Ｇｄを前記路記憶部から削除して、各前記ｇｄを前記路記憶部に記憶し、前記分割経路を１段上位の層に追加する分割工程を有する。
【発明の効果】
【００１７】
本発明にかかる路網図管理装置は、ある場所の状況に応じて当該場所を経由する経路が検索されやすく、かつ、効率的な経路探索を可能とする。
【図面の簡単な説明】
【００１８】
【図１】路網図管理システム１０の構成図である。
【図２】層表３０の構成図である。
【図３】網表４０の構成図である。
【図４】曲形状４５の説明図である。
【図５】頂点表５０の構成図である。
【図６−Ａ】路網例２（層１）の説明図である。
【図６−Ｂ】路網例２（層２）の説明図である。
【図６−Ｃ】路網例２の層表３０の構成図である。
【図６−Ｄ】路網例２の網表４０の構成図である。
【図６−Ｅ】路網例２の頂点表５０の構成図である。
【図７】利用者情報記憶部２７に格納されるデータの構成図である。
【図８】分割手段２５の動作フローチャートである。
【図９−Ａ】路網例２（層１）の経路追加の説明図である。
【図９−Ｂ】路網例２（層２）の分割の説明図である。
【図９−Ｃ】路網例２の層表３０の経路追加・分割後の構成図である。
【図９−Ｄ】路網例２の網表４０の経路追加・分割後の構成図である。
【図９−Ｅ】路網例２の頂点表５０の経路追加・分割後の構成図である。
【図１０】探索手段２６の動作フローチャートである。
【図１１】探索手段２６の再帰的探査の動作フローチャートである。
【図１２】路網例１（層１）の説明図である。
【図１３】路網例１（層２）の説明図である。
【図１４】路網例１（層３）の説明図である。
【図１５】路網例１（層１）の分割経路探査の説明図である。
【図１６】路網例１（層２）の分割経路探査の説明図である。
【図１７】路網例１（層３）の分割経路探査の説明図である。
【図１８】路網例１（層２）の経路追加の説明図である。
【図１９】路網例１（層３）の分割の説明図である。
【図２０】路網例１（層１）の経路追加の説明図である。
【図２１】本発明にかかる路網図管理装置２０の基本的構成を示す。
【発明を実施するための形態】
【００１９】
図１は、路網図管理システム１０の構成図である。路網図管理システム１０は、１つ又は複数の路網図管理装置２０と１つ又は複数の送信装置１１を包含する。送信装置１１は端末１２を備えていても良い。
【００２０】
路網図管理装置２０は、例えば、カーナビゲーション装置、ウォーキング道案内装置、海路案内装置、空路案内装置である。路網図管理装置２０は分割手段２５、路記憶部２８を備える。路網図管理装置２０は、受信手段２２、入力手段２３、表示手段２４、探索手段２６、利用者情報記憶部２７を備えていても良い。
【００２１】
路記憶部２８はディスク装置等の記憶装置である。路記憶部２８は、道路、山道、海路、空路等のネットワーク図（路網図）を階層化して記憶する。上位のネットワーク図は、主要な路（高速道路、幹線国道等）だけのネットワークを記述しており、その詳細度は低い（記述が粗い）。下位のネットワーク図は、主要でない道路（小さな市町村道等）のネットワークも記述しており、その詳細度は高い。
【００２２】
図１２、図１３、図１４は路記億部２８に記憶されている路網図の例（路網例１）である。これらの図は、渋谷駅周辺の階層化された道路網図である。図１２は最上位層（例えば層１）の道路網図である。図１２は、通り名のつくような大きな国道を記述している。図１３は中間層（層２）の道路網図である。図１３は、図１２の道路網図に、やや道幅の狭い国道や県道、それらの交差点等の情報を追加したものとなっている。図１４は下位層（層３）の道路網図である。図１４は、図１３の道路網図に市道レベルの道路を追加し、更に詳細なものになっている。なお、層の識別子付けは、上例と異なっていても良い（例えば、最下位層を層１とする）。また、本発明に於いて、階層の数は２以上であればよく、本例の如く３層に限定されない。
【００２３】
送信装置１１は、端末１２等から入力した、ある地点に於ける祭りや博覧会開催等の状況情報を路網図管理装置２０に送信する。状況情報は、発生しているイベントの種類等（イベント属性６１）とその発生位置（注目位置１３）等である。受信手段２２は受信機等であり、送信装置１１から送信された状況情報を受信する。
【００２４】
分割手段２５は、注目位置１３が探索されやすいように、路記憶部２８の路網図（道路網図等）を更新する。
【００２５】
入力手段２３はタッチパネルやキーボード等であり、出発位置と目的位置を包含する経路探索要求を入力する。
【００２６】
探索手段２６は、入力手段２３から入力された出発位置から目的位置迄の移動経路を、路記憶部２８の路網図から検索する。但し、出発位置は、路網図管理装置２０等が備えたＧＰＳ装置（Global Positioning System）（図示されない）から取得しても良い。探索手段２６は探索した移動経路を表示手段２４に出力する。表示手段２４はディスプレイ装置等である。探索手段２６は、移動経路を地図上にオーバーラップ等させて表示しても良い。
【００２７】
利用者情報記憶部２７はディスク装置等の記憶装置である。利用者情報記憶部２７は路網図管理装置２０の利用者の情報を格納する。
【００２８】
分割手段２５及び探索手段２６は、その機能を果たす専用ハードウェアとして実装されても良いし、路網図管理プログラム２９がメモリに格納されてコンピュータ２１のプロセッサで実行されることにより、その機能を果たすように実装されても良い。
【００２９】
路記憶部２８は、階層化された路網図の各層を、頂点と頂点間の辺から構成される網として格納する。頂点は道路等の交差点をモデル化したものである。頂点は道路等の端点（行き止まり等）を表す場合もある。辺は道路等の交差点間等の区間をモデル化したものである。具体的に、路記憶部２８は階層化された路網図を、例えば、層表３０、網表４０および頂点表５０という形式で格納する。
【００３０】
図２は層表３０の構成図である。層表３０は路網図の各層対応にエントリを有する。例えば最上段（第１エントリ）が最上位層に対応し、その下の第２エントリが最上層の１段下の層に対応する。第３エントリ以降、各エントリは順に下位の層に対応する。各エントリは対応する層に属する網の識別子である網ＩＤ３２を格納する。網ＩＤ３２は、例えばＧｈｎという形式である。ここで、ｈは層の識別子（ｈ＝１以上）でありｎは層ｈ内の通し番号である。ｈｎは網番号である。
【００３１】
路網図の下位の層は、１段上位の層における辺の閉路で囲まれた領域ごとの分割網に分割されて格納されている。ここで、閉路はコード（chord）を含まない閉路である。分割手段２５や探索手段２６は、網の分割や経路探索に於いて、閉路に含まれる辺や当該辺の端点を介して、層間の遷移を行う。
【００３２】
なお、下位の層に属する網の数は、上位の層に属する網の数より大きい。最上位層に属する網の数は通常１である。路網図は、経路探索やアクセス効率化のために分割されている。
【００３３】
図５は頂点表５０の構成図である。頂点表５０は網ごとに分割されて存在する。頂点表５０は、網ＩＤ３２と当該網に属する頂点ごとのエントリから構成される。各エントリは、頂点ＩＤ５１と座標５２を包含する。頂点ＩＤ５１は頂点の識別子であり、例えばｖ（ｇ、ｎ）という形式である。ｇは当該頂点が属する網の網番号である。ｎは網Ｇｇ内の通し番号である。座標５２は当該頂点の位置を表す。位置は、例えば緯度と経度の対である。位置は他の座標系に基づく値であっても良い。
【００３４】
図３は網表４０の構成図である。網表４０は網ごとに分割されて存在する。網表４０は、網ＩＤ３２と当該網に属する辺ごとのエントリから構成される。各エントリは、辺ＩＤ４１、始点４２、終点４３、上位辺４４、曲形状４５、長さ４６、左網４７、右網４８等を包含する。
【００３５】
辺ＩＤ４１は、エントリに対応した辺（以下、対応辺）の識別子である。辺ＩＤ４１は、例えばｅ（ｇ、ｎ）という形式である。ここで、ｇは対応辺が属する網の網番号である。ｎは網Ｇｇ内の通し番号である。
【００３６】
始点４２と終点４３は、対応辺の両端の頂点の頂点ＩＤ５１を示す。上位辺４４は、対応辺がモデル化する道路等の区間をモデル化する１段上位層の辺の辺ＩＤ４１である。例えば、図１３における辺ｅ１乃至ｅ８のおのおのの上位辺４４は図１２に於ける辺Ｅである。このように層ｈの辺（Ｅ、等）は、下位の層ｈ＋１においていくつかの辺（ｅ１、等）に分割されて表現される。
【００３７】
辺は道路等の区間をモデル化する。従って、辺は曲線である場合がある。曲形状４５はこの曲線の形状を記述する。曲形状４５は、例えば図４に示すように、曲線を近似する折れ線を中間座標系列として記述したものでも良い。曲形状４５は、曲率を用いる等、他の形式の記述データであっても良い。
【００３８】
長さ４６は対応辺がモデル化する道路等の距離である。長さ４６は、曲形状４５を反映した値であることが好ましい。長さ４６は、道路等の制限速度や高速料金等も反映した移動コストを格納しても良い。
【００３９】
左網４７と右網４８は対応辺に関連付けられている１段下位層の網ＩＤ３２を格納する。上述したように、１段下位の層は、対応辺を含む２つの閉路で囲まれた領域ごとに分割されている。従って、１段下位の層には、対応辺（正確には、対応辺がモデル化する道路等の区間をモデル化する下位の層の辺群）を境界とする２つの網が存在する。左網４７と右網４８はこの２つの網の網ＩＤ３２を格納する。
【００４０】
辺の両端である始点４２と終点４３は区別されており辺は方向を持つ。従って、位置ｑが与えられたとき、分割手段２５等は、位置ｑが対応辺の左右どちら側に位置するかを判別して、ｑが属する下位層の網ＩＤ３２を取得できる。例えば、対応辺に関連付けられている折れ線がｒ＝（ｍ１，ｍ２，．．．，ｍｋ）であるとき、分割手段２５等は、線分（ｍｉ，ｍｉ＋１），ｉ＝１，２，．．．，ｋ−１のなかからｑと最も近い線分（ｍｘ，ｍｘ＋１）を決定して、２つのベクトル（ｍｘ，ｍｘ＋１）と（ｍｘ＋１，ｑ）の外積を求める。分割手段２５等は、例えば符号が正である場合は左網４７から、そうでない場合は右網４８から、下位層の網ＩＤ３２を取得する。分割手段２５等は、符号の正負と左右の対応付けを逆にしても良い。上記計算の詳細は、Ronald L. Graham: An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. (1972)等の文献に記載されている。
【００４１】
なお、左網４７と右網４８の一方または両方がＮｕｌｌである場合がある。対応辺が、海岸線の道路等をモデル化している場合、対応辺の海側、例えば左網４７はＮｕｌｌとなる。また、対応辺が最下層に属す場合等、左網４７と右網４８の両方がＮｕｌｌとなる。
【００４２】
なお、頂点表５０は、頂点ＩＤ５１対応に当該頂点に接続されている全ての辺の辺ＩＤ４１を格納していても良い。
【００４３】
図６−Ａと６−Ｂは路記憶部２８に格納されている路網図の例（網路例２）である。図６−Ｃは本路網図を記述する層表３０を例示する。図６−Ｄは本路網図を記述する網表４０を例示する。図６−Ｅは本路網図を記述する頂点表５０を例示する。
【００４４】
本例の路網図は、図６−Ａの上位層（層１）と図６−Ｂの下位層（層２）の２層から構成される。層１は１つの網Ｇ１１を包含する。網Ｇ１１は、辺ｅ（１１、１）、ｅ（１１、２）ｅ（１１、３）で構成される閉路で囲まれた領域Ａと、辺ｅ（１１、３）、ｅ（１１、４）、ｅ（１１、５）で構成される閉路で囲まれた領域Ｂを有する。従って、層２は、領域Ａに対応する網Ｇ２１と領域Ｂに対応する網Ｇ２２に分割されて記憶される。
【００４５】
上述の辺は例えば全て主要道路をモデル化したものである。層２は、主要道路をモデル化した辺ｅ（２１、１）乃至ｅ（２１、５）およびｅ（２２、１）乃至ｅ（２２、５）に加え、非主要道路をモデル化した辺ｅ（２１、６）とｅ（２２、６）を包含する。また、ｅ（２１、６）とｅ（２２、６）の始点４２と終点４３の頂点ｖ（２１、３）、ｖ（２１、５）、ｖ（２２、２）、ｖ（２２、４）も追加されている。即ち、層２の方が層１より詳細度が高い。
【００４６】
層１の辺ｅ（１１、３）の例えば左側は領域Ａである。従って、当該辺の左網４７には、層２における領域Ａの網の網ＩＤ３２であるＧ２１が格納されている。層１の辺ｅ（１１、３）の右側は領域Ｂである。従って、当該辺の右網４８には、層２における領域Ｂの網の網ＩＤ３２であるＧ２２が登録されている。同様に、層１の辺ｅ（１１、１）の左側は領域Ａである。従って、当該辺の左網４７には、層２における領域Ａの網の網ＩＤ３２であるＧ２１が登録されている。
【００４７】
なお、ｅ（１１、３）と、ｅ（２１、５）およびｅ（２１、４）は同じ道路等の区間をモデル化している。従って、ｅ（２１、５）およびｅ（２１、４）の上位辺４４はともに、ｅ（１１、３）となる（図６−Ｄ）。同様に、ｅ（１１、３）と、ｅ（２２、１）およびｅ（２２、２）は同じ道路等の区間をモデル化している。従って、ｅ（２２、１）およびｅ（２２、２）の上位辺４４はともに、ｅ（１１、３）となる（図６−Ｄ）。
【００４８】
また、ｅ（２１、６）およびｅ（２２、６）は層２のみでモデル化された非主要道路に対応するため、上位辺４４は格納されていない（Ｎｕｌｌ値である）。
【００４９】
図７は、利用者情報記憶部２７に格納されるデータの構成図である。利用者情報記憶部２７は、イベント属性６１と更新層６２を対にして記憶している。更新層６２は、イベント属性６１を持つイベントが発生したとき、当該イベントの発生位置に至る経路を路網図のどの層にまで追加するかを指定する。発生位置への経路が上位の層に追加されるほど、発生位置を通過する経路が探索されやすくなる。従って、利用者の興味が高いイベント属性６１に対応する更新層６２は上位の層を指定する。
【００５０】
図８は分割手段２５の動作フローチャートである。分割手段２５は、受信手段２２からイベント属性６１、注目位置１３（ｑ）と誤差を入力する（Ｓ１）。分割手段２５は、利用者情報記憶部２７から入力したイベント属性６１に対応する更新層６２を取得し（Ｓ２）、層表３０から最上位層の網ＩＤ３２を取得する（Ｓ３）。
【００５１】
取得した網ＩＤ３２の網（Ｇｈと略記）の網表４０と頂点表５０を路記憶部２８からメモリに読み込んだ後、分割手段２５はＧｈ内でｑの最近傍辺を探索して、その辺ＩＤ４１を取得する（Ｓ４）。分割手段２５は、各辺の始点４２及び終点４２の座標５２や、曲形状４５の折れ線等を参照して最近傍辺を決定する。このとき、分割手段２５は非特許文献１に記載されている技術を用いても良い。
【００５２】
例えばｑが図６−Ａの×印の位置であるとき、分割手段２５は最近傍辺の辺ＩＤ４１としてｅ（１１、３）を取得する。
【００５３】
次に、分割手段２５はｑが最近傍辺上に位置しているかを判別する（Ｓ５）。このとき、分割手段２５は、ｑと最近傍辺の距離が入力した誤差範囲内であれば最近傍辺上に位置していると判断する。距離は平面上の距離であり、移動経路の長さ４６ではない。誤差はｑ等の位置測定装置の測定誤差を示す値である。
【００５４】
ｑが最近傍辺上に位置していない場合（Ｓ５でＮ）、分割手段２５はＧｈの網ＩＤ３２をスタックにプッシュダウンする（Ｓ６）。同手段は、ｑが最近傍辺の左右の何れに位置するかを判断し、ｑが左側に位置すれば左網４７から、ｑが右側に位置すれば右網４８から、１段下位のｈ＋１層の網ＩＤ３２（この網ＩＤ３２の網が新たなＧｈとなる）を取得する（Ｓ７）。
【００５５】
ｑが図６−Ａの×印の位置であるとき、分割手段２５は最近傍辺ｅ（１１、３）の左網４７（図６−Ｄ）から網ＩＤ３２としてＧ２１を取得する。
【００５６】
その後、分割手段２５は、取得したｈ＋１層の網ＩＤ３２がＮｕｌｌでなければ（ＳＧでＮ）Ｓ４のステップに戻る。通常、Ｓ７で取得したｈ＋１層の網ＩＤ３２がＮｕｌｌとなることはない。しかし、ｑの入力値に予想外の誤差が含まれていた場合等で、ｑが最近傍辺上に位置しているにもかかわらず分割手段２５が位置していないと判断（Ｓ５でＮ）をし、かつ、最近傍辺の一方または両方にｈ＋１層の網が無いと、例外的にＮｕｌｌとなり得る。
【００５７】
ｑが最近傍辺上に位置している場合（Ｓ５でＹ）、分割手段２５はＧｈが最上位の層でないことを、例えば層表３０を参照して確認する（Ｓ８でＮ）。Ｇｈが最上位の層であれば（Ｓ８でＹ）、分割手段２５は処理を終了する。ｑが最上位層の辺上に位置するのであれば、経路追加は必要ないからである。
【００５８】
なお、Ｓ７で取得したｈ＋１層の網ＩＤ３２がＮｕｌｌである場合（ＳＧでＹ）、分割手段２５は、スタックの最上段をポップアップして（ＳＨ）、Ｓ８の処理を行う。
【００５９】
ｑが最上位層でない最近傍辺上に位置している場合（Ｓ５でＹ、Ｓ８でＮ）、分割手段２５は、ｑから１段上位の層（ｈ−１層）に通じる各辺の頂点への経路（但し、上位層に通じる辺上の経路は除く）（分割経路）を求める（Ｓ９）。ｈ−１層に通じる辺とは、Ｇｈの境界を構成する辺であり、網表４０において上位辺４４に値が設定されている辺である。
【００６０】
例えばｑが図６−Ｂの×印の位置であるとき、ｑはＧ２１において最近傍辺ｅ（２１、６）上に位置している（Ｓ５でＹ）。従って、分割経路は、ｑとｖ（２１、５）間およびｑとｖ（２１、５）間となる。
【００６１】
分割手段２５は、Ｇｈを分割経路上の辺を境界とする部分網に分割し、分割して出来た網の網表４０および頂点表５０を新たに生成する（ＳＡ）。分割手段２５は、作成された網の網ＩＤ３２を層表３０に追加する。
【００６２】
分割手段２５は、例えば図６−ＢのＧ２１をｅ（２１、６）を境界として分割し、図９−Ｂに図示する新たな網Ｇ２３およびＧ２４を生成する。分割手段２５は、元のＧ２１の網表４０および頂点表５０（図６−Ｄ、図６−Ｅ）を基に、Ｇ２３およびＧ２４の網表４０および頂点表５０（図９−Ｄ、図９−Ｅ）を生成する。
【００６３】
分割手段２５は、Ｇｈにおける分割経路上の辺をｈ−１層に追加する（ＳＢ）。分割手段２５は、追加対象となる網の網ＩＤ３２をスタックの最上段から取得する。また、同手段は追加した辺が上位辺４４を有する辺と交わっていれば、当該上位辺４４を追加された頂点で分割する。
【００６４】
例えば分割手段２５は、図９−ＡのＧ１１に辺ｅ（１１、６）を追加して、元の辺ｅ（１１、３）を頂点ｖ（１１、６）で分割する。分割手段２５は、元の辺ｅ（１１、２）を頂点ｖ（１１、５）で分割する。
【００６５】
分割手段２５は、ｈ−１層の辺の左網４７と右網４８に、分割した網の網ＩＤ３２を格納する（ＳＣ）。具体的に、分割手段２５は、先ず追加した辺の左網４７と右網４８に分割した網の網ＩＤ３２を格納する。さらに同手段は、ｈ−１層において分割したＧｈの網ＩＤ３２を左網４７または右網４８に有する辺またはその分割辺の左網４７と右網４８に、分割した網の網ＩＤ３２を格納する。
【００６６】
例えば、図９−Ｄにおいて、追加された辺ｅ（１１、６）の左網４７にはＧ２３が、右網４８にはＧ２４が格納される。また、図６−Ｄにおいて、分割前のＧ２１を左網４７に持つｅ（１１、１）の左網４７には分割後のＧ２３が格納される。
【００６７】
ついで、分割手段２５は分割前の網Ｇｈの網表４０および頂点表５０を削除する（ＳＤ）。分割手段２５は、削除された網の網ＩＤ３２を層表３０から削除する。
【００６８】
例えば、分割手段２５は、図６−Ｄにおける網Ｇ２１の網表４０を削除する。
【００６９】
ｈ−１層が更新層６２でなければ（ＳＥでＮ）、分割手段２５はスタックの最上段から網ＩＤ３２を取得した後、スタックをポップアップして（ＳＦ）Ｓ９に戻る。ｈ−１層が更新層６２であれば（ＳＥでＹ）、分割手段２５は処理を終了する。
【００７０】
以上の説明から明らかなように、図９−Ｃは路網例２の経路追加・分割後の層表３０の例である。図９−Ｄは路網例２の経路追加・分割後の網表４０の例である。図９−Ｅは路網例２の経路追加・分割後の頂点表５０の例である。
【００７１】
図１５乃至図２０は、図１２乃至図１３に示す階層化された道路網の分割を説明する図である。図１５乃至図２０は、注目位置１３（ｑ）が与えられたとき、分割手段２５が地図の更新を行う際の手順の流れを例示する。この例は、ｑを通過する経路を最上位の層に追加するものである。即ち、更新層６２が最上位層である場合の例である。
【００７２】
図１５は、図１２と同様に最上位（層１）の道路網の一部を抜粋した図である。図１５はｑの最近傍辺がeであることを示している。また、受信手段２２で取得した位置情報は、高々εの誤差を含むとする。ここで、ｑと辺ｅの間の距離がある許容値ε以下であることと、qを中心として半径εの円とｅの曲形状４５で与えられる折れ線が交差することは等価である。図１５の破線で描かれているｑを中心として半径εの円とｅの折れ線は交差していないので、ｑは辺ｅ上に位置しない。従って、分割手段２５は、下層の道路網を取得する。具体的に分割手段２５は、ｅのｑ側（左網４７または右網４８）に関連付けられている下位の道路網を取得する。
【００７３】
図１６は、辺ｅに関連付けられて取得された側の下位の層の道路網の抜粋を示している。分割手段２５は、新たに道路網の一部を取得したら、その道路網に対して最近傍辺を求めるために曲形状４５等のデータ構造（R-tree）を読み込み、ｑの最近傍辺を求める。図１６では、辺ｅ'が層２におけるｑの最近傍辺であることを示している。階層１の場合と同様に、図１６の破線で描かれているｑを中心として半径εの円とｅ'の折れ線は交差しないので、ｑは辺ｅ'上に位置しない。従って、分割手段２５は、図１７に示すｅ'のｑ側に関連付けられている下層（層３）の道路網Ｇを取得する。
【００７４】
このとき、Ｇにおけるｑの最近傍辺はｑから十分近いので、分割手段２５はそれ以上層を下る手続きを終了する（図８のＳ５でＹ）。分割手段２５は、次にこの道路網Ｇに対して、Ｇの上位の層２に存在するＧを囲む辺への最短経路を求める。
【００７５】
図１８はこの手続きの結果を示す。辺ｅ１'は、ｑから辺ｅ１への最短経路の両端点をつなぐ辺である。分割手段２５は、Ｇを囲むすべての辺に関してｑからの最短経路を求めるが、図が煩雑になるため図１８には示していない。
【００７６】
分割手段２５は、いま求めたｑからＧを囲む辺への最短経路ｅ１'、ｅ２'、ｅ３'等により、Ｇをさらに細かく分割する。分割手段２５は、Ｇの上位層２のグラフＧ'（図１６）に各辺ｅ１'、ｅ２'、ｅ３'等を追加するようにＧ'に対する網表４０を更新する。例えば、分割手段２５は、曲形状４５のR-trｅｅに対して、ｅ１', ｅ２', ｅ３'…の各折れ線を追加する。
【００７７】
そして、分割手段２５は、Ｇ'のそれぞれの辺と分割された道路網の関連付けを行う。例えば、図１９は、Ｇを分割した結果、ｅ１', ｅ２' および上位の階層２に存在する辺ｅｉ乃至ｅｉ＋５によって囲まれる道路網ｇ１が新たに得られていることを示している。このとき、分割前はｅi の右網４８としてＧが関連付けられていたが、分割後の関連付けの更新として、ｅi の右網４８はｇ１となる。
【００７８】
最終的に、分割手段２５は、Ｇ'においてＧ'を囲む最上位のグラフＧ''の各辺への最短経路を求め、その経路をＧ''へ追加する（図２０）ように網表４０および頂点表５０の更新を行う。
【００７９】
図１０は、探索手段２６の動作フローチャートである。探索手段２６は、受信手段２２から出発位置（ｓ）、目的位置（ｔ）と誤差を入力する（Ｓ１１）。探索手段２６は、出発位置を路網図管理装置２０等が備えるＧＰＳ装置から取得しても良い。探索手段２６は、層表３０から最上位層の網ＩＤ３２を取得する（Ｓ１２）。
【００８０】
取得した網ＩＤ３２の網（Ｇｈと略記）の網表４０と頂点表５０をメモリに読み込んだ後、探索手段２６はＧｈ内でｓの最近傍辺（最近傍辺ｓ）とｔの最近傍辺(最近傍辺ｔ）とを探索して、おのおのの辺ＩＤ４１を取得する（Ｓ１３）。次に、探索手段２６はｓが最近傍辺ｓ上に位置している、または、ｔが最近傍辺ｔ上に位置しているかを判別する（Ｓ１４）。このとき、探索手段２６は、ｓまたはｔと各々の最近傍辺の距離が入力した誤差範囲内であれば最近傍辺上に位置していると判断する。
【００８１】
ｓとｔの何れもが最近傍辺上に位置していない場合（Ｓ５でＮ）、探索手段２６は、ｓが最近傍辺の左右の何れに位置するかを判断する。そして同手段は、ｓが左側に位置すれば左網４７から、ｓが右側に位置すれば右網４８から、１段下位のｈ＋１層の網ＩＤ３２（当該網を網Ｇｈ＋１ｓと略記）を取得する（Ｓ１５）。探索手段２６は、ｔが最近傍辺の左右の何れに位置するかを判断し、ｔが左側に位置すれば左網４７から、ｔが右側に位置すれば右網４８から、１段下位のｈ＋１層の網ＩＤ３２（当該網を網Ｇｈ＋１ｔと略記）を取得する（Ｓ１６）。Ｇｈ＋１ｓおよびＧｈ＋１ｔの網ＩＤ３２が一致すれば（Ｓ１７でＹ）、探索手段２６はＳ１３に戻る。
【００８２】
Ｇｈ＋１ｓおよびＧｈ＋１ｔの網ＩＤ３２が一致すれば（Ｓ１７でＹ）、探索手段２６はＧｈ内で、Ｇｈ＋１ｓとＧｈ＋１ｔ間の経路（経路２）を探索して取得する（Ｓ１８）。ここで、Ｇｈ＋１ｓとＧｈ＋１ｔ間の経路とは、Ｇｈ＋１ｓを囲む辺上の各頂点からＧｈ＋１ｔを囲む辺上の各頂点への経路の内で距離が最短の経路を指す。Ｇｈ＋１ｓを囲む辺とは、左網４７または右網４８にＧｈ＋１ｓの網ＩＤ３２が格納されている辺である。また、経路の距離は当該経路に属する辺の長さ４６の合計値である。なお、探索手段２６は、経路の探索の為に、Dijkstraのアルゴリズム等の一般的な検索アルゴリズムを用いることができる。
【００８３】
図９−ＡにおいてＧ２４がＧｈ＋１ｓである場合、Ｇｈ＋１ｓを囲む辺上の各頂点は、ｖ（１１、３）、ｖ（１１、５）、ｖ（１１、６）となる。
【００８４】
次に、探索手段２６はｓと経路２のｓ側の端点（Ｇｈ＋１ｓの周辺上の頂点となる。ｓｈ＋１と略記）の間の経路（経路１）をｈ＋１以下の層から再帰的探索により取得する（Ｓ１９）。図１１は再帰的探索の詳細を示す。更に、探索手段２６は経路２のｔ側の端点（Ｇｈ＋１ｔの周辺上の頂点となる。ｔｈ＋１と略記）とｔの間の経路（経路３）をｈ＋１以下の層から再帰的探索により取得する（Ｓ１Ａ）。
【００８５】
探索手段２６は、経路１、経路２、経路３をつなげてｓからｔへの移動経路を取得する（Ｓ１Ｂ）。最後に、探索手段２６は、ｓからｔ移動経路を表示手段２４に表示する（Ｓ１Ｉ）。
【００８６】
探索手段２６はｓが最近傍辺ｓ上に位置している、かつ、ｔが最近傍辺ｔ上に位置している場合（Ｓ１４でＹ、Ｓ１ＣでＹ）、Ｇｈ内でｓからｔへの移動経路検索を行う（Ｓ１Ｄ）。
【００８７】
ｓまたはｔの一方（例えばｓ）が最近傍辺上に位置しているが、他方（例えばｔ）が最近傍辺上に位置していない場合（Ｓ１４でＹ、Ｓ１ＣでＮ）、探索手段２６は以下の処理を行う。
【００８８】
探索手段２６は、ｔが最近傍辺の左右の何れに位置するかを判断し、ｔが左側に位置すれば左網４７から、ｔが右側に位置すれば右網４８から、１段下位のｈ＋１層の網ＩＤ３２（当該網を網Ｇｈ＋１ｔと略記）を取得する（Ｓ１Ｅ）。
【００８９】
その後、探索手段２６は、Ｇｈ内で、ｓとＧｈ＋１ｔ間の経路（経路４）を探索して取得する（Ｓ１Ｆ）。ここで、ｓとＧｈ＋１ｔ間の経路とは、ｓからＧｈ＋１ｔを囲む辺上の各頂点への経路の内で距離が最短の経路を指す。Ｇｈ＋１ｔを囲む辺とは、左網４７または右網４８にＧｈ＋１ｔの網ＩＤ３２が格納されている辺である。
【００９０】
探索手段２６は経路４のｔ側の端点（Ｇｈ＋１ｔの周辺上の頂点となる。ｔｈ＋１と略記）とｔの間の経路（経路５）をｈ＋１以下の層から再帰的探索により取得し（Ｓ１Ｇ）、最後に経路４と５を連結してｓからｔへの移動経路を取得する（Ｓ１Ｈ）。
【００９１】
ｔが最近傍辺上に位置しているがｓが最近傍辺上に位置していない場合、探索手段２６は、ｓとｔの立場を逆転して同様の処理を行う。
【００９２】
図１１は、探索手段２６の再帰的探査の動作フローチャートである。図１１は、ｔｈ＋１とｔの間の第５の経路をｈ＋１以下の層から検索する場合（Ｓ１Ｇ等の詳細）を例示する。
【００９３】
探索手段２６は、Ｇｈ＋１ｔの網ＩＤ３２とｔｈ＋１をスタックの最上段にプッシュダウンする（Ｓ２１）。探索手段２６はｔが最近傍辺の左右の何れに位置するかを判断し、ｔが左側に位置すれば左網４７から、右側に位置すれば右網４８から、１段下位のｈ＋２層の網ＩＤ３２（当該網を網Ｇｈ＋２ｔと略記）を取得する（Ｓ２２）。
【００９４】
探索手段２６は、Ｇｈ＋１内で、ｔｈ＋１とＧｈ＋２ｔ間の経路を探索して取得する（Ｓ２３）。なお、当該経路の端点となるＧｈ＋２ｔの周辺上の頂点は、ｔｈ＋２として参照される。
探索手段２６は、検索した経路をＳ２２でプッシュダウンしたスタックの最上段に追記する（Ｓ２４）。
【００９５】
Ｇｈ＋２ｔの網表４０と頂点表５０をメモリに読み込んだ後、探索手段２６はＧｈ＋２ｔ内でｔの最近傍辺を取得する（Ｓ２５）。探索手段２６は、ｔが最近傍辺上に位置しているかを判別する（Ｓ２６）。このとき、探索手段２６は、ｔと最近傍辺の距離が入力した誤差範囲内であれば最近傍辺上に位置していると判断する。
【００９６】
ｔが最近傍辺上に位置しなければ（Ｓ２６でＮ）、探索手段２６はＳ２１に戻る。このときＧｈ＋２ｔは新たなＧｈ＋１となり、ｔｈ＋２は新たなｔｈ＋１となる。
【００９７】
ｔが最近傍辺上に位置すれば（Ｓ２６でＹ）、探索手段２６はＧｈ＋２内でｔｈ＋２とｔの間の経路６を求める（Ｓ２７）。
【００９８】
最後に探索手段２６は、スタックを一段ずつポップアップしながら、スタックに記憶していた経路を順次ｔから遠ざかる方向に経路６と連結して経路５を取得して（Ｓ２８）、処理を終了する。
【００９９】
本実施形態の路網図管理システム１０は、ある場所の状況に応じて、当該場所を経由する経路を検索されやすくする。その理由は、分割手段２５が、注目位置１３を経由する経路を上位の層に追加するからである。
【０１００】
さらに、本実施形態の路網図管理システム１０は、経路検索および経路追加を効率的に行うことが出来る。その理由は、路網図を部分網に分割して路記憶部２８に記憶しており、経路検索および経路追加において、必要な部分しかメモリに読み込まず、また、当該部分内でのみ経路探索を行うからである。
【０１０１】
さらに、本実施形態の路網図管理システム１０は、利用者の嗜好に基づいた経路追加を行うことが出来る。その理由は、利用者情報記憶部２７に基づいて、経路追加をする層を決定するからである。
【０１０２】
本発明の第２の実施形態の路網図管理装置２０の分割手段２５は、ｑから１段上位の層（ｈ−１層）に通じる所定数（２、等）の辺の頂点だけへの経路を求める（図８のＳ９）。辺の選択は、各辺対応に網表４０に登録されている優先度等に基づいて行う。
【０１０３】
本実施形態の路網図管理装置２０は経路追加を高速に実施できる。その理由は、分割経路の探索数が限定されるからである。
【０１０４】
また、路網図管理装置２０は、経路追加を常に所定層（例えば最上層）以下の層に行うこととしてもよい。この場合、路網図管理装置２０は利用者情報記憶部２７、受信手段２２を備えなくても良い。
【０１０５】
さらに、路網図管理装置２０は、入力探索手段２６、表示手段２４、探索手段２６を備え無くても良い。入力探索手段２６、表示手段２４、探索手段２６は、路記憶部２８を共有する探索装置（図示されない）が備えても良い。
【０１０６】
図２１は、本発明にかかる路網図管理装置２０の基本的構成を示す。路網図管理装置２０は、路記憶部２８と分割手段２５を備える。
【符号の説明】
【０１０７】
１０ 路網図管理システム
１１ 送信装置
１２ 端末
１３ 注目位置
２０ 路網図管理装置
２１ コンピュータ
２２ 受信手段
２３ 入力手段
２４ 表示手段
２５ 分割手段
２６ 探索手段
２７ 利用者情報記憶部
２８ 路記憶部
２９ 路網図管理プログラム
３０ 層表
３２ 網ＩＤ
４０ 網表
４１ 辺ＩＤ
４２ 始点
４３ 終点
４４ 上位辺
４５ 曲形状
４６ 長さ
４７ 左網
４８ 右網
５０ 頂点表
５１ 頂点ＩＤ
５２ 座標
６１ イベント属性
６２ 更新層
【技術分野】
【０００１】
本発明は、路網図管理装置、路網図管理システム、路網図管理プログラムおよび路網図管理方法に関する。
【背景技術】
【０００２】
特許文献１は、道路を複数の階層に分類し、各階層データが階層内の交差点及び上位階層の道路との交差点に関する情報、交差点間の道路に関する情報を備える地図データを用いたナビゲーションシステムを開示する。このシステムは、出発地と目的地からそれぞれ上位の所定の階層の道路の交差点までの経路探査を行い、その後所定階層内での経路探査を行う。この地図データに於いて、下位の階層は、例えば上位の階層の道路により囲まれた範囲毎に分けて記憶される。
【０００３】
特許文献２は、適切な経路を探索する為に、階層化された地図情報を更新する地図情報生成装置を開示する。この装置は、下位の階層に属す道路の移動コストが上位の階層に属す道路を利用するよりも低コストであるとき、この下位の階層に属す道路を上位の階層の地図情報へ追加する。この装置は、例えば県道であっても空いていて快適に走れるならば、国道と同じ階層の地図情報にこの県道を追加する。
【０００４】
特許文献３は、全国の地図データを読み込み、最上段階の選択基準の道路（例えば国道）を境界としてエリア分割する地図データ作成装置を開示する。この装置は、分割エリアをナビ用データに変換した状態でのデータサイズが上限値を超えている場合は、次段階の選択基準道路（例えば県道・市町村道）を境界として再分割する。
【０００５】
非特許文献１は、空間インデックスを管理する一般的なデータ構造の例であるR-Treesを開示する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平５−２７６７９号公報
【特許文献２】特開２００７−２４５１５号公報
【特許文献３】特開２００４−２２６７３０号公報
【非特許文献】
【０００７】
【非特許文献１】2006年、シュプリンガー、アールツリー：セオリー・アンド・アプリケーション (R-Trees: Theory and Applications, Springer, 2006)
【発明の概要】
【発明が解決しようとする課題】
【０００８】
カーナビゲーション装置などの経路探索において、ある場所の状況に応じて、当該場所を経由する経路を検索されやすくすることが好ましい場合がある。例えば、或る場所でユーザの関心が高いイベントが発生（祭りや博覧会の開催等）している期間中、移動途中のユーザが当該イベント会場に寄り道できるような経路を優先して探索出来れば好ましい。
【０００９】
階層構造を有する地図情報を利用して経路探索を行う装置がこのような探索を行う為には、当該イベント会場を経由する経路が上位層の地図情報に登録されていると良い。当該経路が主要でない経路であって、通常は下位層の地図情報にしか登録されていない場合は、イベントの開催に合わせて、カーナビゲーション装置などが動的に当該経路を上位層の地図情報に追加すると良い。
【００１０】
ところで、特許文献１に開示されるナビゲーションシステムのように、階層化された地図情報の下位層を上位層の道路により囲まれた範囲に分割して記憶している経路探索装置が存在する。このような経路探索装置は、経路探索に於いてメモリ上に読み込む下位層の地図情報のデータ量を減らすことが出来る為、効率的な経路探索が可能である。
【００１１】
しかしながら、このような装置は、特許文献２に開示されている装置のように、簡単に新たな経路を上位層に追加できない。その理由は、下位層が新たな経路に基づいて分割されていないからである。一方、特許文献２に開示された装置は、効率的な経路探索が出来ない。その理由は、下位層の分割が考慮されていないからである。
【００１２】
即ち、特許文献１と特許文献２に開示された装置は、何れも、経路探索において、ある場所の状況に応じて、当該場所を経由する経路を検索されやすくすることと、効率よい経路探索を両立することが出来ないという課題がある。特許文献３および非特許文献１に開示された技術もこの課題を解決しない。
【００１３】
本願発明の目的は、上記課題を解決する路網図管理装置、路網図管理システム、路網図管理プログラムおよび路網図管理方法を提供することにある。
【課題を解決するための手段】
【００１４】
本発明の一実施形態の路網図管理装置は、路網の詳細度に基づいて複数の層（２つの層間において詳細度が低い層を上位層、高い層を下位層と呼ぶ）に階層化され、各層において一段上位層の路の閉路で囲まれている領域ごとに分割網に分割されている路網図が、当該閉路を構成する上位層の各路の両側に当該路を境界とする２つの分割網を関連付けて格納された路記憶部と、最上位層から下位に向けて順次前記路網図の各層をアクセスして、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている前記注目位置側の前記分割網（Ｇｄ）を、当該Ｇｄに前記注目位置を含む前記路が存在するようになるまで一段下位層から取得して、最後に取得した前記Ｇｄが属する層から上位に向けて更新層の一段下位層まで順次各層をアクセスして、各層に於いて、当該Ｇｄの前記境界を構成する前記路の少なくとも２つと前記注目位置間の経路（分割経路）を前記Ｇｄ内で探索して、前記Ｇｄを前記分割経路で複数の分割網（ｇｄ）に分割して、前記Ｇｄを前記路記憶部から削除して、各前記ｇｄを前記路記憶部に記憶し、前記分割経路を１段上位の層に追加する分割手段を備える。
【００１５】
本発明の一実施形態の路網図管理プログラムは、路網の詳細度に基づいて複数の層（２つの層間において詳細度が低い層を上位層、高い層を下位層と呼ぶ）に階層化され、各層において一段上位層の路の閉路で囲まれている領域ごとに分割網に分割されている路網図が、当該閉路を構成する上位層の各路の両側に当該路を境界とする２つの分割網を関連付けて格納された路記憶部を備えたコンピュータに、最上位層から下位に向けて順次前記路網図の各層をアクセスして、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている前記注目位置側の前記分割網（Ｇｄ）を、当該Ｇｄに前記注目位置を含む前記路が存在するようになるまで一段下位層から取得して、最後に取得した前記Ｇｄが属する層から上位に向けて更新層の一段下位層まで順次各層をアクセスして、各層に於いて、当該Ｇｄの前記境界を構成する前記路の少なくとも２つと前記注目位置間の経路（分割経路）を前記Ｇｄ内で探索して、前記Ｇｄを前記分割経路で複数の分割網（ｇｄ）に分割して、前記Ｇｄを前記路記憶部から削除して、各前記ｇｄを前記路記憶部に記憶し、前記分割経路を１段上位の層に追加する分割処理を実行させる。
【００１６】
本発明の一実施形態の路網図管理方法は、路網の詳細度に基づいて複数の層（２つの層間において詳細度が低い層を上位層、高い層を下位層と呼ぶ）に階層化され、各層において一段上位層の路の閉路で囲まれている領域ごとに分割網に分割されている路網図が、当該閉路を構成する上位層の各路の両側に当該路を境界とする２つの分割網を関連付けて格納された路記憶部を備えたコンピュータが、最上位層から下位に向けて順次前記路網図の各層をアクセスして、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている前記注目位置側の前記分割網（Ｇｄ）を、当該Ｇｄに前記注目位置を含む前記路が存在するようになるまで一段下位層から取得して、最後に取得した前記Ｇｄが属する層から上位に向けて更新層の一段下位層まで順次各層をアクセスして、各層に於いて、当該Ｇｄの前記境界を構成する前記路の少なくとも２つと前記注目位置間の経路（分割経路）を前記Ｇｄ内で探索して、前記Ｇｄを前記分割経路で複数の分割網（ｇｄ）に分割して、前記Ｇｄを前記路記憶部から削除して、各前記ｇｄを前記路記憶部に記憶し、前記分割経路を１段上位の層に追加する分割工程を有する。
【発明の効果】
【００１７】
本発明にかかる路網図管理装置は、ある場所の状況に応じて当該場所を経由する経路が検索されやすく、かつ、効率的な経路探索を可能とする。
【図面の簡単な説明】
【００１８】
【図１】路網図管理システム１０の構成図である。
【図２】層表３０の構成図である。
【図３】網表４０の構成図である。
【図４】曲形状４５の説明図である。
【図５】頂点表５０の構成図である。
【図６−Ａ】路網例２（層１）の説明図である。
【図６−Ｂ】路網例２（層２）の説明図である。
【図６−Ｃ】路網例２の層表３０の構成図である。
【図６−Ｄ】路網例２の網表４０の構成図である。
【図６−Ｅ】路網例２の頂点表５０の構成図である。
【図７】利用者情報記憶部２７に格納されるデータの構成図である。
【図８】分割手段２５の動作フローチャートである。
【図９−Ａ】路網例２（層１）の経路追加の説明図である。
【図９−Ｂ】路網例２（層２）の分割の説明図である。
【図９−Ｃ】路網例２の層表３０の経路追加・分割後の構成図である。
【図９−Ｄ】路網例２の網表４０の経路追加・分割後の構成図である。
【図９−Ｅ】路網例２の頂点表５０の経路追加・分割後の構成図である。
【図１０】探索手段２６の動作フローチャートである。
【図１１】探索手段２６の再帰的探査の動作フローチャートである。
【図１２】路網例１（層１）の説明図である。
【図１３】路網例１（層２）の説明図である。
【図１４】路網例１（層３）の説明図である。
【図１５】路網例１（層１）の分割経路探査の説明図である。
【図１６】路網例１（層２）の分割経路探査の説明図である。
【図１７】路網例１（層３）の分割経路探査の説明図である。
【図１８】路網例１（層２）の経路追加の説明図である。
【図１９】路網例１（層３）の分割の説明図である。
【図２０】路網例１（層１）の経路追加の説明図である。
【図２１】本発明にかかる路網図管理装置２０の基本的構成を示す。
【発明を実施するための形態】
【００１９】
図１は、路網図管理システム１０の構成図である。路網図管理システム１０は、１つ又は複数の路網図管理装置２０と１つ又は複数の送信装置１１を包含する。送信装置１１は端末１２を備えていても良い。
【００２０】
路網図管理装置２０は、例えば、カーナビゲーション装置、ウォーキング道案内装置、海路案内装置、空路案内装置である。路網図管理装置２０は分割手段２５、路記憶部２８を備える。路網図管理装置２０は、受信手段２２、入力手段２３、表示手段２４、探索手段２６、利用者情報記憶部２７を備えていても良い。
【００２１】
路記憶部２８はディスク装置等の記憶装置である。路記憶部２８は、道路、山道、海路、空路等のネットワーク図（路網図）を階層化して記憶する。上位のネットワーク図は、主要な路（高速道路、幹線国道等）だけのネットワークを記述しており、その詳細度は低い（記述が粗い）。下位のネットワーク図は、主要でない道路（小さな市町村道等）のネットワークも記述しており、その詳細度は高い。
【００２２】
図１２、図１３、図１４は路記億部２８に記憶されている路網図の例（路網例１）である。これらの図は、渋谷駅周辺の階層化された道路網図である。図１２は最上位層（例えば層１）の道路網図である。図１２は、通り名のつくような大きな国道を記述している。図１３は中間層（層２）の道路網図である。図１３は、図１２の道路網図に、やや道幅の狭い国道や県道、それらの交差点等の情報を追加したものとなっている。図１４は下位層（層３）の道路網図である。図１４は、図１３の道路網図に市道レベルの道路を追加し、更に詳細なものになっている。なお、層の識別子付けは、上例と異なっていても良い（例えば、最下位層を層１とする）。また、本発明に於いて、階層の数は２以上であればよく、本例の如く３層に限定されない。
【００２３】
送信装置１１は、端末１２等から入力した、ある地点に於ける祭りや博覧会開催等の状況情報を路網図管理装置２０に送信する。状況情報は、発生しているイベントの種類等（イベント属性６１）とその発生位置（注目位置１３）等である。受信手段２２は受信機等であり、送信装置１１から送信された状況情報を受信する。
【００２４】
分割手段２５は、注目位置１３が探索されやすいように、路記憶部２８の路網図（道路網図等）を更新する。
【００２５】
入力手段２３はタッチパネルやキーボード等であり、出発位置と目的位置を包含する経路探索要求を入力する。
【００２６】
探索手段２６は、入力手段２３から入力された出発位置から目的位置迄の移動経路を、路記憶部２８の路網図から検索する。但し、出発位置は、路網図管理装置２０等が備えたＧＰＳ装置（Global Positioning System）（図示されない）から取得しても良い。探索手段２６は探索した移動経路を表示手段２４に出力する。表示手段２４はディスプレイ装置等である。探索手段２６は、移動経路を地図上にオーバーラップ等させて表示しても良い。
【００２７】
利用者情報記憶部２７はディスク装置等の記憶装置である。利用者情報記憶部２７は路網図管理装置２０の利用者の情報を格納する。
【００２８】
分割手段２５及び探索手段２６は、その機能を果たす専用ハードウェアとして実装されても良いし、路網図管理プログラム２９がメモリに格納されてコンピュータ２１のプロセッサで実行されることにより、その機能を果たすように実装されても良い。
【００２９】
路記憶部２８は、階層化された路網図の各層を、頂点と頂点間の辺から構成される網として格納する。頂点は道路等の交差点をモデル化したものである。頂点は道路等の端点（行き止まり等）を表す場合もある。辺は道路等の交差点間等の区間をモデル化したものである。具体的に、路記憶部２８は階層化された路網図を、例えば、層表３０、網表４０および頂点表５０という形式で格納する。
【００３０】
図２は層表３０の構成図である。層表３０は路網図の各層対応にエントリを有する。例えば最上段（第１エントリ）が最上位層に対応し、その下の第２エントリが最上層の１段下の層に対応する。第３エントリ以降、各エントリは順に下位の層に対応する。各エントリは対応する層に属する網の識別子である網ＩＤ３２を格納する。網ＩＤ３２は、例えばＧｈｎという形式である。ここで、ｈは層の識別子（ｈ＝１以上）でありｎは層ｈ内の通し番号である。ｈｎは網番号である。
【００３１】
路網図の下位の層は、１段上位の層における辺の閉路で囲まれた領域ごとの分割網に分割されて格納されている。ここで、閉路はコード（chord）を含まない閉路である。分割手段２５や探索手段２６は、網の分割や経路探索に於いて、閉路に含まれる辺や当該辺の端点を介して、層間の遷移を行う。
【００３２】
なお、下位の層に属する網の数は、上位の層に属する網の数より大きい。最上位層に属する網の数は通常１である。路網図は、経路探索やアクセス効率化のために分割されている。
【００３３】
図５は頂点表５０の構成図である。頂点表５０は網ごとに分割されて存在する。頂点表５０は、網ＩＤ３２と当該網に属する頂点ごとのエントリから構成される。各エントリは、頂点ＩＤ５１と座標５２を包含する。頂点ＩＤ５１は頂点の識別子であり、例えばｖ（ｇ、ｎ）という形式である。ｇは当該頂点が属する網の網番号である。ｎは網Ｇｇ内の通し番号である。座標５２は当該頂点の位置を表す。位置は、例えば緯度と経度の対である。位置は他の座標系に基づく値であっても良い。
【００３４】
図３は網表４０の構成図である。網表４０は網ごとに分割されて存在する。網表４０は、網ＩＤ３２と当該網に属する辺ごとのエントリから構成される。各エントリは、辺ＩＤ４１、始点４２、終点４３、上位辺４４、曲形状４５、長さ４６、左網４７、右網４８等を包含する。
【００３５】
辺ＩＤ４１は、エントリに対応した辺（以下、対応辺）の識別子である。辺ＩＤ４１は、例えばｅ（ｇ、ｎ）という形式である。ここで、ｇは対応辺が属する網の網番号である。ｎは網Ｇｇ内の通し番号である。
【００３６】
始点４２と終点４３は、対応辺の両端の頂点の頂点ＩＤ５１を示す。上位辺４４は、対応辺がモデル化する道路等の区間をモデル化する１段上位層の辺の辺ＩＤ４１である。例えば、図１３における辺ｅ１乃至ｅ８のおのおのの上位辺４４は図１２に於ける辺Ｅである。このように層ｈの辺（Ｅ、等）は、下位の層ｈ＋１においていくつかの辺（ｅ１、等）に分割されて表現される。
【００３７】
辺は道路等の区間をモデル化する。従って、辺は曲線である場合がある。曲形状４５はこの曲線の形状を記述する。曲形状４５は、例えば図４に示すように、曲線を近似する折れ線を中間座標系列として記述したものでも良い。曲形状４５は、曲率を用いる等、他の形式の記述データであっても良い。
【００３８】
長さ４６は対応辺がモデル化する道路等の距離である。長さ４６は、曲形状４５を反映した値であることが好ましい。長さ４６は、道路等の制限速度や高速料金等も反映した移動コストを格納しても良い。
【００３９】
左網４７と右網４８は対応辺に関連付けられている１段下位層の網ＩＤ３２を格納する。上述したように、１段下位の層は、対応辺を含む２つの閉路で囲まれた領域ごとに分割されている。従って、１段下位の層には、対応辺（正確には、対応辺がモデル化する道路等の区間をモデル化する下位の層の辺群）を境界とする２つの網が存在する。左網４７と右網４８はこの２つの網の網ＩＤ３２を格納する。
【００４０】
辺の両端である始点４２と終点４３は区別されており辺は方向を持つ。従って、位置ｑが与えられたとき、分割手段２５等は、位置ｑが対応辺の左右どちら側に位置するかを判別して、ｑが属する下位層の網ＩＤ３２を取得できる。例えば、対応辺に関連付けられている折れ線がｒ＝（ｍ１，ｍ２，．．．，ｍｋ）であるとき、分割手段２５等は、線分（ｍｉ，ｍｉ＋１），ｉ＝１，２，．．．，ｋ−１のなかからｑと最も近い線分（ｍｘ，ｍｘ＋１）を決定して、２つのベクトル（ｍｘ，ｍｘ＋１）と（ｍｘ＋１，ｑ）の外積を求める。分割手段２５等は、例えば符号が正である場合は左網４７から、そうでない場合は右網４８から、下位層の網ＩＤ３２を取得する。分割手段２５等は、符号の正負と左右の対応付けを逆にしても良い。上記計算の詳細は、Ronald L. Graham: An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. (1972)等の文献に記載されている。
【００４１】
なお、左網４７と右網４８の一方または両方がＮｕｌｌである場合がある。対応辺が、海岸線の道路等をモデル化している場合、対応辺の海側、例えば左網４７はＮｕｌｌとなる。また、対応辺が最下層に属す場合等、左網４７と右網４８の両方がＮｕｌｌとなる。
【００４２】
なお、頂点表５０は、頂点ＩＤ５１対応に当該頂点に接続されている全ての辺の辺ＩＤ４１を格納していても良い。
【００４３】
図６−Ａと６−Ｂは路記憶部２８に格納されている路網図の例（網路例２）である。図６−Ｃは本路網図を記述する層表３０を例示する。図６−Ｄは本路網図を記述する網表４０を例示する。図６−Ｅは本路網図を記述する頂点表５０を例示する。
【００４４】
本例の路網図は、図６−Ａの上位層（層１）と図６−Ｂの下位層（層２）の２層から構成される。層１は１つの網Ｇ１１を包含する。網Ｇ１１は、辺ｅ（１１、１）、ｅ（１１、２）ｅ（１１、３）で構成される閉路で囲まれた領域Ａと、辺ｅ（１１、３）、ｅ（１１、４）、ｅ（１１、５）で構成される閉路で囲まれた領域Ｂを有する。従って、層２は、領域Ａに対応する網Ｇ２１と領域Ｂに対応する網Ｇ２２に分割されて記憶される。
【００４５】
上述の辺は例えば全て主要道路をモデル化したものである。層２は、主要道路をモデル化した辺ｅ（２１、１）乃至ｅ（２１、５）およびｅ（２２、１）乃至ｅ（２２、５）に加え、非主要道路をモデル化した辺ｅ（２１、６）とｅ（２２、６）を包含する。また、ｅ（２１、６）とｅ（２２、６）の始点４２と終点４３の頂点ｖ（２１、３）、ｖ（２１、５）、ｖ（２２、２）、ｖ（２２、４）も追加されている。即ち、層２の方が層１より詳細度が高い。
【００４６】
層１の辺ｅ（１１、３）の例えば左側は領域Ａである。従って、当該辺の左網４７には、層２における領域Ａの網の網ＩＤ３２であるＧ２１が格納されている。層１の辺ｅ（１１、３）の右側は領域Ｂである。従って、当該辺の右網４８には、層２における領域Ｂの網の網ＩＤ３２であるＧ２２が登録されている。同様に、層１の辺ｅ（１１、１）の左側は領域Ａである。従って、当該辺の左網４７には、層２における領域Ａの網の網ＩＤ３２であるＧ２１が登録されている。
【００４７】
なお、ｅ（１１、３）と、ｅ（２１、５）およびｅ（２１、４）は同じ道路等の区間をモデル化している。従って、ｅ（２１、５）およびｅ（２１、４）の上位辺４４はともに、ｅ（１１、３）となる（図６−Ｄ）。同様に、ｅ（１１、３）と、ｅ（２２、１）およびｅ（２２、２）は同じ道路等の区間をモデル化している。従って、ｅ（２２、１）およびｅ（２２、２）の上位辺４４はともに、ｅ（１１、３）となる（図６−Ｄ）。
【００４８】
また、ｅ（２１、６）およびｅ（２２、６）は層２のみでモデル化された非主要道路に対応するため、上位辺４４は格納されていない（Ｎｕｌｌ値である）。
【００４９】
図７は、利用者情報記憶部２７に格納されるデータの構成図である。利用者情報記憶部２７は、イベント属性６１と更新層６２を対にして記憶している。更新層６２は、イベント属性６１を持つイベントが発生したとき、当該イベントの発生位置に至る経路を路網図のどの層にまで追加するかを指定する。発生位置への経路が上位の層に追加されるほど、発生位置を通過する経路が探索されやすくなる。従って、利用者の興味が高いイベント属性６１に対応する更新層６２は上位の層を指定する。
【００５０】
図８は分割手段２５の動作フローチャートである。分割手段２５は、受信手段２２からイベント属性６１、注目位置１３（ｑ）と誤差を入力する（Ｓ１）。分割手段２５は、利用者情報記憶部２７から入力したイベント属性６１に対応する更新層６２を取得し（Ｓ２）、層表３０から最上位層の網ＩＤ３２を取得する（Ｓ３）。
【００５１】
取得した網ＩＤ３２の網（Ｇｈと略記）の網表４０と頂点表５０を路記憶部２８からメモリに読み込んだ後、分割手段２５はＧｈ内でｑの最近傍辺を探索して、その辺ＩＤ４１を取得する（Ｓ４）。分割手段２５は、各辺の始点４２及び終点４２の座標５２や、曲形状４５の折れ線等を参照して最近傍辺を決定する。このとき、分割手段２５は非特許文献１に記載されている技術を用いても良い。
【００５２】
例えばｑが図６−Ａの×印の位置であるとき、分割手段２５は最近傍辺の辺ＩＤ４１としてｅ（１１、３）を取得する。
【００５３】
次に、分割手段２５はｑが最近傍辺上に位置しているかを判別する（Ｓ５）。このとき、分割手段２５は、ｑと最近傍辺の距離が入力した誤差範囲内であれば最近傍辺上に位置していると判断する。距離は平面上の距離であり、移動経路の長さ４６ではない。誤差はｑ等の位置測定装置の測定誤差を示す値である。
【００５４】
ｑが最近傍辺上に位置していない場合（Ｓ５でＮ）、分割手段２５はＧｈの網ＩＤ３２をスタックにプッシュダウンする（Ｓ６）。同手段は、ｑが最近傍辺の左右の何れに位置するかを判断し、ｑが左側に位置すれば左網４７から、ｑが右側に位置すれば右網４８から、１段下位のｈ＋１層の網ＩＤ３２（この網ＩＤ３２の網が新たなＧｈとなる）を取得する（Ｓ７）。
【００５５】
ｑが図６−Ａの×印の位置であるとき、分割手段２５は最近傍辺ｅ（１１、３）の左網４７（図６−Ｄ）から網ＩＤ３２としてＧ２１を取得する。
【００５６】
その後、分割手段２５は、取得したｈ＋１層の網ＩＤ３２がＮｕｌｌでなければ（ＳＧでＮ）Ｓ４のステップに戻る。通常、Ｓ７で取得したｈ＋１層の網ＩＤ３２がＮｕｌｌとなることはない。しかし、ｑの入力値に予想外の誤差が含まれていた場合等で、ｑが最近傍辺上に位置しているにもかかわらず分割手段２５が位置していないと判断（Ｓ５でＮ）をし、かつ、最近傍辺の一方または両方にｈ＋１層の網が無いと、例外的にＮｕｌｌとなり得る。
【００５７】
ｑが最近傍辺上に位置している場合（Ｓ５でＹ）、分割手段２５はＧｈが最上位の層でないことを、例えば層表３０を参照して確認する（Ｓ８でＮ）。Ｇｈが最上位の層であれば（Ｓ８でＹ）、分割手段２５は処理を終了する。ｑが最上位層の辺上に位置するのであれば、経路追加は必要ないからである。
【００５８】
なお、Ｓ７で取得したｈ＋１層の網ＩＤ３２がＮｕｌｌである場合（ＳＧでＹ）、分割手段２５は、スタックの最上段をポップアップして（ＳＨ）、Ｓ８の処理を行う。
【００５９】
ｑが最上位層でない最近傍辺上に位置している場合（Ｓ５でＹ、Ｓ８でＮ）、分割手段２５は、ｑから１段上位の層（ｈ−１層）に通じる各辺の頂点への経路（但し、上位層に通じる辺上の経路は除く）（分割経路）を求める（Ｓ９）。ｈ−１層に通じる辺とは、Ｇｈの境界を構成する辺であり、網表４０において上位辺４４に値が設定されている辺である。
【００６０】
例えばｑが図６−Ｂの×印の位置であるとき、ｑはＧ２１において最近傍辺ｅ（２１、６）上に位置している（Ｓ５でＹ）。従って、分割経路は、ｑとｖ（２１、５）間およびｑとｖ（２１、５）間となる。
【００６１】
分割手段２５は、Ｇｈを分割経路上の辺を境界とする部分網に分割し、分割して出来た網の網表４０および頂点表５０を新たに生成する（ＳＡ）。分割手段２５は、作成された網の網ＩＤ３２を層表３０に追加する。
【００６２】
分割手段２５は、例えば図６−ＢのＧ２１をｅ（２１、６）を境界として分割し、図９−Ｂに図示する新たな網Ｇ２３およびＧ２４を生成する。分割手段２５は、元のＧ２１の網表４０および頂点表５０（図６−Ｄ、図６−Ｅ）を基に、Ｇ２３およびＧ２４の網表４０および頂点表５０（図９−Ｄ、図９−Ｅ）を生成する。
【００６３】
分割手段２５は、Ｇｈにおける分割経路上の辺をｈ−１層に追加する（ＳＢ）。分割手段２５は、追加対象となる網の網ＩＤ３２をスタックの最上段から取得する。また、同手段は追加した辺が上位辺４４を有する辺と交わっていれば、当該上位辺４４を追加された頂点で分割する。
【００６４】
例えば分割手段２５は、図９−ＡのＧ１１に辺ｅ（１１、６）を追加して、元の辺ｅ（１１、３）を頂点ｖ（１１、６）で分割する。分割手段２５は、元の辺ｅ（１１、２）を頂点ｖ（１１、５）で分割する。
【００６５】
分割手段２５は、ｈ−１層の辺の左網４７と右網４８に、分割した網の網ＩＤ３２を格納する（ＳＣ）。具体的に、分割手段２５は、先ず追加した辺の左網４７と右網４８に分割した網の網ＩＤ３２を格納する。さらに同手段は、ｈ−１層において分割したＧｈの網ＩＤ３２を左網４７または右網４８に有する辺またはその分割辺の左網４７と右網４８に、分割した網の網ＩＤ３２を格納する。
【００６６】
例えば、図９−Ｄにおいて、追加された辺ｅ（１１、６）の左網４７にはＧ２３が、右網４８にはＧ２４が格納される。また、図６−Ｄにおいて、分割前のＧ２１を左網４７に持つｅ（１１、１）の左網４７には分割後のＧ２３が格納される。
【００６７】
ついで、分割手段２５は分割前の網Ｇｈの網表４０および頂点表５０を削除する（ＳＤ）。分割手段２５は、削除された網の網ＩＤ３２を層表３０から削除する。
【００６８】
例えば、分割手段２５は、図６−Ｄにおける網Ｇ２１の網表４０を削除する。
【００６９】
ｈ−１層が更新層６２でなければ（ＳＥでＮ）、分割手段２５はスタックの最上段から網ＩＤ３２を取得した後、スタックをポップアップして（ＳＦ）Ｓ９に戻る。ｈ−１層が更新層６２であれば（ＳＥでＹ）、分割手段２５は処理を終了する。
【００７０】
以上の説明から明らかなように、図９−Ｃは路網例２の経路追加・分割後の層表３０の例である。図９−Ｄは路網例２の経路追加・分割後の網表４０の例である。図９−Ｅは路網例２の経路追加・分割後の頂点表５０の例である。
【００７１】
図１５乃至図２０は、図１２乃至図１３に示す階層化された道路網の分割を説明する図である。図１５乃至図２０は、注目位置１３（ｑ）が与えられたとき、分割手段２５が地図の更新を行う際の手順の流れを例示する。この例は、ｑを通過する経路を最上位の層に追加するものである。即ち、更新層６２が最上位層である場合の例である。
【００７２】
図１５は、図１２と同様に最上位（層１）の道路網の一部を抜粋した図である。図１５はｑの最近傍辺がeであることを示している。また、受信手段２２で取得した位置情報は、高々εの誤差を含むとする。ここで、ｑと辺ｅの間の距離がある許容値ε以下であることと、qを中心として半径εの円とｅの曲形状４５で与えられる折れ線が交差することは等価である。図１５の破線で描かれているｑを中心として半径εの円とｅの折れ線は交差していないので、ｑは辺ｅ上に位置しない。従って、分割手段２５は、下層の道路網を取得する。具体的に分割手段２５は、ｅのｑ側（左網４７または右網４８）に関連付けられている下位の道路網を取得する。
【００７３】
図１６は、辺ｅに関連付けられて取得された側の下位の層の道路網の抜粋を示している。分割手段２５は、新たに道路網の一部を取得したら、その道路網に対して最近傍辺を求めるために曲形状４５等のデータ構造（R-tree）を読み込み、ｑの最近傍辺を求める。図１６では、辺ｅ'が層２におけるｑの最近傍辺であることを示している。階層１の場合と同様に、図１６の破線で描かれているｑを中心として半径εの円とｅ'の折れ線は交差しないので、ｑは辺ｅ'上に位置しない。従って、分割手段２５は、図１７に示すｅ'のｑ側に関連付けられている下層（層３）の道路網Ｇを取得する。
【００７４】
このとき、Ｇにおけるｑの最近傍辺はｑから十分近いので、分割手段２５はそれ以上層を下る手続きを終了する（図８のＳ５でＹ）。分割手段２５は、次にこの道路網Ｇに対して、Ｇの上位の層２に存在するＧを囲む辺への最短経路を求める。
【００７５】
図１８はこの手続きの結果を示す。辺ｅ１'は、ｑから辺ｅ１への最短経路の両端点をつなぐ辺である。分割手段２５は、Ｇを囲むすべての辺に関してｑからの最短経路を求めるが、図が煩雑になるため図１８には示していない。
【００７６】
分割手段２５は、いま求めたｑからＧを囲む辺への最短経路ｅ１'、ｅ２'、ｅ３'等により、Ｇをさらに細かく分割する。分割手段２５は、Ｇの上位層２のグラフＧ'（図１６）に各辺ｅ１'、ｅ２'、ｅ３'等を追加するようにＧ'に対する網表４０を更新する。例えば、分割手段２５は、曲形状４５のR-trｅｅに対して、ｅ１', ｅ２', ｅ３'…の各折れ線を追加する。
【００７７】
そして、分割手段２５は、Ｇ'のそれぞれの辺と分割された道路網の関連付けを行う。例えば、図１９は、Ｇを分割した結果、ｅ１', ｅ２' および上位の階層２に存在する辺ｅｉ乃至ｅｉ＋５によって囲まれる道路網ｇ１が新たに得られていることを示している。このとき、分割前はｅi の右網４８としてＧが関連付けられていたが、分割後の関連付けの更新として、ｅi の右網４８はｇ１となる。
【００７８】
最終的に、分割手段２５は、Ｇ'においてＧ'を囲む最上位のグラフＧ''の各辺への最短経路を求め、その経路をＧ''へ追加する（図２０）ように網表４０および頂点表５０の更新を行う。
【００７９】
図１０は、探索手段２６の動作フローチャートである。探索手段２６は、受信手段２２から出発位置（ｓ）、目的位置（ｔ）と誤差を入力する（Ｓ１１）。探索手段２６は、出発位置を路網図管理装置２０等が備えるＧＰＳ装置から取得しても良い。探索手段２６は、層表３０から最上位層の網ＩＤ３２を取得する（Ｓ１２）。
【００８０】
取得した網ＩＤ３２の網（Ｇｈと略記）の網表４０と頂点表５０をメモリに読み込んだ後、探索手段２６はＧｈ内でｓの最近傍辺（最近傍辺ｓ）とｔの最近傍辺(最近傍辺ｔ）とを探索して、おのおのの辺ＩＤ４１を取得する（Ｓ１３）。次に、探索手段２６はｓが最近傍辺ｓ上に位置している、または、ｔが最近傍辺ｔ上に位置しているかを判別する（Ｓ１４）。このとき、探索手段２６は、ｓまたはｔと各々の最近傍辺の距離が入力した誤差範囲内であれば最近傍辺上に位置していると判断する。
【００８１】
ｓとｔの何れもが最近傍辺上に位置していない場合（Ｓ５でＮ）、探索手段２６は、ｓが最近傍辺の左右の何れに位置するかを判断する。そして同手段は、ｓが左側に位置すれば左網４７から、ｓが右側に位置すれば右網４８から、１段下位のｈ＋１層の網ＩＤ３２（当該網を網Ｇｈ＋１ｓと略記）を取得する（Ｓ１５）。探索手段２６は、ｔが最近傍辺の左右の何れに位置するかを判断し、ｔが左側に位置すれば左網４７から、ｔが右側に位置すれば右網４８から、１段下位のｈ＋１層の網ＩＤ３２（当該網を網Ｇｈ＋１ｔと略記）を取得する（Ｓ１６）。Ｇｈ＋１ｓおよびＧｈ＋１ｔの網ＩＤ３２が一致すれば（Ｓ１７でＹ）、探索手段２６はＳ１３に戻る。
【００８２】
Ｇｈ＋１ｓおよびＧｈ＋１ｔの網ＩＤ３２が一致すれば（Ｓ１７でＹ）、探索手段２６はＧｈ内で、Ｇｈ＋１ｓとＧｈ＋１ｔ間の経路（経路２）を探索して取得する（Ｓ１８）。ここで、Ｇｈ＋１ｓとＧｈ＋１ｔ間の経路とは、Ｇｈ＋１ｓを囲む辺上の各頂点からＧｈ＋１ｔを囲む辺上の各頂点への経路の内で距離が最短の経路を指す。Ｇｈ＋１ｓを囲む辺とは、左網４７または右網４８にＧｈ＋１ｓの網ＩＤ３２が格納されている辺である。また、経路の距離は当該経路に属する辺の長さ４６の合計値である。なお、探索手段２６は、経路の探索の為に、Dijkstraのアルゴリズム等の一般的な検索アルゴリズムを用いることができる。
【００８３】
図９−ＡにおいてＧ２４がＧｈ＋１ｓである場合、Ｇｈ＋１ｓを囲む辺上の各頂点は、ｖ（１１、３）、ｖ（１１、５）、ｖ（１１、６）となる。
【００８４】
次に、探索手段２６はｓと経路２のｓ側の端点（Ｇｈ＋１ｓの周辺上の頂点となる。ｓｈ＋１と略記）の間の経路（経路１）をｈ＋１以下の層から再帰的探索により取得する（Ｓ１９）。図１１は再帰的探索の詳細を示す。更に、探索手段２６は経路２のｔ側の端点（Ｇｈ＋１ｔの周辺上の頂点となる。ｔｈ＋１と略記）とｔの間の経路（経路３）をｈ＋１以下の層から再帰的探索により取得する（Ｓ１Ａ）。
【００８５】
探索手段２６は、経路１、経路２、経路３をつなげてｓからｔへの移動経路を取得する（Ｓ１Ｂ）。最後に、探索手段２６は、ｓからｔ移動経路を表示手段２４に表示する（Ｓ１Ｉ）。
【００８６】
探索手段２６はｓが最近傍辺ｓ上に位置している、かつ、ｔが最近傍辺ｔ上に位置している場合（Ｓ１４でＹ、Ｓ１ＣでＹ）、Ｇｈ内でｓからｔへの移動経路検索を行う（Ｓ１Ｄ）。
【００８７】
ｓまたはｔの一方（例えばｓ）が最近傍辺上に位置しているが、他方（例えばｔ）が最近傍辺上に位置していない場合（Ｓ１４でＹ、Ｓ１ＣでＮ）、探索手段２６は以下の処理を行う。
【００８８】
探索手段２６は、ｔが最近傍辺の左右の何れに位置するかを判断し、ｔが左側に位置すれば左網４７から、ｔが右側に位置すれば右網４８から、１段下位のｈ＋１層の網ＩＤ３２（当該網を網Ｇｈ＋１ｔと略記）を取得する（Ｓ１Ｅ）。
【００８９】
その後、探索手段２６は、Ｇｈ内で、ｓとＧｈ＋１ｔ間の経路（経路４）を探索して取得する（Ｓ１Ｆ）。ここで、ｓとＧｈ＋１ｔ間の経路とは、ｓからＧｈ＋１ｔを囲む辺上の各頂点への経路の内で距離が最短の経路を指す。Ｇｈ＋１ｔを囲む辺とは、左網４７または右網４８にＧｈ＋１ｔの網ＩＤ３２が格納されている辺である。
【００９０】
探索手段２６は経路４のｔ側の端点（Ｇｈ＋１ｔの周辺上の頂点となる。ｔｈ＋１と略記）とｔの間の経路（経路５）をｈ＋１以下の層から再帰的探索により取得し（Ｓ１Ｇ）、最後に経路４と５を連結してｓからｔへの移動経路を取得する（Ｓ１Ｈ）。
【００９１】
ｔが最近傍辺上に位置しているがｓが最近傍辺上に位置していない場合、探索手段２６は、ｓとｔの立場を逆転して同様の処理を行う。
【００９２】
図１１は、探索手段２６の再帰的探査の動作フローチャートである。図１１は、ｔｈ＋１とｔの間の第５の経路をｈ＋１以下の層から検索する場合（Ｓ１Ｇ等の詳細）を例示する。
【００９３】
探索手段２６は、Ｇｈ＋１ｔの網ＩＤ３２とｔｈ＋１をスタックの最上段にプッシュダウンする（Ｓ２１）。探索手段２６はｔが最近傍辺の左右の何れに位置するかを判断し、ｔが左側に位置すれば左網４７から、右側に位置すれば右網４８から、１段下位のｈ＋２層の網ＩＤ３２（当該網を網Ｇｈ＋２ｔと略記）を取得する（Ｓ２２）。
【００９４】
探索手段２６は、Ｇｈ＋１内で、ｔｈ＋１とＧｈ＋２ｔ間の経路を探索して取得する（Ｓ２３）。なお、当該経路の端点となるＧｈ＋２ｔの周辺上の頂点は、ｔｈ＋２として参照される。
探索手段２６は、検索した経路をＳ２２でプッシュダウンしたスタックの最上段に追記する（Ｓ２４）。
【００９５】
Ｇｈ＋２ｔの網表４０と頂点表５０をメモリに読み込んだ後、探索手段２６はＧｈ＋２ｔ内でｔの最近傍辺を取得する（Ｓ２５）。探索手段２６は、ｔが最近傍辺上に位置しているかを判別する（Ｓ２６）。このとき、探索手段２６は、ｔと最近傍辺の距離が入力した誤差範囲内であれば最近傍辺上に位置していると判断する。
【００９６】
ｔが最近傍辺上に位置しなければ（Ｓ２６でＮ）、探索手段２６はＳ２１に戻る。このときＧｈ＋２ｔは新たなＧｈ＋１となり、ｔｈ＋２は新たなｔｈ＋１となる。
【００９７】
ｔが最近傍辺上に位置すれば（Ｓ２６でＹ）、探索手段２６はＧｈ＋２内でｔｈ＋２とｔの間の経路６を求める（Ｓ２７）。
【００９８】
最後に探索手段２６は、スタックを一段ずつポップアップしながら、スタックに記憶していた経路を順次ｔから遠ざかる方向に経路６と連結して経路５を取得して（Ｓ２８）、処理を終了する。
【００９９】
本実施形態の路網図管理システム１０は、ある場所の状況に応じて、当該場所を経由する経路を検索されやすくする。その理由は、分割手段２５が、注目位置１３を経由する経路を上位の層に追加するからである。
【０１００】
さらに、本実施形態の路網図管理システム１０は、経路検索および経路追加を効率的に行うことが出来る。その理由は、路網図を部分網に分割して路記憶部２８に記憶しており、経路検索および経路追加において、必要な部分しかメモリに読み込まず、また、当該部分内でのみ経路探索を行うからである。
【０１０１】
さらに、本実施形態の路網図管理システム１０は、利用者の嗜好に基づいた経路追加を行うことが出来る。その理由は、利用者情報記憶部２７に基づいて、経路追加をする層を決定するからである。
【０１０２】
本発明の第２の実施形態の路網図管理装置２０の分割手段２５は、ｑから１段上位の層（ｈ−１層）に通じる所定数（２、等）の辺の頂点だけへの経路を求める（図８のＳ９）。辺の選択は、各辺対応に網表４０に登録されている優先度等に基づいて行う。
【０１０３】
本実施形態の路網図管理装置２０は経路追加を高速に実施できる。その理由は、分割経路の探索数が限定されるからである。
【０１０４】
また、路網図管理装置２０は、経路追加を常に所定層（例えば最上層）以下の層に行うこととしてもよい。この場合、路網図管理装置２０は利用者情報記憶部２７、受信手段２２を備えなくても良い。
【０１０５】
さらに、路網図管理装置２０は、入力探索手段２６、表示手段２４、探索手段２６を備え無くても良い。入力探索手段２６、表示手段２４、探索手段２６は、路記憶部２８を共有する探索装置（図示されない）が備えても良い。
【０１０６】
図２１は、本発明にかかる路網図管理装置２０の基本的構成を示す。路網図管理装置２０は、路記憶部２８と分割手段２５を備える。
【符号の説明】
【０１０７】
１０ 路網図管理システム
１１ 送信装置
１２ 端末
１３ 注目位置
２０ 路網図管理装置
２１ コンピュータ
２２ 受信手段
２３ 入力手段
２４ 表示手段
２５ 分割手段
２６ 探索手段
２７ 利用者情報記憶部
２８ 路記憶部
２９ 路網図管理プログラム
３０ 層表
３２ 網ＩＤ
４０ 網表
４１ 辺ＩＤ
４２ 始点
４３ 終点
４４ 上位辺
４５ 曲形状
４６ 長さ
４７ 左網
４８ 右網
５０ 頂点表
５１ 頂点ＩＤ
５２ 座標
６１ イベント属性
６２ 更新層
【特許請求の範囲】
【請求項１】
路網の詳細度に基づいて複数の層（２つの層間において詳細度が低い層を上位層、高い層を下位層と呼ぶ）に階層化され、各層において一段上位層の路の閉路で囲まれている領域ごとに分割網に分割されている路網図が、当該閉路を構成する上位層の各路の両側に当該路を境界とする２つの分割網を関連付けて格納された路記憶部と、
最上位層から下位に向けて順次前記路網図の各層をアクセスして、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている前記注目位置側の前記分割網（Ｇｄ）を、当該Ｇｄに前記注目位置を含む前記路が存在するようになるまで一段下位層から取得して、
最後に取得した前記Ｇｄが属する層から上位に向けて更新層の一段下位層まで順次各層をアクセスして、各層に於いて、当該Ｇｄの前記境界を構成する前記路の少なくとも２つと前記注目位置間の経路（分割経路）を前記Ｇｄ内で探索して、前記Ｇｄを前記分割経路で複数の分割網（ｇｄ）に分割して、前記Ｇｄを前記路記憶部から削除して、各前記ｇｄを前記路記憶部に記憶し、前記分割経路を１段上位の層に追加する分割手段を備える路網図管理装置。
【請求項２】
当該Ｇｄの前記境界を構成する前記路のおのおのと前記注目位置間の経路（分割経路）を前記Ｇｄ内で探索する前記分割手段を備える請求項１の路網図管理装置。
【請求項３】
最上位層から順次下位に向けて各層をアクセスして、各層に於いて、指定された出発位置の最近傍の路を特定して当該路に関連付けられている前記出発位置側の前記分割網（Ｇｓ）および指定された目的位置の最近傍の路を特定して当該路に関連付けられている前記目的位置側の前記分割網（Ｇｔ）を、一段下位層から取得して、当該両分割網に基づいて、前記出発点と前記到達点間の移動経路を探索して出力する探索手段を備える請求項１または２の路網図管理装置。
【請求項４】
前記Ｇｓと前記Ｇｔが同一（Ｇ）であって、当該Ｇ内に前記出発位置または前記目的位置の一方の位置を含む路が存在するが他方の位置を含む路が存在しない場合に、当該層に於いて、前記他方の位置の最近傍の路を特定して当該路に関連付けられている前記他方位置側の前記分割網（Ｇｔ）を下位層から取得し、前記一方の位置と前記Ｇｔ間の経路（第４の経路）を前記Ｇ内で探索し、その後、前記Ｇｔと当該第４の経路の交点と前記他方位置の経路（第５の経路）を当該下位層以下の層から探索し、前記第４の経路、および、前記第５の経路を直列に結合した移動経路を出力する前記探索手段を備える請求項３の路網図管理装置。
【請求項５】
同一層に於いて前記Ｇｓと前記Ｇｔが異なる場合に、前記Ｇｓと前記Ｇｔ間の経路（第１の経路）を当該層の１段上位の層内で探索し、その後、前記Ｇｓと当該第１の経路の交点と前記出発位置間の経路（第２の経路）と前記Ｇｔと当該第１の経路の交点と前記目的位置間の経路（第３の経路）を当該層以下の層から探索し、前記第２の経路、前記第１の経路、および、前記第３の経路を直列に結合した移動経路を出力する前記探索手段を備える請求項３または４の路網図管理装置。
【請求項６】
イベント属性に対応付けられた前記更新層の指定を格納する利用者情報記憶部と、
前記注目位置、前記イベント属性を受信する受信手段と、
前記出発位置と前記目的位置を入力する入力手段と、
前記移動経路を表示する表示手段と、
前記利用者情報記憶部から、受信された当該イベント属性に対応する前記更新層の指定を取得する前記分割手段を備える請求項３乃至５の何れかの路網図管理装置。
【請求項７】
前記注目位置、前記イベント属性を送信するする送信装置と、
請求項６の路網図管理装置を包含する路網図管理システム。
【請求項８】
路網の詳細度に基づいて複数の層（２つの層間において詳細度が低い層を上位層、高い層を下位層と呼ぶ）に階層化され、各層において一段上位層の路の閉路で囲まれている領域ごとに分割網に分割されている路網図が、当該閉路を構成する上位層の各路の両側に当該路を境界とする２つの分割網を関連付けて格納された路記憶部を備えたコンピュータに、
最上位層から下位に向けて順次前記路網図の各層をアクセスして、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている前記注目位置側の前記分割網（Ｇｄ）を、当該Ｇｄに前記注目位置を含む前記路が存在するようになるまで一段下位層から取得して、
最後に取得した前記Ｇｄが属する層から上位に向けて更新層の一段下位層まで順次各層をアクセスして、各層に於いて、当該Ｇｄの前記境界を構成する前記路の少なくとも２つと前記注目位置間の経路（分割経路）を前記Ｇｄ内で探索して、前記Ｇｄを前記分割経路で複数の分割網（ｇｄ）に分割して、前記Ｇｄを前記路記憶部から削除して、各前記ｇｄを前記路記憶部に記憶し、前記分割経路を１段上位の層に追加する分割処理を実行させる路網図管理プログラム。
【請求項９】
前記コンピュータに、
当該Ｇｄの前記境界を構成する前記路のおのおのと前記注目位置間の経路（分割経路）を前記Ｇｄ内で探索する前記分割処理を実行させる請求項８の路網図管理プログラム。
【請求項１０】
前記コンピュータに、
最上位層から順次下位に向けて各層をアクセスして、各層に於いて、指定された出発位置の最近傍の路を特定して当該路に関連付けられている前記出発位置側の前記分割網（Ｇｓ）および指定された目的位置の最近傍の路を特定して当該路に関連付けられている前記目的位置側の前記分割網（Ｇｔ）を、一段下位層から取得して、当該両分割網に基づいて、前記出発点と前記到達点間の移動経路を探索して出力する探索処理を実行させる請求項８または９の路網図管理プログラム。
【請求項１１】
前記コンピュータに、
前記Ｇｓと前記Ｇｔが同一（Ｇ）であって、当該Ｇ内に前記出発位置または前記目的位置の一方の位置を含む路が存在するが他方の位置を含む路が存在しない場合に、当該層に於いて、前記他方の位置の最近傍の路を特定して当該路に関連付けられている前記他方位置側の前記分割網（Ｇｔ）を下位層から取得し、前記一方の位置と前記Ｇｔ間の経路（第４の経路）を前記Ｇ内で探索し、その後、前記Ｇｔと当該第４の経路の交点と前記他方位置の経路（第５の経路）を当該下位層以下の層から探索し、前記第４の経路、および、前記第５の経路を直列に結合した移動経路を出力する前記探索処理を実行させる請求項１０の路網図管理プログラム。
【請求項１２】
前記コンピュータに、
同一層に於いて前記Ｇｓと前記Ｇｔが異なる場合に、前記Ｇｓと前記Ｇｔ間の経路（第１の経路）を当該層の１段上位の層内で探索し、その後、前記Ｇｓと当該第１の経路の交点と前記出発位置間の経路（第２の経路）と前記Ｇｔと当該第１の経路の交点と前記目的位置間の経路（第３の経路）を当該層以下の層から探索し、前記第２の経路、前記第１の経路、および、前記第３の経路を直列に結合した移動経路を出力する前記探索処理を実行させる、請求項１０または１１の路網図管理プログラム。
【請求項１３】
イベント属性に対応付けられた前記更新層の指定を格納する利用者情報記憶部を備えた前記コンピュータに、
前記注目位置、前記イベント属性を受信する受信処理と、
前記出発位置と前記目的位置を入力する入力処理と、
前記移動経路を表示する表示処理と、
前記利用者情報記憶部から、受信された当該イベント属性に対応する前記更新層の指定を取得する前記分割処理を実行させる請求項１０乃至１２の何れかの路網図管理プログラム。
【請求項１４】
路網の詳細度に基づいて複数の層（２つの層間において詳細度が低い層を上位層、高い層を下位層と呼ぶ）に階層化され、各層において一段上位層の路の閉路で囲まれている領域ごとに分割網に分割されている路網図が、当該閉路を構成する上位層の各路の両側に当該路を境界とする２つの分割網を関連付けて格納された路記憶部を備えたコンピュータが、
最上位層から下位に向けて順次前記路網図の各層をアクセスして、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている前記注目位置側の前記分割網（Ｇｄ）を、当該Ｇｄに前記注目位置を含む前記路が存在するようになるまで一段下位層から取得して、
最後に取得した前記Ｇｄが属する層から上位に向けて更新層の一段下位層まで順次各層をアクセスして、各層に於いて、当該Ｇｄの前記境界を構成する前記路の少なくとも２つと前記注目位置間の経路（分割経路）を前記Ｇｄ内で探索して、前記Ｇｄを前記分割経路で複数の分割網（ｇｄ）に分割して、前記Ｇｄを前記路記憶部から削除して、各前記ｇｄを前記路記憶部に記憶し、前記分割経路を１段上位の層に追加する分割工程を有する路網図管理方法。
【請求項１５】
前記コンピュータが、
当該Ｇｄの前記境界を構成する前記路のおのおのと前記注目位置間の経路（分割経路）を前記Ｇｄ内で探索する前記分割工程を有する請求項１４の路網図管理方法。
【請求項１６】
前記コンピュータが、
最上位層から順次下位に向けて各層をアクセスして、各層に於いて、指定された出発位置の最近傍の路を特定して当該路に関連付けられている前記出発位置側の前記分割網（Ｇｓ）および指定された目的位置の最近傍の路を特定して当該路に関連付けられている前記目的位置側の前記分割網（Ｇｔ）を、一段下位層から取得して、当該両分割網に基づいて、前記出発点と前記到達点間の移動経路を探索して出力する探索工程を有する請求項１４または１５の路網図管理方法。
【請求項１７】
前記コンピュータが、
前記Ｇｓと前記Ｇｔが同一（Ｇ）であって、当該Ｇ内に前記出発位置または前記目的位置の一方の位置を含む路が存在するが他方の位置を含む路が存在しない場合に、当該層に於いて、前記他方の位置の最近傍の路を特定して当該路に関連付けられている前記他方位置側の前記分割網（Ｇｔ）を下位層から取得し、前記一方の位置と前記Ｇｔ間の経路（第４の経路）を前記Ｇ内で探索し、その後、前記Ｇｔと当該第４の経路の交点と前記他方位置の経路（第５の経路）を当該下位層以下の層から探索し、前記第４の経路、および、前記第５の経路を直列に結合した移動経路を出力する前記探索工程を有する請求項１６の路網図管理方法。
【請求項１８】
前記コンピュータが、
同一層に於いて前記Ｇｓと前記Ｇｔが異なる場合に、前記Ｇｓと前記Ｇｔ間の経路（第１の経路）を当該層の１段上位の層内で探索し、その後、前記Ｇｓと当該第１の経路の交点と前記出発位置間の経路（第２の経路）と前記Ｇｔと当該第１の経路の交点と前記目的位置間の経路（第３の経路）を当該層以下の層から探索し、前記第２の経路、前記第１の経路、および、前記第３の経路を直列に結合した移動経路を出力する前記探索工程を有する、請求項１６または１７の路網図管理方法。
【請求項１９】
イベント属性に対応付けられた前記更新層の指定を格納する利用者情報記憶部を備えた前記コンピュータが、
前記注目位置、前記イベント属性を受信する受信工程と、
前記出発位置と前記目的位置を入力する入力工程と、
前記移動経路を表示する表示工程と、
前記利用者情報記憶部から、受信された当該イベント属性に対応する前記更新層の指定を取得する前記分割工程を有する請求項１６乃至１８の何れかの路網図管理方法。
【請求項１】
路網の詳細度に基づいて複数の層（２つの層間において詳細度が低い層を上位層、高い層を下位層と呼ぶ）に階層化され、各層において一段上位層の路の閉路で囲まれている領域ごとに分割網に分割されている路網図が、当該閉路を構成する上位層の各路の両側に当該路を境界とする２つの分割網を関連付けて格納された路記憶部と、
最上位層から下位に向けて順次前記路網図の各層をアクセスして、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている前記注目位置側の前記分割網（Ｇｄ）を、当該Ｇｄに前記注目位置を含む前記路が存在するようになるまで一段下位層から取得して、
最後に取得した前記Ｇｄが属する層から上位に向けて更新層の一段下位層まで順次各層をアクセスして、各層に於いて、当該Ｇｄの前記境界を構成する前記路の少なくとも２つと前記注目位置間の経路（分割経路）を前記Ｇｄ内で探索して、前記Ｇｄを前記分割経路で複数の分割網（ｇｄ）に分割して、前記Ｇｄを前記路記憶部から削除して、各前記ｇｄを前記路記憶部に記憶し、前記分割経路を１段上位の層に追加する分割手段を備える路網図管理装置。
【請求項２】
当該Ｇｄの前記境界を構成する前記路のおのおのと前記注目位置間の経路（分割経路）を前記Ｇｄ内で探索する前記分割手段を備える請求項１の路網図管理装置。
【請求項３】
最上位層から順次下位に向けて各層をアクセスして、各層に於いて、指定された出発位置の最近傍の路を特定して当該路に関連付けられている前記出発位置側の前記分割網（Ｇｓ）および指定された目的位置の最近傍の路を特定して当該路に関連付けられている前記目的位置側の前記分割網（Ｇｔ）を、一段下位層から取得して、当該両分割網に基づいて、前記出発点と前記到達点間の移動経路を探索して出力する探索手段を備える請求項１または２の路網図管理装置。
【請求項４】
前記Ｇｓと前記Ｇｔが同一（Ｇ）であって、当該Ｇ内に前記出発位置または前記目的位置の一方の位置を含む路が存在するが他方の位置を含む路が存在しない場合に、当該層に於いて、前記他方の位置の最近傍の路を特定して当該路に関連付けられている前記他方位置側の前記分割網（Ｇｔ）を下位層から取得し、前記一方の位置と前記Ｇｔ間の経路（第４の経路）を前記Ｇ内で探索し、その後、前記Ｇｔと当該第４の経路の交点と前記他方位置の経路（第５の経路）を当該下位層以下の層から探索し、前記第４の経路、および、前記第５の経路を直列に結合した移動経路を出力する前記探索手段を備える請求項３の路網図管理装置。
【請求項５】
同一層に於いて前記Ｇｓと前記Ｇｔが異なる場合に、前記Ｇｓと前記Ｇｔ間の経路（第１の経路）を当該層の１段上位の層内で探索し、その後、前記Ｇｓと当該第１の経路の交点と前記出発位置間の経路（第２の経路）と前記Ｇｔと当該第１の経路の交点と前記目的位置間の経路（第３の経路）を当該層以下の層から探索し、前記第２の経路、前記第１の経路、および、前記第３の経路を直列に結合した移動経路を出力する前記探索手段を備える請求項３または４の路網図管理装置。
【請求項６】
イベント属性に対応付けられた前記更新層の指定を格納する利用者情報記憶部と、
前記注目位置、前記イベント属性を受信する受信手段と、
前記出発位置と前記目的位置を入力する入力手段と、
前記移動経路を表示する表示手段と、
前記利用者情報記憶部から、受信された当該イベント属性に対応する前記更新層の指定を取得する前記分割手段を備える請求項３乃至５の何れかの路網図管理装置。
【請求項７】
前記注目位置、前記イベント属性を送信するする送信装置と、
請求項６の路網図管理装置を包含する路網図管理システム。
【請求項８】
路網の詳細度に基づいて複数の層（２つの層間において詳細度が低い層を上位層、高い層を下位層と呼ぶ）に階層化され、各層において一段上位層の路の閉路で囲まれている領域ごとに分割網に分割されている路網図が、当該閉路を構成する上位層の各路の両側に当該路を境界とする２つの分割網を関連付けて格納された路記憶部を備えたコンピュータに、
最上位層から下位に向けて順次前記路網図の各層をアクセスして、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている前記注目位置側の前記分割網（Ｇｄ）を、当該Ｇｄに前記注目位置を含む前記路が存在するようになるまで一段下位層から取得して、
最後に取得した前記Ｇｄが属する層から上位に向けて更新層の一段下位層まで順次各層をアクセスして、各層に於いて、当該Ｇｄの前記境界を構成する前記路の少なくとも２つと前記注目位置間の経路（分割経路）を前記Ｇｄ内で探索して、前記Ｇｄを前記分割経路で複数の分割網（ｇｄ）に分割して、前記Ｇｄを前記路記憶部から削除して、各前記ｇｄを前記路記憶部に記憶し、前記分割経路を１段上位の層に追加する分割処理を実行させる路網図管理プログラム。
【請求項９】
前記コンピュータに、
当該Ｇｄの前記境界を構成する前記路のおのおのと前記注目位置間の経路（分割経路）を前記Ｇｄ内で探索する前記分割処理を実行させる請求項８の路網図管理プログラム。
【請求項１０】
前記コンピュータに、
最上位層から順次下位に向けて各層をアクセスして、各層に於いて、指定された出発位置の最近傍の路を特定して当該路に関連付けられている前記出発位置側の前記分割網（Ｇｓ）および指定された目的位置の最近傍の路を特定して当該路に関連付けられている前記目的位置側の前記分割網（Ｇｔ）を、一段下位層から取得して、当該両分割網に基づいて、前記出発点と前記到達点間の移動経路を探索して出力する探索処理を実行させる請求項８または９の路網図管理プログラム。
【請求項１１】
前記コンピュータに、
前記Ｇｓと前記Ｇｔが同一（Ｇ）であって、当該Ｇ内に前記出発位置または前記目的位置の一方の位置を含む路が存在するが他方の位置を含む路が存在しない場合に、当該層に於いて、前記他方の位置の最近傍の路を特定して当該路に関連付けられている前記他方位置側の前記分割網（Ｇｔ）を下位層から取得し、前記一方の位置と前記Ｇｔ間の経路（第４の経路）を前記Ｇ内で探索し、その後、前記Ｇｔと当該第４の経路の交点と前記他方位置の経路（第５の経路）を当該下位層以下の層から探索し、前記第４の経路、および、前記第５の経路を直列に結合した移動経路を出力する前記探索処理を実行させる請求項１０の路網図管理プログラム。
【請求項１２】
前記コンピュータに、
同一層に於いて前記Ｇｓと前記Ｇｔが異なる場合に、前記Ｇｓと前記Ｇｔ間の経路（第１の経路）を当該層の１段上位の層内で探索し、その後、前記Ｇｓと当該第１の経路の交点と前記出発位置間の経路（第２の経路）と前記Ｇｔと当該第１の経路の交点と前記目的位置間の経路（第３の経路）を当該層以下の層から探索し、前記第２の経路、前記第１の経路、および、前記第３の経路を直列に結合した移動経路を出力する前記探索処理を実行させる、請求項１０または１１の路網図管理プログラム。
【請求項１３】
イベント属性に対応付けられた前記更新層の指定を格納する利用者情報記憶部を備えた前記コンピュータに、
前記注目位置、前記イベント属性を受信する受信処理と、
前記出発位置と前記目的位置を入力する入力処理と、
前記移動経路を表示する表示処理と、
前記利用者情報記憶部から、受信された当該イベント属性に対応する前記更新層の指定を取得する前記分割処理を実行させる請求項１０乃至１２の何れかの路網図管理プログラム。
【請求項１４】
路網の詳細度に基づいて複数の層（２つの層間において詳細度が低い層を上位層、高い層を下位層と呼ぶ）に階層化され、各層において一段上位層の路の閉路で囲まれている領域ごとに分割網に分割されている路網図が、当該閉路を構成する上位層の各路の両側に当該路を境界とする２つの分割網を関連付けて格納された路記憶部を備えたコンピュータが、
最上位層から下位に向けて順次前記路網図の各層をアクセスして、各層に於いて、指定された注目位置の最近傍の路を特定して当該路に関連付けられている前記注目位置側の前記分割網（Ｇｄ）を、当該Ｇｄに前記注目位置を含む前記路が存在するようになるまで一段下位層から取得して、
最後に取得した前記Ｇｄが属する層から上位に向けて更新層の一段下位層まで順次各層をアクセスして、各層に於いて、当該Ｇｄの前記境界を構成する前記路の少なくとも２つと前記注目位置間の経路（分割経路）を前記Ｇｄ内で探索して、前記Ｇｄを前記分割経路で複数の分割網（ｇｄ）に分割して、前記Ｇｄを前記路記憶部から削除して、各前記ｇｄを前記路記憶部に記憶し、前記分割経路を１段上位の層に追加する分割工程を有する路網図管理方法。
【請求項１５】
前記コンピュータが、
当該Ｇｄの前記境界を構成する前記路のおのおのと前記注目位置間の経路（分割経路）を前記Ｇｄ内で探索する前記分割工程を有する請求項１４の路網図管理方法。
【請求項１６】
前記コンピュータが、
最上位層から順次下位に向けて各層をアクセスして、各層に於いて、指定された出発位置の最近傍の路を特定して当該路に関連付けられている前記出発位置側の前記分割網（Ｇｓ）および指定された目的位置の最近傍の路を特定して当該路に関連付けられている前記目的位置側の前記分割網（Ｇｔ）を、一段下位層から取得して、当該両分割網に基づいて、前記出発点と前記到達点間の移動経路を探索して出力する探索工程を有する請求項１４または１５の路網図管理方法。
【請求項１７】
前記コンピュータが、
前記Ｇｓと前記Ｇｔが同一（Ｇ）であって、当該Ｇ内に前記出発位置または前記目的位置の一方の位置を含む路が存在するが他方の位置を含む路が存在しない場合に、当該層に於いて、前記他方の位置の最近傍の路を特定して当該路に関連付けられている前記他方位置側の前記分割網（Ｇｔ）を下位層から取得し、前記一方の位置と前記Ｇｔ間の経路（第４の経路）を前記Ｇ内で探索し、その後、前記Ｇｔと当該第４の経路の交点と前記他方位置の経路（第５の経路）を当該下位層以下の層から探索し、前記第４の経路、および、前記第５の経路を直列に結合した移動経路を出力する前記探索工程を有する請求項１６の路網図管理方法。
【請求項１８】
前記コンピュータが、
同一層に於いて前記Ｇｓと前記Ｇｔが異なる場合に、前記Ｇｓと前記Ｇｔ間の経路（第１の経路）を当該層の１段上位の層内で探索し、その後、前記Ｇｓと当該第１の経路の交点と前記出発位置間の経路（第２の経路）と前記Ｇｔと当該第１の経路の交点と前記目的位置間の経路（第３の経路）を当該層以下の層から探索し、前記第２の経路、前記第１の経路、および、前記第３の経路を直列に結合した移動経路を出力する前記探索工程を有する、請求項１６または１７の路網図管理方法。
【請求項１９】
イベント属性に対応付けられた前記更新層の指定を格納する利用者情報記憶部を備えた前記コンピュータが、
前記注目位置、前記イベント属性を受信する受信工程と、
前記出発位置と前記目的位置を入力する入力工程と、
前記移動経路を表示する表示工程と、
前記利用者情報記憶部から、受信された当該イベント属性に対応する前記更新層の指定を取得する前記分割工程を有する請求項１６乃至１８の何れかの路網図管理方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６−Ａ】
【図６−Ｂ】
【図６−Ｃ】
【図６−Ｄ】
【図６−Ｅ】
【図７】
【図８】
【図９−Ａ】
【図９−Ｂ】
【図９−Ｃ】
【図９−Ｄ】
【図９−Ｅ】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２】
【図３】
【図４】
【図５】
【図６−Ａ】
【図６−Ｂ】
【図６−Ｃ】
【図６−Ｄ】
【図６−Ｅ】
【図７】
【図８】
【図９−Ａ】
【図９−Ｂ】
【図９−Ｃ】
【図９−Ｄ】
【図９−Ｅ】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【公開番号】特開２０１０−２１７４５９（Ｐ２０１０−２１７４５９Ａ）
【公開日】平成２２年９月３０日（２０１０．９．３０）
【国際特許分類】
【出願番号】特願２００９−６３７１９（Ｐ２００９−６３７１９）
【出願日】平成２１年３月１７日（２００９．３．１７）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２２年９月３０日（２０１０．９．３０）
【国際特許分類】
【出願日】平成２１年３月１７日（２００９．３．１７）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]