経路設定装置
【課題】出発地から目的地の間の経路において通行の妨げとなる障害地物を回避する適切な経由地を設定してから最適な経路を設定する経路設定装置を提供する。
【解決手段】 経路設定装置２４２は、通行の妨げとなる障害地物の位置および形状の情報を含む障害地物データおよび障害地物を横断する地点として障害地物に関連付けられた横断地点の位置情報を含む横断地点データを記憶する地図データ記憶部２４１と、出発地および目的地の間を結ぶ線分と交差する障害地物を抽出する交差障害地物抽出部２４０３と、交差する障害地物を横断する横断地点を抽出する横断地点抽出部２４０５と、選択横断地点を仮の目的地に設定して出発地および仮の目的地を用いて交差障害地物抽出部の処理以降の処理を繰り返し、選択横断地点を仮の出発地に設定して仮の出発地および目的地を用いて交差障害地物抽出部の処理以降の処理を繰り返す経由地設定部２４０５とを備える。
【解決手段】 経路設定装置２４２は、通行の妨げとなる障害地物の位置および形状の情報を含む障害地物データおよび障害地物を横断する地点として障害地物に関連付けられた横断地点の位置情報を含む横断地点データを記憶する地図データ記憶部２４１と、出発地および目的地の間を結ぶ線分と交差する障害地物を抽出する交差障害地物抽出部２４０３と、交差する障害地物を横断する横断地点を抽出する横断地点抽出部２４０５と、選択横断地点を仮の目的地に設定して出発地および仮の目的地を用いて交差障害地物抽出部の処理以降の処理を繰り返し、選択横断地点を仮の出発地に設定して仮の出発地および目的地を用いて交差障害地物抽出部の処理以降の処理を繰り返す経由地設定部２４０５とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路探索において予め川等の障害地物を横断する経由地を設定して最適な経路を設定する経路設定装置に関するものである。
【背景技術】
【０００２】
従来から、出発地から目的地に至る経路を探索して案内するナビゲーションシステムが利用されている。
【０００３】
従来のナビゲーションシステムとしては、例えば、出発地から目的地への経路の探索において、出発地と目的地との間に予め中間地点を決定するナビゲーションシステムが提案されている。具体的には、出発地と目的地との間に大きな湖等の無道路地域がある場合は、外形に基づいて無道路地域を迂回する中間地点を決定するというものである（例えば、特許文献１を参照。）。特許文献１に記載されている技術によれば、経路探索する前に中間地点を定めておくことにより、経路探索中に推奨する経路の候補となる通路のつながりを伸ばしていく処理において、通路を効率よく伸ばしていくことができるので、経路探索する処理の負担が軽減される。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−３００９３４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１に記載されている発明によれば、無道路地域を物理的に避ける領域を中間地点として設定するのみであり、その設定された地点が必ずしも最適経路の通過地点とは限らない。例えば、無道路地域が川であって、出発地と目的地との間に広大な流域を有している場合には、無道路地域の外形に基づいて迂回する中間地点は川の流域の外に設定される。この場合、その位置は遠方に位置することになる可能性があり、このようなときは適切な中間地点とはならないという問題点がある。
【０００６】
また、出発地と目的地との間に存在する川に橋が複数存在しており橋で区切られた区間を上述した無道路地域ととらえた場合であっても川の蛇行状態によっては、そもそも出発地や目的地が無道路地域の中に含まれてしまう場合がある。この場合、無道路地域の外形に基づく計算だけでは最適な中間地点を設定することができないという問題点がある。
【０００７】
本発明は、２つの地点の間の経路において通行の妨げとなる障害地物を回避する適切な経由地を設定してから最適な経路を設定する経路設定装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、本発明の経路設定装置は、通行の妨げとなる障害地物の位置および形状の情報を含む障害地物データおよび前記障害地物を横断する地点として前記障害地物に関連付けられた横断地点の位置情報を含む横断地点データを含む地図データを記憶する地図データ記憶部と、前記地図データを参照して出発地および目的地の間を結ぶ線分と交差する前記障害地物を抽出する交差障害地物抽出部と、該交差障害地物抽出部が前記交差する障害地物を抽出した場合であって、かつ、該抽出した障害地物と前記線分とが交差する地点が偶数地点である場合には、前記交差する障害地物を迂回したときに経由する迂回地点を、前記出発地および目的地の位置ならびに前記障害地物の位置および形状の情報に基づいて前記交差する障害地物の存在領域近傍に設定する迂回地点設定部と、前記交差障害地物抽出部が前記交差する障害地物を抽出した場合には、前記地図データを参照して前記交差する障害地物を横断する横断地点を抽出する横断地点抽出部と、前記迂回地点設定部が前記迂回地点を設定した場合には、前記迂回地点を前記出発地および目的地の地点の間の経由地として設定し、前記横断地点抽出部が前記横断地点を抽出した場合には、抽出されている前記横断地点を１つずつ選択し、選択した横断地点である選択横断地点を仮の目的地に設定して前記出発地および前記仮の目的地を用いて前記交差障害地物抽出部の処理以降の処理を繰り返す第１の再帰処理を実行させ、該第１の再帰処理において前記障害地物が抽出されないときには前記選択横断地点を前記出発地からの進行先の経由地として設定するとともに、前記選択横断地点を仮の出発地に設定して該仮の出発地および前記目的地を用いて前記交差障害地物抽出部の処理以降の処理を繰り返す第２の再帰処理を実行させ、該第２の再帰処理において前記障害地物が抽出されないときには前記選択横断地点を前記目的地への進行元の経由地として設定し、前記第１の再帰処理または前記第２の再帰処理において前記横断地点が抽出されたときには、該横断地点を選択横断地点として前記第１の再帰処理および前記第２の再帰処理を実行させる経由地設定部と、該経由地設定部が設定した前記経由地の最適な進行順序を求めて前記出発地および目的地の間の最適な経路を設定する経路設定部とを備えるものである。
【０００９】
なお、上述した特徴は、本発明の特徴のすべてを列挙したものではなく、これらを要部とする構成（または方法）もまた発明となり得る。
【発明の効果】
【００１０】
本発明の経路設定装置は、通行の妨げとなる障害地物の位置および形状の情報を含む障害地物データおよび障害地物を横断する地点として障害地物に関連付けられた横断地点の位置情報を含む横断地点データを含む地図データを記憶しており、出発地および目的地の間を結ぶ線分と交差する障害地物が抽出された場合に、交差する状態に応じて、障害地物を迂回する迂回地点や、障害地物を横断する横断地点を求め、迂回地点または横断地点を経由地として経由地の最適な進行順序を求めてから最適な経路を設定するものである。したがって、本発明の経路設定装置によれば、広大な流域を有する川のような障害地物や、蛇行した川のような障害地物であっても、迂回地点や横断地点からなる最適な経由地の進行順序を求めることができる。そして、迂回したり横断したりする経由地とその最適な進行順序を経路の探索をする前に予め求めているので、経路の探索にかかる処理について余分な負担が生じないという利点がある。
【図面の簡単な説明】
【００１１】
【図１】本実施形態のナビゲーションシステムの構成を示すブロック図である。
【図２】本実施形態の経路設定装置の構成を示すブロック図である。
【図３】（ａ）〜（ｄ）は本実施形態のナビゲーションシステムに利用される地図データのデータ構造を示す図である。
【図４】本実施形態のナビゲーションシステムの概略の処理のフローチャートである。
【図５】本実施形態のナビゲーションシステムの経由地を設定する処理のフローチャートである。
【図６】本実施形態のナビゲーションシステムの経由地を設定する処理のフローチャートである。
【図７】本実施形態の経由地設定の一例を示す図である。
【図８】本実施形態の経由地設定の一例を示す図である。
【図９】本実施形態の経由地設定の一例を示す図である。
【図１０】本実施形態の経由地設定の一例を示す図である。
【図１１】本実施形態の経由地設定の一例を示す図である。
【図１２】本実施形態の経由地設定の一例を示す図である。
【図１３】本実施形態の経由地設定の一例を示す図である。
【図１４】本実施形態の経由地設定の一例を示す図である。
【図１５】本実施形態の経路設定処理を説明する図である。
【図１６】本実施形態の経由地設定の他の例を示す図である。
【発明を実施するための形態】
【００１２】
以下、本発明を具体化した実施形態を説明する。
【００１３】
図１に示すように、本実施形態のナビゲーションシステム１は、携帯端末１０およびこの携帯端末１０と情報ネットワークを通して接続される情報センター２０を備える。携帯端末１０は、無線通信部１１、現在位置検出部、画像表示部および装置本体を備える携帯電話であり、歩行者用ナビゲーション端末として利用される。情報センター２０は、データ通信部２３、入力部２１、表示部２２および計算機２４を備える大型コンピュータである。そして、図２に示すように、計算機２４は、地図データ記憶部２４１、地点設定部２４０２、交差障害地物抽出部２４０３、経由地設定部２４０４、横断地点抽出部２４０５、迂回地点設定部２４０６、経路設定部２４０８および画像生成部２４３を備えている。このうち、地点設定部２４０２、交差障害地物抽出部２４０３、経由地設定部２４０４、横断地点抽出部２４０５および迂回地点設定部２４０６および経路設定部２４０８は経路設定装置２４２を構成している。
【００１４】
携帯端末１０を構成する無線通信部１１は、送信機、受信機およびアンテナからなるトランシーバである。また、現在位置検出部は、ＧＰＳ衛星からの電波に基づいて現在位置を検出するＧＰＳ受信器と、ＧＰＳ衛星からの電波を受信しにくい地下街内等は現在位置を検出するために設置された無線局からの近距離の無線受信に基づいて現在位置を求めて現在位置のデータを出力する近距離無線位置検出器とからなる。また、画像表示部は、液晶ディスプレイ等であって画像表示面に通信メニュー画面や地図画像等の画像を表示するデバイスである。そして、装置本体は、専用の計算機を含む各ハードウェアを収納する筐体である。なお、本実施形態の携帯端末１０は、画像表示部の表面がタッチパネルの機能を有しており、ユーザの指定により、目的地、表示したい地図のエリア、縮尺、施設のフロアおよびその階層等を指定することができる。
【００１５】
情報センター２０を構成するデータ通信部２３は、光ファイバーによりインターネットＷと接続する機能を備えており、インターネットＷから無線通信を介して携帯端末１０の無線通信部１１と接続される。また、地図データ記憶部２４１は、フラッシュメモリ、ハードディスク、ＤＶＤまたはブルーレイディスク等の外部記憶装置であり、地図データを記憶している。また、表示部２２は、液晶ディスプレイ等であって画像表示面に画像を表示するデバイスである。また、入力部２１は、キーボードやマウス等であってオペレータ等の指示内容を入力するデバイスである。そして、計算機２４は、コンピュータプログラムや処理条件等が予め記憶されているＲＯＭやＲＡＭ等の内部記憶装置、およびこのコンピュータプログラムを実行するＣＰＵ等からなる大型のコンピュータである。
【００１６】
地図データ記憶部２４１が記憶している地図データは、行政界図、道路図および施設図等を生成するためのポリラインやポリゴンのデータ等の地図表示用データと、車または歩行者が通行可能な通路の接続状態をノードおよびリンクで表現するネットワークデータと、通行の妨げとなる障害地物の位置および形状の情報を含む障害地物データとを含むものである。障害地物データは、障害地物を横断する地点として障害地物に関連付けられた横断地点の位置情報を含む横断地点データと関連付けられている。障害地物は、例えば川等の地理的に大規模なものであって人や車が直接横断することができない地物であり、横断地点は、例えば川を横断するために建設された橋である。なお、本実施形態において、川については車が通行可能な橋の位置で区切った区間を１単位の障害地物としている。
【００１７】
障害地物データは、図３（ａ）に示すように、障害地物を認識するための情報である障害地物ＩＤ、複数の障害地物が連なって構成する連帯障害地物を示す情報である連帯障害地物ＩＤ、障害地物を横断する横断路を認識する情報である横断路ＩＤ、障害地物の長さを示す情報である障害地物長、障害地物同士が接続する地点の情報である障害地物接続点ＩＤ、障害地物の形状を表現するための情報である形状情報、障害地物の存在領域を認識するための情報である外接矩形情報等の情報を含んでいる。本実施形態において、障害地物は形状補間点である形状情報を用いてポリラインとして地図に表示される。
【００１８】
横断地点データは、図３（ｂ）に示すように、上述した横断路ＩＤ、横断路の一方の端点である端点１のノードの情報に相当する端点１ノードＩＤ、横断路の他方の端点である端点２のノードの情報に相当する端点２ノードＩＤ、横断路に含まれるリンク列の各リンクの情報である横断路リンクＩＤ、上述した障害地物接続点ＩＤおよび横断路の通過コストを示す情報である通過コスト等の情報を含んでいる。端点１、２は例えば端の出入口であり、ネットワークデータにおいて同じ位置にノードが対応付けられている。
【００１９】
また、障害地物データは連帯障害地物データとも関連づけられている。連帯障害地物データは、図３（ｃ）に示すように、連帯障害地物ＩＤ、連帯障害地物の名称を示す情報である連帯障害地物名称、連帯障害地物の種類を示す情報である連帯障害地物種類、連帯障害地物を構成する各障害地物の障害地物ＩＤ、連帯障害地物の存在領域を認識するための外接矩形情報等の情報を含んでいる。連帯障害地物種類は、例えば川、崖として登録される。
【００２０】
また、障害地物データは障害地物接続点データとも関連付けられている。障害地物同士が接続する地点である障害地物接続点は、本実施形態においては障害地物として表示されるポリラインの端点に相当し、接続している全ての障害地物の障害地物ＩＤを含んでいる。障害地物接続点データは、図３（ｄ）に示すように、障害地物接続点ＩＤ、障害地物接続点の種別を示す情報である種別、障害地物接続点の位置を示す情報である緯度経度座標、接続している障害地物ＩＤ等の情報を含んでいる。これらの情報は障害地物同士の接続状態を認識可能にする情報である。本実施形態においては、例えば連帯障害地物が川であれば、橋である横断路と障害地物との交点の位置に障害地物接続点が位置するので、種別は「障害地物と横断路との交点」となる。また、１つの障害地物接続点に対して複数の障害地物が接続していることもある。これは、例えば、障害地物が川であるときには、本流に支流が合流している場合であって合流点の位置を障害地物接続点としているとき等が当てはまる。この場合の障害地物接続点の種別は「接続点」として登録される。なお、本実施形態とは異なり、例えば連帯障害地物である川を橋と橋との中間点で区切った区間を１単位の障害地物とする場合の種別も「接続点」として登録される。
【００２１】
データ通信部２３は、携帯端末１０側で指定した出発地および目的地、または携帯端末１０の現在位置のデータを受信する。
【００２２】
地点設定部２４０２は、携帯端末１０側で指定した出発地および目的地の２つの地点を設定して交差障害地物抽出部２４０３へ出力する機能を有する。また、地点設定部２４０２は、後述する経由地設定部から、仮の目的地の情報を受け取った場合には、出発地および仮の目的地の２つの地点を設定して交差障害地物抽出部２４０３へ出力し、仮の出発地の情報を受け取った場合には、目的地および仮の出発地の２つの地点を設定して交差障害地物抽出部２４０３へ出力する。
【００２３】
交差障害地物抽出部２４０３は、地図データを参照して、地点設定部２４０２が設定した出発地および目的地の２つの地点の間を結ぶ線分と交差する障害地物を抽出する機能を有する。本実施形態においては、連帯障害地物データの外接矩形情報または障害地物データの外接矩形情報を参照して、線分と交差している可能性のある障害地物を予め特定するようにしているので、効率的に交差判定を行なうことができる。また、交差障害地物抽出部２４０３は、交差障害地物抽出部２４０３が抽出した線分が交差する障害地物を抽出する機能も有している。
【００２４】
横断地点抽出部２４０５は、地図データを参照して交差する障害地物を横断する横断地点を抽出する機能を有する。本実施形態においては、横断地点抽出部２４０５は、横断路抽出部２４１０および横断路端点抽出部２４１１を備えている。横断路抽出部２４１０は線分が交差する障害地物を横断する横断路を抽出し、横断路端点抽出部２４１１は横断路の端点を横断地点として抽出する。
【００２５】
迂回地点設定部２４０６は、交差する障害地物を迂回したときに経由する迂回地点を、前記出発地および目的地の位置ならびに前記障害地物の位置および形状の情報に基づいて前記交差する障害地物の存在領域近傍に設定する機能を有する。迂回地点設定部２４０６は、交差障害地物抽出部２４０３が線分と交差する障害地物を抽出した場合であって、線分がいずれかの障害地物と交差し、かつ交差する回数が偶数回である場合は、２つの地点は検出された障害地物によって隔てられた領域の同一領域内に存在すると判断できるため、障害地物を横断する横断地点ではなく、障害地物を避けて進行するための迂回地点を設定する。
【００２６】
経由地設定部２４０４は、交差障害地物抽出部２４０３が障害地物を抽出しているか否かを判定する機能を有している。経由地設定部２４０４は、地点設定部２４０２が設定した出発地および目的地の２つの地点の間を結ぶ線分と交差する障害地物を交差障害地物抽出部２４０３により抽出していないと判定した場合は、出発地および目的地の２つの地点について間に経由地が存在しないことを確定し、出発地から目的地への進行順序を設定する。設定している２つの地点について進行順序を設定すると、その２つの地点および進行順序を経由地リストに格納する。
【００２７】
また、経由地設定部２４０４は、交差障害地物抽出部２４０３が障害地物を抽出していると判定した場合は、迂回地点設定部２４０６に対して障害地物に対応する迂回地点を返すように要求し、迂回地点設定部２４０６が迂回地点を設定したときには、迂回地点を出発地および目的地の地点の間の経由地として設定し、出発地から経由地までの進行順序および経由地から目的地までの進行順序を設定する。
【００２８】
さらに、経由地設定部２４０４は、交差障害地物抽出部２４０３が障害地物を抽出していると判定した場合は、横断地点抽出部２４０５に対して障害地物に対応する横断地点を返すように要求し、横断地点抽出部２４０５が横断地点を抽出したときには、横断地点抽出部２４０５から抽出された横断地点を受け取り、抽出した横断地点を横断地点リストに格納する。本実施形態においては、横断地点抽出部２４０５は、線分と交差する障害地物に対応する横断路を抽出し、抽出した横断路の端点を横断地点として返すようにしている。また、本実施形態においては、抽出された障害地物の障害地物ＩＤに関連付けられている障害地物接続点ＩＤによって隣接する障害地物を特定できるので、複数の障害地物から横断路を抽出することができる。なお、このような処理は状況に応じて実行するようにしている。例えば、抽出された障害地物に隣接する障害地物の長さが閾値よりも小さいものであった場合は、隣接する障害地物に対応する横断路も合わせて抽出することとしている。
【００２９】
そして、経由地設定部２４０４は、抽出されている横断地点を横断地点リストから１つずつ選択し、選択した横断地点である選択横断地点を仮の目的地に設定して仮の目的地の情報を地点設定部２４０２へ送る。こうすることにより、地点設定部２４０２が出発地および仮の目的地の２つの地点を設定して交差障害地物抽出部２４０３へ出力し、出発地および仮の目的地を用いて交差障害地物抽出部２４０３の処理以降の処理を繰り返す処理（第１の再帰処理）が実行される。経由地設定部２４０４は、この第１の再帰処理において障害地物が抽出されないときには選択横断地点を出発地からの進行先の経由地として設定する。さらに、経由地設定部２４０４は、同じ選択横断地点を仮の出発地として地点設定部２４０２へ送る。こうすることにより、地点設定部２４０２が目的地および仮の出発地の２つの地点を設定して交差障害地物抽出部２４０３へ出力し、仮の出発地および目的地を用いて交差障害地物抽出部２４０３の処理以降の処理を繰り返す処理（第２の再帰処理）が実行される。経由地設定部２４０４は、この第２の再帰処理において障害地物が抽出されないときには選択横断地点を目的地への進行元の経由地として設定する。このように、経由地設定部２４０４は、仮の目的地または仮の出発地を設定して交差障害地物抽出部２４０３以降の処理を繰り返すように制御する機能を有する。また、経由地設定部２４０４は、第１の再帰処理または第２の再帰処理において横断地点が抽出されたときには、抽出された横断地点を選択横断地点として第１の再帰処理および第２の再帰処理を実行させる。なお、本実施形態においては、選択横断地点とした横断路の一方の端点を仮の目的地とした場合は、選択横断地点の代わりにその横断路の他方の端点を仮の出発地として設定することとしている。経由地設定部２４０４は、第１、第２の再帰処理が終了し、２つの地点の間の進行順序が設定されたときには、その２つの地点および進行順序を経由地リストに格納する。
【００３０】
そして、経由地設定部２４０４は、第１、第２の再帰処理が終了し、横断地点リストにまだ選択されていない横断地点が残っているときには、残っている横断地点から選択した選択横断地点による第１、第２の再帰処理を実行させる。経由地設定部２４０４は、線分と交差する障害地物が抽出されないとき、または横断地点リストに横断地点が残っていないときは、経由地リストに含まれる出発地、経由地、目的地および進行順序の情報を経路設定部２４０８へ出力する。
【００３１】
すなわち、経由地設定部２４０４は、交差障害地物抽出部２４０３が障害地物を抽出していると判定した場合には、地点設定部２４０２に２つの地点を再設定させ、迂回地点を設定するまたは横断地点を抽出する処理を再帰的に繰り返すように制御する機能を有している。本実施形態において、経由地設定部２４０４による再帰的に繰り返す処理は、出発地側から確定していく方向となるように制御する。つまり、横断地点リストから選択横断地点として選択する１つの横断地点は出発地に近いほうから優先して選択していく。
【００３２】
経路設定部２４０８は、地点設定部２４０２が設定した出発地点、目的地点および経由地を、地図データ記憶部２４１に記憶されている地図データを参照して地図上に決定するとともに、ネットワークデータを用いて出発地点から目的地点に到る経路を算出して推奨する経路を設定する機能を有する。
【００３３】
画像生成部２４３は、基準フロアおよび周辺フロアに対応するフロア表示用データに基づいて地図画像を生成し、生成した地図画像のデータをデータ通信部２３へ出力する。
【００３４】
本実施形態の経路設定装置２４２は、通行の妨げとなる障害地物の位置および形状の情報を含む障害地物データおよび障害地物を横断する地点として障害地物に関連付けられた横断地点の位置情報を含む横断地点データを含む地図データを記憶しており、出発地および目的地の間を結ぶ線分と交差する障害地物が抽出された場合に、交差する状態に応じて、障害地物を迂回する迂回地点や、障害地物を横断する横断地点を求め、迂回地点または横断地点を経由地として経由地の最適な進行順序を求めてから最適な経路を設定するものである。したがって、広大な流域を有する川のような障害地物や、蛇行した川のような障害地物であっても、迂回地点や横断地点からなる最適な経由地の進行順序を求めることができる。また、迂回したり横断したりする経由地とその最適な進行順序を経路の探索をする前に予め求めているので、経路の探索にかかる処理について余分な負担が生じないという利点がある。
【００３５】
本実施形態のナビゲーションシステム１の処理について説明する。本実施形態は、現在位置から目的地へ至る経路を設定し、携帯端末１０の現在位置の移動にともなってその都度地図画像を表示するナビゲーションシステムの例である。本実施形態のナビゲーションシステム１は、図４に示すように、出発地および目的地を設定する処理を実行し（ステップＳ４００）、出発地および目的地の２つの地点の間に経由地を設定する処理を実行し（ステップＳ５００）、ステップＳ５００の結果に基づいて出発地から目的地へ至る経路を設定する処理を実行する（ステップＳ６００）。
【００３６】
＜地点設定処理＞
本実施形態のナビゲーションシステム１が、出発地および目的地を設定する処理（ステップＳ４００）の詳細は以下のとおりである。
【００３７】
まず、携帯端末１０側でユーザがタッチパネルを操作することにより目的地を指定する。携帯端末１０は、現在位置検出部により定期的に現在位置を検出しており、ユーザの指定を受け付けると、指定された目的地の情報と現在位置の情報とを無線通信部１１によりインターネットＷを介して配信サーバへ送信する処理を実行する。なお、携帯端末１０は、この後も現在位置を定期的に検出して、そのたびに、最新の現在位置の情報を配信サーバへ送信する。
【００３８】
携帯端末１０がデータを送信する処理が終了すると、配信サーバ側で、データ通信部２３が目的地の情報と現在位置の情報を受信して受信したこれらのデータを経路設定装置の地点設定部２４０２へ出力する処理を実行する。情報センター２０において、計算機２４は、地点設定部２４０２が目的地の情報の基づく目的地および現在位置の情報に基づく出発地の２つの地点を設定する処理を実行する（ステップＳ４００）。図７〜図１５は、それぞれ本実施形態の経由地設定の一例を示す図である。まず、図７に示す本実施形態の経由地設定の一例においては、地図上に出発地Ｓおよび目的地Ｇの２つの地点が設定されている。
【００３９】
＜経由地設定処理＞
次に、本実施形態のナビゲーションシステム１が、地点設定部２４０２により設定された２つの地点の間に経由地を設定する処理（ステップＳ５００）について、図５および図６を用いて詳細に説明する。ステップＳ４００が終了すると、計算機２４は、交差障害地物抽出部２４０３により、地図データを参照して、地点設定部２４０２が設定した出発地Ｓおよび目的地Ｇの２つの地点の間を結ぶ線分と交差する障害地物を抽出する処理を実行する（ステップＳ５０１）。本実施形態の経由地設定の一例においては、図７に示すように、出発地Ｓおよび目的地Ｇの間を結ぶ線分ＳＮ００を引いたときに、線分ＳＮ００と交差する障害地物ＫＷ３が抽出される。障害地物ＫＷ３は連帯障害地物データにおいて連帯障害地物種類が川として登録されている連帯障害地物ＫＷを構成する障害地物ＫＷ１〜ＫＷ４のうちの１つである。障害地物ＫＷ２と障害地物ＫＷ３とは、連帯障害地物ＫＷと横断路ＨＳ２との交点に位置する障害地物接続点（図示せず）で接続しており、障害地物ＫＷ３と障害地物ＫＷ４とは、連帯障害地物ＫＷと横断路ＨＳ１との交点に位置する障害地物接続点（図示せず）で接続している。また、障害地物ＫＷ１と障害地物ＫＷ２とは障害地物接続点ＧＲで接続している。また、障害地物接続点ＧＲは連帯障害地物ＫＷと連帯障害地物ＫＳとの合流点であり、障害地物接続点ＧＲにおいて、連帯障害地物ＫＳを構成する障害地物ＫＳ１、連帯障害地物ＫＷを構成する障害地物ＫＷ１、ＫＳ２が接続している。
【００４０】
ステップＳ５０１が終了すると、計算機２４は、経由地設定部２４０４により、前の処理のときに障害地物が抽出されているか否かを判定する処理を実行する（ステップＳ５０２）。計算機２４は、ステップＳ５０２において、前の処理のときに障害地物が抽出されていないと判定した場合は（ステップＳ５０２：Ｎｏ）、経由地を設定する処理（ステップＳ５００）を終了する。
【００４１】
また、計算機２４は、ステップＳ５０２において、前の処理のときに障害地物が抽出されていると判定した場合は（ステップＳ５０２：Ｙｅｓ）、経由地設定部２４０４により、交差障害地物抽出部２４０３が抽出した障害地物を要求して受け取る処理を実行する（ステップＳ５０３）。
【００４２】
ステップＳ５０３が終了すると、計算機２４は、迂回地点設定部２４０６により、交差する障害地物を迂回したときに経由する迂回地点を設定する処理を実行する（ステップＳ５０４）。具体的には、線分がいずれかの障害地物と交差し、かつ交差する回数が偶数回である場合は迂回地点が設定される。本実施形態において、迂回地点の設定は、設定している２つの地点の両方について障害地物に対する接線を求め、求めた接線同士の交点が障害地物から所定の距離以内にあるときにはこの交点を迂回地点として設定する。具体的には、線分と障害地物との複数の交点のうち、２つの地点の出発地側からみて、奇数番目の交点とその次の交点までの間の障害地物の形状と線分とで囲まれるエリアを全て求め、それらを包含する最小の凸図形を算出し、その凸図形に対して２つの地点から接線を求める。なお、求めた接線同士の交点が障害地物から所定の距離以内にないときには、設定している２つの地点を結ぶ線分に対して平行な障害地物に対する接線を求め、この接線と前に求めた２つの接線との交点を求め、求めた交点の中間点を迂回地点として設定する。
【００４３】
図７に示す本実施形態の経由地設定の一例とは異なる他の例を図１６に示す。図１６に示すように、線分ＳＮ７０と障害地物ＫＷ７との交点Ｐ１、Ｐ２、Ｐ３、Ｐ４がまず抽出される。次に、出発地Ｓからみて奇数番目であるＰ１とその次の交点Ｐ２からなる線分と障害地物ＫＷ７とで囲まれる領域Ａ１を求め、同様にしてＰ３とＰ４からは領域Ａ２を求める。これらＡ１とＡ２を包含する最小の凸図形Ａ３に対して、出発地Ｓおよび目的地Ｇからの接線Ｌ１、Ｌ２がそれぞれ求められる。Ｌ１とＬ２の交点であるＤ７が障害地物ＫＷ７から所定の距離よりも離れていると判断された場合は、線分ＳＮ７０と平行でかつ前述の領域Ａ３と接している線Ｌ３を求め、Ｌ１、Ｌ２との交点の中間点Ｄ８を迂回地点として設定する。
【００４４】
本実施形態の経由地設定の一例においては、図８に示すように、障害地物ＫＷに対する接線ＴＧ１１，ＴＧ１２の交点Ｄ１が迂回地点として設定される。ステップＳ５０４が終了すると、計算機２４は、経由地設定部２４０４により、前の処理のときに迂回地点が設定されているか否かを判定する処理を実行する（ステップＳ５０５）。
【００４５】
計算機２４は、ステップＳ５０５において、迂回地点が設定されていないと判定した場合は（ステップＳ５０５：Ｎｏ）、ステップＳ５０７へ移行する。また、計算機２４は、ステップＳ５０５において、迂回地点が設定されていると判定した場合は（ステップＳ５０５：Ｙｅｓ）、経由地設定部２４０４により、迂回地点を、設定している２つの地点の間で経由する経由地として設定する処理を実行する（ステップＳ５０６）。なお、計算機２４は、経由地設定部２４０４により、出発地から経由地までの進行順序および経由地から目的地までの進行順序も設定する。本実施形態の経由地設定の一例においては、ステップＳ５０４の処理によって設定されている図８に示す迂回地点Ｄ１が経由地Ｄ１として設定され、出発地Ｓから経由地Ｄ１までの進行順序および経由地Ｄ１から目的地Ｇまでの進行順序も設定される。このとき、２つの地点のうちの目的地側は最終到着地の目的地であるため、出発地Ｓ−経由地Ｄ１−目的地Ｇの順の１つの経路が確定する。
【００４６】
ステップＳ５０６が終了すると、計算機２４は、経由地設定部２４０４により、横断地点抽出部２４０５に対して障害地物に対応する横断地点を返すように要求し、横断地点抽出部２４０５により、交差する障害地物を横断する横断地点を抽出して経由地設定部２４０４へ返す。そして、計算機２４は、経由地設定部２４０４により、抽出した横断地点からなる横断地点リストを作成して格納する処理を実行する（ステップＳ５０７）。本実施形態においては、交差する障害地物に関連付けて登録されている横断路を特定し、さらに、特定した横断路に関連付けて登録されている横断路の端点を特定してこれを横断地点として抽出する。例えば、本実施形態の経由地設定の一例においては、図９に示すように、障害地物ＫＷには橋である横断路ＨＳ１，ＨＳ２が関連付けて登録されている。また、横断路ＨＳ１には端点ＨＳ１Ｔ１，ＨＳ１Ｔ２が関連付けて登録されており、横断路ＨＳ２には端点ＨＳ２Ｔ１，ＨＳ２Ｔ２が関連付けて登録されている。なお、本実施形態においては、特定したすべての横断路の端点についてそれぞれ出発地Ｓとの間を結ぶ線分ＳＮ０１，ＳＮ０２，ＳＮ０３，ＳＮ０４と交差する障害地物を抽出するとともに障害地物と交差する回数を解析し、このうち線分が交差する回数が奇数回である横断路の端点は出発地と障害地物によって隔てられているとして横断地点リストには格納しない。図９に示す本実施形態の経由地設定の一例においては、経由地設定部２４０４は、横断地点ＨＳ１Ｔ１，ＨＳ２Ｔ２からなる横断地点リストを作成して格納する。
【００４７】
ステップＳ５０７が終了すると、計算機２４は、経由地設定部２４０４により、抽出されている横断地点を横断地点リストから１つずつ選択する処理を実行する（ステップＳ５０８）。選択した横断地点を選択横断地点とする。本実施形態においては、横断地点リストから選択横断地点として選択する１つの横断地点は出発地に近いほうから優先して選択していくようにしているので、経由地設定の一例においては、図１０に示すように、まず、横断地点ＨＳ１Ｔ１を選択することになる。
【００４８】
第１の再帰処理（出発地Ｓ−横断地点ＨＳ１Ｔ１）：
ステップＳ５０８が終了すると、計算機２４は、経由地設定部２４０４により、抽出されている横断地点を横断地点リストから１つずつ選択し、選択した横断地点である選択横断地点を仮の目的地に設定して仮の目的地の情報を地点設定部２４０２へ送り、地点設定部２４０２により、出発地および仮の目的地の２つの地点を設定して交差障害地物抽出部２４０３へ出力し、ステップＳ５００の処理を繰り返す第１の再帰処理を実行する（ステップＳ５０９）。具体的には、本実施形態の経由地設定の一例においては、図１０に示す、出発地Ｓおよび仮の目的地とした選択横断地点ＨＳ１Ｔ１の２つの地点を用いてステップＳ５００の再帰処理が実行される。なお、図１０に示す場合は、ステップＳ５０２において２つの地点の間を結ぶ線分ＳＮ１１と交差する障害地物が抽出されないので選択横断地点ＨＳ１Ｔ１を出発地Ｓからの進行先の経由地として設定する。
【００４９】
第２の再帰処理（横断地点ＨＳ１Ｔ１−目的地Ｇ）：
ステップＳ５０９が終了すると、計算機２４は、経由地設定部２４０４により、同じ選択横断地点ＨＳ１Ｔ１を仮の出発地として地点設定部２４０２へ送り、地点設定部２４０２により、目的地および仮の出発地の２つの地点を設定して交差障害地物抽出部２４０３へ出力し、ステップＳ５００の処理を繰り返す第２の再帰処理を実行する（ステップＳ５１０）。具体的には、本実施形態の経由地設定の一例においては、図１１に示す、目的地Ｇおよび仮の出発地とした選択横断地点ＨＳ１Ｔ１の２つの地点を用いてステップＳ５００の再帰処理が実行される。なお、このとき、横断地点ＨＳ１Ｔ１はステップＳ５０９において出発地Ｓからの進行順序が設定されているので、出発地Ｓから横断路ＨＳ１における他方の端点ＨＳ１Ｔ２に至る進行順序が確定するので、その結果、横断地点ＨＳ１Ｔ２が仮の出発地となって第２の再帰処理が実行される。図１１に示すように、第２の再帰処理におけるステップＳ５０１において、この２つの地点の間を結ぶ線分ＳＮ１２からは交差する障害地物ＫＷ３が抽出される。そして、第２の再帰処理におけるステップＳ５０７において、Ｕターンする方向となる横断地点ＨＳ１Ｔ１や線分が交差する回数が奇数回である横断地点ＨＳ２Ｔ２は横断地点リストに追加せず、線分が交差する回数が０である横断地点ＨＳ２Ｔ１が横断地点リストに追加して格納される。
【００５０】
第１の再帰処理（横断地点ＨＳ１Ｔ２−横断地点ＨＳ２Ｔ１）：
本実施形態の経由地設定の一例においては、上述した第２の再帰処理（横断地点ＨＳ１Ｔ１−目的地Ｇ）において横断地点が抽出されているので、抽出された横断地点を選択横断地点として第１の再帰処理および第２の再帰処理を実行させることになる。ステップＳ５０８が終了すると、ステップＳ５０９において、横断地点ＨＳ２Ｔ１を選択し、選択横断地点ＨＳ２Ｔ１を仮の目的地とする２つの地点を用いた第１の再帰処理が実行される。この場合の出発地は横断地点ＨＳ２Ｔ１を算出するときに仮の出発地として用いた横断地点ＨＳ１Ｔ２になる。この２つの地点については、図１２に示すように、第１の再帰処理におけるステップＳ５０２において２つの地点の間を結ぶ線分ＳＮ２１と交差する障害地物が抽出されないので、選択横断地点ＨＳ２Ｔ１をこのときに出発地となっている横断地点ＨＳ１Ｔ２からの進行先の経由地として設定する。
【００５１】
第２の再帰処理（横断地点ＨＳ２Ｔ２−目的地Ｇ）：
本実施形態の経由地設定の一例においては、ステップＳ５０９が終了すると、ステップＳ５１０において、選択横断地点ＨＳ２Ｔ１を仮の出発地とする２つの地点を用いて第２の再帰処理が実行される。この場合、選択横断地点ＨＳ２Ｔ１は直前のステップＳ５０９において目的地Ｓからの進行順序が確定しているので、横断路ＨＳ２における他方の端点ＨＳ２Ｔ２に至る進行順序が確定するので、その結果、横断地点ＨＳ２Ｔ２が仮の出発地となって第２の再帰処理が実行される。この２つの地点については、図１３に示すように、第２の再帰処理におけるステップＳ５０２において２つの地点を結ぶ線分ＳＮ２２と交差する障害地物が抽出されないので、選択横断地点ＨＳ２Ｔ２を目的地Ｇへの進行元の経由地として設定する。
【００５２】
ステップＳ５０９およびステップＳ５１０の再帰処理が実行され、経由地設定部２４０４により、設定されている２つの地点およびその進行順序を経由地リストへ追加して格納する処理を実行する（ステップＳ５１１）。本実施形態の経由地設定の一例においては、出発地Ｓ−横断地点ＨＳ１Ｔ１−横断地点ＨＳ１Ｔ２−横断地点ＨＳ２Ｔ１−横断地点ＨＳ２Ｔ２−目的地Ｇの順の１つの経路が確定され、経由地リストに追加される。
【００５３】
ステップＳ５１１が終了すると、計算機２４は、経由地設定部２４０４により、本実施形態において経由地の候補となる横断地点を格納している横断地点リストに横断地点が残っているか否かを判定する処理を実行する（ステップＳ５１２）。計算機２４は、ステップＳ５１２において、横断地点リストに横断地点が残っていると判定した場合は（ステップＳ５１２：Ｙｅｓ）、ステップＳ５０８へ移行する。本実施形態の経由地設定の一例においては、ここまでの処理が実行された時点で、横断地点リストに横断地点ＨＳ２Ｔ２が残っているので、続けて、この横断地点ＨＳ２Ｔ２を選択横断地点として第１、第２の再帰処理が実行されることになる。
【００５４】
横断地点ＨＳ２Ｔ２を算出するときに用いた出発地および目的地はユーザの操作に基づいた出発地Ｓおよび目的地Ｇである。本実施形態の経由地設定の一例においては、図１４に示すように、第１の再帰処理においては、ステップＳ５０２において２つの地点を結ぶ線分ＳＮ３１と交差する障害地物ＫＷが抽出され、かつ交差する地点が偶数地点であるため、ステップＳ５０４において出発地Ｓとの間に迂回地点Ｄ３が設定され、これがステップＳ５０６において経由地Ｄ３として設定される。これにより、出発地Ｓ−経由地Ｄ３−横断地点ＨＳ２Ｔ２の進行順序が確定する。そして、次のステップＳ５０７においては、横断地点ＨＳ１Ｔ１が横断地点リストに格納される。なお、横断地点ＨＳ１Ｔ１が横断地点リストに格納された場合、先述したように、出発地Ｓ−横断地点ＨＳ１Ｔ１−横断地点ＨＳ１Ｔ２−横断地点ＨＳ２Ｔ１−横断地点ＨＳ２Ｔ２の順の１つの経路が確定することになる。次に、仮の目的地である横断地点ＨＳ２Ｔ２の他方の端点であるＨＳ２T１が仮の出発地となるが、その後の再帰処理を行なって得られる経路は出発地Sへ戻る経路となる。従って、これらの経路順は経由地リストに追加されない。
【００５５】
ステップＳ５１２において、横断地点リストに横断地点が残っていないと判定した場合は（ステップＳ５１２：Ｎｏ）、計算機２４は、経由地設定部２４０４により、経由地リストを確定して経由地リストに含まれる出発地、経由地、目的地および進行順序の情報を経路設定部２４０８へ出力する処理を実行し、しかる後に、経由地を設定する処理（ステップＳ５００）を終了する。本実施形態の経由地設定の一例においては、ここまでの処理が実行された時点で、出発地Sから目的地Gへの経由地設定における横断地点リストが空であるため、経由地設定を終了する。
【００５６】
＜経路設定処理＞
次に、本実施形態のナビゲーションシステム１において、地点設定部により確定された経由地リストに基づいて出発地から目的地へ至る経路を設定する処理（ステップＳ６００）について詳細に説明する。本実施形態においては、最初に設定された出発地および目的地の２地点間について障害地物を横断したり避けたりして到達できる進行順序が設定されている経由地リストを全て取得することとしており、取得した進行順序が確定している経由地リストに対応する経由地進行パターンの全てについて経路探索処理を行い、最も通過コストが低くなる最適な進行順序の経路を設定する。本実施形態の経由地設定の一例においては、図１５に示すように、上述した経由地を設定する処理によって設定された出発地Ｓ−経由地Ｄ１−目的地Ｇの順の１つの経路、または出発地Ｓ−横断地点ＨＳ１Ｔ１−横断地点ＨＳ１Ｔ２−横断地点ＨＳ２Ｔ１−横断地点ＨＳ２Ｔ２−目的地Ｇの順のもう１つの経路についてそれぞれ経路探索を行ない、最も通過コストが低くなる最適な経路を設定する。
【００５７】
また、設定された迂回地点は、横断地点と異なり、その地点に確実に到達しなければならないものではなく、あくまで障害地物を効率よく避けるための目安となる領域とする。図１５に示すように、経由地として設定した迂回地点Ｄ１を中心とした所定の領域Ｄ１Ｗを迂回地点到達領域Ｄ１Ｗとして設けることで、障害地物ＫＷを避けられる程度に経路の通路が延びたところで、迂回地点Ｄ１に到達したものとして次の経由地へ処理を移す事ができる。
【００５８】
＜その他＞
なお、本発明は上述の実施形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々の変更、改良が可能である。例えば、上述した実施形態においては、ステップS５０８において、進行順序において出発地に近いほうから横断地点を取り出すようにしているが、例えば、進行順序において目的地に近いほうから横断地点を取り出すようにしてもよく、また、ランダムに取り出すようにしてもよい。
【００５９】
また、経由地間の線分距離の合計値によって２点間の経路の概算コストを算出し、それによって１つに絞られた経由地進行パターンに関してのみ、経路探索を行うことも可能である。例えば、最初に設定された出発地および目的地の２地点間について障害地物を避けて到達できる経由地進行パターンを全て取得した後、それぞれの経由地進行パターンについて上述した概算コストを算出し、最も概算コストの小さい経由地進行パターンのみを経路設定部へ出力することもできる。
【００６０】
また、例えば、ある２地点間において横断地点が複数あるなどの理由により複数の経路が候補となる場合は、上述の概算コストが最も小さい経路を構成する経由地のみをその２地点間の経由地として確定することもできる。
【００６１】
また、上述した実施形態においては、横断路端点抽出部が抽出する横断路の端点の情報は、予め整備されたデータとして保持しているが、障害地物と横断路の交点の情報から、地図データを参照して利用者の通行可能な経路を辿ってその都度抽出しても良い。
【００６２】
また、上述した実施形態においては、横断地点データには、障害地物を横断する横断路とその端点の情報を含んでおり、線分と交差する障害地物に対応する横断路を抽出し、抽出した横断路の端点を横断地点としているが、横断路のようなデータを持たず、障害地物上に１点の横断地点を登録しておいて、このような簡略化した横断地点を用いて経由地を設定するナビゲーションシステムとすることもできる。
【００６３】
また、上述した実施形態においては、経路順の確定できない横断地点に関し、２つの地点からなる線分が障害地物と交差するとき、その障害地物ＩＤと交差回数が、最初に設定された出発地と目的地を結ぶ線分で得られた障害地物の障害地物ＩＤと交差回数に対し、同一障害地物ＩＤでかつ交差回数が同一以上である場合は横断地点リストに加えないとすることもできる。
【００６４】
また、上述した実施形態においては、２つの地点により迂回地点が設定された場合、迂回地点を経由地として確定し、その後に抽出される横断地点については経由地としてそのまま確定するのではなく、迂回地点から横断地点までの概略コストや障害地物との交差回数が、迂回地点から目的地までの概算コストより明らかに大きい場合や、障害地物との交差回数が極端に大きい場合には、横断地点を経由地として確定せず、再帰処理を中断することもできる。
【符号の説明】
【００６５】
２３・・・データ通信部
２４・・・計算機
２４１・・・地図データ記憶部
２４０３・・・交差障害地物抽出部
２４０４・・・経由地設定部
２４０５・・・横断地点抽出部
２４０６・・・迂回地点設定部
２４１０・・・横断路抽出部
２４１１・・・横断路端点抽出部
２４２・・・経路設定装置
【技術分野】
【０００１】
本発明は、経路探索において予め川等の障害地物を横断する経由地を設定して最適な経路を設定する経路設定装置に関するものである。
【背景技術】
【０００２】
従来から、出発地から目的地に至る経路を探索して案内するナビゲーションシステムが利用されている。
【０００３】
従来のナビゲーションシステムとしては、例えば、出発地から目的地への経路の探索において、出発地と目的地との間に予め中間地点を決定するナビゲーションシステムが提案されている。具体的には、出発地と目的地との間に大きな湖等の無道路地域がある場合は、外形に基づいて無道路地域を迂回する中間地点を決定するというものである（例えば、特許文献１を参照。）。特許文献１に記載されている技術によれば、経路探索する前に中間地点を定めておくことにより、経路探索中に推奨する経路の候補となる通路のつながりを伸ばしていく処理において、通路を効率よく伸ばしていくことができるので、経路探索する処理の負担が軽減される。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−３００９３４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１に記載されている発明によれば、無道路地域を物理的に避ける領域を中間地点として設定するのみであり、その設定された地点が必ずしも最適経路の通過地点とは限らない。例えば、無道路地域が川であって、出発地と目的地との間に広大な流域を有している場合には、無道路地域の外形に基づいて迂回する中間地点は川の流域の外に設定される。この場合、その位置は遠方に位置することになる可能性があり、このようなときは適切な中間地点とはならないという問題点がある。
【０００６】
また、出発地と目的地との間に存在する川に橋が複数存在しており橋で区切られた区間を上述した無道路地域ととらえた場合であっても川の蛇行状態によっては、そもそも出発地や目的地が無道路地域の中に含まれてしまう場合がある。この場合、無道路地域の外形に基づく計算だけでは最適な中間地点を設定することができないという問題点がある。
【０００７】
本発明は、２つの地点の間の経路において通行の妨げとなる障害地物を回避する適切な経由地を設定してから最適な経路を設定する経路設定装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、本発明の経路設定装置は、通行の妨げとなる障害地物の位置および形状の情報を含む障害地物データおよび前記障害地物を横断する地点として前記障害地物に関連付けられた横断地点の位置情報を含む横断地点データを含む地図データを記憶する地図データ記憶部と、前記地図データを参照して出発地および目的地の間を結ぶ線分と交差する前記障害地物を抽出する交差障害地物抽出部と、該交差障害地物抽出部が前記交差する障害地物を抽出した場合であって、かつ、該抽出した障害地物と前記線分とが交差する地点が偶数地点である場合には、前記交差する障害地物を迂回したときに経由する迂回地点を、前記出発地および目的地の位置ならびに前記障害地物の位置および形状の情報に基づいて前記交差する障害地物の存在領域近傍に設定する迂回地点設定部と、前記交差障害地物抽出部が前記交差する障害地物を抽出した場合には、前記地図データを参照して前記交差する障害地物を横断する横断地点を抽出する横断地点抽出部と、前記迂回地点設定部が前記迂回地点を設定した場合には、前記迂回地点を前記出発地および目的地の地点の間の経由地として設定し、前記横断地点抽出部が前記横断地点を抽出した場合には、抽出されている前記横断地点を１つずつ選択し、選択した横断地点である選択横断地点を仮の目的地に設定して前記出発地および前記仮の目的地を用いて前記交差障害地物抽出部の処理以降の処理を繰り返す第１の再帰処理を実行させ、該第１の再帰処理において前記障害地物が抽出されないときには前記選択横断地点を前記出発地からの進行先の経由地として設定するとともに、前記選択横断地点を仮の出発地に設定して該仮の出発地および前記目的地を用いて前記交差障害地物抽出部の処理以降の処理を繰り返す第２の再帰処理を実行させ、該第２の再帰処理において前記障害地物が抽出されないときには前記選択横断地点を前記目的地への進行元の経由地として設定し、前記第１の再帰処理または前記第２の再帰処理において前記横断地点が抽出されたときには、該横断地点を選択横断地点として前記第１の再帰処理および前記第２の再帰処理を実行させる経由地設定部と、該経由地設定部が設定した前記経由地の最適な進行順序を求めて前記出発地および目的地の間の最適な経路を設定する経路設定部とを備えるものである。
【０００９】
なお、上述した特徴は、本発明の特徴のすべてを列挙したものではなく、これらを要部とする構成（または方法）もまた発明となり得る。
【発明の効果】
【００１０】
本発明の経路設定装置は、通行の妨げとなる障害地物の位置および形状の情報を含む障害地物データおよび障害地物を横断する地点として障害地物に関連付けられた横断地点の位置情報を含む横断地点データを含む地図データを記憶しており、出発地および目的地の間を結ぶ線分と交差する障害地物が抽出された場合に、交差する状態に応じて、障害地物を迂回する迂回地点や、障害地物を横断する横断地点を求め、迂回地点または横断地点を経由地として経由地の最適な進行順序を求めてから最適な経路を設定するものである。したがって、本発明の経路設定装置によれば、広大な流域を有する川のような障害地物や、蛇行した川のような障害地物であっても、迂回地点や横断地点からなる最適な経由地の進行順序を求めることができる。そして、迂回したり横断したりする経由地とその最適な進行順序を経路の探索をする前に予め求めているので、経路の探索にかかる処理について余分な負担が生じないという利点がある。
【図面の簡単な説明】
【００１１】
【図１】本実施形態のナビゲーションシステムの構成を示すブロック図である。
【図２】本実施形態の経路設定装置の構成を示すブロック図である。
【図３】（ａ）〜（ｄ）は本実施形態のナビゲーションシステムに利用される地図データのデータ構造を示す図である。
【図４】本実施形態のナビゲーションシステムの概略の処理のフローチャートである。
【図５】本実施形態のナビゲーションシステムの経由地を設定する処理のフローチャートである。
【図６】本実施形態のナビゲーションシステムの経由地を設定する処理のフローチャートである。
【図７】本実施形態の経由地設定の一例を示す図である。
【図８】本実施形態の経由地設定の一例を示す図である。
【図９】本実施形態の経由地設定の一例を示す図である。
【図１０】本実施形態の経由地設定の一例を示す図である。
【図１１】本実施形態の経由地設定の一例を示す図である。
【図１２】本実施形態の経由地設定の一例を示す図である。
【図１３】本実施形態の経由地設定の一例を示す図である。
【図１４】本実施形態の経由地設定の一例を示す図である。
【図１５】本実施形態の経路設定処理を説明する図である。
【図１６】本実施形態の経由地設定の他の例を示す図である。
【発明を実施するための形態】
【００１２】
以下、本発明を具体化した実施形態を説明する。
【００１３】
図１に示すように、本実施形態のナビゲーションシステム１は、携帯端末１０およびこの携帯端末１０と情報ネットワークを通して接続される情報センター２０を備える。携帯端末１０は、無線通信部１１、現在位置検出部、画像表示部および装置本体を備える携帯電話であり、歩行者用ナビゲーション端末として利用される。情報センター２０は、データ通信部２３、入力部２１、表示部２２および計算機２４を備える大型コンピュータである。そして、図２に示すように、計算機２４は、地図データ記憶部２４１、地点設定部２４０２、交差障害地物抽出部２４０３、経由地設定部２４０４、横断地点抽出部２４０５、迂回地点設定部２４０６、経路設定部２４０８および画像生成部２４３を備えている。このうち、地点設定部２４０２、交差障害地物抽出部２４０３、経由地設定部２４０４、横断地点抽出部２４０５および迂回地点設定部２４０６および経路設定部２４０８は経路設定装置２４２を構成している。
【００１４】
携帯端末１０を構成する無線通信部１１は、送信機、受信機およびアンテナからなるトランシーバである。また、現在位置検出部は、ＧＰＳ衛星からの電波に基づいて現在位置を検出するＧＰＳ受信器と、ＧＰＳ衛星からの電波を受信しにくい地下街内等は現在位置を検出するために設置された無線局からの近距離の無線受信に基づいて現在位置を求めて現在位置のデータを出力する近距離無線位置検出器とからなる。また、画像表示部は、液晶ディスプレイ等であって画像表示面に通信メニュー画面や地図画像等の画像を表示するデバイスである。そして、装置本体は、専用の計算機を含む各ハードウェアを収納する筐体である。なお、本実施形態の携帯端末１０は、画像表示部の表面がタッチパネルの機能を有しており、ユーザの指定により、目的地、表示したい地図のエリア、縮尺、施設のフロアおよびその階層等を指定することができる。
【００１５】
情報センター２０を構成するデータ通信部２３は、光ファイバーによりインターネットＷと接続する機能を備えており、インターネットＷから無線通信を介して携帯端末１０の無線通信部１１と接続される。また、地図データ記憶部２４１は、フラッシュメモリ、ハードディスク、ＤＶＤまたはブルーレイディスク等の外部記憶装置であり、地図データを記憶している。また、表示部２２は、液晶ディスプレイ等であって画像表示面に画像を表示するデバイスである。また、入力部２１は、キーボードやマウス等であってオペレータ等の指示内容を入力するデバイスである。そして、計算機２４は、コンピュータプログラムや処理条件等が予め記憶されているＲＯＭやＲＡＭ等の内部記憶装置、およびこのコンピュータプログラムを実行するＣＰＵ等からなる大型のコンピュータである。
【００１６】
地図データ記憶部２４１が記憶している地図データは、行政界図、道路図および施設図等を生成するためのポリラインやポリゴンのデータ等の地図表示用データと、車または歩行者が通行可能な通路の接続状態をノードおよびリンクで表現するネットワークデータと、通行の妨げとなる障害地物の位置および形状の情報を含む障害地物データとを含むものである。障害地物データは、障害地物を横断する地点として障害地物に関連付けられた横断地点の位置情報を含む横断地点データと関連付けられている。障害地物は、例えば川等の地理的に大規模なものであって人や車が直接横断することができない地物であり、横断地点は、例えば川を横断するために建設された橋である。なお、本実施形態において、川については車が通行可能な橋の位置で区切った区間を１単位の障害地物としている。
【００１７】
障害地物データは、図３（ａ）に示すように、障害地物を認識するための情報である障害地物ＩＤ、複数の障害地物が連なって構成する連帯障害地物を示す情報である連帯障害地物ＩＤ、障害地物を横断する横断路を認識する情報である横断路ＩＤ、障害地物の長さを示す情報である障害地物長、障害地物同士が接続する地点の情報である障害地物接続点ＩＤ、障害地物の形状を表現するための情報である形状情報、障害地物の存在領域を認識するための情報である外接矩形情報等の情報を含んでいる。本実施形態において、障害地物は形状補間点である形状情報を用いてポリラインとして地図に表示される。
【００１８】
横断地点データは、図３（ｂ）に示すように、上述した横断路ＩＤ、横断路の一方の端点である端点１のノードの情報に相当する端点１ノードＩＤ、横断路の他方の端点である端点２のノードの情報に相当する端点２ノードＩＤ、横断路に含まれるリンク列の各リンクの情報である横断路リンクＩＤ、上述した障害地物接続点ＩＤおよび横断路の通過コストを示す情報である通過コスト等の情報を含んでいる。端点１、２は例えば端の出入口であり、ネットワークデータにおいて同じ位置にノードが対応付けられている。
【００１９】
また、障害地物データは連帯障害地物データとも関連づけられている。連帯障害地物データは、図３（ｃ）に示すように、連帯障害地物ＩＤ、連帯障害地物の名称を示す情報である連帯障害地物名称、連帯障害地物の種類を示す情報である連帯障害地物種類、連帯障害地物を構成する各障害地物の障害地物ＩＤ、連帯障害地物の存在領域を認識するための外接矩形情報等の情報を含んでいる。連帯障害地物種類は、例えば川、崖として登録される。
【００２０】
また、障害地物データは障害地物接続点データとも関連付けられている。障害地物同士が接続する地点である障害地物接続点は、本実施形態においては障害地物として表示されるポリラインの端点に相当し、接続している全ての障害地物の障害地物ＩＤを含んでいる。障害地物接続点データは、図３（ｄ）に示すように、障害地物接続点ＩＤ、障害地物接続点の種別を示す情報である種別、障害地物接続点の位置を示す情報である緯度経度座標、接続している障害地物ＩＤ等の情報を含んでいる。これらの情報は障害地物同士の接続状態を認識可能にする情報である。本実施形態においては、例えば連帯障害地物が川であれば、橋である横断路と障害地物との交点の位置に障害地物接続点が位置するので、種別は「障害地物と横断路との交点」となる。また、１つの障害地物接続点に対して複数の障害地物が接続していることもある。これは、例えば、障害地物が川であるときには、本流に支流が合流している場合であって合流点の位置を障害地物接続点としているとき等が当てはまる。この場合の障害地物接続点の種別は「接続点」として登録される。なお、本実施形態とは異なり、例えば連帯障害地物である川を橋と橋との中間点で区切った区間を１単位の障害地物とする場合の種別も「接続点」として登録される。
【００２１】
データ通信部２３は、携帯端末１０側で指定した出発地および目的地、または携帯端末１０の現在位置のデータを受信する。
【００２２】
地点設定部２４０２は、携帯端末１０側で指定した出発地および目的地の２つの地点を設定して交差障害地物抽出部２４０３へ出力する機能を有する。また、地点設定部２４０２は、後述する経由地設定部から、仮の目的地の情報を受け取った場合には、出発地および仮の目的地の２つの地点を設定して交差障害地物抽出部２４０３へ出力し、仮の出発地の情報を受け取った場合には、目的地および仮の出発地の２つの地点を設定して交差障害地物抽出部２４０３へ出力する。
【００２３】
交差障害地物抽出部２４０３は、地図データを参照して、地点設定部２４０２が設定した出発地および目的地の２つの地点の間を結ぶ線分と交差する障害地物を抽出する機能を有する。本実施形態においては、連帯障害地物データの外接矩形情報または障害地物データの外接矩形情報を参照して、線分と交差している可能性のある障害地物を予め特定するようにしているので、効率的に交差判定を行なうことができる。また、交差障害地物抽出部２４０３は、交差障害地物抽出部２４０３が抽出した線分が交差する障害地物を抽出する機能も有している。
【００２４】
横断地点抽出部２４０５は、地図データを参照して交差する障害地物を横断する横断地点を抽出する機能を有する。本実施形態においては、横断地点抽出部２４０５は、横断路抽出部２４１０および横断路端点抽出部２４１１を備えている。横断路抽出部２４１０は線分が交差する障害地物を横断する横断路を抽出し、横断路端点抽出部２４１１は横断路の端点を横断地点として抽出する。
【００２５】
迂回地点設定部２４０６は、交差する障害地物を迂回したときに経由する迂回地点を、前記出発地および目的地の位置ならびに前記障害地物の位置および形状の情報に基づいて前記交差する障害地物の存在領域近傍に設定する機能を有する。迂回地点設定部２４０６は、交差障害地物抽出部２４０３が線分と交差する障害地物を抽出した場合であって、線分がいずれかの障害地物と交差し、かつ交差する回数が偶数回である場合は、２つの地点は検出された障害地物によって隔てられた領域の同一領域内に存在すると判断できるため、障害地物を横断する横断地点ではなく、障害地物を避けて進行するための迂回地点を設定する。
【００２６】
経由地設定部２４０４は、交差障害地物抽出部２４０３が障害地物を抽出しているか否かを判定する機能を有している。経由地設定部２４０４は、地点設定部２４０２が設定した出発地および目的地の２つの地点の間を結ぶ線分と交差する障害地物を交差障害地物抽出部２４０３により抽出していないと判定した場合は、出発地および目的地の２つの地点について間に経由地が存在しないことを確定し、出発地から目的地への進行順序を設定する。設定している２つの地点について進行順序を設定すると、その２つの地点および進行順序を経由地リストに格納する。
【００２７】
また、経由地設定部２４０４は、交差障害地物抽出部２４０３が障害地物を抽出していると判定した場合は、迂回地点設定部２４０６に対して障害地物に対応する迂回地点を返すように要求し、迂回地点設定部２４０６が迂回地点を設定したときには、迂回地点を出発地および目的地の地点の間の経由地として設定し、出発地から経由地までの進行順序および経由地から目的地までの進行順序を設定する。
【００２８】
さらに、経由地設定部２４０４は、交差障害地物抽出部２４０３が障害地物を抽出していると判定した場合は、横断地点抽出部２４０５に対して障害地物に対応する横断地点を返すように要求し、横断地点抽出部２４０５が横断地点を抽出したときには、横断地点抽出部２４０５から抽出された横断地点を受け取り、抽出した横断地点を横断地点リストに格納する。本実施形態においては、横断地点抽出部２４０５は、線分と交差する障害地物に対応する横断路を抽出し、抽出した横断路の端点を横断地点として返すようにしている。また、本実施形態においては、抽出された障害地物の障害地物ＩＤに関連付けられている障害地物接続点ＩＤによって隣接する障害地物を特定できるので、複数の障害地物から横断路を抽出することができる。なお、このような処理は状況に応じて実行するようにしている。例えば、抽出された障害地物に隣接する障害地物の長さが閾値よりも小さいものであった場合は、隣接する障害地物に対応する横断路も合わせて抽出することとしている。
【００２９】
そして、経由地設定部２４０４は、抽出されている横断地点を横断地点リストから１つずつ選択し、選択した横断地点である選択横断地点を仮の目的地に設定して仮の目的地の情報を地点設定部２４０２へ送る。こうすることにより、地点設定部２４０２が出発地および仮の目的地の２つの地点を設定して交差障害地物抽出部２４０３へ出力し、出発地および仮の目的地を用いて交差障害地物抽出部２４０３の処理以降の処理を繰り返す処理（第１の再帰処理）が実行される。経由地設定部２４０４は、この第１の再帰処理において障害地物が抽出されないときには選択横断地点を出発地からの進行先の経由地として設定する。さらに、経由地設定部２４０４は、同じ選択横断地点を仮の出発地として地点設定部２４０２へ送る。こうすることにより、地点設定部２４０２が目的地および仮の出発地の２つの地点を設定して交差障害地物抽出部２４０３へ出力し、仮の出発地および目的地を用いて交差障害地物抽出部２４０３の処理以降の処理を繰り返す処理（第２の再帰処理）が実行される。経由地設定部２４０４は、この第２の再帰処理において障害地物が抽出されないときには選択横断地点を目的地への進行元の経由地として設定する。このように、経由地設定部２４０４は、仮の目的地または仮の出発地を設定して交差障害地物抽出部２４０３以降の処理を繰り返すように制御する機能を有する。また、経由地設定部２４０４は、第１の再帰処理または第２の再帰処理において横断地点が抽出されたときには、抽出された横断地点を選択横断地点として第１の再帰処理および第２の再帰処理を実行させる。なお、本実施形態においては、選択横断地点とした横断路の一方の端点を仮の目的地とした場合は、選択横断地点の代わりにその横断路の他方の端点を仮の出発地として設定することとしている。経由地設定部２４０４は、第１、第２の再帰処理が終了し、２つの地点の間の進行順序が設定されたときには、その２つの地点および進行順序を経由地リストに格納する。
【００３０】
そして、経由地設定部２４０４は、第１、第２の再帰処理が終了し、横断地点リストにまだ選択されていない横断地点が残っているときには、残っている横断地点から選択した選択横断地点による第１、第２の再帰処理を実行させる。経由地設定部２４０４は、線分と交差する障害地物が抽出されないとき、または横断地点リストに横断地点が残っていないときは、経由地リストに含まれる出発地、経由地、目的地および進行順序の情報を経路設定部２４０８へ出力する。
【００３１】
すなわち、経由地設定部２４０４は、交差障害地物抽出部２４０３が障害地物を抽出していると判定した場合には、地点設定部２４０２に２つの地点を再設定させ、迂回地点を設定するまたは横断地点を抽出する処理を再帰的に繰り返すように制御する機能を有している。本実施形態において、経由地設定部２４０４による再帰的に繰り返す処理は、出発地側から確定していく方向となるように制御する。つまり、横断地点リストから選択横断地点として選択する１つの横断地点は出発地に近いほうから優先して選択していく。
【００３２】
経路設定部２４０８は、地点設定部２４０２が設定した出発地点、目的地点および経由地を、地図データ記憶部２４１に記憶されている地図データを参照して地図上に決定するとともに、ネットワークデータを用いて出発地点から目的地点に到る経路を算出して推奨する経路を設定する機能を有する。
【００３３】
画像生成部２４３は、基準フロアおよび周辺フロアに対応するフロア表示用データに基づいて地図画像を生成し、生成した地図画像のデータをデータ通信部２３へ出力する。
【００３４】
本実施形態の経路設定装置２４２は、通行の妨げとなる障害地物の位置および形状の情報を含む障害地物データおよび障害地物を横断する地点として障害地物に関連付けられた横断地点の位置情報を含む横断地点データを含む地図データを記憶しており、出発地および目的地の間を結ぶ線分と交差する障害地物が抽出された場合に、交差する状態に応じて、障害地物を迂回する迂回地点や、障害地物を横断する横断地点を求め、迂回地点または横断地点を経由地として経由地の最適な進行順序を求めてから最適な経路を設定するものである。したがって、広大な流域を有する川のような障害地物や、蛇行した川のような障害地物であっても、迂回地点や横断地点からなる最適な経由地の進行順序を求めることができる。また、迂回したり横断したりする経由地とその最適な進行順序を経路の探索をする前に予め求めているので、経路の探索にかかる処理について余分な負担が生じないという利点がある。
【００３５】
本実施形態のナビゲーションシステム１の処理について説明する。本実施形態は、現在位置から目的地へ至る経路を設定し、携帯端末１０の現在位置の移動にともなってその都度地図画像を表示するナビゲーションシステムの例である。本実施形態のナビゲーションシステム１は、図４に示すように、出発地および目的地を設定する処理を実行し（ステップＳ４００）、出発地および目的地の２つの地点の間に経由地を設定する処理を実行し（ステップＳ５００）、ステップＳ５００の結果に基づいて出発地から目的地へ至る経路を設定する処理を実行する（ステップＳ６００）。
【００３６】
＜地点設定処理＞
本実施形態のナビゲーションシステム１が、出発地および目的地を設定する処理（ステップＳ４００）の詳細は以下のとおりである。
【００３７】
まず、携帯端末１０側でユーザがタッチパネルを操作することにより目的地を指定する。携帯端末１０は、現在位置検出部により定期的に現在位置を検出しており、ユーザの指定を受け付けると、指定された目的地の情報と現在位置の情報とを無線通信部１１によりインターネットＷを介して配信サーバへ送信する処理を実行する。なお、携帯端末１０は、この後も現在位置を定期的に検出して、そのたびに、最新の現在位置の情報を配信サーバへ送信する。
【００３８】
携帯端末１０がデータを送信する処理が終了すると、配信サーバ側で、データ通信部２３が目的地の情報と現在位置の情報を受信して受信したこれらのデータを経路設定装置の地点設定部２４０２へ出力する処理を実行する。情報センター２０において、計算機２４は、地点設定部２４０２が目的地の情報の基づく目的地および現在位置の情報に基づく出発地の２つの地点を設定する処理を実行する（ステップＳ４００）。図７〜図１５は、それぞれ本実施形態の経由地設定の一例を示す図である。まず、図７に示す本実施形態の経由地設定の一例においては、地図上に出発地Ｓおよび目的地Ｇの２つの地点が設定されている。
【００３９】
＜経由地設定処理＞
次に、本実施形態のナビゲーションシステム１が、地点設定部２４０２により設定された２つの地点の間に経由地を設定する処理（ステップＳ５００）について、図５および図６を用いて詳細に説明する。ステップＳ４００が終了すると、計算機２４は、交差障害地物抽出部２４０３により、地図データを参照して、地点設定部２４０２が設定した出発地Ｓおよび目的地Ｇの２つの地点の間を結ぶ線分と交差する障害地物を抽出する処理を実行する（ステップＳ５０１）。本実施形態の経由地設定の一例においては、図７に示すように、出発地Ｓおよび目的地Ｇの間を結ぶ線分ＳＮ００を引いたときに、線分ＳＮ００と交差する障害地物ＫＷ３が抽出される。障害地物ＫＷ３は連帯障害地物データにおいて連帯障害地物種類が川として登録されている連帯障害地物ＫＷを構成する障害地物ＫＷ１〜ＫＷ４のうちの１つである。障害地物ＫＷ２と障害地物ＫＷ３とは、連帯障害地物ＫＷと横断路ＨＳ２との交点に位置する障害地物接続点（図示せず）で接続しており、障害地物ＫＷ３と障害地物ＫＷ４とは、連帯障害地物ＫＷと横断路ＨＳ１との交点に位置する障害地物接続点（図示せず）で接続している。また、障害地物ＫＷ１と障害地物ＫＷ２とは障害地物接続点ＧＲで接続している。また、障害地物接続点ＧＲは連帯障害地物ＫＷと連帯障害地物ＫＳとの合流点であり、障害地物接続点ＧＲにおいて、連帯障害地物ＫＳを構成する障害地物ＫＳ１、連帯障害地物ＫＷを構成する障害地物ＫＷ１、ＫＳ２が接続している。
【００４０】
ステップＳ５０１が終了すると、計算機２４は、経由地設定部２４０４により、前の処理のときに障害地物が抽出されているか否かを判定する処理を実行する（ステップＳ５０２）。計算機２４は、ステップＳ５０２において、前の処理のときに障害地物が抽出されていないと判定した場合は（ステップＳ５０２：Ｎｏ）、経由地を設定する処理（ステップＳ５００）を終了する。
【００４１】
また、計算機２４は、ステップＳ５０２において、前の処理のときに障害地物が抽出されていると判定した場合は（ステップＳ５０２：Ｙｅｓ）、経由地設定部２４０４により、交差障害地物抽出部２４０３が抽出した障害地物を要求して受け取る処理を実行する（ステップＳ５０３）。
【００４２】
ステップＳ５０３が終了すると、計算機２４は、迂回地点設定部２４０６により、交差する障害地物を迂回したときに経由する迂回地点を設定する処理を実行する（ステップＳ５０４）。具体的には、線分がいずれかの障害地物と交差し、かつ交差する回数が偶数回である場合は迂回地点が設定される。本実施形態において、迂回地点の設定は、設定している２つの地点の両方について障害地物に対する接線を求め、求めた接線同士の交点が障害地物から所定の距離以内にあるときにはこの交点を迂回地点として設定する。具体的には、線分と障害地物との複数の交点のうち、２つの地点の出発地側からみて、奇数番目の交点とその次の交点までの間の障害地物の形状と線分とで囲まれるエリアを全て求め、それらを包含する最小の凸図形を算出し、その凸図形に対して２つの地点から接線を求める。なお、求めた接線同士の交点が障害地物から所定の距離以内にないときには、設定している２つの地点を結ぶ線分に対して平行な障害地物に対する接線を求め、この接線と前に求めた２つの接線との交点を求め、求めた交点の中間点を迂回地点として設定する。
【００４３】
図７に示す本実施形態の経由地設定の一例とは異なる他の例を図１６に示す。図１６に示すように、線分ＳＮ７０と障害地物ＫＷ７との交点Ｐ１、Ｐ２、Ｐ３、Ｐ４がまず抽出される。次に、出発地Ｓからみて奇数番目であるＰ１とその次の交点Ｐ２からなる線分と障害地物ＫＷ７とで囲まれる領域Ａ１を求め、同様にしてＰ３とＰ４からは領域Ａ２を求める。これらＡ１とＡ２を包含する最小の凸図形Ａ３に対して、出発地Ｓおよび目的地Ｇからの接線Ｌ１、Ｌ２がそれぞれ求められる。Ｌ１とＬ２の交点であるＤ７が障害地物ＫＷ７から所定の距離よりも離れていると判断された場合は、線分ＳＮ７０と平行でかつ前述の領域Ａ３と接している線Ｌ３を求め、Ｌ１、Ｌ２との交点の中間点Ｄ８を迂回地点として設定する。
【００４４】
本実施形態の経由地設定の一例においては、図８に示すように、障害地物ＫＷに対する接線ＴＧ１１，ＴＧ１２の交点Ｄ１が迂回地点として設定される。ステップＳ５０４が終了すると、計算機２４は、経由地設定部２４０４により、前の処理のときに迂回地点が設定されているか否かを判定する処理を実行する（ステップＳ５０５）。
【００４５】
計算機２４は、ステップＳ５０５において、迂回地点が設定されていないと判定した場合は（ステップＳ５０５：Ｎｏ）、ステップＳ５０７へ移行する。また、計算機２４は、ステップＳ５０５において、迂回地点が設定されていると判定した場合は（ステップＳ５０５：Ｙｅｓ）、経由地設定部２４０４により、迂回地点を、設定している２つの地点の間で経由する経由地として設定する処理を実行する（ステップＳ５０６）。なお、計算機２４は、経由地設定部２４０４により、出発地から経由地までの進行順序および経由地から目的地までの進行順序も設定する。本実施形態の経由地設定の一例においては、ステップＳ５０４の処理によって設定されている図８に示す迂回地点Ｄ１が経由地Ｄ１として設定され、出発地Ｓから経由地Ｄ１までの進行順序および経由地Ｄ１から目的地Ｇまでの進行順序も設定される。このとき、２つの地点のうちの目的地側は最終到着地の目的地であるため、出発地Ｓ−経由地Ｄ１−目的地Ｇの順の１つの経路が確定する。
【００４６】
ステップＳ５０６が終了すると、計算機２４は、経由地設定部２４０４により、横断地点抽出部２４０５に対して障害地物に対応する横断地点を返すように要求し、横断地点抽出部２４０５により、交差する障害地物を横断する横断地点を抽出して経由地設定部２４０４へ返す。そして、計算機２４は、経由地設定部２４０４により、抽出した横断地点からなる横断地点リストを作成して格納する処理を実行する（ステップＳ５０７）。本実施形態においては、交差する障害地物に関連付けて登録されている横断路を特定し、さらに、特定した横断路に関連付けて登録されている横断路の端点を特定してこれを横断地点として抽出する。例えば、本実施形態の経由地設定の一例においては、図９に示すように、障害地物ＫＷには橋である横断路ＨＳ１，ＨＳ２が関連付けて登録されている。また、横断路ＨＳ１には端点ＨＳ１Ｔ１，ＨＳ１Ｔ２が関連付けて登録されており、横断路ＨＳ２には端点ＨＳ２Ｔ１，ＨＳ２Ｔ２が関連付けて登録されている。なお、本実施形態においては、特定したすべての横断路の端点についてそれぞれ出発地Ｓとの間を結ぶ線分ＳＮ０１，ＳＮ０２，ＳＮ０３，ＳＮ０４と交差する障害地物を抽出するとともに障害地物と交差する回数を解析し、このうち線分が交差する回数が奇数回である横断路の端点は出発地と障害地物によって隔てられているとして横断地点リストには格納しない。図９に示す本実施形態の経由地設定の一例においては、経由地設定部２４０４は、横断地点ＨＳ１Ｔ１，ＨＳ２Ｔ２からなる横断地点リストを作成して格納する。
【００４７】
ステップＳ５０７が終了すると、計算機２４は、経由地設定部２４０４により、抽出されている横断地点を横断地点リストから１つずつ選択する処理を実行する（ステップＳ５０８）。選択した横断地点を選択横断地点とする。本実施形態においては、横断地点リストから選択横断地点として選択する１つの横断地点は出発地に近いほうから優先して選択していくようにしているので、経由地設定の一例においては、図１０に示すように、まず、横断地点ＨＳ１Ｔ１を選択することになる。
【００４８】
第１の再帰処理（出発地Ｓ−横断地点ＨＳ１Ｔ１）：
ステップＳ５０８が終了すると、計算機２４は、経由地設定部２４０４により、抽出されている横断地点を横断地点リストから１つずつ選択し、選択した横断地点である選択横断地点を仮の目的地に設定して仮の目的地の情報を地点設定部２４０２へ送り、地点設定部２４０２により、出発地および仮の目的地の２つの地点を設定して交差障害地物抽出部２４０３へ出力し、ステップＳ５００の処理を繰り返す第１の再帰処理を実行する（ステップＳ５０９）。具体的には、本実施形態の経由地設定の一例においては、図１０に示す、出発地Ｓおよび仮の目的地とした選択横断地点ＨＳ１Ｔ１の２つの地点を用いてステップＳ５００の再帰処理が実行される。なお、図１０に示す場合は、ステップＳ５０２において２つの地点の間を結ぶ線分ＳＮ１１と交差する障害地物が抽出されないので選択横断地点ＨＳ１Ｔ１を出発地Ｓからの進行先の経由地として設定する。
【００４９】
第２の再帰処理（横断地点ＨＳ１Ｔ１−目的地Ｇ）：
ステップＳ５０９が終了すると、計算機２４は、経由地設定部２４０４により、同じ選択横断地点ＨＳ１Ｔ１を仮の出発地として地点設定部２４０２へ送り、地点設定部２４０２により、目的地および仮の出発地の２つの地点を設定して交差障害地物抽出部２４０３へ出力し、ステップＳ５００の処理を繰り返す第２の再帰処理を実行する（ステップＳ５１０）。具体的には、本実施形態の経由地設定の一例においては、図１１に示す、目的地Ｇおよび仮の出発地とした選択横断地点ＨＳ１Ｔ１の２つの地点を用いてステップＳ５００の再帰処理が実行される。なお、このとき、横断地点ＨＳ１Ｔ１はステップＳ５０９において出発地Ｓからの進行順序が設定されているので、出発地Ｓから横断路ＨＳ１における他方の端点ＨＳ１Ｔ２に至る進行順序が確定するので、その結果、横断地点ＨＳ１Ｔ２が仮の出発地となって第２の再帰処理が実行される。図１１に示すように、第２の再帰処理におけるステップＳ５０１において、この２つの地点の間を結ぶ線分ＳＮ１２からは交差する障害地物ＫＷ３が抽出される。そして、第２の再帰処理におけるステップＳ５０７において、Ｕターンする方向となる横断地点ＨＳ１Ｔ１や線分が交差する回数が奇数回である横断地点ＨＳ２Ｔ２は横断地点リストに追加せず、線分が交差する回数が０である横断地点ＨＳ２Ｔ１が横断地点リストに追加して格納される。
【００５０】
第１の再帰処理（横断地点ＨＳ１Ｔ２−横断地点ＨＳ２Ｔ１）：
本実施形態の経由地設定の一例においては、上述した第２の再帰処理（横断地点ＨＳ１Ｔ１−目的地Ｇ）において横断地点が抽出されているので、抽出された横断地点を選択横断地点として第１の再帰処理および第２の再帰処理を実行させることになる。ステップＳ５０８が終了すると、ステップＳ５０９において、横断地点ＨＳ２Ｔ１を選択し、選択横断地点ＨＳ２Ｔ１を仮の目的地とする２つの地点を用いた第１の再帰処理が実行される。この場合の出発地は横断地点ＨＳ２Ｔ１を算出するときに仮の出発地として用いた横断地点ＨＳ１Ｔ２になる。この２つの地点については、図１２に示すように、第１の再帰処理におけるステップＳ５０２において２つの地点の間を結ぶ線分ＳＮ２１と交差する障害地物が抽出されないので、選択横断地点ＨＳ２Ｔ１をこのときに出発地となっている横断地点ＨＳ１Ｔ２からの進行先の経由地として設定する。
【００５１】
第２の再帰処理（横断地点ＨＳ２Ｔ２−目的地Ｇ）：
本実施形態の経由地設定の一例においては、ステップＳ５０９が終了すると、ステップＳ５１０において、選択横断地点ＨＳ２Ｔ１を仮の出発地とする２つの地点を用いて第２の再帰処理が実行される。この場合、選択横断地点ＨＳ２Ｔ１は直前のステップＳ５０９において目的地Ｓからの進行順序が確定しているので、横断路ＨＳ２における他方の端点ＨＳ２Ｔ２に至る進行順序が確定するので、その結果、横断地点ＨＳ２Ｔ２が仮の出発地となって第２の再帰処理が実行される。この２つの地点については、図１３に示すように、第２の再帰処理におけるステップＳ５０２において２つの地点を結ぶ線分ＳＮ２２と交差する障害地物が抽出されないので、選択横断地点ＨＳ２Ｔ２を目的地Ｇへの進行元の経由地として設定する。
【００５２】
ステップＳ５０９およびステップＳ５１０の再帰処理が実行され、経由地設定部２４０４により、設定されている２つの地点およびその進行順序を経由地リストへ追加して格納する処理を実行する（ステップＳ５１１）。本実施形態の経由地設定の一例においては、出発地Ｓ−横断地点ＨＳ１Ｔ１−横断地点ＨＳ１Ｔ２−横断地点ＨＳ２Ｔ１−横断地点ＨＳ２Ｔ２−目的地Ｇの順の１つの経路が確定され、経由地リストに追加される。
【００５３】
ステップＳ５１１が終了すると、計算機２４は、経由地設定部２４０４により、本実施形態において経由地の候補となる横断地点を格納している横断地点リストに横断地点が残っているか否かを判定する処理を実行する（ステップＳ５１２）。計算機２４は、ステップＳ５１２において、横断地点リストに横断地点が残っていると判定した場合は（ステップＳ５１２：Ｙｅｓ）、ステップＳ５０８へ移行する。本実施形態の経由地設定の一例においては、ここまでの処理が実行された時点で、横断地点リストに横断地点ＨＳ２Ｔ２が残っているので、続けて、この横断地点ＨＳ２Ｔ２を選択横断地点として第１、第２の再帰処理が実行されることになる。
【００５４】
横断地点ＨＳ２Ｔ２を算出するときに用いた出発地および目的地はユーザの操作に基づいた出発地Ｓおよび目的地Ｇである。本実施形態の経由地設定の一例においては、図１４に示すように、第１の再帰処理においては、ステップＳ５０２において２つの地点を結ぶ線分ＳＮ３１と交差する障害地物ＫＷが抽出され、かつ交差する地点が偶数地点であるため、ステップＳ５０４において出発地Ｓとの間に迂回地点Ｄ３が設定され、これがステップＳ５０６において経由地Ｄ３として設定される。これにより、出発地Ｓ−経由地Ｄ３−横断地点ＨＳ２Ｔ２の進行順序が確定する。そして、次のステップＳ５０７においては、横断地点ＨＳ１Ｔ１が横断地点リストに格納される。なお、横断地点ＨＳ１Ｔ１が横断地点リストに格納された場合、先述したように、出発地Ｓ−横断地点ＨＳ１Ｔ１−横断地点ＨＳ１Ｔ２−横断地点ＨＳ２Ｔ１−横断地点ＨＳ２Ｔ２の順の１つの経路が確定することになる。次に、仮の目的地である横断地点ＨＳ２Ｔ２の他方の端点であるＨＳ２T１が仮の出発地となるが、その後の再帰処理を行なって得られる経路は出発地Sへ戻る経路となる。従って、これらの経路順は経由地リストに追加されない。
【００５５】
ステップＳ５１２において、横断地点リストに横断地点が残っていないと判定した場合は（ステップＳ５１２：Ｎｏ）、計算機２４は、経由地設定部２４０４により、経由地リストを確定して経由地リストに含まれる出発地、経由地、目的地および進行順序の情報を経路設定部２４０８へ出力する処理を実行し、しかる後に、経由地を設定する処理（ステップＳ５００）を終了する。本実施形態の経由地設定の一例においては、ここまでの処理が実行された時点で、出発地Sから目的地Gへの経由地設定における横断地点リストが空であるため、経由地設定を終了する。
【００５６】
＜経路設定処理＞
次に、本実施形態のナビゲーションシステム１において、地点設定部により確定された経由地リストに基づいて出発地から目的地へ至る経路を設定する処理（ステップＳ６００）について詳細に説明する。本実施形態においては、最初に設定された出発地および目的地の２地点間について障害地物を横断したり避けたりして到達できる進行順序が設定されている経由地リストを全て取得することとしており、取得した進行順序が確定している経由地リストに対応する経由地進行パターンの全てについて経路探索処理を行い、最も通過コストが低くなる最適な進行順序の経路を設定する。本実施形態の経由地設定の一例においては、図１５に示すように、上述した経由地を設定する処理によって設定された出発地Ｓ−経由地Ｄ１−目的地Ｇの順の１つの経路、または出発地Ｓ−横断地点ＨＳ１Ｔ１−横断地点ＨＳ１Ｔ２−横断地点ＨＳ２Ｔ１−横断地点ＨＳ２Ｔ２−目的地Ｇの順のもう１つの経路についてそれぞれ経路探索を行ない、最も通過コストが低くなる最適な経路を設定する。
【００５７】
また、設定された迂回地点は、横断地点と異なり、その地点に確実に到達しなければならないものではなく、あくまで障害地物を効率よく避けるための目安となる領域とする。図１５に示すように、経由地として設定した迂回地点Ｄ１を中心とした所定の領域Ｄ１Ｗを迂回地点到達領域Ｄ１Ｗとして設けることで、障害地物ＫＷを避けられる程度に経路の通路が延びたところで、迂回地点Ｄ１に到達したものとして次の経由地へ処理を移す事ができる。
【００５８】
＜その他＞
なお、本発明は上述の実施形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々の変更、改良が可能である。例えば、上述した実施形態においては、ステップS５０８において、進行順序において出発地に近いほうから横断地点を取り出すようにしているが、例えば、進行順序において目的地に近いほうから横断地点を取り出すようにしてもよく、また、ランダムに取り出すようにしてもよい。
【００５９】
また、経由地間の線分距離の合計値によって２点間の経路の概算コストを算出し、それによって１つに絞られた経由地進行パターンに関してのみ、経路探索を行うことも可能である。例えば、最初に設定された出発地および目的地の２地点間について障害地物を避けて到達できる経由地進行パターンを全て取得した後、それぞれの経由地進行パターンについて上述した概算コストを算出し、最も概算コストの小さい経由地進行パターンのみを経路設定部へ出力することもできる。
【００６０】
また、例えば、ある２地点間において横断地点が複数あるなどの理由により複数の経路が候補となる場合は、上述の概算コストが最も小さい経路を構成する経由地のみをその２地点間の経由地として確定することもできる。
【００６１】
また、上述した実施形態においては、横断路端点抽出部が抽出する横断路の端点の情報は、予め整備されたデータとして保持しているが、障害地物と横断路の交点の情報から、地図データを参照して利用者の通行可能な経路を辿ってその都度抽出しても良い。
【００６２】
また、上述した実施形態においては、横断地点データには、障害地物を横断する横断路とその端点の情報を含んでおり、線分と交差する障害地物に対応する横断路を抽出し、抽出した横断路の端点を横断地点としているが、横断路のようなデータを持たず、障害地物上に１点の横断地点を登録しておいて、このような簡略化した横断地点を用いて経由地を設定するナビゲーションシステムとすることもできる。
【００６３】
また、上述した実施形態においては、経路順の確定できない横断地点に関し、２つの地点からなる線分が障害地物と交差するとき、その障害地物ＩＤと交差回数が、最初に設定された出発地と目的地を結ぶ線分で得られた障害地物の障害地物ＩＤと交差回数に対し、同一障害地物ＩＤでかつ交差回数が同一以上である場合は横断地点リストに加えないとすることもできる。
【００６４】
また、上述した実施形態においては、２つの地点により迂回地点が設定された場合、迂回地点を経由地として確定し、その後に抽出される横断地点については経由地としてそのまま確定するのではなく、迂回地点から横断地点までの概略コストや障害地物との交差回数が、迂回地点から目的地までの概算コストより明らかに大きい場合や、障害地物との交差回数が極端に大きい場合には、横断地点を経由地として確定せず、再帰処理を中断することもできる。
【符号の説明】
【００６５】
２３・・・データ通信部
２４・・・計算機
２４１・・・地図データ記憶部
２４０３・・・交差障害地物抽出部
２４０４・・・経由地設定部
２４０５・・・横断地点抽出部
２４０６・・・迂回地点設定部
２４１０・・・横断路抽出部
２４１１・・・横断路端点抽出部
２４２・・・経路設定装置
【特許請求の範囲】
【請求項１】
通行の妨げとなる障害地物の位置および形状の情報を含む障害地物データおよび前記障害地物を横断する地点として前記障害地物に関連付けられた横断地点の位置情報を含む横断地点データを含む地図データを記憶する地図データ記憶部と、
前記地図データを参照して出発地および目的地の間を結ぶ線分と交差する前記障害地物を抽出する交差障害地物抽出部と、
該交差障害地物抽出部が前記交差する障害地物を抽出した場合であって、かつ、該抽出した障害地物と前記線分とが交差する地点が偶数地点である場合には、前記交差する障害地物を迂回したときに経由する迂回地点を、前記出発地および目的地の位置ならびに前記障害地物の位置および形状の情報に基づいて前記交差する障害地物の存在領域近傍に設定する迂回地点設定部と、
前記交差障害地物抽出部が前記交差する障害地物を抽出した場合には、前記地図データを参照して前記交差する障害地物を横断する横断地点を抽出する横断地点抽出部と、
前記迂回地点設定部が前記迂回地点を設定した場合には、前記迂回地点を前記出発地および目的地の地点の間の経由地として設定し、前記横断地点抽出部が前記横断地点を抽出した場合には、抽出されている前記横断地点を１つずつ選択し、選択した横断地点である選択横断地点を仮の目的地に設定して前記出発地および前記仮の目的地を用いて前記交差障害地物抽出部の処理以降の処理を繰り返す第１の再帰処理を実行させ、該第１の再帰処理において前記障害地物が抽出されないときには前記選択横断地点を前記出発地からの進行先の経由地として設定するとともに、前記選択横断地点を仮の出発地に設定して該仮の出発地および前記目的地を用いて前記交差障害地物抽出部の処理以降の処理を繰り返す第２の再帰処理を実行させ、該第２の再帰処理において前記障害地物が抽出されないときには前記選択横断地点を前記目的地への進行元の経由地として設定し、前記第１の再帰処理または前記第２の再帰処理において前記横断地点が抽出されたときには、該横断地点を選択横断地点として前記第１の再帰処理および前記第２の再帰処理を実行させる経由地設定部と、
該経由地設定部が設定した前記経由地の最適な進行順序を求めて前記出発地および目的地の間の最適な経路を設定する経路設定部と
を備える経路設定装置。
【請求項２】
請求項１に記載の経路設定装置であって、
前記地図データは、障害地物を横断する横断路および該横断路の端点の情報を含んでおり、
前記横断地点抽出部は、前記線分が交差する障害地物を横断する前記横断路を抽出する横断路抽出部と、前記横断路の前記端点を前記横断地点として抽出する横断路端点抽出部と
を備えることを特徴とする経路設定装置。
【請求項３】
請求項１に記載の経路設定装置であって、
前記地図データは、複数の前記障害地物からなるものであって当該障害地物同士の接続状態を認識可能な情報を含んでおり、
前記横断地点抽出部は、前記交差障害地物抽出部が抽出した前記障害地物と接続する前記障害地物を横断する前記横断地点を追加して抽出することを特徴とする経路設定装置。
【請求項１】
通行の妨げとなる障害地物の位置および形状の情報を含む障害地物データおよび前記障害地物を横断する地点として前記障害地物に関連付けられた横断地点の位置情報を含む横断地点データを含む地図データを記憶する地図データ記憶部と、
前記地図データを参照して出発地および目的地の間を結ぶ線分と交差する前記障害地物を抽出する交差障害地物抽出部と、
該交差障害地物抽出部が前記交差する障害地物を抽出した場合であって、かつ、該抽出した障害地物と前記線分とが交差する地点が偶数地点である場合には、前記交差する障害地物を迂回したときに経由する迂回地点を、前記出発地および目的地の位置ならびに前記障害地物の位置および形状の情報に基づいて前記交差する障害地物の存在領域近傍に設定する迂回地点設定部と、
前記交差障害地物抽出部が前記交差する障害地物を抽出した場合には、前記地図データを参照して前記交差する障害地物を横断する横断地点を抽出する横断地点抽出部と、
前記迂回地点設定部が前記迂回地点を設定した場合には、前記迂回地点を前記出発地および目的地の地点の間の経由地として設定し、前記横断地点抽出部が前記横断地点を抽出した場合には、抽出されている前記横断地点を１つずつ選択し、選択した横断地点である選択横断地点を仮の目的地に設定して前記出発地および前記仮の目的地を用いて前記交差障害地物抽出部の処理以降の処理を繰り返す第１の再帰処理を実行させ、該第１の再帰処理において前記障害地物が抽出されないときには前記選択横断地点を前記出発地からの進行先の経由地として設定するとともに、前記選択横断地点を仮の出発地に設定して該仮の出発地および前記目的地を用いて前記交差障害地物抽出部の処理以降の処理を繰り返す第２の再帰処理を実行させ、該第２の再帰処理において前記障害地物が抽出されないときには前記選択横断地点を前記目的地への進行元の経由地として設定し、前記第１の再帰処理または前記第２の再帰処理において前記横断地点が抽出されたときには、該横断地点を選択横断地点として前記第１の再帰処理および前記第２の再帰処理を実行させる経由地設定部と、
該経由地設定部が設定した前記経由地の最適な進行順序を求めて前記出発地および目的地の間の最適な経路を設定する経路設定部と
を備える経路設定装置。
【請求項２】
請求項１に記載の経路設定装置であって、
前記地図データは、障害地物を横断する横断路および該横断路の端点の情報を含んでおり、
前記横断地点抽出部は、前記線分が交差する障害地物を横断する前記横断路を抽出する横断路抽出部と、前記横断路の前記端点を前記横断地点として抽出する横断路端点抽出部と
を備えることを特徴とする経路設定装置。
【請求項３】
請求項１に記載の経路設定装置であって、
前記地図データは、複数の前記障害地物からなるものであって当該障害地物同士の接続状態を認識可能な情報を含んでおり、
前記横断地点抽出部は、前記交差障害地物抽出部が抽出した前記障害地物と接続する前記障害地物を横断する前記横断地点を追加して抽出することを特徴とする経路設定装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２０１２−１８９４７１（Ｐ２０１２−１８９４７１Ａ）
【公開日】平成２４年１０月４日（２０１２．１０．４）
【国際特許分類】
【出願番号】特願２０１１−５３８４０（Ｐ２０１１−５３８４０）
【出願日】平成２３年３月１１日（２０１１．３．１１）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
【公開日】平成２４年１０月４日（２０１２．１０．４）
【国際特許分類】
【出願日】平成２３年３月１１日（２０１１．３．１１）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
[ Back to top ]