(57)【要約】【課題】地図上の移動可能域に適切な経路情報を生成することができる。【解決手段】三角形分割部３２が、地図上の移動物の移動可能域に対して、ドロネー三角形分割を行い、経路ノード生成部３４が、ドロネー三角形分割によって得られた三角形の各々に対して、三角形が、地図上の地物の端を含まない場合、又は、２辺に地図上の地物の端を含む場合、三角形に経路ノードを生成せず、三角形が、１辺のみに地図上の地物の端を含む場合、三角形に経路ノードを生成する。ノード接続部３６が、隣り合う三角形の各々の前記経路ノードをリンクで結合することにより、移動可能域の経路情報を生成する。【選択図】図３
2020074060.tif 000002
【特許請求の範囲】
【請求項１】
経路ノード、及び前記経路ノード間を結合したリンクで表される、地図上の移動物の移動可能域の経路情報に基づいて、前記経路ノードの各々について、前記経路ノードを挟むリンクで形成されるリンク角が閾値以上である場合、前記経路ノードを削除し、前記削除された前記経路ノードを挟むリンクの各々の残りの経路ノード間を結合したリンクを生成し、前記削除された前記経路ノードを挟むリンクを削除する
経路情報生成装置。
【請求項２】
経路ノード、及び前記経路ノード間を結合したリンクで表される、地図上の移動物の移動可能域の経路情報に基づいて、前記経路ノードの各々について、前記経路ノードを挟むリンクで形成されるリンク角が閾値以上である場合、前記経路ノードを削除し、前記削除された前記経路ノードを挟むリンクの各々の残りの経路ノード間を結合したリンクを生成し、前記削除された前記経路ノードを挟むリンクを削除する
経路情報生成方法。
【請求項３】
コンピュータを、請求項１記載の経路情報生成装置を構成する各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地図上の移動可能域の経路情報を生成するための経路情報生成装置、経路結合装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
従来より、地図上に経路情報を生成する技術が知られている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】”Automatic Extraction of Improved Geometrical Network Model from CityGML for Indoor navigation”＜インターネット検索：https://3d.bk.tudelft.nl/pdfs/FilippoMortari_thesis.pdf  検索日：2016/05/10＞
【発明の概要】
【発明が解決しようとする課題】
【０００４】
屋内地図と屋外地図を結合する場合、屋外地図には予め経路が引かれていることが多いが、屋内地図で経路が引かれることはまれである。
【０００５】
そのため、屋内地図と屋外地図を結合の際には、屋内地図に経路を生成する必要があり、生成した経路を既存の経路に接続する必要がある。
【０００６】
本発明は、上記の事情を鑑みてなされたものであり、地図上の移動可能域に適切な経路情報を生成することができる経路情報生成装置、方法、及びプログラムを提供することを目的とする。
【０００７】
また、経路情報を適切に結合することができる経路結合装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するために、第１の発明に係る経路情報生成装置は、地図上の移動物の移動可能域に対して、ドロネー三角形分割を行う三角形分割部と、前記三角形分割部によるドロネー三角形分割によって得られた三角形の各々に対して、前記三角形が、地図上の地物の端を含まない場合、又は、２辺に地図上の地物の端を含む場合、前記三角形に経路ノードを生成せず、前記三角形が、１辺のみに地図上の地物の端を含む場合、前記三角形に経路ノードを生成する経路ノード生成部と、前記経路ノード生成部によって生成された、隣り合う三角形の各々の前記経路ノードをリンクで結合することにより、前記移動可能域の経路情報を生成するノード接続部と、を含んで構成されている。
【０００９】
また、第２の発明に係る経路情報生成方法は、三角形分割部が、地図上の移動物の移動可能域に対して、ドロネー三角形分割を行い、経路ノード生成部が、前記三角形分割部によるドロネー三角形分割によって得られた三角形の各々に対して、前記三角形が、地図上の地物の端を含まない場合、又は、２辺に地図上の地物の端を含む場合、前記三角形に経路ノードを生成せず、前記三角形が、１辺のみに地図上の地物の端を含む場合、前記三角形に経路ノードを生成し、ノード接続部が、前記経路ノード生成部によって生成された、隣り合う三角形の各々の前記経路ノードをリンクで結合することにより、前記移動可能域の経路情報を生成する。
【００１０】
第３の発明に係る経路情報生成装置は、地図上の移動物の移動可能域に対して、ドロネー三角形分割を行う三角形分割部と、前記三角形分割部によるドロネー三角形分割によって得られた三角形の各々に対して、前記三角形が、地図上の地物の端を含まない場合、又は、２辺に地図上の地物の端を含む場合、前記三角形の重心に経路ノードを生成し、前記三角形が、１辺のみに地図上の地物の端を含む場合、前記三角形の前記１辺以外の２辺の各々の等分点間を結んだ直線の中点に経路ノードを生成する経路ノード生成部と、前記経路ノード生成部によって生成された、隣り合う三角形の各々の前記経路ノードをリンクで結合することにより、前記移動可能域の経路情報を生成するノード接続部と、を含んで構成されている。
【００１１】
第４の発明に係る経路情報生成方法は、三角形分割部が、地図上の移動物の移動可能域に対して、ドロネー三角形分割を行い、経路ノード生成部が、前記三角形分割部によるドロネー三角形分割によって得られた三角形の各々に対して、前記三角形が、地図上の地物の端を含まない場合、又は、２辺に地図上の地物の端を含む場合、前記三角形の重心に経路ノードを生成し、前記三角形が、１辺のみに地図上の地物の端を含む場合、前記三角形の前記１辺以外の２辺の各々の等分点間を結んだ直線の中点に経路ノードを生成し、ノード接続部が、前記経路ノード生成部によって生成された、隣り合う三角形の各々の前記経路ノードをリンクで結合することにより、前記移動可能域の経路情報を生成する。
【００１２】
このように、第１の発明〜第４の発明によれば、地図上の移動物の移動可能域に対して、ドロネー三角形分割を行い、三角形の各々に対して、経路ノードを生成し、リンクで結合して、移動可能域の経路情報を生成することにより、地図上の移動可能域に適切な経路情報を生成することができる。
【００１３】
第５の発明に係る経路結合装置は、地図上の移動物の移動可能域に対して、経路ノード、及び前記経路ノード間を結合したリンクで表される第一の経路情報を生成する経路情報生成部と、前記第一の経路情報の前記移動可能域の予め定められた出入り口を介して、前記第一の経路情報の接続先となる第二の経路情報であって、前記経路ノード及び前記リンクで表される第二の経路情報と、前記経路情報生成部によって生成された前記第一の経路情報とを結合する経路情報結合部と、を含んで構成されている。
【００１４】
第６の発明に係る経路結合方法は、経路情報生成部が、地図上の移動物の移動可能域に対して、経路ノード、及び前記経路ノード間を結合したリンクで表される第一の経路情報を生成し、経路情報結合部が、前記第一の経路情報の前記移動可能域の予め定められた出入り口を介して、前記第一の経路情報の接続先となる第二の経路情報であって、前記経路ノード及び前記リンクで表される第二の経路情報と、前記経路情報生成部によって生成された前記第一の経路情報とを結合する。
【００１５】
このように、第５の発明及び第６の発明によれば、出入口ノードを介して、第一の経路情報と第二の経路情報とを結合することにより、経路情報を適切に結合することができる。
【００１６】
第７の発明に係る経路情報生成装置は、経路ノード、及び前記経路ノード間を結合したリンクで表される、地図上の移動物の移動可能域の経路情報に基づいて、前記経路ノードの各々について、前記経路ノードを挟むリンクで形成されるリンク角が閾値以上である場合、前記経路ノードを削除し、前記削除された前記経路ノードを挟むリンクの各々の残りの経路ノード間を結合したリンクを生成し、前記削除された前記経路ノードを挟むリンクを削除する。
【００１７】
第８の発明に係る経路情報生成方法は、経路ノード、及び前記経路ノード間を結合したリンクで表される、地図上の移動物の移動可能域の経路情報に基づいて、前記経路ノードの各々について、前記経路ノードを挟むリンクで形成されるリンク角が閾値以上である場合、前記経路ノードを削除し、前記削除された前記経路ノードを挟むリンクの各々の残りの経路ノード間を結合したリンクを生成し、前記削除された前記経路ノードを挟むリンクを削除する。
【００１８】
このように、第７の発明及び第８の発明によれば、経路情報の経路ノードの各々について、経路ノードを挟むリンクで形成されるリンク角に応じて、経路ノードを削除することにより、地図上の移動可能域に適切な経路情報を生成することができる。
【００１９】
また、第９の発明のプログラムは、コンピュータを、上記の経路情報生成装置又は経路結合装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００２０】
以上説明したように、本発明の経路情報生成装置、方法、及びプログラムによれば、地図上の移動可能域に適切な経路情報を生成することができる、という効果が得られる。
【００２１】
また、本発明の経路結合装置、方法、及びプログラムによれば、経路情報を適切に結合することができる、という効果が得られる。
【図面の簡単な説明】
【００２２】
【図１】屋内経路の生成及び経路の結合の例を示す図である。
【図２】本発明の第１の実施の形態における経路結合装置のブロック図である。
【図３】本発明の第１の実施の形態における経路結合装置の経路情報生成部のブロック図である。
【図４】ドロネー三角形分割を行った結果の例を示す図である。
【図５】三角形に経路ノードを生成した結果の例を示す図である。
【図６】三角形に経路ノードを生成する方法を説明するための図である。
【図７】（Ａ）リンク角が閾値以上の場合にノードを削除する方法を説明するための図、及び（Ｂ）リンク角が閾値未満の場合にノードをそのまま残すことを説明するための図である。
【図８】ノードを削減した結果の例を示す図である。
【図９】ノード間をリンクで結合した結果の例を示す図である。
【図１０】本発明の第１の実施の形態における経路結合装置の経路情報結合部のブロック図である。
【図１１】出入口ノードを生成した結果の例を示す図である。
【図１２】出入口ノードと経路ノードとを結合した結果の例を示す図である。
【図１３】（Ａ）出入口ノード範囲内に経路ノードがない場合の例を示す図、（Ｂ）出入口ノードからリンクに垂線を引いた結果の例を示す図、及び（Ｃ）出入口ノードとノードとを結合した結果の例を示す図である。
【図１４】出入口ノードと経路ノードとを結合した結果の例を示す図である。
【図１５】（Ａ）出入口ノード範囲内に経路ノードがない場合の例を示す図、（Ｂ）出入口ノードからリンクに垂線を引いた結果の例を示す図、及び（Ｃ）出入口ノードとノードとを結合した結果の例を示す図である。
【図１６】本発明の第１の実施の形態における経路結合装置の経路結合処理ルーチンを示すフローチャートである。
【図１７】本発明の第１の実施の形態における経路結合装置の経路情報を生成する処理の流れを示すフローチャートである。
【図１８】本発明の第１の実施の形態における経路結合装置の経路情報を結合する処理の流れを示すフローチャートである。
【図１９】ドロネー三角形分割を行った結果の例を示す図である。
【図２０】本発明の第３の実施の形態における経路結合装置の経路情報生成部のブロック図である。
【図２１】ドロネー三角形分割を行った結果と表の例を示す図である。
【図２２】表の例を示す図である。
【図２３】表の例を示す図である。
【図２４】三角形の形状を更新する方法を説明するための図である。
【図２５】表の例を示す図である。
【図２６】三角形の形状及び表を更新する方法を説明するための図である。
【図２７】三角形の形状及び表を更新した結果の例を示す図である。
【図２８】多角形に経路ノードを生成する方法を説明するための図である。
【図２９】三角形を結合する処理を行った結果の例を示す図である。
【図３０】本発明の第３の実施の形態における経路結合装置の三角形を結合する処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００２３】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２４】
＜概要＞
本発明の実施の形態に係る経路結合装置は、屋内地図と屋外地図を結合する際に屋内地図に経路を生成する必要があり、生成した経路を既存の経路に接続する必要があるという背景に基づき、図１に示すように、屋内経路の自動生成と、屋内経路と屋外経路との自動接続を行うものである。
【００２５】
ここで、以降で使用する言葉の定義を説明する。歩行可能域は、建物の廊下など、人が歩行可能な領域であり、移動可能域の一例である。地物は、壁や廊下のほか、柱、店舗、トイレ、エスカレータ、立ち入り禁止区域など、地図上に描かれるあらゆるものを総称したものである。ポリゴンは、壁、廊下など、地図上に描画される様々な地物であり、本実施の形態では、これらを多角形と見なしてポリゴンと呼ぶ。
【００２６】
リンクは、人がこの上を歩くことを想定し、歩行可能域に引かれる線である。リンクの両端は必ずノードであり、リンクは、向き、長さという属性情報を一組だけ持つ。従って、リンクの途中で分岐がある場合や、リンクの向きを変える場合には、その起点となる点にノードを打ち、リンクを分割する。
【００２７】
ノードは、リンクの起点、もしくは終点となる点である。リンクの向きを変える（カーブを作成する）、リンクを分岐させる、などの場合にノードが生成されるほか、店舗などの地物の最寄りにナビゲーションポイントを設けたい場合などには、意図的にリンクの途中にノードを打って、リンクを分割する場合がある。
【００２８】
＜第１の実施の形態＞
＜第１の実施の形態に係る経路結合装置の構成＞
次に、第１の実施の形態に係る経路結合装置の構成について説明する。図２に示すように、第１の実施の形態に係る経路結合装置１００は、ＣＰＵと、ＲＡＭと、後述する各処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この経路結合装置１００は、機能的には図２に示すように、入力部１０と、演算部２０とを備えている。
【００２９】
入力部１０は、歩行者の歩行可能域を含む屋内地図を入力として受け付ける。
【００３０】
演算部２０は、図２に示すように、経路情報生成部２２、経路情報結合部２４、及び地図データベース２６を備えている。
【００３１】
地図データベース２６には、経路ノード及びリンクで表された経路情報が予め付与された屋外地図が格納されている。また、地図データベース２６には、経路情報結合部２４により屋外地図と結合された屋内地図が格納される。
【００３２】
経路情報生成部２２は、入力部１０で受け付けた屋内地図について、経路ノード及びリンクで表された経路情報を生成する。経路情報生成部２２は、図３に示すように、歩行可能域抽出部３０、三角形分割部３２、経路ノード生成部３４、及びノード接続部３６を備えている。
【００３３】
歩行可能域抽出部３０は、入力部１０で受け付けた屋内地図の歩行可能域を切り取った図形を生成する。
【００３４】
三角形分割部３２は、歩行可能域抽出部３０によって生成された屋内地図の歩行可能域の図形の頂点を入力点群として、ドロネー三角形分割を行う。三角形分割部３２は、図４に示すように、歩行可能域からはみ出した三角形など、経路として適合しない三角形を消去する。そして、三角形分割部３２は、歩行可能域で三角形となっていない図形に対し、再度三角形を生成する。
【００３５】
経路ノード生成部３４は、三角形分割部３２によるドロネー三角形分割によって得られた三角形の各々に対して、当該三角形が、屋内地図上の地物を表わすポリゴンの端を含まない場合、又は、２辺にポリゴンの端を含む場合、当該三角形に経路ノードを生成せず、一方、当該三角形が、１辺のみにポリゴンの端を含む場合、当該三角形に経路ノードを生成する（図５参照）。また、１辺のみにポリゴンの端を含む三角形に経路ノードを生成する際には、図６に示すように、その辺を除く他の２辺を等分し、その等分点に直線を引いた中点に経路ノードを作成する。このように、経路ノードを歩行可能域の中心に生成する。歩行可能域の中心に経路を生成するのは、ナビゲーションされる人・車いす等の安全性を考えた結果である。また、歩行可能域の角や行き止まりでは、余計な三角形が生成され、不要な分岐が生成されるので、該当する三角形では経路ノードを生成しない。
【００３６】
また、経路ノード生成部３４は、更に、隣り合う三角形の各々の経路ノードをリンクで接続し、経路ノードの各々について、当該経路ノードを挟むリンクで形成されるリンク角が閾値以上である場合、当該経路ノードを削除する。例えば、人間の視野角を基準にして、経路ノードを挟むそれぞれのリンクの角度が１３５度以上であれば、当該経路ノードを削除し（図７（Ａ）参照）、経路ノードを挟むそれぞれのリンクの角度が１３５度未満であれば、当該経路ノードをそのまま残す（図７（Ｂ）参照）。また、削除された経路ノードを挟むリンクの各々の残りの経路ノード間を結合したリンクを生成し、削除された経路ノードを挟むリンクを削除する。
【００３７】
これにより、図８に示すように、屋内地図上の歩行可能域に生成される経路ノードを削減することができる。
【００３８】
ノード接続部３６は、図９に示すように、経路ノード生成部３４によって生成された、隣り合う三角形の各々の経路ノードをリンクで結合することにより、経路情報を生成する。
【００３９】
経路情報結合部２４は、経路情報生成部２２によって生成された屋内地図上の歩行可能域の経路情報と、屋外地図上の経路情報とを結合する。
【００４０】
経路情報結合部２４は、図１０に示すように、屋外地図取得部４０、出入口地物探索部４２、屋内経路結合部４４、及び屋外経路結合部４６を備えている。
【００４１】
屋外地図取得部４０は、経路情報生成部２２によって経路情報が生成された屋内地図と接続される屋外地図を、地図データベース２６から取得する。
【００４２】
例えば、経路情報生成部２２によって経路情報が生成された屋内地図上の経路情報が近傍に存在し、接続できる条件である屋外地図を、地図データベース２６から取得する。
【００４３】
出入口地物探索部４２は、経路情報生成部２２によって経路情報が生成された屋内地図から、出入口の属性を持つ地物を探索し、該当地物が存在すれば、その地物の中央に、出入口ノードを生成する（図１１のノード（４）参照）。
【００４４】
屋内経路結合部４４は、生成された出入口ノードに対して、以下の場合分けに応じて、出入口ノードと屋内地図上の経路情報とを結合する。
【００４５】
まず、出入口ノードから予め定められた範囲内に、経路情報生成部２２によって生成された経路情報の経路ノードが存在する場合、出入口ノードと、当該経路情報の経路ノードとを結合したリンクを生成する。例えば、図１２に示すように、出入口ノード（４）の出入口ノード範囲内（例えば、５ｍ以内）に屋内地図上の経路ノード（２）がある場合、当該経路ノード（２）と出入口ノード（４）とを結合するリンクを生成する。
【００４６】
一方、出入口ノードから予め定められた範囲内に、経路情報生成部２２によって生成された経路情報の経路ノードが存在しない場合、出入口ノードに最も近い、当該経路情報のリンク上にノードを生成し、生成したノードと出入口ノードとを結合したリンクを生成する。例えば、図１３（Ａ）に示すように、出入口ノード（４）の出入口ノード範囲内に屋内地図上の経路ノードが存在しない場合、図１３（Ｂ）に示すように、出入口ノード（４）から、出入口ノード（４）に最も近いリンクに垂線を引き、図１３（Ｃ）に示すように、交点に経路ノード（２）を生成する。経路ノード（２）を生成した後、出入口ノード（４）と経路ノード（２）をリンクで結ぶ。
【００４７】
屋外経路結合部４６は、生成された出入口ノードに対して、以下の場合分けで、出入口ノードと屋外地図上の経路情報とを結合する。
【００４８】
まず、出入口ノードから予め定められた範囲内に、屋外地図上の経路情報の経路ノードが存在する場合、出入口ノードと、当該経路情報の経路ノードとを結合したリンクを生成する。例えば、図１４に示すように、出入口ノード（４）の出入口ノード範囲内（例えば、５ｍ以内）に屋外地図上の経路ノード（６）がある場合、当該経路ノード（６）と出入口ノード（４）とを結合するリンクを生成する。
【００４９】
一方、出入口ノードから予め定められた範囲内に、屋外地図上の経路情報の経路ノードが存在しない場合、出入口ノードに最も近い、当該経路情報のリンク上にノードを生成し、生成したノードと出入口ノードとを結合したリンクを生成する。例えば、図１５（Ａ）に示すように、出入口ノード（４）の出入口ノード範囲内に屋外地図上の経路ノードが存在しない場合、図１５（Ｂ）に示すように、出入口ノード（４）から、出入口ノード（４）に最も近いリンクに垂線を引き、図１５（Ｃ）に示すように、交点に経路ノード（６）を生成する。経路ノード（６）を生成した後、出入口ノード（４）と経路ノード（６）をリンクで結ぶ。
【００５０】
以上のように、屋内経路結合部４４及び屋外経路結合部４６により、屋内地図上の経路情報と屋外地図上の経路情報とが、出入口ノードを介して結合される。このとき、出入口を通過する際の安全性を考えて、出入口を通過するリンクは、出入口の中心を、出入口に直角に通過するよう生成される。
【００５１】
屋外経路結合部４６は、屋外地図上の経路情報と結合された屋内地図を、地図データベース２６に格納する。
【００５２】
＜第１の実施の形態に係る経路結合装置の作用＞
次に、本発明の第１の実施の形態に係る経路結合装置１００の作用について説明する。
【００５３】
まず、経路情報を含む屋外地図が、経路結合装置１００の地図データベース２６に格納されている。そして、歩行可能域を含む屋内地図を、入力部１０によって受け付けると、経路結合装置１００は、図１６に示す経路結合処理ルーチンを実行する。
【００５４】
まず、ステップＳ１００において、入力された屋内地図の歩行可能域に対して経路情報を生成する。
【００５５】
そして、ステップＳ１０２において、上記ステップＳ１００で生成された屋内地図の経路情報と、地図データベース２６に格納されている屋外地図の経路情報とを結合して、屋内地図を、地図データベース２６に格納し、経路結合処理ルーチンを終了する。
【００５６】
上記ステップＳ１００は、図１７に示す処理ルーチンによって実現される。
【００５７】
ステップＳ１１０では、入力部１０で受け付けた屋内地図の歩行可能域を切り取った図形を生成する。ステップＳ１１２では、上記ステップＳ１１０で生成された屋内地図の歩行可能域の図形の頂点を入力点群として、ドロネー三角形分割を行う。
【００５８】
そして、ステップＳ１１４では、上記ステップＳ１１２で得られた三角形のうち、経路として適合しない三角形を消去する。ステップＳ１１６では、歩行可能域で三角形となっていない図形に対し、再度三角形を生成する。
【００５９】
ステップＳ１１８では、処理対象の三角形が、屋内地図上の地物を表わすポリゴンの端を含まないか、あるいは、２辺にポリゴンの端を含むか判定する。処理対象の三角形が、屋内地図上の地物を表わすポリゴンの端を含まない場合、あるいは、２辺にポリゴンの端を含む場合には、処理対象の三角形に経路ノードを生成しないで、ステップＳ１２２へ移行する。
【００６０】
一方、処理対象の三角形が、１辺のみにポリゴンの端を含む場合、ステップＳ１２０において、処理対象の三角形の、ポリゴンの端を含む辺を除く他の２辺を等分し、その等分点に直線を引いた中点に経路ノードを作成する。
【００６１】
ステップＳ１２２では、上記ステップＳ１１２〜Ｓ１１６によって得られた全ての三角形に対して、上記ステップＳ１１８、Ｓ１２０の処理を実行したか否かを判定する。上記ステップＳ１１８、Ｓ１２０の処理を実行していない三角形が存在する場合には、上記ステップＳ１１８へ戻り、当該三角形を処理対象とする。一方、上記ステップＳ１１２〜Ｓ１１６によって得られた全ての三角形に対して、上記ステップＳ１１８、Ｓ１２０の処理を実行した場合には、ステップＳ１２４において、隣り合う三角形の各々の経路ノードをリンクで接続する。
【００６２】
ステップＳ１２６では、経路ノードの各々について、当該経路ノードを挟むリンクで形成されるリンク角が閾値以上である場合、当該経路ノードを削除する。
【００６３】
そして、ステップＳ１２８において、上記ステップＳ１２６の結果として得られた三角形の経路ノードに基づいて、隣り合う三角形の各々の経路ノードをリンクで結合することにより、屋内地図の経路情報を生成し、処理ルーチンを終了する。
【００６４】
上記ステップＳ１０２は、図１８に示す処理ルーチンによって実現される。
【００６５】
ステップＳ１３０では、上記ステップＳ１００で経路情報が生成された屋内地図と接続される屋外地図を、地図データベース２６から取得する。ステップＳ１３２では、上記ステップＳ１００で経路情報が生成された屋内地図から、出入口の属性を持つ地物を探索し、ステップＳ１３４において、上記ステップＳ１３２で探索された地物の中央に、出入口ノードを生成する。
【００６６】
ステップＳ１３６では、上記ステップＳ１３４で生成された出入口ノードから予め定められた範囲内に、上記ステップＳ１００で生成された屋内地図上の経路情報の経路ノードが存在するか否かを判定する。出入口ノードから予め定められた範囲内に、屋内地図上の経路情報の経路ノードが存在する場合、ステップＳ１３８において、出入口ノードと、当該経路情報の経路ノードのうち、出入口ノードに最も近い経路ノードとを結合したリンクを生成する。
【００６７】
一方、出入口ノードから予め定められた範囲内に、上記ステップＳ１００で生成された屋内地図上の経路情報の経路ノードが存在しない場合、ステップＳ１４０において、出入口ノードに最も近い、当該経路情報のリンク上にノードを生成し、ステップＳ１４２において、上記ステップＳ１４０で生成したノードと出入口ノードとを結合したリンクを生成する。
【００６８】
ステップＳ１４４では、上記ステップＳ１３４で生成された出入口ノードから予め定められた範囲内に、上記ステップＳ１３０で取得した屋外地図上の経路情報の経路ノードが存在するか否かを判定する。出入口ノードから予め定められた範囲内に、屋外地図上の経路情報の経路ノードが存在する場合、ステップＳ１４６において、出入口ノードと、当該経路情報の経路ノードのうち、出入口ノードに最も近い経路ノードとを結合したリンクを生成する。
【００６９】
一方、出入口ノードから予め定められた範囲内に、上記ステップＳ１３０で取得した屋外地図上の経路情報の経路ノードが存在しない場合、ステップＳ１４８において、出入口ノードに最も近い、当該経路情報のリンク上にノードを生成し、ステップＳ１５０において、上記ステップＳ１４８で生成したノードと出入口ノードとを結合したリンクを生成する。
【００７０】
ステップＳ１５２では、上記ステップＳ１３２で探索された全ての出入口地物に対して、上記ステップＳ１３４〜Ｓ１５０の処理を実行したか否かを判定し、上記ステップＳ１３４〜Ｓ１５０の処理を実行していない出入口地物が存在する場合には、当該出入口地物を処理対象として上記ステップＳ１３４へ戻る。一方、上記ステップＳ１３２で探索された全ての出入口地物に対して、上記ステップＳ１３４〜Ｓ１５０の処理を実行した場合には、ステップＳ１５４において、屋外地図と結合された屋内地図を、地図データベース２６に格納して処理ルーチンを終了する。
【００７１】
以上説明したように、本発明の第１の実施の形態に係る経路結合装置によれば、屋内地図上の歩行者の歩行可能域に対して、ドロネー三角形分割を行い、三角形の各々に対して、経路ノードを生成し、リンクで結合して、屋内地図上の歩行可能域の経路情報を生成することにより、屋内地図上の歩行可能域に適切な経路情報を生成することができる。また、生成した三角形が、ポリゴンの端を含まない場合、もしくはポリゴンの端を２辺含む場合は、当該三角形に経路ノードを生成しないようにすることにより、不要なノードを生成しないようにすることができる。
【００７２】
また、出入口ノードを介して、屋内地図上の歩行可能域の経路情報と屋外地図上の経路情報とを結合することにより、屋内地図と屋外地図の経路情報を適切に結合することができる。
【００７３】
また、ドロネー三角形分割を、屋内地図の歩行可能域に適用すると、実際の壁の凹凸が細かくてノードがたくさん生成される。経路探索をする際、ノードが多いと計算処理のリソースが大きいという問題がある。そこで、本実施の形態では、経路探索に必要な分かれ道と曲がり角のノードのみ生成することで、計算処理のリソースを抑制する。経路探索に必要な分かれ道と曲がり角のノードのみ生成するために、本実施の形態では、経路情報の経路ノードの各々について、経路ノードを挟むリンクで形成されるリンク角に応じて、経路ノードを削除する。それらは直線に近い経路を構成するものであり、分かれ道と曲がり角を構成するものではないからである。
【００７４】
＜第２の実施の形態＞
次に、第２の実施の形態について説明する。なお、第２の実施の形態に係る経路結合装置は、第１の実施の形態と同様の構成であるため、同一符号を付して説明を省略する。
【００７５】
第２の実施の形態では、生成した三角形が、ポリゴンの端を含まない場合、もしくはポリゴンの端を２辺含む場合は、三角形の重心に経路ノードを生成する点が、第１の実施の形態と異なっている。
【００７６】
＜第２の実施の形態に係る経路結合装置の構成＞
第２の実施の形態に係る経路結合装置の経路ノード生成部３４は、三角形分割部３２によるドロネー三角形分割によって得られた三角形の各々に対して、当該三角形が、屋内地図上の地物を表わすポリゴンの端を含まない場合、又は、２辺にポリゴンの端を含む場合、当該三角形の重点に経路ノードを生成し、一方、当該三角形が、１辺のみにポリゴンの端を含む場合、その辺を除く他の２辺を等分し、その等分点に直線を引いた中点に経路ノードを作成する。
【００７７】
このように、角や行き止まりに店舗等があり、主となる経路から分岐して角や行き止まりに寄っていく経路が必要な場合は、該当する三角形の重心にノードを生成する。このとき、重心にノードを生成するのは、三角形のどの辺からも等距離となる点にノードを生成するためである。
【００７８】
なお、第２の実施の形態に係る経路結合装置の他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【００７９】
以上説明したように、本発明の第２の実施の形態に係る経路結合装置によれば、屋内地図上の歩行者の歩行可能域に対して、ドロネー三角形分割を行い、生成した三角形が、ポリゴンの端を含まない場合、もしくはポリゴンの端を２辺含む場合は、当該三角形の重心に経路ノードを生成することにより、角や行き止まりに店舗等があり、主となる経路から分岐して角や行き止まりに寄っていく経路を生成することができる。
【００８０】
＜第３の実施の形態＞
次に、第３の実施の形態について説明する。なお、第１の実施の形態と同様の構成となる部分については、同一符号を付して説明を省略する。
【００８１】
第３の実施の形態では、ドロネー三角形分割により得られた三角形のうち、面積が小さい三角形を、隣り合う三角形と結合して、三角形の数を減らし、経路ノードの数を削減する点が、第１の実施の形態と異なっている。
【００８２】
＜概要＞
図１９に示すように、実データに対して本アルゴリズムを用いて三角形分割を行っていくと、実データではポリゴンの形状が複雑なため、小さな三角形が大量に生成され、不要ノードが多く生成されてしまう。そこで、本実施の形態では、小さな三角形を結合していくことにより、三角形の数を減らし、不要なノードを削除する。
【００８３】
＜第３の実施の形態に係る経路結合装置の構成＞
第３の実施の形態に係る経路結合装置１００の経路情報生成部２２は、図２０に示すように、歩行可能域抽出部３０、三角形分割部３２、三角形結合部３００、経路ノード生成部３４、及びノード接続部３６を備えている。
【００８４】
三角形結合部３００は、三角形分割部３２によるドロネー三角形分割によって得られた三角形の各々に対して、三角形の面積が閾値以下である場合、面積が閾値より大きくなるように、三角形と隣り合う三角形と結合して多角形を生成する。
【００８５】
具体的には、以下の方法で小さな三角形を結合していく。
【００８６】
まず、三角形ごとに、面積を求める。
【００８７】
面積が閾値以下である三角形は、結合対象となる。そして、図２１に示す表から、結合対象の三角形と隣り合う三角形を結合先として取得する。図２１に示す表は、三角形又は多角形毎に、隣の三角形又は多角形が格納されている。上記図２１の例では、「隣の三角形又は多角形」に格納された１つ目の三角形Ｂを結合先とする。
【００８８】
そして、図２２に示すように、結合先の三角形Ｂは、結合対象の三角形Ａの「隣の三角形又は多角形」を引き継ぐ。次に、図２３に示すように、結合先である三角形Ｂの「隣の三角形又は多角形」の、自身のＩＤと結合対象のＩＤを消去する。
【００８９】
そして、図２４に示すように、結合対象の三角形と結合先の三角形とを結合した多角形を生成するように形状を更新する。また、図２５に示すように、表を更新する。まず、図２５（Ａ）に示すように、結合対象のＩＤ「Ａ」をＣの「隣の三角形又は多角形」から削除する。そして、図２５（Ｂ）に示すように、結合先のＩＤ「Ｂ」をＣの「隣の三角形又は多角形」に追加する。そして、図２５（Ｃ）に示すように、結合対象「Ａ」行の「隣の三角形又は多角形」を空白にする。
【００９０】
次に、結合先の多角形の面積を求め、設定した面積より小さい場合は、当該結合先の多角形を結合対象として、上記の処理を繰り返し、結合処理を実施する（図２６参照）。
【００９１】
そして、結合処理済みの多角形は、「隣の三角形又は多角形」が（空白）ではない場合のみ保持され、経路ノード生成部３４へ引き渡される（図２７参照）。
【００９２】
経路ノード生成部３４は、三角形結合部３００による多角形の生成結果から得られる三角形及び多角形の各々に対して、上記第１の実施の形態又は第２の実施の形態と同様に、経路ノードを生成する。このとき、結合処理済みの多角形については、図２８に示すように、多角形の重心に経路ノードを生成する。このように、多角形の場合、多角形の辺が壁と隣接する組み合わせが多種考えられるため、すべての辺から均等に離れた点（重心）に経路ノードを生成することが好ましい。
【００９３】
上記のように、小さな三角形を結合する処理を行うことにより、上記図１９の例では、図２９に示すように、三角形の数が削減され、ノードの数が削減される。
【００９４】
＜第３の実施の形態に係る経路結合装置の作用＞
次に、本発明の第３の実施の形態に係る経路結合装置１００の作用について説明する。
【００９５】
歩行可能域を含む屋内地図を、入力部１０によって受け付けると、経路結合装置１００は、上記図１６に示す経路結合処理ルーチンと同様の処理ルーチンを実行する。このとき、ステップＳ１１６の後に、小さな三角形を結合する処理を行う。この処理は、図３０に示す処理ルーチンによって実現する。
【００９６】
まず、ステップＳ３００では、上記ステップＳ１１６の結果として得られた三角形ごとに、面積を求める。また、三角形毎に、隣の三角形を表に格納する。
【００９７】
ステップＳ３０２では、上記ステップＳ１１６又は後述するステップＳ３１２で得られた表に格納されている、「隣の三角形又は多角形」が（空白）ではない三角形又は多角形のうち、面積が閾値以下のものを、結合対象として設定する。次のステップＳ３０４では、表から、結合対象の三角形又は多角形と隣り合う三角形又は多角形を結合先として設定する。
【００９８】
そして、ステップＳ３０６において、結合先の三角形又は多角形が、結合対象の三角形又は多角形の「隣の三角形又は多角形」を引き継ぐように表を更新する。次に、ステップＳ３０８では、結合先である三角形又は多角形の「隣の三角形又は多角形」の、自身のＩＤと結合対象のＩＤを消去する。
【００９９】
ステップＳ３１０では、結合対象の三角形又は多角形と結合先の三角形又は多角形とを結合した多角形を生成するように形状を更新する。また、ステップＳ３１２において、結合対象のＩＤを「隣の三角形又は多角形」から削除し、結合先のＩＤを「隣の三角形又は多角形」に追加し、結合対象の行の「隣の三角形又は多角形」を空白にするように、表を更新する。
【０１００】
次のステップＳ３１４では、結合先の多角形の面積を求める。ステップＳ３１６では、上記ステップＳ１１６の結果として得られた三角形、又は上記ステップＳ３１０で得られた多角形のうち、面積が閾値以下のものがあるか否かを判定する。面積が閾値以下の三角形又は多角形が存在する場合には、上記ステップＳ３０２へ戻って、当該三角形又は多角形を結合対象として設定する。一方、面積が閾値以下の三角形又は多角形が存在しない場合には、処理ルーチンを終了し、「隣の三角形又は多角形」が（空白）ではない三角形又は多角形について、上記ステップＳ１１８〜ステップＳ１２２の処理が実行される。
【０１０１】
なお、第３の実施の形態に係る経路結合装置１００の他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【０１０２】
以上説明したように、第３の実施の形態に係る経路結合装置によれば、ドロネー三角形分割により生成された三角形のうち、小さな三角形を隣り合う三角形と結合して、三角形の数を減らし、経路ノードを削除することにより、屋内地図上の移動可能域に適切な経路情報を生成することができる。このように、面積が小さい三角形をつなぐノードを削除するのは、それらが直線に近い経路を構成するものであり、分かれ道と曲がり角を構成するものではないからである。
【０１０３】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１０４】
例えば、屋内地図上の歩行可能域の経路情報を生成する場合を例に説明したが、これに限定されるものではなく、地図上の歩行者以外の移動物の移動可能域の経路情報を生成するようにしてもよい。例えば、ベビーカーや車椅子などの走行可能域の経路情報や、ロボットなど、生物以外の移動物の移動可能域の経路情報を生成するようにしてもよい。
【０１０５】
また、経路結合装置１００が、屋内地図上の歩行可能域の経路情報を生成する場合を例に説明したが、これに限定されるものではなく、経路結合装置１００とは別の経路情報生成装置が、屋内地図上の歩行可能域の経路情報を生成するようにしてもよい。この場合には、経路情報生成装置は、歩行可能域抽出部３０、三角形分割部３２、経路ノード生成部３４、及びノード接続部３６を備えていればよい。
【０１０６】
また、歩行可能域に対してドロネー三角形分割を行ってから、ノードを削減する場合を例に説明したが、これに限定されるものではない。例えば、上記の経路情報生成装置が、ノード及びリンクで表わされる経路情報を入力として、リンク角が閾値以上の経路ノードを削減するようにしてもよい。この場合には、経路情報生成装置は、歩行可能域抽出部３０及び三角形分割部３２を省略して、経路ノード生成部３４及びノード接続部３６を含んで構成される。このように、ノード削除のみを行う経路情報生成装置は、ノード数が多い経路情報からノード数を減らすことにより、大まかな経路情報でもよいので高速に経路情報を提供したい場合に対応することができる。
【０１０７】
また、上述の経路結合装置１００は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【０１０８】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能であるし、ネットワークを介して提供することも可能である。
【符号の説明】
【０１０９】
１０ 入力部
２０ 演算部
２２ 経路情報生成部
２４ 経路情報結合部
２６ 地図データベース
３０ 歩行可能域抽出部
３２ 三角形分割部
３４ 経路ノード生成部
３６ ノード接続部
４０ 屋外地図取得部
４２ 出入口地物探索部
４４ 屋内経路結合部
４６ 屋外経路結合部
１００ 経路結合装置
３００ 三角形結合部
【図１】
2020074060.tif 000003
【図２】
2020074060.tif 000004
【図３】
2020074060.tif 000005
【図４】
2020074060.tif 000006
【図５】
2020074060.tif 000007
【図６】
2020074060.tif 000008
【図７】
2020074060.tif 000009
【図８】
2020074060.tif 000010
【図９】
2020074060.tif 000011
【図１０】
2020074060.tif 000012
【図１１】
2020074060.tif 000013
【図１２】
2020074060.tif 000014
【図１３】
2020074060.tif 000015
【図１４】
2020074060.tif 000016
【図１５】
2020074060.tif 000017
【図１６】
2020074060.tif 000018
【図１７】
2020074060.tif 000019
【図１８】
2020074060.tif 000020
【図１９】
2020074060.tif 000021
【図２０】
2020074060.tif 000022
【図２１】
2020074060.tif 000023
【図２２】
2020074060.tif 000024
【図２３】
2020074060.tif 000025
【図２４】
2020074060.tif 000026
【図２５】
2020074060.tif 000027
【図２６】
2020074060.tif 000028
【図２７】
2020074060.tif 000029
【図２８】
2020074060.tif 000030
【図２９】
2020074060.tif 000031
【図３０】
2020074060.tif 000032