建物用の経路案内グラフ
本明細書で開示される主題は、建物情報に少なくとも一部基づいて、経路案内グラフを作成するための、システム、方法などに関する。いくつかの例示的な実装形態では、方法は、建物構造の少なくとも一部を表す建物情報を得るステップを含む。点のグリッドが、建物情報に重畳されうる。少なくとも1つの経路案内グラフが、重畳された点のグリッドおよび建物情報に少なくとも一部基づいて、作成されうる。他の例示的な実装形態も、説明される。
【発明の詳細な説明】
【技術分野】
【０００１】
米国特許法第119条による優先権の主張
この米国特許本出願は、2009年10月1日に出願された、AUTOMATIC ROUTING TOPOLOGY EXTRACTION FROM CAD MAPSという表題の、米国特許仮出願第61/247866号と、2009年10月1日に出願された、SYSTEM FOR INDOOR LOCATIONという表題の米国特許仮出願第61/247865号と、2009年10月1日に出願された、AUTOMATIC ROUTING TOPOLOGY EXTRACTION FROM LOW DETAIL SCHEMATICSという表題の米国特許仮出願第61/247869号と、2010年1月22日に出願された、MAP ACQUISITION AND PROCESSING FOR LOCATION BASED SERVICESという表題の米国特許仮出願第61/297524号との利益を主張するものであり、これらの仮出願の各々が、本出願の譲受人に譲渡され、参照によって本明細書に明示的に組み込まれる。
【０００２】
本明細書で開示される主題は、建物情報に少なくとも一部基づいて、経路案内グラフを作成することに関する。
【背景技術】
【０００３】
地図は、20世紀中に電子的形態で利用可能になり始めた。インターネットの出現により、基本的に世界中のあらゆる場所の地図に、最終的にはアクセスすることができる。ウェブ上の地図サービスは、地点「A」から地点「B」への案内を提供することもできる。これらのウェブ上での地図案内は、比較的静的である。しかし、衛星測位システム(SPS)技術およびさらに小型の電子機器の発明により、いわゆるターンバイターンの案内を、人々が自分の目的地に向かって移動するにつれて動的に提供することができる。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
残念ながら、これらの電子地図およびウェブ上の地図サービスは、ある住所から別の住所への案内のように、屋外で案内を提供することを目的としている。同様に、従来は、ターンバイターンの案内は道路上に限られている。今のところ、屋内で同様の地図および案内サービスを提供する能力が欠けている。
【課題を解決するための手段】
【０００５】
ある例示的な実装形態では、方法は、建物構造の少なくとも一部を表現する建物情報を得るステップと、点のグリッドを建物情報に重畳するステップとを含みうる。少なくとも1つの経路案内グラフが、重畳された点のグリッドと建物情報とに少なくとも一部基づいて、作成されうる。しかし、これは例示的な実装形態に過ぎず、他の実装形態が本明細書で説明され、特許請求される主題から外れることなく実装されうることを、理解されたい。
【０００６】
非限定的かつ非網羅的な態様、特徴などが、以下の図面を参照して説明され、様々な図面全体で、同様の番号は同様の部分を指す。
【図面の簡単な説明】
【０００７】
【図１】ある実装形態による、注記情報を有する例示的な建物情報の概略図である。
【図２】ある実装形態による、注記情報への関連付けを含む例示的な経路案内グラフが作成された、建物情報の概略図である。
【図３】ある実装形態による、建物情報および建物道案内ファイルの例を示すブロック図である。
【図４】ある実装形態による、例示的な建物情報の概略図である。
【図５】ある実装形態による、例示的な点のグリッドが重畳された、建物情報の概略図である。
【図６】ある実装形態による、建物情報に少なくとも一部基づいて経路案内グラフを作成するための例示的な方法を示す、流れ図である。
【図７】ある実装形態による、建物情報を分析して経路案内グラフを作成するための例示的な方法を示す、流れ図である。
【図８】ある実装形態による、点のグリッドが重畳された、例示的な建物の部分の概略図である。
【図９】ある実装形態による、扉が閉じられた状態で模擬され、独立の領域が相互接続された点から決定されうる、例示的な建物の部分の概略図である。
【図１０】ある実装形態による、扉が閉じられた状態で模擬され、注記情報が複数の接続されていないグラフに重畳される、例示的な建物の部分の概略図である。
【図１１】ある実装形態による、扉が開いた状態で模擬され、入口および出口が決定されうる、例示的な建物の部分の概略図である。
【図１２】ある実装形態による、扉が開いた状態で模擬され、独立の領域が使用可能か使用不可能かが決定されうる、例示的な建物の部分の概略図である。
【図１３】ある実装形態による、独立の領域が廊下として検出されうる、少なくとも1つの例示的な建物の部分の概略図である。
【図１４】建物の経路案内グラフの1つまたは複数の態様を実施することができる、ある実装形態による例示的な機器の概略図である。
【発明を実施するための形態】
【０００８】
本明細書全体における、「ある特徴」、「1つの特徴」、「ある例」、「一例」などへの言及は、特徴および/または例とともに説明される、具体的な特徴、構造、特性などが、特許請求される主題の少なくとも1つの特徴および/または例に関連するということを意味する。したがって、本明細書の様々な箇所における、「一例では」、「ある例」、「1つの特徴として」、「ある特徴」、「ある例示的な実装形態では」などのような語句の使用は、全てが同じ特徴、例、および/または例示的な実装形態を指すとは限らない。さらに、具体的な特徴、例、構造、特性などは、1つまたは複数の例示的な実装形態、例示的なシステムなどに組み合わされうる。
【０００９】
上で示されたように、2点間の案内およびターンバイターンの案内は、現在、屋外の環境、特に画定された道路のある環境に限定されている。一方、建物の内部では、通常、同様の地図または道案内の機能は提供されない。屋内での道案内を実現するために、ユーザーが現在位置している環境の地図が用いられうる。しかし、地図だけでは屋内での道案内には不十分であることがある。ユーザーを地図上のある地点から別の地点へ道案内するのを支援するために、グラフおよび関連する注記レイヤが用いられうる。そのようなグラフは、一般に経路案内グラフと呼ばれる。
【００１０】
点のグリッドは、建物の地図のような建物情報に重畳されうる。点のグリッドは、接続グラフの基準として機能することができ、接続グラフは、建物を分析し、また、エンティティがどのように建物中を移動するかを表現しうる経路案内グラフを作成するのに、用いることができる。関連する注記情報を有する経路案内グラフは、所与の地図の使用可能な領域を表すことができ、ある点から別の点への通行がどのように可能かを示すことができる。任意の所与の建物について、経路案内グラフは、使用可能な領域および建物内のある点から別の点への通行可能な経路を示す、ノードおよびエッジのセットを含みうる。残念ながら、関連付けられた注記情報を有するそのような経路案内グラフは、コンピュータ支援設計(CAD)の地図から直接は得られず、多くの建物構造は、CADの地図のような標準的なファイルフォーマットで表現されているだけである。CADの地図は、壁、部屋、廊下のような建物の構造についての情報を含むことが多いが、CADの地図は、エンティティがそのような建物構造全体をどのように移動するかを特定せず、または示さない。屋内の位置情報サービス(LBS)のエコシステムに対しては、手動で経路案内地図を描き、屋内の場所の構造を識別することは、豊富な情報を有する数億の建物構造を追加するのにスケーラブルな方法ではない。
【００１１】
本明細書で説明されるいくつかの例示的な実装形態では、方法は、既存の建物の(例えばCAD)ファイルを分析するステップと、その建物のCADファイルから抽出される情報に少なくとも一部基づいて、経路案内グラフを作成するステップとを伴いうる。例示的な経路案内グラフの作成処理は、多くの建物のCADファイルに共通の既存の要素を用いて、自動的に実行されうる。CAD地図の分析から、関連する注記情報を有する強力な経路案内グラフが生成されうる。そのような経路案内グラフを用いて、屋内での測位および/または道案内情報がユーザー(例えば、ユーザーのモバイル機器)に提供されうる。
【００１２】
図1は、ある実装形態による、注記情報104を有する例示的な建物情報の概略図100である。ある例示的な実装形態では、概略図100は、建物の少なくとも一部を表しうる。その外観は、いくつか例を挙げると、線、曲線、円弧、多角形などを含みうる。これらの項目は、建物構造の具体的な要素を表すように定義されうる。建物構造の例は、限定はされないが、スタジアム、アリーナ、コンベンションセンター、モール、トンネルまたは橋または廊下などで接続された建物の集合体、空港、オフィスビル(壁/仕切りで再配置可能なものを含む)、これらの組み合わせなどを含む。
【００１３】
例示的な建物の要素は、限定はされないが、壁、扉、柱、部屋などを含む。示されるように、概略図100は、いくつか例を挙げると、複数の扉102、注記情報104、線により表される壁などを含みうる。視覚的に明瞭にするために、そのような要素の全てが、図1において参照番号により明示的に示されてはいないが、説明文が、どの建物情報の構成要素がどの特定の描画上の要素により示されているかを示す。
【００１４】
概略図100は、外側の壁、内側の壁、部屋、廊下、内側の扉、外側の扉などを含みうる。しかし、壁、廊下、扉の種類などは通常、建物地図ファイルでは明示的には識別されない。人間はそのような建物の要素を容易に識別できうるが、機械は通常そのような能力をもたない。本明細書で説明されるようないくつかの例示的な実装形態は、少なくともいくつかの建物構造を識別することを可能にする。
【００１５】
機械が具体的な建物の要素を識別したとしても、機械が支援する道案内は必ずしも可能にはならないことがあることを理解されたい。例えば、ある人が、概略図100の地点#1から地点#2まで移動しようとすることがある。道案内指示を提供できるようにするために、概略図100の建物構造のために経路案内グラフが作成されうる。ユーザーが、具体的な部屋番号、使用者、および/または名付けられた場所への案内を求めることが許される場合、注記情報はそのような経路案内グラフと関連付けられうる。例示的な経路案内グラフおよび注記情報は、図2を特に参照して本明細書で以下でさらに説明される。
【００１６】
いくつかの例示的な実装形態では、対象の建物構造のCADの地図または同様の地図が利用可能でありうる。屋内での道案内は、地図の抽出および補間を用いて可能になりうる。地図の抽出により、例えばautoCADファイル(.dwg)に存在する地図情報が、いくつか例を挙げると、経路案内、位置決め、インセンティブアプリケーション、検索などのような屋内での位置情報サービスを可能にする、よりアクセスしやすい情報に変換されうる。この変換において、CADファイルで表されるような物理的な地図の特性が操作され、経路案内モジュールにより利用されうる構造に変換されうる。加えて、そのような抽出処理および変換処理は、自動化された方式で、および/または自動的に行われうる。実際には、地図の抽出および変換には、ユーザーは最小限しか関わらないか全く関わらない。さらに、そのような処理は、1つの地図につき数分程度で完了しうる。
【００１７】
いくつかの例示的な実装形態において、以下の動作のいずれも、自動化することができる。そのような例示的な動作は、異なる順序で実行されてもよく、かつ/または完全にもしくは一部重複するように実行されてもよい。第1に、建物構造内の使用可能な場所および使用不可能な場所が、識別されうる。地図を与えられると、ユーザーにより通行可能なそうした領域の位置が特定されうる。建物構造の内側と外側も、識別されうる。建物の外側の領域を(例えば内側の領域に対して)識別することで、次に位置決め技術を提供するのを容易にし、地図の領域内でのユーザーの位置決めを改善することができる。
【００１８】
第2に、地図の独立の領域が識別されうる。使用可能性を定義することに加えて、地図の個々の領域が全般的に識別されうる。例えば、所与のオフィスまたは他の部屋の境界を識別することで、経路案内の仕組みが容易になりうる。第3に、地図内の独立の領域の入口および出口の点が、識別されうる。会議室のような独立の領域に到達するために、ユーザーは、入口/出口の点に案内されうる。
【００１９】
第4に、建物の入口および出口の点が、所与の建物構造に対して特定されうる。シームレスな屋内での経路案内と、屋内から屋外への経路案内とを両方、より良く実現するために、入口および出口の点が、経路案内グラフの一部として、または経路案内グラフに関連するものとして、特定され含まれうる。加えて、緊急時行動および避難計画のためのアプリケーションが、そのような建物の入口および出口の点を利用することができる。
【００２０】
第5に、複数の場所を一緒に結びつけ、経路案内アプリケーションを動作させる経路案内グラフが、作成されうる。第6に、部屋の名前および場所のような注記レイヤからの情報を、地図情報から抽出することができ、経路案内、検索、位置フィルタリング(例えば、測位モジュールに対して制約を与えることによる)、および他の用途(例えば、別の位置情報システム(LBS))で用いるために、作成された経路案内グラフと統合することができる。図2に例として示されるように、オフィススペースの使用者ならびに部屋の名前で、部屋を名付けることができる。
【００２１】
図2は、ある実装形態による、注記情報212への関連付けを含む例示的な経路案内グラフ210が作成された、建物情報の概略図200である。示されるように、概略図200は、出口/入口202、内側の扉204、少なくとも1つの使用可能な領域206、建物の外側の領域208、経路案内グラフ210、および注記情報212を含みうる。経路案内グラフ210を用いて、案内アプリケーションおよび/またはシステムは、例えば地点#1から地点#2へ移動するための道案内指示を、個人に提供することができる。
【００２２】
視覚的に明瞭にするために、全てのそのような例示される要素が、図2において参照番号により明示的に示されてはいないが、説明文が、どの建物の要素がどの特定の描画上の要素により示されているかを示す。また、概略図200および経路案内グラフ210は、図2において示され本明細書において以下で説明されるようないくつかの例示的な構成要素を含むが、特許請求される主題はそのようには限定されない。代わりに、所与の実装形態は、より多くの、より少ない、かつ/または異なる構成要素を含んでもよい。
【００２３】
いくつかの例示的な実装形態では、経路案内のトポロジーを示す経路案内グラフ210が、概略図200の建物構造に対応するように作成されうる。建物情報の例示的な分析の一部として、独立の領域が決定されうる。独立の領域は、いくつか例を挙げると、部屋、廊下、建物の外側などを含みうる。少なくとも1つの独立の領域が、建物の外側の領域208を含むものと確定されうる。1つまたは複数の別の独立の領域は、使用不可能な領域206を含むものと判定されうる。立ち入ることのできる独立の領域は、使用可能な領域(例えば、入室可能な部屋、廊下など)を含むものと判定されうる。本明細書で用いられる場合、「部屋」(またはより一般的には区域)は、いくつか例を挙げると、オフィス、小部屋、休憩室、店舗、売店、フードコート、アパート/コンドミニアム、ブース、展示物、空港のゲート、アトラクション、他の定義可能な区域、およびこれらの組み合わせなどを含みうる。
【００２４】
1つもしくは複数の出口および/または入口202は、建物情報に含まれる扉が建物の外側の領域208に接続し、そこへのアクセスを提供する場合、そのような扉から決定されうる。1つまたは複数の内部の扉204は、内側の部屋、廊下などのような他の使用可能な領域へのアクセスを提供すると判定されうる。注記情報212は、経路案内グラフ210と関連付けられ、異なる領域(例えば部屋、区域など)の間での道案内サービスまたは他の位置情報サービスをさらに実現することができる。限定ではなく例として、注記情報212は、部屋の指定(例えば「A」、「1.24」など)、部屋の名前(例えば「会議室1」など)、部屋の目的(例えば「浴室」、「厨房」など)、部屋の居住者または使用者(例えば「Amy」、「Ray」など)などを含みうる。注記情報212は、いくつか例を挙げると、ロビー、エレベーター群、食事の場所などのような特定の区域と関連する情報を提供することもできる。経路案内グラフ210は、ある注記された領域から別の注記された領域への経路を含む、ある地点から別の地点への経路を描くのに用いることができる。
【００２５】
図3は、ある実装形態による、建物情報302および建物道案内ファイル308の例を示す、ブロック図300である。いくつかの例示的な実装形態では、建物情報302は、建物構造の少なくとも一部を表現する、任意の情報のセットまたは集合を含んでもよい。建物情報302に少なくとも一部基づいて、建物道案内ファイル308が作成されうる。建物道案内ファイル308は、少なくとも1つの経路案内グラフ312、注記情報314、および/または1つもしくは複数の接続グラフ316を含みうる。少なくとも経路案内グラフ312は、注記情報314に関連付けられ、または注記情報314と連携しうる。建物情報302、建物道案内ファイル308などは、電気信号(例えばデジタル信号)として実現されうる。
【００２６】
例として、建物情報302は、建物設計ファイル304および/または建物レイアウトファイル306を含みうる。建物設計ファイル304は、建物構造の少なくとも一部を表すデータ310a(例えば、CADまたは同様のフォーマットのデータ)を含みうる。建物レイアウトファイル306は、建物構造の少なくとも一部を表すデータ310b(例えば、drawing interchange/exchange format(DXF)または同様のフォーマットのデータ)を含みうる。建物情報302の例が以下で説明されるが、特許請求される主題はこれらの例にはそのようには限定はされない。より具体的には、建物情報302は、変換前または変換後の、変換を伴うまたは変換を伴わない、およびその他の、任意のフォーマットで存在しうる。さらに、建物情報302は、建物道案内ファイル308を作成する処理の間、任意の1つまたは複数のフォーマットで表されうる。例えば、建物道案内ファイル308の第1の部分は、建物情報302が第1のフォーマットである時に作成することができ、建物道案内ファイル308の第2の部分は、建物情報302が第2のフォーマットである時に作成することができる。
【００２７】
例示的な実装形態では、建物設計ファイル304は、建物構造および1つまたは複数の注記情報レイヤを格納するCADファイルに相当しうる。拡張子が「.dwg」のファイルは、拡張子が「.dxf」のファイルに変換することができ、「.dxf」ファイルは、テキスト構文解析機能を用いることで構文解析されうる、オープンフォーマットである。一般に、プロプライエタリフォーマット(例えば、「.dwg」ファイルなどのような)は、公に知られている構文(例えば、「.dxf」ファイルなどのような)を有する任意の交換フォーマットに変換されうる。CADファイル中のどの注記レイヤまたは複数の注記レイヤが、作製された経路案内グラフと関連付けられることになる注記レイヤであるかを識別するのに、この時点で使用者との対話が用いられうる。例えば、部屋の名前を関連付けることを望む場合、使用者が、そのようなレイヤの名前を選択または特定することができる。そのようなレイヤ(例えば「部屋レイヤ」)は、CADファイルの中で別々に標識されうる。あるいは、注記レイヤの選択は、いくつか例を挙げると、自動的に行われてもよく、1つまたは複数の規則にしたがって自動化されてもよく、これらの組み合わせなどであってもよい。
【００２８】
dxfでフォーマットされたファイルが得られると、建物の少なくとも一部の構造情報を抽出することができる。そのような情報は、いくつか例を挙げると、壁、窓、扉、柱などに関連しうる。dxfでフォーマットされたファイルにより、建物情報の要素を、線、弧などにより表すことができる。より具体的には、dxfでフォーマットされたファイルが構文解析された後、壁のような情報を線分により表すことができ、扉のような情報を線分および弧により表すことができる。
【００２９】
例えば、ある特定の壁が「部屋A」の壁であること、または、ある特定の扉が外側の出口/入口であることを示す情報は、存在しないことがある。しかし、そのような建物の要素の情報を処理して、抽出された情報から何らかの他のレイヤを推定することができる。例えば、ある特定の部屋(例えば「部屋A」)の境界ボックスを識別するために、位置情報が部屋の注記レイヤから抽出されうる。部屋の注記レイヤは、「部屋A」を特定する空間中の座標点(例えば、x=22、y=758)を示しうる。この情報を用いて、例えば、この点の周りの最小の閉じた領域または独立の領域が、経路案内の目的で決定され、部屋Aと標識されうる。注記情報を関連付けるこの処理の例示的な手法が、図10を特に参照して本明細書において以下でさらに説明される。
【００３０】
図4は、ある実装形態による、例示的な建物情報400の概略図である。建物情報400は、(図3の)建物情報302の例であってよい。したがって、建物情報400は、CADフォーマット、テキスト構文解析可能なフォーマット、これらの組み合わせ、または任意の他の1つまたは複数の種類のフォーマットであってよい。いくつかの例示的な実装形態では、建物情報400は、1つまたは複数の建物の要素を表す項目を含みうる。
【００３１】
示されるように、建物情報400は、壁402および扉404を少なくとも含む。「扉」404は、いくつか例を挙げると、階段の吹き抜け、エレベーターなども含みうる。さらに、建物の階への最初の入口(またはそこからの最後の出口)となる任意の要素は、扉404であると考えることができる。さらに、建物の要素を表す、より多くのまたは異なる構成要素が、建物情報400の一部として代替的に含まれてもよい。建物情報400は、注記情報406も含みうる。図5から、そのような建物構造の一部を表す建物情報400を用いて例示的な概念を示す。
【００３２】
図5は、ある実装形態による、例示的な点のグリッド502が重畳された、建物情報400の概略図500である。示されるように、概略図500は、建物情報400、点のグリッド502、先端の建物構造の点504、外側の点506を含みうる。いくつかの例示的な実装形態では、点のグリッド502は、建物情報400に重畳されうる。限定ではなく例として、点のグリッド502は、2つの軸(例えばx軸およびy軸)に沿って一定の間隔で位置する点のセットであってよい。点のグリッド502は、建物情報400の建物構造の、一部、実質的に全て、全て、または全てよりも広い範囲をカバーしてもよい。示されるように、点のグリッド502は、建物情報400の建物構造の外側の境界を超えて延びる。
【００３３】
点のグリッドの分解能または縮尺(例えば、2つの隣接点の間隔)は、変化してもよい。例えば、分解能は、いくつか例を挙げると、位置情報サービスで求められる正確さのレベル(例えば道案内の地図の正確さ)、建物情報の分析を分担しうるリソース(例えばメモリ、処理、および/または時間)の使用可能な量、部屋または他の独立の領域の実際のサイズもしくは予測されるサイズなどに基づいて、変化しうる。縮尺も、単一の建物構造における異なる所望の分解能のレベルに対応するように、単一の点のグリッドにおいて変化しうる。例示的な実装形態では、点のグリッドの数は、カバーされている地図のサイズにより決まりうる。地図のサイズは、線、弧などのような地図中の要素の各々の座標を求めることによって、かつ、要素の最小のならびに最大のx座標およびy座標を求めることによって、自動的に計算することができる。さらに、いくつかのCADファイルは、-1400、-200のような、負側の象限に原点を有することがある。そのような場合、地図の抽出処理は、地図の最小のx座標およびy座標を0,0における原点とするように変換することができ、他の要素もそれにしたがって変換することができる。そのような変換は、実行されると、地図の要素、POI(Point of Interest)などに関連する座標の理解を、容易にすることができる。POIは、いくつか例を挙げると、店舗、部屋、ターミナル/ゲート、展示物などを含みうる。例えば、所与の部屋が建物の左側の角から200フィートの距離にあるということを示すことが比較的わかりやすくなり、建物の左側の角は、変換によって原点0,0となるように定義されうる。
【００３４】
外側の点506は、先端の建物構造の点504に少なくとも一部基づいて、決定されうる。示されるように、先端の建物構造の点504は、建物構造の最も右側で最も上の点(例えば、最大のx-y座標を有する建物構造の点)である。あるいは、先端の建物構造の点504は、最小のx座標およびy座標を有してもよく、最も右側で最も下の点であってもよく、最大のy座標を有する最も左側の点であってもよく、またはその他であってもよい。先端の建物構造の点504(例えば、建物構造の最大座標(x,y))が選択されると、外側の点506を、例えばx-y座標の少なくとも1つを所定の量変化させることによって、点504に少なくとも一部基づいて決定することができる。例えば、外側の点506は、先端の建物構造の点504のx座標にΔxを加えることによって、かつ、先端の建物構造の点504のy座標にΔyを加えることによって、(例えば、外側の座標(x+Δx,y+Δy)を決定するように)決定されうる。本明細書において以下で説明されるように、外側の点506は、建物構造の外側の領域の決定に用いることができる。
【００３５】
点のグリッド502を重畳するための、建物構造の「グリッド化」を、外側の点506で開始することができる。グリッド化は、建物または建物の階の全てを含む、建物の所望の部分の全体がカバーされるまで、外側の点506から始めて、例えば複数の方向に1フィート間隔で点を追加することで、達成されうる。建物の周りの最大の領域が、建物情報ファイルから抽出される任意のオブジェクト(例えば、線分、扉、注記レイヤなど)のx座標とy座標の最小値および最大値を決めることによって、決定されうる。
【００３６】
図6は、ある実装形態による、建物情報に少なくとも一部基づいて、経路案内グラフを作成するための例示的な方法を示す、流れ図600である。示されるように、流れ図600は、4つの動作ブロック602、604、606、および608を含む。動作602〜608は特定の順序で示され説明されるが、特許請求される主題から逸脱することなく、方法は代替的な方式で実行されうることを理解されたい。また、流れ図600の動作は、互いに完全にまたは一部重複して実行されてもよい。加えて、以下の説明は、いくつかの他の図(例えば図3〜5)で示される具体的な態様および特徴に言及するが、方法は他の態様および/または特徴とともに実行されてもよい。
【００３７】
いくつかの例示的な実装形態では、動作602において、建物構造の少なくとも一部を表現する建物情報が取得されうる。例えば、(例えば、建物情報400として図4で示されるような)建物構造の少なくとも一部を表現する建物情報302が取得されうる。建物情報302は、いくつか例を挙げると、メモリから取り出すことによって、無線通信リンクまたは有線通信リンクを介して受信することによって、または他の方法で、取得することができる。動作604において、点のグリッドが建物情報に重畳されうる。例えば、点のグリッド502が、建物情報400に重畳されうる。
【００３８】
動作606において、建物情報が、点のグリッドを用いて分析されうる。例えば、点のグリッド502を用いた建物情報400の分析により、いくつか例を挙げると、独立の領域を決定すること、建物の入口および出口を決定すること、使用可能な領域と使用不可能な領域を決定すること、廊下を検出することなどを、可能にすることができる。点のグリッドを用いて建物情報を分析する例示的な手法が、図7を特に参照して本明細書において以下でさらに説明される。動作608において、経路案内グラフを、重畳された点のグリッドおよび建物情報に少なくとも一部基づいて作成することができる(例えば、少なくとも1つの経路案内グラフを表す電気信号(例えばデジタル信号)が生成されうる)。例えば、注記情報314への関連付けを有する経路案内グラフ312を、重畳された点のグリッド502および建物情報302に少なくとも一部基づいて、建物情報400のために作成することができる。
【００３９】
そのような経路案内グラフは、同じ機器または異なる機器において次に使用するために保存されてもよく、かつ/または、作成された後すぐに、もしくは実質的にすぐに使用されてもよい。例えば、経路案内グラフのデータベースは、次に取り出すために、かつ位置情報サービスに対して次に適用するために、保存されうる。あるいは、機器(例えばモバイル機器)が経路案内グラフを作成し、オンデマンドで、道案内または他の位置情報アプリケーションのために経路案内グラフを使用してもよい。いずれにしても、建物構造に関連する道案内情報(例えば、方向、完全なまたは部分的な経路案内グラフなど)を、少なくとも1つの経路案内グラフを用いてモバイル機器に提供することができる。
【００４０】
図7は、ある実装形態による、建物情報を分析して経路案内グラフを作成するための、例示的な方法を示す流れ図700である。示されるように、流れ図700は、10個の動作ブロック702〜720を含む。動作702〜720は特定の順序で示され説明されるが、特許請求される主題から逸脱することなく、方法は代替の方式で実行されうることを理解されたい。また、流れ図700の動作は、互いに完全にまたは一部重複して実行されてもよい。加えて、以下の説明は、いくつかの他の図(例えば図3〜5および図8〜13)で示される具体的な態様および特徴に言及するが、方法は他の態様および/または特徴とともに実行されてもよい。
【００４１】
動作702において、扉は、閉じた状態で模擬されうる。例えば、建物情報400の扉は、閉じていると考えることができる。動作704において、点のグリッド(例えば、点のグリッド502)の隣接点を、障害のない接続で相互接続することができる。例えば、接続が建物の要素と交差して接続グラフ316の少なくとも一部を形成しない場合、所与の点から、最大8つの近隣の点との間に接続を確立することができる。扉が閉じた状態で、この相互接続は複数の接続されていないグラフを形成することができる。
【００４２】
動作706において、複数の独立の領域が決定されうる。例えば、複数の独立の領域を、扉を閉じた状態で隣接点を障害のない接続によって相互接続することで形成される、複数の接続されていないグラフに少なくとも一部基づいて、決定することができる。動作708において、建物の部分の外側の少なくとも1つの独立の領域を、確定することができる。例えば、建物の部分の外側にあるものとして識別されるある点(例えば外側の点506)を用いて、外側の独立の領域を確定することができる。
【００４３】
動作702〜708の例示的な実装形態が、図9を特に参照して本明細書において以下でさらに説明される。動作710において、建物の注記情報が、接続グラフに重畳されうる。例えば、注記情報314は、少なくとも1つの接続グラフ316と関連付けられうる。動作710の例示的な実装形態が、図10を特に参照して、本明細書において以下でさらに説明される。
【００４４】
動作712において、扉は、開いた状態で模擬されうる。例えば、建物情報400の扉は、開いていると考えることができる。さらに、扉の点(例えば、扉の位置を表す点)が、開いた各扉の点のグリッドに追加されうる。動作714において、点のグリッド(例えば点のグリッド502)の隣接点が、障害のない接続により相互接続されうる。そのような相互接続される点は、扉の点として追加されるノードを含みうる。点が既に相互接続されている場合(例えば動作704において)、新しく追加される扉の点は、既存の接続されていないグラフに相互接続されうる。したがって、扉の点は、点のグリッドの他の点に接続され、少なくとも1つの相互接続されたグラフを形成することができる。
【００４５】
動作716において、建物構造の少なくとも1つの1つまたは複数の入口/出口が決定されうる。例えば、外側の独立の領域に(例えば、障害のない接続を介して)直接接続する扉は、建物の入口/出口であると判定されうる。動作712〜716の例示的な実装形態は、図11を特に参照して、本明細書において以下でさらに説明される。
【００４６】
動作718において、どの独立の領域が使用可能か、および、1つまたは複数の独立の領域が使用不可能であるかどうかが判定されうる。例えば、1つまたは複数の独立の領域に、外側の点から到達できるかどうかが、判定されうる。動作718の例示的な実装形態は、図12を特に参照して、本明細書において以下でさらに説明される。動作720において、1つまたは複数の廊下が検出されうる。例えば、1つまたは複数の独立の領域が少なくとも1つの廊下を含むかどうかが、各独立の領域に直接接続される扉の数に少なくとも一部基づいて、検出されうる。独立の領域は、閉じた状態で模擬される扉により決定されうるが(例えば動作706において)、廊下の検出は、任意の状態で模擬される扉により実行されうる。動作720の例示的な実装形態は、図13を特に参照して、本明細書において以下でさらに説明される。
【００４７】
図8は、ある実装形態による、点のグリッド502が重畳された、例示的な建物の部分800の概略図である。明瞭にするために示されるように、建物の部分800は、(図4の)建物情報400の一部(例えば断面)である。建物の部分800は、図8、ならびに図9〜12において、さらに詳細に示すために拡大されている。図9〜12は、全般に、建物の部分800を用いる異なる態様および/または実装形態を示す。図8において、建物の部分800は、壁402および扉404を含む。図8には示されないが、(図5の)先端の建物構造の点504および外側の点506、ならびに、建物構造の外側の角が、図9および11に表されている。
【００４８】
図9は、ある実装形態による、扉902が閉じた状態で模擬され、独立の領域904が相互接続された点から決定されうる、例示的な建物部分の概略図900である。いくつかの例示的な実装形態では、概略図900に示されるように、少なくともいくつかの動作が、扉902を閉じた状態で模擬して、実行される。(代替的な設計では、閉じた扉は、一時的に扉を壁で置き換えたのと等価であると考えることができる。)具体的には、4つの扉902a、902b、902c、および902dが示される。扉を閉じたものとして模擬することで、独立の領域が分離されうる。
【００４９】
扉902を閉じた状態で、点のグリッド(例えば、図8の点のグリッド502)からの点が、障害のない接続により隣接点と相互接続されうる。点の相互接続は、例えば、あらゆる任意の点から開始することができる。壁、閉じた扉または他の建物構造に直接位置する全ての点が、無視されうる。2点間の接続(例えば第1の地点から第2の地点への接続)は、例えば、そのような接続が、壁、柱、閉じた扉などのような建物構造と衝突しない、かつ/または交差しない場合、障害がないと考えることができる。2つの点は、例えば、それらが近隣の点である(例えば、第2の点が第1の点の近くの8つの点のうちの1点である)場合、隣接していると考えることができる。例えば、点(i,j)に対して、接続は、障害がない場合、点(i,j)と、8個のすぐ周りの点(i-1,j)、(i+1,j)、(i,j-1)、(i,j+1)、(i-1,j-1)、(i+1,j+1)、(i-1,j+1)、および(i+1,j-1)の各々との間に描くことができる。しかし、特許請求される主題は、この特定の相互接続手法にそのように限定はされない。
【００５０】
扉902を閉じた状態で、障害のない接続で隣接点を相互接続することで、複数の接続されていないグラフ(例えば、複数の接続されていない接続グラフ)が形成されうる。そのような複数の接続されていないグラフは、複数の独立の領域904を含むと考えることができる。具体的には、7つの独立の領域904a、904b、904c、904d、904e、904f、および904gが示される。4つの独立の領域904a、904b、904c、および904dが、扉902a、902b、902c、および902dを「閉じた」結果として少なくとも一部、形成される。図8および9と図4および5の比較から明らかなように、玄関の一部である独立の領域904eが、概略図900において部分的に示されている。独立の領域904fは、扉に直接は接続されない。独立の領域904fは、図12を特に参照して、本明細書において以下でさらに論じられる。
【００５１】
外側の点506は、独立の領域904gの一部を形成する点である。独立の領域904が少なくとも1つの外側の点506を含む場合、そのような独立の領域904は、建物構造に対して外側の領域を含むと考えることができる。したがって、独立の領域904gは、建物構造の外側にある独立の領域を含むと判定されうる。
【００５２】
図10は、ある実装形態による、扉が閉じた状態で模擬され、注記情報1002が複数の接続されていないグラフに重畳される、例示的な建物の部分の概略図1000である。注記情報(例えば、注記情報406)は、建物情報(例えば、建物情報400)の一部として含まれうる。いくつかの例示的な実装形態では、そのような注記情報は、経路案内グラフに重畳されうる。注記情報(例えば、注記情報302)の1つまたは複数の注記レイヤは、いくつか例を挙げると、規則のセットにしたがって自動的に、手動で、自動的な手法と手動の手法の何らかの組み合わせで、または他の方法で選択されうる。
【００５３】
注記情報の具体的な項目は、建物情報の地図上の座標と関連付けられうる。座標は、x座標,y座標の形態であってもよく、または何らかの他の形態であってもよい。限定ではなく例として、座標は、物理的な距離、測定された距離、ピクセルまたはドットの計数、これらの何らかの組み合わせなどに関して提供されうる。しかし、特許請求される主題は、座標情報の形態、フォーマットなどによって限定はされない。
【００５４】
2つの項目の注記情報1002が示される。しかし、代替的に、2つよりも少ない、または2つよりも多い、注記情報1002のそのような項目が存在してもよく、経路案内グラフに関連付けられてもよい。示されるように、注記情報1002aは座標(X1,Y1)と関連付けられ、「部屋1.14」のデータを含む。注記情報1002bは座標(X2,Y2)と関連付けられ、「部屋1.17」および「会議」のデータを含む。このデータは、以下のような特定の独立の領域904に関連付けられうる。
【００５５】
注記情報1002の所与の座標点は、独立の領域に対応する接続されていないグラフに接続されうる。扉が閉じた例示的な実施形態によれば、そのようなグラフの各々はこの時点では完全に接続がないことがあるので、座標点は、多くても、そのような複数の接続されていない接続グラフの1つのみに接続されうる。したがって、座標点を、グリッド化された建物の地図領域に挿入することができ、障害のない接続を、その座標点から他の点に描くことができる。これらのような例示的な方式で、抽出された注記レイヤを、対応する独立の領域と関連付けることができる。
【００５６】
具体的な例として、注記情報1002aの座標(X1,Y1)は、障害のない接続により独立の領域904bの点に接続されうる。したがって、注記情報1002aのデータ「部屋1.14」は、独立の領域904bに関連付けられうる。同様に、注記情報1002bの座標(X2,Y2)は、障害のない接続により独立の領域904cの点に接続されうる。したがって、注記情報1002bのデータ「部屋1.17」および/または「会議」は、独立の領域904cに関連付けられうる。
【００５７】
図11は、ある実装形態による、扉1102が開いた状態で模擬され、入口および出口が決定されうる、例示的な建物の部分の概略図1100である。いくつかの例示的な実装形態では、概略図1100に示されるように、少なくともいくつかの動作を、扉1102を開いた状態で模擬して(または等価的に、一時的に壁を除去して)、実行することができる。具体的には、5つの扉1102a、1102b、1102c、1102d、および1102eが示される。示されるように、開いた各扉1102は、少なくとも1つの点を用いて、経路案内グラフの扉のノードとして、模擬されうる。しかし、各扉は入口/出口の点ではなくてもよく、内側の部屋につながるだけの扉は、入口/出口の点とは考えることができない。
【００５８】
扉1102が開いた状態で、点のグリッド(例えば、図8の点のグリッド502)からの点が、障害のない接続を用いて、隣接点と相互接続されうる。そのような点のグリッドは、開いた扉1102の点も含みうる。扉の点1102を、障害のない接続により、独立の領域(例えば、扉が閉じた状態で模擬される時に、接続されていないグラフに対応する独立の領域)に直接接続するように試みることができる。扉1102が開いており扉の点により模擬された状態で、隣接点を障害のない接続で相互接続することにより、少なくとも1つの接続されたグラフ1104が形成されうる。
【００５９】
(図7の)動作708について本明細書において上で説明され、さらに図9を特に参照して説明されたように、少なくとも1つの独立の領域が、建物構造の外側の領域に相当するものとして確定されうる。例示的な実装形態では、独立の領域904gは、外側の領域に相当すると確定されうる。扉を開いた状態で模擬して、独立の領域904gはまた、接続されたグラフ1104の少なくとも一部を含みうる。概略図1100においては、先端の建物構造の点504は、建物構造(例えば、最小のx座標および最小のy座標を有する建物の要素)の最も左側で最も下の点に位置しうることにも留意されたい。
【００６０】
例示的な実装形態では、障害のない接続を、独立の領域904gのような確定された外側の領域の各点から、扉に対応する各点まで描くことを試みることができる。障害のない接続により扉1102が独立の領域904gの点に接続されうる場合、そのような扉は、建物構造の入口/出口であると判定されうる。したがって、扉1102eは、建物構造の少なくとも1つの入口/出口を含むと判定されうる。
【００６１】
入口/出口の点が特定される前に、特定される時に、かつ/または特定された後に、扉(例えば、内側の扉と外側の扉の両方)が全般に、障害のない接続を用いて、独立の領域に接続されうる。いくつかの例示的な実装形態では、使用不可能な領域は、少なくとも1つの入口/出口の点に接続できない領域であると判定されうる。例示的な手法が、図12を特に参照して、以下でさらに説明される。
【００６２】
図12は、ある実装形態による、扉が開いた状態で模擬され、独立の領域が使用可能か使用不可能かが判定されうる、例示的な建物の部分の概略図1200である。ある例示的な実装形態では、各々の独立の領域が、経路案内グラフを介して外側の点506から到達可能かどうかについて、分析されうる。独立の領域が外側の点506から到達可能である場合、独立の領域は、使用可能な領域1202を含むと考えることができる。一方、独立の領域が外側の点506から到達可能ではない場合、独立の領域は、使用不可能な領域1204を含むと考えることができる。
【００６３】
例示的な実装形態では、図5および8と図12を比較することで、概略図1200の外側の領域に外側の点506から到達可能であるということが明らかになる。したがって、領域1202eは、使用可能な領域1202eを含むと考えることができる。同様に、領域1202a、1202b、1202c、および1202dは、やはり外側の点506から到達可能であるので、使用可能な領域を含むと考えることができる。一方、領域1204には、外側の点506から経路案内グラフに沿って到達することができない。したがって、領域1204は、使用不可能な領域1204を含むと考えることができる。
【００６４】
少なくとも、使用可能な領域を含む独立の領域の接続されていないグラフが、障害のない接続によって相互接続された後に、少なくとも1つの接続グラフから経路案内グラフが作成されうる。点のグリッドの点は、そのような経路案内グラフのノードを含んでもよく、点を相互接続する接続は、そのような経路案内グラフのエッジを含んでもよい。さらに、到達できない領域を使用不可能な場所として区分けするとともに、Point of Interestを、対応する独立の領域と関連付けてもよく/接続してもよい。ある場所から別の場所への経路案内は、経路案内グラフにおいて2つの点/ノードを選択し、残りのグラフに対して最短経路アルゴリズム(例えばダイクストラ法など)を実行することによって、実施されうる。道案内指示(限定はされないが、リアルタイムの案内および/またはターンバイターンの案内を含む)は、そのような経路案内グラフを用いて提供されうる。さらに、代替的にかつ/または追加で、他の位置情報サービス(例えば位置決め、位置フィルタリングなど)を、作成された経路案内グラフに少なくとも一部基づいて、ユーザー(例えばモバイル機器のユーザー)に提供することができる。
【００６５】
図13は、ある実装形態による、独立の領域が廊下として検出されうる、少なくとも1つの例示的な建物の部分の概略図1300である。独立の領域は、扉が閉じた状態で模擬される時に決定されうるが、1つまたは複数の廊下は、扉が閉じた状態で、開いた状態で、または他の状態で模擬される時に、決定された独立の領域から検出されうる。いくつかの例示的な実装形態では、複数の独立の領域から、建物構造の1つまたは複数の廊下が、所与の独立の領域に直接接続される扉(例えば内側の扉)の所定の閾値に少なくとも一部基づいて、検出されうる。
【００６６】
図13において、概略図1300は、(図4の)建物情報400に相当する。独立の領域1302は、直接接続される扉の数に応じて、1つまたは複数の廊下を含むものと検出されうる。いくつかの例示的な実装形態では、領域(または点)が障害のない接続を介して相互接続されうる場合、直接別の領域、点などに接続することができる。概略図1300で示されるような例では、独立の領域1302は、23個の内側の扉のうちの22個に直接接続される。したがって、独立の領域1302は、示される建物構造の内側の扉の96%に、直接接続される。
【００６７】
限定ではなく例として、内側の扉の所定の閾値は、いくつか例を挙げると、絶対値、相対的な関係、これらの組み合わせなどであってよい。例えば、閾値は、建物構造(または、階、区画、ウィングなどのような、建物構造の画定された部分)の扉の総数に関連してもよい。あるいは、閾値は、他の独立の領域に直接接続される扉の平均の数に関連してもよい。
【００６８】
より具体的には、廊下を表す建物情報またはグラフの構成要素を検出するために、上記の平均の割合の建物構造の内側の扉に接続される独立の領域が見出されうる。例えば、ある実装形態では、建物構造の扉の、または建物構造内の扉の、少なくとも5%〜25%(例えば少なくとも10%)に接続し、かつ最低でも4個の扉に接続する独立の領域を、廊下であると定義することができる。例えば、建物構造が50個の扉を有する場合、(例えば20%の閾値レベルでは)10個以上の扉に接続される任意の独立の領域が、廊下として定義されうる。
【００６９】
図14は、ある実装形態による、例示的な機器1400を示す概略図であり、例示的な機器2000は、建物用の経路案内グラフの1つまたは複数の態様を実施することができる。示されるように、機器1400は、少なくとも1つのプロセッサ1402、1つまたは複数のメモリ1404、少なくとも1つの通信インターフェース1406、少なくとも1つの電源1408、および、SPSユニット(SPSU)(明確には示されていない)のような他の構成要素1410を含みうる。メモリ1404は、命令1412を含むものとして示されている。しかし、代替的には、機器1400は、示されている構成要素よりも、多くの、少ない、および/または異なる構成要素を含んでもよい。
【００７０】
いくつかの例示的な実装形態では、機器1400は、電子機器を含んでもよく、かつ/または備えてもよい。機器1400は、例えば、少なくとも1つのプロセッサおよび/またはメモリを有する任意の電子機器を含んでもよい。機器1400の例は、限定はされないが、固定式の処理機器(例えば、デスクトップコンピュータ、1つまたは複数のサーバコンピュータ、少なくとも1つの遠隔通信ノード、インテリジェントルータ/スイッチ、これらの何らかの組み合わせなど)、移動式の処理機器(例えば、ノートブックコンピュータ、携帯情報端末(PDA)、ネットブック、スレートまたはタブレット型コンピュータ、持ち運び式娯楽機器、携帯電話、スマートフォン、移動局、これらの何らかの組み合わせなど)などを含む。
【００７１】
電源1408は、機器1400の構成要素および/または回路に電力を供給することができる。電源1408は、電池のような持ち運び可能な電源であってもよく、または、自動車、家、または他の建物のコンセントのような、固定式の電源であってもよい。電源1408はまた、太陽または炭素燃料を用いる発電機のような、可搬型の電源であってもよい。電源1408は、機器1400と一体であっても分離していてもよい。
【００７２】
プロセッサ1402は、任意の1つまたは複数の処理ユニットを含みうる。メモリ1404は、プロセッサ1402により実行可能でありうる命令1412(例えば、プログラム、アプリケーションなど、またはこれらの一部、使用可能なデータ構造、プロセッサ実行可能命令/コード、これらの何らかの組み合わせなど)を保存し、格納し、または命令1412へのアクセスを提供することができる。1つまたは複数のプロセッサ1402によるそのような命令1412の実行により、機器1400は、特別な用途のコンピューティング機器、装置、プラットフォーム、これらの組み合わせなどに変換されうる。
【００７３】
命令1412は、経路案内グラフ命令1412a、建物情報1412b、および/または建物道案内ファイル1412cを含みうる。建物情報1412bは、例えば、(図3の)建物情報302(例えば(図4の)建物情報400)に対応しうる。建物道案内ファイル1412cは、例えば、(図3の)建物道案内ファイル308に対応していてもよく、建物道案内ファイル308は、少なくとも1つの経路案内グラフ312、1つまたは複数の接続グラフ316、および/または関連する注記情報314を含みうる。経路案内グラフ命令1412aは、例えば、(図6および7の)流れ図600および/または700の1つまたは複数の実施を実現することができる、命令に相当しうる。経路案内グラフ命令1412aを実行して、例えば、建物情報1412bに少なくとも一部基づいて、建物道案内ファイル1412cの少なくとも一部を生成することができる。明確には示されていないが、命令1412は、建物道案内ファイル1412cを用いて1つまたは複数の位置情報サービス(LBS)を提供するための命令も含みうる。
【００７４】
例示的な実装形態では、サーバおよび/または遠隔通信ノードのような固定式の処理機器が、経路案内グラフ命令1412aを実行して、建物情報1412bに少なくとも一部基づいて、建物道案内ファイル1412cを作成することができる。同一のまたは異なる固定式処理機器が、建物道案内ファイル1412cを用いて、例えば、SPSUを含みうるモバイル機器にLBSを提供することができる。あるいは、そのような固定式の処理機器は、建物道案内ファイル1412cをモバイル機器に提供して、いくつかのLBSを可能にする、またはいくつかのLBSのさらなる実行を可能にすることができる。さらに別の代替形態として、モバイル機器は、経路案内グラフ命令1412aを含み、(例えばオンデマンドで)ダウンロードされた建物情報1412bから建物道案内ファイル1412cを作成することができる。他の代替形態も、特許請求される主題から逸脱することなく、代わりに実施することができる。
【００７５】
通信インターフェース1406は、機器1400と他の機器(例えば、および/または使用する人)との間の1つまたは複数のインターフェースを提供することができる。したがって、通信インターフェース1406は、画面(例えばタッチスクリーン)、スピーカー、マイクロフォン、キーボードもしくはキー、ノブ/ホイール、または人と機器の間の他の入力/出力機構を含んでもよい。通信インターフェース1406は、送受信機(例えば送信機および/または受信機)、無線、アンテナ、有線インターフェースコネクタまたは他のそのような装置、これらの何らかの組み合わせなどを含み、無線信号および/または有線信号を(例えば無線通信リンクまたは有線通信リンクを通じて)通信することができる。通信インターフェース1406は、機器1400の他の構成要素間の、バスまたは他の相互接続としての役割も果たしうる。他の構成要素1410は、存在する場合、1つまたは複数の他の様々なセンサ、機構などを含んでもよい。
【００７６】
本明細書で説明された方法は、具体的な特徴および/または例にしたがって、用途に応じて様々な手段で実装されうる。例えば、そのような方法は、ハードウェア、ファームウェア、ソフトウェア、個別の/固定された論理回路、これらの任意の組み合わせなどで実装されうる。ハードウェアによる実装形態では、例えば、プロセッサ/処理ユニットは、いくつか例を挙げると、1つまたは複数の特定用途向け集積回路(ASIC)、デジタルシグナルプロセッサ(DSP)、デジタルシグナルプロセシングデバイス(DSPD)、プログラマブル論理デバイス(PLD)、フィールドプログラマブルゲートアレイ(FPGA)、プロセッサ全般、コントローラ、マイクロコントローラ、マイクロプロセッサ、電子的なデバイス、命令を実行するようにプログラムされた、かつ/もしくは本明細書で説明される機能を実行するように設計された、他のデバイスまたはユニット、および/またはこれらの組み合わせの中に、実装されうる。本明細書において、用語「制御論理回路」は、ソフトウェア/ファームウェアで実装される論理回路、ハードウェア(例えば個別の/固定された論理回路)、これらの任意の組み合わせなどを包含しうる。
【００７７】
ファームウェアおよび/またはソフトウェアによる実装形態では、方法は、本明細書で説明される機能を実行するモジュール(例えば、プロシージャ、関数など)により実装されうる。命令を有形に具現化する任意の機械可読媒体が、本明細書で説明される方法を実装する際に用いられうる。例えば、ソフトウェアコードをメモリに保存することができ、処理ユニットにより実行することができる。メモリは、処理ユニット内に実装されてもよく、処理ユニットの外側に実装されてもよい。本明細書で用いられる用語「メモリ」は、任意の種類の、長期的な、短期的な、揮発性の、非揮発性の、または他のメモリを指し、特定の種類のメモリまたは特定の数のメモリ、または記憶が保存される媒体の特定の種類に何ら限定されることはない。
【００７８】
ファームウェアおよび/またはソフトウェアによる実装形態では、機能は、1つまたは複数の命令またはコードとして、コンピュータ可読媒体に保存されうる。例には、データ構造でエンコードされたコンピュータ可読媒体と、コンピュータプログラムによりエンコードされたコンピュータ可読媒体とを含む。コンピュータ可読媒体は、製造物品の形態であってもよい。コンピュータ可読媒体は、物理的なコンピュータ記憶媒体を含む。記憶媒体は、コンピュータによりアクセスされうる任意の利用可能な媒体であってよい。限定ではなく例として、そのようなコンピュータ可読媒体は、RAM、ROM、EEPROM、CD-ROMもしくは他の光ディスク記憶装置、磁気ディスク記憶装置、半導体記憶装置、もしくは他の記憶機器、または、命令またはデータ構造の形態で所望のプログラムコードを保存するのに用いることができ、コンピュータによりアクセスすることができる、任意の他の媒体を含みうる。本明細書で用いられる場合、ディスク(disk)およびディスク(disc)は、コンパクトディスク(CD)、レーザーディスク（登録商標）、光ディスク、デジタル多目的ディスク(DVD)、フロッピー（登録商標）ディスクおよびブルーレイディスクを含み、ディスク(disk)は通常データを磁気的に再生し、ディスク(disc)はレーザーによりデータを光学的に再生する。上記の組み合わせも、コンピュータ可読媒体の範囲に含まれるべきである。
【００７９】
コンピュータ可読媒体への保存に加えて、命令および/またはデータは、通信装置に含まれる伝送媒体上の信号として提供されてもよい。例えば、通信装置は、命令およびデータを示す信号を有する送受信機を含んでもよい。命令およびデータは、1つまたは複数の処理ユニットに特許請求の範囲で概説される機能を実装させるように、構成される。つまり、通信装置は、開示される機能を実行するための情報を示す信号を有する、伝送媒体を含む。第1の時間では、通信装置に含まれる伝送媒体は、情報の第1の部分を含み開示される機能を実行することができるが、第2の時間では、通信装置に含まれる伝送媒体は、開示される機能を実行するための情報の第2の部分を含んでもよい。
【００８０】
電子機器は、Wi-Fi/WLANまたは他の無線ネットワークとともに動作することもできる。例えば、位置データが、Wi-Fiまたは他の無線ネットワークを介して取得されうる。Wi-Fi/WLAN信号に加えて、無線/移動式の機器は、全地球測位システム(GPS)、Galileo、GLONASS、NAVSTAR、QZSS、これらのシステムの組み合わせの衛星を用いるシステム、または将来開発される任意のSPSからの信号でありうる、衛星からの信号を受信することもでき、上述の各システムは、本明細書では衛星測位システム(SPS)と一般に呼ばれる。さらに、本明細書で説明される実装形態は、擬似衛星または衛星と擬似衛星の組み合わせを利用する、測位システムとともに用いられうる。擬似衛星は通常、擬似ランダムノイズ(PRN)符号または、Lバンド(または他の周波数)の搬送波信号に変調された他の測距コード(例えば、GPSまたはCDMAセルラー信号に類似した)をブロードキャストする、地上の送信機であり、上記の搬送波信号はGPS時間と同期されうる。各々のそのような送信機は、遠隔の受信機による識別を可能にするために、固有のPNコードを割り当てられうる。擬似衛星は、トンネル、鉱山、建物、アーバンキャニオン、または他の囲まれた領域のような、軌道衛星からのSPS信号が利用できない状況では、特に有用でありうる。擬似衛星の別の実装形態は、無線ビーコンとして知られている。本明細書で用いられる用語「衛星」は、擬似衛星、擬似衛星の等価物、および同様のかつ/または類似の技術も含むべきである。本明細書で用いられる場合、用語「SPS信号」は、擬似衛星または擬似衛星の等価物からのSPSのような信号も含むべきである。いくつかの実装形態は、フェムトセル、またはフェムトセルを含むシステムの組み合わせにも、適用されうる。
【００８１】
例示的な実装形態では、SPSU(存在すれば)は、1つまたは複数のSPSシステムを用いて、機器1400の位置を決定することができてもよい。したがって、本明細書で説明される例示的な実装形態は、様々なSPSとともに用いられうる。SPSは通常、エンティティが、送信機から受信された信号に少なくとも一部基づいて、地上または上空での自身の位置を決定することを可能にするように位置付けられた、送信機のシステムを含む。そのような送信機は、必須ではないが通常、一定の数のチップの繰り返し擬似ランダムノイズ(PN)符号でマークされた信号を送信し、地上の管制局、ユーザー装置、および/または宇宙船に存在しうる。具体的な例では、そのような送信機は、地球軌道宇宙機(SV)に存在しうる。例えば、全地球測位システム(GPS)、Galileo、GlonassまたはCompassのような全地球航法衛星システム(GNSS)の集合のSVは(例えば、GPSのように各衛星に対して異なるPN符号を用いて、またはGlonassのように異なる周波数に対して同一の符号を用いて)、その集合内の他のSVにより送信されたPN符号と区別可能なPN符号によりマークされる信号を送信することができる。いくつかの態様によれば、本明細書で提示される技術は、SPSのための地球規模のシステム(例えばGNSS)には限定されない。例えば、本明細書で提供される技術は、日本の準天頂衛星システム(QZSS)、インドのインド地域航法衛星システム(IRNSS)、中国の北斗など、ならびに/または、1つもしくは複数の地球規模のおよび/もしくは地域的な航法衛星システムに関連しうる、もしくはそれらとともに用いることが可能にされうる、様々な補強システム(例えば、静止衛星型衛星航法補強システム(SBAS))に、適用されてもよく、またはそれらとともに用いることが可能であってもよい。限定ではなく例として、SBASは、例えば、広域補強システム(WAAS)、European Geostationary Navigation Overlay Service(EGNOS)、多目的衛星用航法補強システム(MSAS)、GPS Aided Geo Augmented Navigation or GPS and Geo Augmented Navigation system(GAGAN)、および/または同様のもののような、統合情報、差分補正などを提供する補強システムを含みうる。したがって、本明細書で用いられる場合、SPSは、1つまたは複数の地球規模のおよび/もしくは地域的な航法衛星システムならびに/または補強システムの任意の組み合わせを含んでもよく、SPS信号は、SPS信号、SPSのような信号、および/またはそのような1つまたは複数のSPSと関連する他の信号を含んでもよい。
【００８２】
モバイル機器/移動局は、セルラー型の、または他の無線通信機器、個人用通信システム(PCS)機器、個人用ナビゲーション機器(PND)、個人情報管理装置(PIM)、携帯情報端末(PDA)、ラップトップ、タブレット、または、無線通信および/または道案内信号を受信することができる他の適切な機器のような、機器を指す。衛星信号の受信、支援データの受信、および/または位置に関する処理が、機器で行われるかPNDで行われるかには関係なく、モバイル機器は、短距離の無線、赤外線、有線接続、または他の接続などによって、個人用ナビゲーション機器(PND)と通信する機器を含むことも意図されている。また、モバイル機器は、無線通信機器、コンピュータ、ラップトップなどを含む全ての機器を含むことが意図されており、上記の機器類は、衛星信号の受信、支援データの受信、および/または位置に関連する処理が、機器で行われるか、サーバで行われるか、ネットワークに関連する他の機器で行われるかには関係なく、インターネット、Wi-Fi、または他のネットワークを介するなどして、サーバと通信することができる。上記の任意の動作可能な組み合わせも、モバイル機器であると考えることができる。
【００８３】
この発明を実施するための形態の一部は、特定の装置または専用のコンピューティング機器もしくはプラットフォームのメモリに保存されうるバイナリデジタル信号に対する動作の、アルゴリズムまたは記号による表現として提示されている。この特定の明細書においては、「特定の装置」などの用語は、プログラムソフトウェア/命令からの命令にしたがって特定の機能を実行するようにプログラムされた後の、汎用コンピュータを含む。アルゴリズムによる説明または記号による表現は、信号処理または関連技術の当業者が、自身の成果の本質を他の当業者に伝えるために用いられる、技法の例である。アルゴリズムとはここでは、かつ一般的に、所望の結果につながる、一貫した一連の動作または同様の信号処理であると考えることができる。これに関連して、動作または処理は、物理量の物理的な操作に関わる。必須ではないが通常、そのような物理量は、保存し、移送し、組み合わせ、比較し、送信し、受信し、または他の方法で操作することができる、電気信号および/または磁気信号の形態をとりうる。
【００８４】
主に一般に用いられているという理由で、そのような信号を、ビット、データ、値、要素、シンボル、文字、変数、語、数、番号などと呼ぶことが便利なことがあるということがわかっている。しかし、これらの用語および類似の用語は全て、適切な物理量と関連付けられるべきであり、便宜的な呼び方に過ぎないということを理解されたい。別段特に述べられない限り、上の議論から明らかなように、「処理する」、「計算する」、「算出する」、「決定する」、「確定する」、「識別する」、「関連付ける」、「取得する」、「実行する」、「適用する」、「調査する」、「分析する」、「作成する」、「模擬する」、「相互接続する」、「重畳する」、「検出する」などのような用語を利用する、本明細書の議論の全体が、専用コンピュータまたは同様の専用の電子的なコンピューティング機器のような、特定の装置の動作または処理を指すことが、理解されよう。したがって、この明細書においては、専用のコンピュータまたは同様の専用の電子的なコンピューティング機器は、信号を操作または変換することができ、上記の信号は通常、専用のコンピュータまたは同様の専用の電子的なコンピューティング機器の、メモリ、レジスタ、もしくは他の情報記憶機器、伝送機器、または表示機器の中で、物理的な、電気的な量、電子的な量、および/または磁気的な量として表される。
【００８５】
例示的な特徴であると現在考えられていることが、示されて説明されてきたが、特許請求される主題から逸脱することなく、様々な他の修正を行うことができ、等価物により置換できることが、当業者には理解されよう。加えて、本明細書で説明される主要な概念から逸脱することなく、多くの修正が、具体的な状況を特許請求される主題の教示に適合させるために行われうる。したがって、特許請求される主題は開示される具体的な例に限定されず、そのような特許請求される主題は、添付の特許請求の範囲およびその等価物の範囲にある、全ての態様も含みうることが、意図されている。
【符号の説明】
【００８６】
100 建物情報の概略図
104 注記情報
200 建物情報の概略図
206 使用不可能な領域
208 建物の外側の領域
210 経路案内グラフ
302 建物情報
304 建物地図ファイル
306 データ
308 建物道案内ファイル
312 経路案内グラフ
314 注記情報
316 接続グラフ
502 点のグリッド
1400 機器
1402 プロセッサ
1404 メモリ
1406 通信インターフェース
1408 電源
1410 他の構成要素
1412 命令
1412a 経路案内グラフ命令
1412b 建物情報
1412c 建物道案内ファイル
【技術分野】
【０００１】
米国特許法第119条による優先権の主張
この米国特許本出願は、2009年10月1日に出願された、AUTOMATIC ROUTING TOPOLOGY EXTRACTION FROM CAD MAPSという表題の、米国特許仮出願第61/247866号と、2009年10月1日に出願された、SYSTEM FOR INDOOR LOCATIONという表題の米国特許仮出願第61/247865号と、2009年10月1日に出願された、AUTOMATIC ROUTING TOPOLOGY EXTRACTION FROM LOW DETAIL SCHEMATICSという表題の米国特許仮出願第61/247869号と、2010年1月22日に出願された、MAP ACQUISITION AND PROCESSING FOR LOCATION BASED SERVICESという表題の米国特許仮出願第61/297524号との利益を主張するものであり、これらの仮出願の各々が、本出願の譲受人に譲渡され、参照によって本明細書に明示的に組み込まれる。
【０００２】
本明細書で開示される主題は、建物情報に少なくとも一部基づいて、経路案内グラフを作成することに関する。
【背景技術】
【０００３】
地図は、20世紀中に電子的形態で利用可能になり始めた。インターネットの出現により、基本的に世界中のあらゆる場所の地図に、最終的にはアクセスすることができる。ウェブ上の地図サービスは、地点「A」から地点「B」への案内を提供することもできる。これらのウェブ上での地図案内は、比較的静的である。しかし、衛星測位システム(SPS)技術およびさらに小型の電子機器の発明により、いわゆるターンバイターンの案内を、人々が自分の目的地に向かって移動するにつれて動的に提供することができる。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
残念ながら、これらの電子地図およびウェブ上の地図サービスは、ある住所から別の住所への案内のように、屋外で案内を提供することを目的としている。同様に、従来は、ターンバイターンの案内は道路上に限られている。今のところ、屋内で同様の地図および案内サービスを提供する能力が欠けている。
【課題を解決するための手段】
【０００５】
ある例示的な実装形態では、方法は、建物構造の少なくとも一部を表現する建物情報を得るステップと、点のグリッドを建物情報に重畳するステップとを含みうる。少なくとも1つの経路案内グラフが、重畳された点のグリッドと建物情報とに少なくとも一部基づいて、作成されうる。しかし、これは例示的な実装形態に過ぎず、他の実装形態が本明細書で説明され、特許請求される主題から外れることなく実装されうることを、理解されたい。
【０００６】
非限定的かつ非網羅的な態様、特徴などが、以下の図面を参照して説明され、様々な図面全体で、同様の番号は同様の部分を指す。
【図面の簡単な説明】
【０００７】
【図１】ある実装形態による、注記情報を有する例示的な建物情報の概略図である。
【図２】ある実装形態による、注記情報への関連付けを含む例示的な経路案内グラフが作成された、建物情報の概略図である。
【図３】ある実装形態による、建物情報および建物道案内ファイルの例を示すブロック図である。
【図４】ある実装形態による、例示的な建物情報の概略図である。
【図５】ある実装形態による、例示的な点のグリッドが重畳された、建物情報の概略図である。
【図６】ある実装形態による、建物情報に少なくとも一部基づいて経路案内グラフを作成するための例示的な方法を示す、流れ図である。
【図７】ある実装形態による、建物情報を分析して経路案内グラフを作成するための例示的な方法を示す、流れ図である。
【図８】ある実装形態による、点のグリッドが重畳された、例示的な建物の部分の概略図である。
【図９】ある実装形態による、扉が閉じられた状態で模擬され、独立の領域が相互接続された点から決定されうる、例示的な建物の部分の概略図である。
【図１０】ある実装形態による、扉が閉じられた状態で模擬され、注記情報が複数の接続されていないグラフに重畳される、例示的な建物の部分の概略図である。
【図１１】ある実装形態による、扉が開いた状態で模擬され、入口および出口が決定されうる、例示的な建物の部分の概略図である。
【図１２】ある実装形態による、扉が開いた状態で模擬され、独立の領域が使用可能か使用不可能かが決定されうる、例示的な建物の部分の概略図である。
【図１３】ある実装形態による、独立の領域が廊下として検出されうる、少なくとも1つの例示的な建物の部分の概略図である。
【図１４】建物の経路案内グラフの1つまたは複数の態様を実施することができる、ある実装形態による例示的な機器の概略図である。
【発明を実施するための形態】
【０００８】
本明細書全体における、「ある特徴」、「1つの特徴」、「ある例」、「一例」などへの言及は、特徴および/または例とともに説明される、具体的な特徴、構造、特性などが、特許請求される主題の少なくとも1つの特徴および/または例に関連するということを意味する。したがって、本明細書の様々な箇所における、「一例では」、「ある例」、「1つの特徴として」、「ある特徴」、「ある例示的な実装形態では」などのような語句の使用は、全てが同じ特徴、例、および/または例示的な実装形態を指すとは限らない。さらに、具体的な特徴、例、構造、特性などは、1つまたは複数の例示的な実装形態、例示的なシステムなどに組み合わされうる。
【０００９】
上で示されたように、2点間の案内およびターンバイターンの案内は、現在、屋外の環境、特に画定された道路のある環境に限定されている。一方、建物の内部では、通常、同様の地図または道案内の機能は提供されない。屋内での道案内を実現するために、ユーザーが現在位置している環境の地図が用いられうる。しかし、地図だけでは屋内での道案内には不十分であることがある。ユーザーを地図上のある地点から別の地点へ道案内するのを支援するために、グラフおよび関連する注記レイヤが用いられうる。そのようなグラフは、一般に経路案内グラフと呼ばれる。
【００１０】
点のグリッドは、建物の地図のような建物情報に重畳されうる。点のグリッドは、接続グラフの基準として機能することができ、接続グラフは、建物を分析し、また、エンティティがどのように建物中を移動するかを表現しうる経路案内グラフを作成するのに、用いることができる。関連する注記情報を有する経路案内グラフは、所与の地図の使用可能な領域を表すことができ、ある点から別の点への通行がどのように可能かを示すことができる。任意の所与の建物について、経路案内グラフは、使用可能な領域および建物内のある点から別の点への通行可能な経路を示す、ノードおよびエッジのセットを含みうる。残念ながら、関連付けられた注記情報を有するそのような経路案内グラフは、コンピュータ支援設計(CAD)の地図から直接は得られず、多くの建物構造は、CADの地図のような標準的なファイルフォーマットで表現されているだけである。CADの地図は、壁、部屋、廊下のような建物の構造についての情報を含むことが多いが、CADの地図は、エンティティがそのような建物構造全体をどのように移動するかを特定せず、または示さない。屋内の位置情報サービス(LBS)のエコシステムに対しては、手動で経路案内地図を描き、屋内の場所の構造を識別することは、豊富な情報を有する数億の建物構造を追加するのにスケーラブルな方法ではない。
【００１１】
本明細書で説明されるいくつかの例示的な実装形態では、方法は、既存の建物の(例えばCAD)ファイルを分析するステップと、その建物のCADファイルから抽出される情報に少なくとも一部基づいて、経路案内グラフを作成するステップとを伴いうる。例示的な経路案内グラフの作成処理は、多くの建物のCADファイルに共通の既存の要素を用いて、自動的に実行されうる。CAD地図の分析から、関連する注記情報を有する強力な経路案内グラフが生成されうる。そのような経路案内グラフを用いて、屋内での測位および/または道案内情報がユーザー(例えば、ユーザーのモバイル機器)に提供されうる。
【００１２】
図1は、ある実装形態による、注記情報104を有する例示的な建物情報の概略図100である。ある例示的な実装形態では、概略図100は、建物の少なくとも一部を表しうる。その外観は、いくつか例を挙げると、線、曲線、円弧、多角形などを含みうる。これらの項目は、建物構造の具体的な要素を表すように定義されうる。建物構造の例は、限定はされないが、スタジアム、アリーナ、コンベンションセンター、モール、トンネルまたは橋または廊下などで接続された建物の集合体、空港、オフィスビル(壁/仕切りで再配置可能なものを含む)、これらの組み合わせなどを含む。
【００１３】
例示的な建物の要素は、限定はされないが、壁、扉、柱、部屋などを含む。示されるように、概略図100は、いくつか例を挙げると、複数の扉102、注記情報104、線により表される壁などを含みうる。視覚的に明瞭にするために、そのような要素の全てが、図1において参照番号により明示的に示されてはいないが、説明文が、どの建物情報の構成要素がどの特定の描画上の要素により示されているかを示す。
【００１４】
概略図100は、外側の壁、内側の壁、部屋、廊下、内側の扉、外側の扉などを含みうる。しかし、壁、廊下、扉の種類などは通常、建物地図ファイルでは明示的には識別されない。人間はそのような建物の要素を容易に識別できうるが、機械は通常そのような能力をもたない。本明細書で説明されるようないくつかの例示的な実装形態は、少なくともいくつかの建物構造を識別することを可能にする。
【００１５】
機械が具体的な建物の要素を識別したとしても、機械が支援する道案内は必ずしも可能にはならないことがあることを理解されたい。例えば、ある人が、概略図100の地点#1から地点#2まで移動しようとすることがある。道案内指示を提供できるようにするために、概略図100の建物構造のために経路案内グラフが作成されうる。ユーザーが、具体的な部屋番号、使用者、および/または名付けられた場所への案内を求めることが許される場合、注記情報はそのような経路案内グラフと関連付けられうる。例示的な経路案内グラフおよび注記情報は、図2を特に参照して本明細書で以下でさらに説明される。
【００１６】
いくつかの例示的な実装形態では、対象の建物構造のCADの地図または同様の地図が利用可能でありうる。屋内での道案内は、地図の抽出および補間を用いて可能になりうる。地図の抽出により、例えばautoCADファイル(.dwg)に存在する地図情報が、いくつか例を挙げると、経路案内、位置決め、インセンティブアプリケーション、検索などのような屋内での位置情報サービスを可能にする、よりアクセスしやすい情報に変換されうる。この変換において、CADファイルで表されるような物理的な地図の特性が操作され、経路案内モジュールにより利用されうる構造に変換されうる。加えて、そのような抽出処理および変換処理は、自動化された方式で、および/または自動的に行われうる。実際には、地図の抽出および変換には、ユーザーは最小限しか関わらないか全く関わらない。さらに、そのような処理は、1つの地図につき数分程度で完了しうる。
【００１７】
いくつかの例示的な実装形態において、以下の動作のいずれも、自動化することができる。そのような例示的な動作は、異なる順序で実行されてもよく、かつ/または完全にもしくは一部重複するように実行されてもよい。第1に、建物構造内の使用可能な場所および使用不可能な場所が、識別されうる。地図を与えられると、ユーザーにより通行可能なそうした領域の位置が特定されうる。建物構造の内側と外側も、識別されうる。建物の外側の領域を(例えば内側の領域に対して)識別することで、次に位置決め技術を提供するのを容易にし、地図の領域内でのユーザーの位置決めを改善することができる。
【００１８】
第2に、地図の独立の領域が識別されうる。使用可能性を定義することに加えて、地図の個々の領域が全般的に識別されうる。例えば、所与のオフィスまたは他の部屋の境界を識別することで、経路案内の仕組みが容易になりうる。第3に、地図内の独立の領域の入口および出口の点が、識別されうる。会議室のような独立の領域に到達するために、ユーザーは、入口/出口の点に案内されうる。
【００１９】
第4に、建物の入口および出口の点が、所与の建物構造に対して特定されうる。シームレスな屋内での経路案内と、屋内から屋外への経路案内とを両方、より良く実現するために、入口および出口の点が、経路案内グラフの一部として、または経路案内グラフに関連するものとして、特定され含まれうる。加えて、緊急時行動および避難計画のためのアプリケーションが、そのような建物の入口および出口の点を利用することができる。
【００２０】
第5に、複数の場所を一緒に結びつけ、経路案内アプリケーションを動作させる経路案内グラフが、作成されうる。第6に、部屋の名前および場所のような注記レイヤからの情報を、地図情報から抽出することができ、経路案内、検索、位置フィルタリング(例えば、測位モジュールに対して制約を与えることによる)、および他の用途(例えば、別の位置情報システム(LBS))で用いるために、作成された経路案内グラフと統合することができる。図2に例として示されるように、オフィススペースの使用者ならびに部屋の名前で、部屋を名付けることができる。
【００２１】
図2は、ある実装形態による、注記情報212への関連付けを含む例示的な経路案内グラフ210が作成された、建物情報の概略図200である。示されるように、概略図200は、出口/入口202、内側の扉204、少なくとも1つの使用可能な領域206、建物の外側の領域208、経路案内グラフ210、および注記情報212を含みうる。経路案内グラフ210を用いて、案内アプリケーションおよび/またはシステムは、例えば地点#1から地点#2へ移動するための道案内指示を、個人に提供することができる。
【００２２】
視覚的に明瞭にするために、全てのそのような例示される要素が、図2において参照番号により明示的に示されてはいないが、説明文が、どの建物の要素がどの特定の描画上の要素により示されているかを示す。また、概略図200および経路案内グラフ210は、図2において示され本明細書において以下で説明されるようないくつかの例示的な構成要素を含むが、特許請求される主題はそのようには限定されない。代わりに、所与の実装形態は、より多くの、より少ない、かつ/または異なる構成要素を含んでもよい。
【００２３】
いくつかの例示的な実装形態では、経路案内のトポロジーを示す経路案内グラフ210が、概略図200の建物構造に対応するように作成されうる。建物情報の例示的な分析の一部として、独立の領域が決定されうる。独立の領域は、いくつか例を挙げると、部屋、廊下、建物の外側などを含みうる。少なくとも1つの独立の領域が、建物の外側の領域208を含むものと確定されうる。1つまたは複数の別の独立の領域は、使用不可能な領域206を含むものと判定されうる。立ち入ることのできる独立の領域は、使用可能な領域(例えば、入室可能な部屋、廊下など)を含むものと判定されうる。本明細書で用いられる場合、「部屋」(またはより一般的には区域)は、いくつか例を挙げると、オフィス、小部屋、休憩室、店舗、売店、フードコート、アパート/コンドミニアム、ブース、展示物、空港のゲート、アトラクション、他の定義可能な区域、およびこれらの組み合わせなどを含みうる。
【００２４】
1つもしくは複数の出口および/または入口202は、建物情報に含まれる扉が建物の外側の領域208に接続し、そこへのアクセスを提供する場合、そのような扉から決定されうる。1つまたは複数の内部の扉204は、内側の部屋、廊下などのような他の使用可能な領域へのアクセスを提供すると判定されうる。注記情報212は、経路案内グラフ210と関連付けられ、異なる領域(例えば部屋、区域など)の間での道案内サービスまたは他の位置情報サービスをさらに実現することができる。限定ではなく例として、注記情報212は、部屋の指定(例えば「A」、「1.24」など)、部屋の名前(例えば「会議室1」など)、部屋の目的(例えば「浴室」、「厨房」など)、部屋の居住者または使用者(例えば「Amy」、「Ray」など)などを含みうる。注記情報212は、いくつか例を挙げると、ロビー、エレベーター群、食事の場所などのような特定の区域と関連する情報を提供することもできる。経路案内グラフ210は、ある注記された領域から別の注記された領域への経路を含む、ある地点から別の地点への経路を描くのに用いることができる。
【００２５】
図3は、ある実装形態による、建物情報302および建物道案内ファイル308の例を示す、ブロック図300である。いくつかの例示的な実装形態では、建物情報302は、建物構造の少なくとも一部を表現する、任意の情報のセットまたは集合を含んでもよい。建物情報302に少なくとも一部基づいて、建物道案内ファイル308が作成されうる。建物道案内ファイル308は、少なくとも1つの経路案内グラフ312、注記情報314、および/または1つもしくは複数の接続グラフ316を含みうる。少なくとも経路案内グラフ312は、注記情報314に関連付けられ、または注記情報314と連携しうる。建物情報302、建物道案内ファイル308などは、電気信号(例えばデジタル信号)として実現されうる。
【００２６】
例として、建物情報302は、建物設計ファイル304および/または建物レイアウトファイル306を含みうる。建物設計ファイル304は、建物構造の少なくとも一部を表すデータ310a(例えば、CADまたは同様のフォーマットのデータ)を含みうる。建物レイアウトファイル306は、建物構造の少なくとも一部を表すデータ310b(例えば、drawing interchange/exchange format(DXF)または同様のフォーマットのデータ)を含みうる。建物情報302の例が以下で説明されるが、特許請求される主題はこれらの例にはそのようには限定はされない。より具体的には、建物情報302は、変換前または変換後の、変換を伴うまたは変換を伴わない、およびその他の、任意のフォーマットで存在しうる。さらに、建物情報302は、建物道案内ファイル308を作成する処理の間、任意の1つまたは複数のフォーマットで表されうる。例えば、建物道案内ファイル308の第1の部分は、建物情報302が第1のフォーマットである時に作成することができ、建物道案内ファイル308の第2の部分は、建物情報302が第2のフォーマットである時に作成することができる。
【００２７】
例示的な実装形態では、建物設計ファイル304は、建物構造および1つまたは複数の注記情報レイヤを格納するCADファイルに相当しうる。拡張子が「.dwg」のファイルは、拡張子が「.dxf」のファイルに変換することができ、「.dxf」ファイルは、テキスト構文解析機能を用いることで構文解析されうる、オープンフォーマットである。一般に、プロプライエタリフォーマット(例えば、「.dwg」ファイルなどのような)は、公に知られている構文(例えば、「.dxf」ファイルなどのような)を有する任意の交換フォーマットに変換されうる。CADファイル中のどの注記レイヤまたは複数の注記レイヤが、作製された経路案内グラフと関連付けられることになる注記レイヤであるかを識別するのに、この時点で使用者との対話が用いられうる。例えば、部屋の名前を関連付けることを望む場合、使用者が、そのようなレイヤの名前を選択または特定することができる。そのようなレイヤ(例えば「部屋レイヤ」)は、CADファイルの中で別々に標識されうる。あるいは、注記レイヤの選択は、いくつか例を挙げると、自動的に行われてもよく、1つまたは複数の規則にしたがって自動化されてもよく、これらの組み合わせなどであってもよい。
【００２８】
dxfでフォーマットされたファイルが得られると、建物の少なくとも一部の構造情報を抽出することができる。そのような情報は、いくつか例を挙げると、壁、窓、扉、柱などに関連しうる。dxfでフォーマットされたファイルにより、建物情報の要素を、線、弧などにより表すことができる。より具体的には、dxfでフォーマットされたファイルが構文解析された後、壁のような情報を線分により表すことができ、扉のような情報を線分および弧により表すことができる。
【００２９】
例えば、ある特定の壁が「部屋A」の壁であること、または、ある特定の扉が外側の出口/入口であることを示す情報は、存在しないことがある。しかし、そのような建物の要素の情報を処理して、抽出された情報から何らかの他のレイヤを推定することができる。例えば、ある特定の部屋(例えば「部屋A」)の境界ボックスを識別するために、位置情報が部屋の注記レイヤから抽出されうる。部屋の注記レイヤは、「部屋A」を特定する空間中の座標点(例えば、x=22、y=758)を示しうる。この情報を用いて、例えば、この点の周りの最小の閉じた領域または独立の領域が、経路案内の目的で決定され、部屋Aと標識されうる。注記情報を関連付けるこの処理の例示的な手法が、図10を特に参照して本明細書において以下でさらに説明される。
【００３０】
図4は、ある実装形態による、例示的な建物情報400の概略図である。建物情報400は、(図3の)建物情報302の例であってよい。したがって、建物情報400は、CADフォーマット、テキスト構文解析可能なフォーマット、これらの組み合わせ、または任意の他の1つまたは複数の種類のフォーマットであってよい。いくつかの例示的な実装形態では、建物情報400は、1つまたは複数の建物の要素を表す項目を含みうる。
【００３１】
示されるように、建物情報400は、壁402および扉404を少なくとも含む。「扉」404は、いくつか例を挙げると、階段の吹き抜け、エレベーターなども含みうる。さらに、建物の階への最初の入口(またはそこからの最後の出口)となる任意の要素は、扉404であると考えることができる。さらに、建物の要素を表す、より多くのまたは異なる構成要素が、建物情報400の一部として代替的に含まれてもよい。建物情報400は、注記情報406も含みうる。図5から、そのような建物構造の一部を表す建物情報400を用いて例示的な概念を示す。
【００３２】
図5は、ある実装形態による、例示的な点のグリッド502が重畳された、建物情報400の概略図500である。示されるように、概略図500は、建物情報400、点のグリッド502、先端の建物構造の点504、外側の点506を含みうる。いくつかの例示的な実装形態では、点のグリッド502は、建物情報400に重畳されうる。限定ではなく例として、点のグリッド502は、2つの軸(例えばx軸およびy軸)に沿って一定の間隔で位置する点のセットであってよい。点のグリッド502は、建物情報400の建物構造の、一部、実質的に全て、全て、または全てよりも広い範囲をカバーしてもよい。示されるように、点のグリッド502は、建物情報400の建物構造の外側の境界を超えて延びる。
【００３３】
点のグリッドの分解能または縮尺(例えば、2つの隣接点の間隔)は、変化してもよい。例えば、分解能は、いくつか例を挙げると、位置情報サービスで求められる正確さのレベル(例えば道案内の地図の正確さ)、建物情報の分析を分担しうるリソース(例えばメモリ、処理、および/または時間)の使用可能な量、部屋または他の独立の領域の実際のサイズもしくは予測されるサイズなどに基づいて、変化しうる。縮尺も、単一の建物構造における異なる所望の分解能のレベルに対応するように、単一の点のグリッドにおいて変化しうる。例示的な実装形態では、点のグリッドの数は、カバーされている地図のサイズにより決まりうる。地図のサイズは、線、弧などのような地図中の要素の各々の座標を求めることによって、かつ、要素の最小のならびに最大のx座標およびy座標を求めることによって、自動的に計算することができる。さらに、いくつかのCADファイルは、-1400、-200のような、負側の象限に原点を有することがある。そのような場合、地図の抽出処理は、地図の最小のx座標およびy座標を0,0における原点とするように変換することができ、他の要素もそれにしたがって変換することができる。そのような変換は、実行されると、地図の要素、POI(Point of Interest)などに関連する座標の理解を、容易にすることができる。POIは、いくつか例を挙げると、店舗、部屋、ターミナル/ゲート、展示物などを含みうる。例えば、所与の部屋が建物の左側の角から200フィートの距離にあるということを示すことが比較的わかりやすくなり、建物の左側の角は、変換によって原点0,0となるように定義されうる。
【００３４】
外側の点506は、先端の建物構造の点504に少なくとも一部基づいて、決定されうる。示されるように、先端の建物構造の点504は、建物構造の最も右側で最も上の点(例えば、最大のx-y座標を有する建物構造の点)である。あるいは、先端の建物構造の点504は、最小のx座標およびy座標を有してもよく、最も右側で最も下の点であってもよく、最大のy座標を有する最も左側の点であってもよく、またはその他であってもよい。先端の建物構造の点504(例えば、建物構造の最大座標(x,y))が選択されると、外側の点506を、例えばx-y座標の少なくとも1つを所定の量変化させることによって、点504に少なくとも一部基づいて決定することができる。例えば、外側の点506は、先端の建物構造の点504のx座標にΔxを加えることによって、かつ、先端の建物構造の点504のy座標にΔyを加えることによって、(例えば、外側の座標(x+Δx,y+Δy)を決定するように)決定されうる。本明細書において以下で説明されるように、外側の点506は、建物構造の外側の領域の決定に用いることができる。
【００３５】
点のグリッド502を重畳するための、建物構造の「グリッド化」を、外側の点506で開始することができる。グリッド化は、建物または建物の階の全てを含む、建物の所望の部分の全体がカバーされるまで、外側の点506から始めて、例えば複数の方向に1フィート間隔で点を追加することで、達成されうる。建物の周りの最大の領域が、建物情報ファイルから抽出される任意のオブジェクト(例えば、線分、扉、注記レイヤなど)のx座標とy座標の最小値および最大値を決めることによって、決定されうる。
【００３６】
図6は、ある実装形態による、建物情報に少なくとも一部基づいて、経路案内グラフを作成するための例示的な方法を示す、流れ図600である。示されるように、流れ図600は、4つの動作ブロック602、604、606、および608を含む。動作602〜608は特定の順序で示され説明されるが、特許請求される主題から逸脱することなく、方法は代替的な方式で実行されうることを理解されたい。また、流れ図600の動作は、互いに完全にまたは一部重複して実行されてもよい。加えて、以下の説明は、いくつかの他の図(例えば図3〜5)で示される具体的な態様および特徴に言及するが、方法は他の態様および/または特徴とともに実行されてもよい。
【００３７】
いくつかの例示的な実装形態では、動作602において、建物構造の少なくとも一部を表現する建物情報が取得されうる。例えば、(例えば、建物情報400として図4で示されるような)建物構造の少なくとも一部を表現する建物情報302が取得されうる。建物情報302は、いくつか例を挙げると、メモリから取り出すことによって、無線通信リンクまたは有線通信リンクを介して受信することによって、または他の方法で、取得することができる。動作604において、点のグリッドが建物情報に重畳されうる。例えば、点のグリッド502が、建物情報400に重畳されうる。
【００３８】
動作606において、建物情報が、点のグリッドを用いて分析されうる。例えば、点のグリッド502を用いた建物情報400の分析により、いくつか例を挙げると、独立の領域を決定すること、建物の入口および出口を決定すること、使用可能な領域と使用不可能な領域を決定すること、廊下を検出することなどを、可能にすることができる。点のグリッドを用いて建物情報を分析する例示的な手法が、図7を特に参照して本明細書において以下でさらに説明される。動作608において、経路案内グラフを、重畳された点のグリッドおよび建物情報に少なくとも一部基づいて作成することができる(例えば、少なくとも1つの経路案内グラフを表す電気信号(例えばデジタル信号)が生成されうる)。例えば、注記情報314への関連付けを有する経路案内グラフ312を、重畳された点のグリッド502および建物情報302に少なくとも一部基づいて、建物情報400のために作成することができる。
【００３９】
そのような経路案内グラフは、同じ機器または異なる機器において次に使用するために保存されてもよく、かつ/または、作成された後すぐに、もしくは実質的にすぐに使用されてもよい。例えば、経路案内グラフのデータベースは、次に取り出すために、かつ位置情報サービスに対して次に適用するために、保存されうる。あるいは、機器(例えばモバイル機器)が経路案内グラフを作成し、オンデマンドで、道案内または他の位置情報アプリケーションのために経路案内グラフを使用してもよい。いずれにしても、建物構造に関連する道案内情報(例えば、方向、完全なまたは部分的な経路案内グラフなど)を、少なくとも1つの経路案内グラフを用いてモバイル機器に提供することができる。
【００４０】
図7は、ある実装形態による、建物情報を分析して経路案内グラフを作成するための、例示的な方法を示す流れ図700である。示されるように、流れ図700は、10個の動作ブロック702〜720を含む。動作702〜720は特定の順序で示され説明されるが、特許請求される主題から逸脱することなく、方法は代替の方式で実行されうることを理解されたい。また、流れ図700の動作は、互いに完全にまたは一部重複して実行されてもよい。加えて、以下の説明は、いくつかの他の図(例えば図3〜5および図8〜13)で示される具体的な態様および特徴に言及するが、方法は他の態様および/または特徴とともに実行されてもよい。
【００４１】
動作702において、扉は、閉じた状態で模擬されうる。例えば、建物情報400の扉は、閉じていると考えることができる。動作704において、点のグリッド(例えば、点のグリッド502)の隣接点を、障害のない接続で相互接続することができる。例えば、接続が建物の要素と交差して接続グラフ316の少なくとも一部を形成しない場合、所与の点から、最大8つの近隣の点との間に接続を確立することができる。扉が閉じた状態で、この相互接続は複数の接続されていないグラフを形成することができる。
【００４２】
動作706において、複数の独立の領域が決定されうる。例えば、複数の独立の領域を、扉を閉じた状態で隣接点を障害のない接続によって相互接続することで形成される、複数の接続されていないグラフに少なくとも一部基づいて、決定することができる。動作708において、建物の部分の外側の少なくとも1つの独立の領域を、確定することができる。例えば、建物の部分の外側にあるものとして識別されるある点(例えば外側の点506)を用いて、外側の独立の領域を確定することができる。
【００４３】
動作702〜708の例示的な実装形態が、図9を特に参照して本明細書において以下でさらに説明される。動作710において、建物の注記情報が、接続グラフに重畳されうる。例えば、注記情報314は、少なくとも1つの接続グラフ316と関連付けられうる。動作710の例示的な実装形態が、図10を特に参照して、本明細書において以下でさらに説明される。
【００４４】
動作712において、扉は、開いた状態で模擬されうる。例えば、建物情報400の扉は、開いていると考えることができる。さらに、扉の点(例えば、扉の位置を表す点)が、開いた各扉の点のグリッドに追加されうる。動作714において、点のグリッド(例えば点のグリッド502)の隣接点が、障害のない接続により相互接続されうる。そのような相互接続される点は、扉の点として追加されるノードを含みうる。点が既に相互接続されている場合(例えば動作704において)、新しく追加される扉の点は、既存の接続されていないグラフに相互接続されうる。したがって、扉の点は、点のグリッドの他の点に接続され、少なくとも1つの相互接続されたグラフを形成することができる。
【００４５】
動作716において、建物構造の少なくとも1つの1つまたは複数の入口/出口が決定されうる。例えば、外側の独立の領域に(例えば、障害のない接続を介して)直接接続する扉は、建物の入口/出口であると判定されうる。動作712〜716の例示的な実装形態は、図11を特に参照して、本明細書において以下でさらに説明される。
【００４６】
動作718において、どの独立の領域が使用可能か、および、1つまたは複数の独立の領域が使用不可能であるかどうかが判定されうる。例えば、1つまたは複数の独立の領域に、外側の点から到達できるかどうかが、判定されうる。動作718の例示的な実装形態は、図12を特に参照して、本明細書において以下でさらに説明される。動作720において、1つまたは複数の廊下が検出されうる。例えば、1つまたは複数の独立の領域が少なくとも1つの廊下を含むかどうかが、各独立の領域に直接接続される扉の数に少なくとも一部基づいて、検出されうる。独立の領域は、閉じた状態で模擬される扉により決定されうるが(例えば動作706において)、廊下の検出は、任意の状態で模擬される扉により実行されうる。動作720の例示的な実装形態は、図13を特に参照して、本明細書において以下でさらに説明される。
【００４７】
図8は、ある実装形態による、点のグリッド502が重畳された、例示的な建物の部分800の概略図である。明瞭にするために示されるように、建物の部分800は、(図4の)建物情報400の一部(例えば断面)である。建物の部分800は、図8、ならびに図9〜12において、さらに詳細に示すために拡大されている。図9〜12は、全般に、建物の部分800を用いる異なる態様および/または実装形態を示す。図8において、建物の部分800は、壁402および扉404を含む。図8には示されないが、(図5の)先端の建物構造の点504および外側の点506、ならびに、建物構造の外側の角が、図9および11に表されている。
【００４８】
図9は、ある実装形態による、扉902が閉じた状態で模擬され、独立の領域904が相互接続された点から決定されうる、例示的な建物部分の概略図900である。いくつかの例示的な実装形態では、概略図900に示されるように、少なくともいくつかの動作が、扉902を閉じた状態で模擬して、実行される。(代替的な設計では、閉じた扉は、一時的に扉を壁で置き換えたのと等価であると考えることができる。)具体的には、4つの扉902a、902b、902c、および902dが示される。扉を閉じたものとして模擬することで、独立の領域が分離されうる。
【００４９】
扉902を閉じた状態で、点のグリッド(例えば、図8の点のグリッド502)からの点が、障害のない接続により隣接点と相互接続されうる。点の相互接続は、例えば、あらゆる任意の点から開始することができる。壁、閉じた扉または他の建物構造に直接位置する全ての点が、無視されうる。2点間の接続(例えば第1の地点から第2の地点への接続)は、例えば、そのような接続が、壁、柱、閉じた扉などのような建物構造と衝突しない、かつ/または交差しない場合、障害がないと考えることができる。2つの点は、例えば、それらが近隣の点である(例えば、第2の点が第1の点の近くの8つの点のうちの1点である)場合、隣接していると考えることができる。例えば、点(i,j)に対して、接続は、障害がない場合、点(i,j)と、8個のすぐ周りの点(i-1,j)、(i+1,j)、(i,j-1)、(i,j+1)、(i-1,j-1)、(i+1,j+1)、(i-1,j+1)、および(i+1,j-1)の各々との間に描くことができる。しかし、特許請求される主題は、この特定の相互接続手法にそのように限定はされない。
【００５０】
扉902を閉じた状態で、障害のない接続で隣接点を相互接続することで、複数の接続されていないグラフ(例えば、複数の接続されていない接続グラフ)が形成されうる。そのような複数の接続されていないグラフは、複数の独立の領域904を含むと考えることができる。具体的には、7つの独立の領域904a、904b、904c、904d、904e、904f、および904gが示される。4つの独立の領域904a、904b、904c、および904dが、扉902a、902b、902c、および902dを「閉じた」結果として少なくとも一部、形成される。図8および9と図4および5の比較から明らかなように、玄関の一部である独立の領域904eが、概略図900において部分的に示されている。独立の領域904fは、扉に直接は接続されない。独立の領域904fは、図12を特に参照して、本明細書において以下でさらに論じられる。
【００５１】
外側の点506は、独立の領域904gの一部を形成する点である。独立の領域904が少なくとも1つの外側の点506を含む場合、そのような独立の領域904は、建物構造に対して外側の領域を含むと考えることができる。したがって、独立の領域904gは、建物構造の外側にある独立の領域を含むと判定されうる。
【００５２】
図10は、ある実装形態による、扉が閉じた状態で模擬され、注記情報1002が複数の接続されていないグラフに重畳される、例示的な建物の部分の概略図1000である。注記情報(例えば、注記情報406)は、建物情報(例えば、建物情報400)の一部として含まれうる。いくつかの例示的な実装形態では、そのような注記情報は、経路案内グラフに重畳されうる。注記情報(例えば、注記情報302)の1つまたは複数の注記レイヤは、いくつか例を挙げると、規則のセットにしたがって自動的に、手動で、自動的な手法と手動の手法の何らかの組み合わせで、または他の方法で選択されうる。
【００５３】
注記情報の具体的な項目は、建物情報の地図上の座標と関連付けられうる。座標は、x座標,y座標の形態であってもよく、または何らかの他の形態であってもよい。限定ではなく例として、座標は、物理的な距離、測定された距離、ピクセルまたはドットの計数、これらの何らかの組み合わせなどに関して提供されうる。しかし、特許請求される主題は、座標情報の形態、フォーマットなどによって限定はされない。
【００５４】
2つの項目の注記情報1002が示される。しかし、代替的に、2つよりも少ない、または2つよりも多い、注記情報1002のそのような項目が存在してもよく、経路案内グラフに関連付けられてもよい。示されるように、注記情報1002aは座標(X1,Y1)と関連付けられ、「部屋1.14」のデータを含む。注記情報1002bは座標(X2,Y2)と関連付けられ、「部屋1.17」および「会議」のデータを含む。このデータは、以下のような特定の独立の領域904に関連付けられうる。
【００５５】
注記情報1002の所与の座標点は、独立の領域に対応する接続されていないグラフに接続されうる。扉が閉じた例示的な実施形態によれば、そのようなグラフの各々はこの時点では完全に接続がないことがあるので、座標点は、多くても、そのような複数の接続されていない接続グラフの1つのみに接続されうる。したがって、座標点を、グリッド化された建物の地図領域に挿入することができ、障害のない接続を、その座標点から他の点に描くことができる。これらのような例示的な方式で、抽出された注記レイヤを、対応する独立の領域と関連付けることができる。
【００５６】
具体的な例として、注記情報1002aの座標(X1,Y1)は、障害のない接続により独立の領域904bの点に接続されうる。したがって、注記情報1002aのデータ「部屋1.14」は、独立の領域904bに関連付けられうる。同様に、注記情報1002bの座標(X2,Y2)は、障害のない接続により独立の領域904cの点に接続されうる。したがって、注記情報1002bのデータ「部屋1.17」および/または「会議」は、独立の領域904cに関連付けられうる。
【００５７】
図11は、ある実装形態による、扉1102が開いた状態で模擬され、入口および出口が決定されうる、例示的な建物の部分の概略図1100である。いくつかの例示的な実装形態では、概略図1100に示されるように、少なくともいくつかの動作を、扉1102を開いた状態で模擬して(または等価的に、一時的に壁を除去して)、実行することができる。具体的には、5つの扉1102a、1102b、1102c、1102d、および1102eが示される。示されるように、開いた各扉1102は、少なくとも1つの点を用いて、経路案内グラフの扉のノードとして、模擬されうる。しかし、各扉は入口/出口の点ではなくてもよく、内側の部屋につながるだけの扉は、入口/出口の点とは考えることができない。
【００５８】
扉1102が開いた状態で、点のグリッド(例えば、図8の点のグリッド502)からの点が、障害のない接続を用いて、隣接点と相互接続されうる。そのような点のグリッドは、開いた扉1102の点も含みうる。扉の点1102を、障害のない接続により、独立の領域(例えば、扉が閉じた状態で模擬される時に、接続されていないグラフに対応する独立の領域)に直接接続するように試みることができる。扉1102が開いており扉の点により模擬された状態で、隣接点を障害のない接続で相互接続することにより、少なくとも1つの接続されたグラフ1104が形成されうる。
【００５９】
(図7の)動作708について本明細書において上で説明され、さらに図9を特に参照して説明されたように、少なくとも1つの独立の領域が、建物構造の外側の領域に相当するものとして確定されうる。例示的な実装形態では、独立の領域904gは、外側の領域に相当すると確定されうる。扉を開いた状態で模擬して、独立の領域904gはまた、接続されたグラフ1104の少なくとも一部を含みうる。概略図1100においては、先端の建物構造の点504は、建物構造(例えば、最小のx座標および最小のy座標を有する建物の要素)の最も左側で最も下の点に位置しうることにも留意されたい。
【００６０】
例示的な実装形態では、障害のない接続を、独立の領域904gのような確定された外側の領域の各点から、扉に対応する各点まで描くことを試みることができる。障害のない接続により扉1102が独立の領域904gの点に接続されうる場合、そのような扉は、建物構造の入口/出口であると判定されうる。したがって、扉1102eは、建物構造の少なくとも1つの入口/出口を含むと判定されうる。
【００６１】
入口/出口の点が特定される前に、特定される時に、かつ/または特定された後に、扉(例えば、内側の扉と外側の扉の両方)が全般に、障害のない接続を用いて、独立の領域に接続されうる。いくつかの例示的な実装形態では、使用不可能な領域は、少なくとも1つの入口/出口の点に接続できない領域であると判定されうる。例示的な手法が、図12を特に参照して、以下でさらに説明される。
【００６２】
図12は、ある実装形態による、扉が開いた状態で模擬され、独立の領域が使用可能か使用不可能かが判定されうる、例示的な建物の部分の概略図1200である。ある例示的な実装形態では、各々の独立の領域が、経路案内グラフを介して外側の点506から到達可能かどうかについて、分析されうる。独立の領域が外側の点506から到達可能である場合、独立の領域は、使用可能な領域1202を含むと考えることができる。一方、独立の領域が外側の点506から到達可能ではない場合、独立の領域は、使用不可能な領域1204を含むと考えることができる。
【００６３】
例示的な実装形態では、図5および8と図12を比較することで、概略図1200の外側の領域に外側の点506から到達可能であるということが明らかになる。したがって、領域1202eは、使用可能な領域1202eを含むと考えることができる。同様に、領域1202a、1202b、1202c、および1202dは、やはり外側の点506から到達可能であるので、使用可能な領域を含むと考えることができる。一方、領域1204には、外側の点506から経路案内グラフに沿って到達することができない。したがって、領域1204は、使用不可能な領域1204を含むと考えることができる。
【００６４】
少なくとも、使用可能な領域を含む独立の領域の接続されていないグラフが、障害のない接続によって相互接続された後に、少なくとも1つの接続グラフから経路案内グラフが作成されうる。点のグリッドの点は、そのような経路案内グラフのノードを含んでもよく、点を相互接続する接続は、そのような経路案内グラフのエッジを含んでもよい。さらに、到達できない領域を使用不可能な場所として区分けするとともに、Point of Interestを、対応する独立の領域と関連付けてもよく/接続してもよい。ある場所から別の場所への経路案内は、経路案内グラフにおいて2つの点/ノードを選択し、残りのグラフに対して最短経路アルゴリズム(例えばダイクストラ法など)を実行することによって、実施されうる。道案内指示(限定はされないが、リアルタイムの案内および/またはターンバイターンの案内を含む)は、そのような経路案内グラフを用いて提供されうる。さらに、代替的にかつ/または追加で、他の位置情報サービス(例えば位置決め、位置フィルタリングなど)を、作成された経路案内グラフに少なくとも一部基づいて、ユーザー(例えばモバイル機器のユーザー)に提供することができる。
【００６５】
図13は、ある実装形態による、独立の領域が廊下として検出されうる、少なくとも1つの例示的な建物の部分の概略図1300である。独立の領域は、扉が閉じた状態で模擬される時に決定されうるが、1つまたは複数の廊下は、扉が閉じた状態で、開いた状態で、または他の状態で模擬される時に、決定された独立の領域から検出されうる。いくつかの例示的な実装形態では、複数の独立の領域から、建物構造の1つまたは複数の廊下が、所与の独立の領域に直接接続される扉(例えば内側の扉)の所定の閾値に少なくとも一部基づいて、検出されうる。
【００６６】
図13において、概略図1300は、(図4の)建物情報400に相当する。独立の領域1302は、直接接続される扉の数に応じて、1つまたは複数の廊下を含むものと検出されうる。いくつかの例示的な実装形態では、領域(または点)が障害のない接続を介して相互接続されうる場合、直接別の領域、点などに接続することができる。概略図1300で示されるような例では、独立の領域1302は、23個の内側の扉のうちの22個に直接接続される。したがって、独立の領域1302は、示される建物構造の内側の扉の96%に、直接接続される。
【００６７】
限定ではなく例として、内側の扉の所定の閾値は、いくつか例を挙げると、絶対値、相対的な関係、これらの組み合わせなどであってよい。例えば、閾値は、建物構造(または、階、区画、ウィングなどのような、建物構造の画定された部分)の扉の総数に関連してもよい。あるいは、閾値は、他の独立の領域に直接接続される扉の平均の数に関連してもよい。
【００６８】
より具体的には、廊下を表す建物情報またはグラフの構成要素を検出するために、上記の平均の割合の建物構造の内側の扉に接続される独立の領域が見出されうる。例えば、ある実装形態では、建物構造の扉の、または建物構造内の扉の、少なくとも5%〜25%(例えば少なくとも10%)に接続し、かつ最低でも4個の扉に接続する独立の領域を、廊下であると定義することができる。例えば、建物構造が50個の扉を有する場合、(例えば20%の閾値レベルでは)10個以上の扉に接続される任意の独立の領域が、廊下として定義されうる。
【００６９】
図14は、ある実装形態による、例示的な機器1400を示す概略図であり、例示的な機器2000は、建物用の経路案内グラフの1つまたは複数の態様を実施することができる。示されるように、機器1400は、少なくとも1つのプロセッサ1402、1つまたは複数のメモリ1404、少なくとも1つの通信インターフェース1406、少なくとも1つの電源1408、および、SPSユニット(SPSU)(明確には示されていない)のような他の構成要素1410を含みうる。メモリ1404は、命令1412を含むものとして示されている。しかし、代替的には、機器1400は、示されている構成要素よりも、多くの、少ない、および/または異なる構成要素を含んでもよい。
【００７０】
いくつかの例示的な実装形態では、機器1400は、電子機器を含んでもよく、かつ/または備えてもよい。機器1400は、例えば、少なくとも1つのプロセッサおよび/またはメモリを有する任意の電子機器を含んでもよい。機器1400の例は、限定はされないが、固定式の処理機器(例えば、デスクトップコンピュータ、1つまたは複数のサーバコンピュータ、少なくとも1つの遠隔通信ノード、インテリジェントルータ/スイッチ、これらの何らかの組み合わせなど)、移動式の処理機器(例えば、ノートブックコンピュータ、携帯情報端末(PDA)、ネットブック、スレートまたはタブレット型コンピュータ、持ち運び式娯楽機器、携帯電話、スマートフォン、移動局、これらの何らかの組み合わせなど)などを含む。
【００７１】
電源1408は、機器1400の構成要素および/または回路に電力を供給することができる。電源1408は、電池のような持ち運び可能な電源であってもよく、または、自動車、家、または他の建物のコンセントのような、固定式の電源であってもよい。電源1408はまた、太陽または炭素燃料を用いる発電機のような、可搬型の電源であってもよい。電源1408は、機器1400と一体であっても分離していてもよい。
【００７２】
プロセッサ1402は、任意の1つまたは複数の処理ユニットを含みうる。メモリ1404は、プロセッサ1402により実行可能でありうる命令1412(例えば、プログラム、アプリケーションなど、またはこれらの一部、使用可能なデータ構造、プロセッサ実行可能命令/コード、これらの何らかの組み合わせなど)を保存し、格納し、または命令1412へのアクセスを提供することができる。1つまたは複数のプロセッサ1402によるそのような命令1412の実行により、機器1400は、特別な用途のコンピューティング機器、装置、プラットフォーム、これらの組み合わせなどに変換されうる。
【００７３】
命令1412は、経路案内グラフ命令1412a、建物情報1412b、および/または建物道案内ファイル1412cを含みうる。建物情報1412bは、例えば、(図3の)建物情報302(例えば(図4の)建物情報400)に対応しうる。建物道案内ファイル1412cは、例えば、(図3の)建物道案内ファイル308に対応していてもよく、建物道案内ファイル308は、少なくとも1つの経路案内グラフ312、1つまたは複数の接続グラフ316、および/または関連する注記情報314を含みうる。経路案内グラフ命令1412aは、例えば、(図6および7の)流れ図600および/または700の1つまたは複数の実施を実現することができる、命令に相当しうる。経路案内グラフ命令1412aを実行して、例えば、建物情報1412bに少なくとも一部基づいて、建物道案内ファイル1412cの少なくとも一部を生成することができる。明確には示されていないが、命令1412は、建物道案内ファイル1412cを用いて1つまたは複数の位置情報サービス(LBS)を提供するための命令も含みうる。
【００７４】
例示的な実装形態では、サーバおよび/または遠隔通信ノードのような固定式の処理機器が、経路案内グラフ命令1412aを実行して、建物情報1412bに少なくとも一部基づいて、建物道案内ファイル1412cを作成することができる。同一のまたは異なる固定式処理機器が、建物道案内ファイル1412cを用いて、例えば、SPSUを含みうるモバイル機器にLBSを提供することができる。あるいは、そのような固定式の処理機器は、建物道案内ファイル1412cをモバイル機器に提供して、いくつかのLBSを可能にする、またはいくつかのLBSのさらなる実行を可能にすることができる。さらに別の代替形態として、モバイル機器は、経路案内グラフ命令1412aを含み、(例えばオンデマンドで)ダウンロードされた建物情報1412bから建物道案内ファイル1412cを作成することができる。他の代替形態も、特許請求される主題から逸脱することなく、代わりに実施することができる。
【００７５】
通信インターフェース1406は、機器1400と他の機器(例えば、および/または使用する人)との間の1つまたは複数のインターフェースを提供することができる。したがって、通信インターフェース1406は、画面(例えばタッチスクリーン)、スピーカー、マイクロフォン、キーボードもしくはキー、ノブ/ホイール、または人と機器の間の他の入力/出力機構を含んでもよい。通信インターフェース1406は、送受信機(例えば送信機および/または受信機)、無線、アンテナ、有線インターフェースコネクタまたは他のそのような装置、これらの何らかの組み合わせなどを含み、無線信号および/または有線信号を(例えば無線通信リンクまたは有線通信リンクを通じて)通信することができる。通信インターフェース1406は、機器1400の他の構成要素間の、バスまたは他の相互接続としての役割も果たしうる。他の構成要素1410は、存在する場合、1つまたは複数の他の様々なセンサ、機構などを含んでもよい。
【００７６】
本明細書で説明された方法は、具体的な特徴および/または例にしたがって、用途に応じて様々な手段で実装されうる。例えば、そのような方法は、ハードウェア、ファームウェア、ソフトウェア、個別の/固定された論理回路、これらの任意の組み合わせなどで実装されうる。ハードウェアによる実装形態では、例えば、プロセッサ/処理ユニットは、いくつか例を挙げると、1つまたは複数の特定用途向け集積回路(ASIC)、デジタルシグナルプロセッサ(DSP)、デジタルシグナルプロセシングデバイス(DSPD)、プログラマブル論理デバイス(PLD)、フィールドプログラマブルゲートアレイ(FPGA)、プロセッサ全般、コントローラ、マイクロコントローラ、マイクロプロセッサ、電子的なデバイス、命令を実行するようにプログラムされた、かつ/もしくは本明細書で説明される機能を実行するように設計された、他のデバイスまたはユニット、および/またはこれらの組み合わせの中に、実装されうる。本明細書において、用語「制御論理回路」は、ソフトウェア/ファームウェアで実装される論理回路、ハードウェア(例えば個別の/固定された論理回路)、これらの任意の組み合わせなどを包含しうる。
【００７７】
ファームウェアおよび/またはソフトウェアによる実装形態では、方法は、本明細書で説明される機能を実行するモジュール(例えば、プロシージャ、関数など)により実装されうる。命令を有形に具現化する任意の機械可読媒体が、本明細書で説明される方法を実装する際に用いられうる。例えば、ソフトウェアコードをメモリに保存することができ、処理ユニットにより実行することができる。メモリは、処理ユニット内に実装されてもよく、処理ユニットの外側に実装されてもよい。本明細書で用いられる用語「メモリ」は、任意の種類の、長期的な、短期的な、揮発性の、非揮発性の、または他のメモリを指し、特定の種類のメモリまたは特定の数のメモリ、または記憶が保存される媒体の特定の種類に何ら限定されることはない。
【００７８】
ファームウェアおよび/またはソフトウェアによる実装形態では、機能は、1つまたは複数の命令またはコードとして、コンピュータ可読媒体に保存されうる。例には、データ構造でエンコードされたコンピュータ可読媒体と、コンピュータプログラムによりエンコードされたコンピュータ可読媒体とを含む。コンピュータ可読媒体は、製造物品の形態であってもよい。コンピュータ可読媒体は、物理的なコンピュータ記憶媒体を含む。記憶媒体は、コンピュータによりアクセスされうる任意の利用可能な媒体であってよい。限定ではなく例として、そのようなコンピュータ可読媒体は、RAM、ROM、EEPROM、CD-ROMもしくは他の光ディスク記憶装置、磁気ディスク記憶装置、半導体記憶装置、もしくは他の記憶機器、または、命令またはデータ構造の形態で所望のプログラムコードを保存するのに用いることができ、コンピュータによりアクセスすることができる、任意の他の媒体を含みうる。本明細書で用いられる場合、ディスク(disk)およびディスク(disc)は、コンパクトディスク(CD)、レーザーディスク（登録商標）、光ディスク、デジタル多目的ディスク(DVD)、フロッピー（登録商標）ディスクおよびブルーレイディスクを含み、ディスク(disk)は通常データを磁気的に再生し、ディスク(disc)はレーザーによりデータを光学的に再生する。上記の組み合わせも、コンピュータ可読媒体の範囲に含まれるべきである。
【００７９】
コンピュータ可読媒体への保存に加えて、命令および/またはデータは、通信装置に含まれる伝送媒体上の信号として提供されてもよい。例えば、通信装置は、命令およびデータを示す信号を有する送受信機を含んでもよい。命令およびデータは、1つまたは複数の処理ユニットに特許請求の範囲で概説される機能を実装させるように、構成される。つまり、通信装置は、開示される機能を実行するための情報を示す信号を有する、伝送媒体を含む。第1の時間では、通信装置に含まれる伝送媒体は、情報の第1の部分を含み開示される機能を実行することができるが、第2の時間では、通信装置に含まれる伝送媒体は、開示される機能を実行するための情報の第2の部分を含んでもよい。
【００８０】
電子機器は、Wi-Fi/WLANまたは他の無線ネットワークとともに動作することもできる。例えば、位置データが、Wi-Fiまたは他の無線ネットワークを介して取得されうる。Wi-Fi/WLAN信号に加えて、無線/移動式の機器は、全地球測位システム(GPS)、Galileo、GLONASS、NAVSTAR、QZSS、これらのシステムの組み合わせの衛星を用いるシステム、または将来開発される任意のSPSからの信号でありうる、衛星からの信号を受信することもでき、上述の各システムは、本明細書では衛星測位システム(SPS)と一般に呼ばれる。さらに、本明細書で説明される実装形態は、擬似衛星または衛星と擬似衛星の組み合わせを利用する、測位システムとともに用いられうる。擬似衛星は通常、擬似ランダムノイズ(PRN)符号または、Lバンド(または他の周波数)の搬送波信号に変調された他の測距コード(例えば、GPSまたはCDMAセルラー信号に類似した)をブロードキャストする、地上の送信機であり、上記の搬送波信号はGPS時間と同期されうる。各々のそのような送信機は、遠隔の受信機による識別を可能にするために、固有のPNコードを割り当てられうる。擬似衛星は、トンネル、鉱山、建物、アーバンキャニオン、または他の囲まれた領域のような、軌道衛星からのSPS信号が利用できない状況では、特に有用でありうる。擬似衛星の別の実装形態は、無線ビーコンとして知られている。本明細書で用いられる用語「衛星」は、擬似衛星、擬似衛星の等価物、および同様のかつ/または類似の技術も含むべきである。本明細書で用いられる場合、用語「SPS信号」は、擬似衛星または擬似衛星の等価物からのSPSのような信号も含むべきである。いくつかの実装形態は、フェムトセル、またはフェムトセルを含むシステムの組み合わせにも、適用されうる。
【００８１】
例示的な実装形態では、SPSU(存在すれば)は、1つまたは複数のSPSシステムを用いて、機器1400の位置を決定することができてもよい。したがって、本明細書で説明される例示的な実装形態は、様々なSPSとともに用いられうる。SPSは通常、エンティティが、送信機から受信された信号に少なくとも一部基づいて、地上または上空での自身の位置を決定することを可能にするように位置付けられた、送信機のシステムを含む。そのような送信機は、必須ではないが通常、一定の数のチップの繰り返し擬似ランダムノイズ(PN)符号でマークされた信号を送信し、地上の管制局、ユーザー装置、および/または宇宙船に存在しうる。具体的な例では、そのような送信機は、地球軌道宇宙機(SV)に存在しうる。例えば、全地球測位システム(GPS)、Galileo、GlonassまたはCompassのような全地球航法衛星システム(GNSS)の集合のSVは(例えば、GPSのように各衛星に対して異なるPN符号を用いて、またはGlonassのように異なる周波数に対して同一の符号を用いて)、その集合内の他のSVにより送信されたPN符号と区別可能なPN符号によりマークされる信号を送信することができる。いくつかの態様によれば、本明細書で提示される技術は、SPSのための地球規模のシステム(例えばGNSS)には限定されない。例えば、本明細書で提供される技術は、日本の準天頂衛星システム(QZSS)、インドのインド地域航法衛星システム(IRNSS)、中国の北斗など、ならびに/または、1つもしくは複数の地球規模のおよび/もしくは地域的な航法衛星システムに関連しうる、もしくはそれらとともに用いることが可能にされうる、様々な補強システム(例えば、静止衛星型衛星航法補強システム(SBAS))に、適用されてもよく、またはそれらとともに用いることが可能であってもよい。限定ではなく例として、SBASは、例えば、広域補強システム(WAAS)、European Geostationary Navigation Overlay Service(EGNOS)、多目的衛星用航法補強システム(MSAS)、GPS Aided Geo Augmented Navigation or GPS and Geo Augmented Navigation system(GAGAN)、および/または同様のもののような、統合情報、差分補正などを提供する補強システムを含みうる。したがって、本明細書で用いられる場合、SPSは、1つまたは複数の地球規模のおよび/もしくは地域的な航法衛星システムならびに/または補強システムの任意の組み合わせを含んでもよく、SPS信号は、SPS信号、SPSのような信号、および/またはそのような1つまたは複数のSPSと関連する他の信号を含んでもよい。
【００８２】
モバイル機器/移動局は、セルラー型の、または他の無線通信機器、個人用通信システム(PCS)機器、個人用ナビゲーション機器(PND)、個人情報管理装置(PIM)、携帯情報端末(PDA)、ラップトップ、タブレット、または、無線通信および/または道案内信号を受信することができる他の適切な機器のような、機器を指す。衛星信号の受信、支援データの受信、および/または位置に関する処理が、機器で行われるかPNDで行われるかには関係なく、モバイル機器は、短距離の無線、赤外線、有線接続、または他の接続などによって、個人用ナビゲーション機器(PND)と通信する機器を含むことも意図されている。また、モバイル機器は、無線通信機器、コンピュータ、ラップトップなどを含む全ての機器を含むことが意図されており、上記の機器類は、衛星信号の受信、支援データの受信、および/または位置に関連する処理が、機器で行われるか、サーバで行われるか、ネットワークに関連する他の機器で行われるかには関係なく、インターネット、Wi-Fi、または他のネットワークを介するなどして、サーバと通信することができる。上記の任意の動作可能な組み合わせも、モバイル機器であると考えることができる。
【００８３】
この発明を実施するための形態の一部は、特定の装置または専用のコンピューティング機器もしくはプラットフォームのメモリに保存されうるバイナリデジタル信号に対する動作の、アルゴリズムまたは記号による表現として提示されている。この特定の明細書においては、「特定の装置」などの用語は、プログラムソフトウェア/命令からの命令にしたがって特定の機能を実行するようにプログラムされた後の、汎用コンピュータを含む。アルゴリズムによる説明または記号による表現は、信号処理または関連技術の当業者が、自身の成果の本質を他の当業者に伝えるために用いられる、技法の例である。アルゴリズムとはここでは、かつ一般的に、所望の結果につながる、一貫した一連の動作または同様の信号処理であると考えることができる。これに関連して、動作または処理は、物理量の物理的な操作に関わる。必須ではないが通常、そのような物理量は、保存し、移送し、組み合わせ、比較し、送信し、受信し、または他の方法で操作することができる、電気信号および/または磁気信号の形態をとりうる。
【００８４】
主に一般に用いられているという理由で、そのような信号を、ビット、データ、値、要素、シンボル、文字、変数、語、数、番号などと呼ぶことが便利なことがあるということがわかっている。しかし、これらの用語および類似の用語は全て、適切な物理量と関連付けられるべきであり、便宜的な呼び方に過ぎないということを理解されたい。別段特に述べられない限り、上の議論から明らかなように、「処理する」、「計算する」、「算出する」、「決定する」、「確定する」、「識別する」、「関連付ける」、「取得する」、「実行する」、「適用する」、「調査する」、「分析する」、「作成する」、「模擬する」、「相互接続する」、「重畳する」、「検出する」などのような用語を利用する、本明細書の議論の全体が、専用コンピュータまたは同様の専用の電子的なコンピューティング機器のような、特定の装置の動作または処理を指すことが、理解されよう。したがって、この明細書においては、専用のコンピュータまたは同様の専用の電子的なコンピューティング機器は、信号を操作または変換することができ、上記の信号は通常、専用のコンピュータまたは同様の専用の電子的なコンピューティング機器の、メモリ、レジスタ、もしくは他の情報記憶機器、伝送機器、または表示機器の中で、物理的な、電気的な量、電子的な量、および/または磁気的な量として表される。
【００８５】
例示的な特徴であると現在考えられていることが、示されて説明されてきたが、特許請求される主題から逸脱することなく、様々な他の修正を行うことができ、等価物により置換できることが、当業者には理解されよう。加えて、本明細書で説明される主要な概念から逸脱することなく、多くの修正が、具体的な状況を特許請求される主題の教示に適合させるために行われうる。したがって、特許請求される主題は開示される具体的な例に限定されず、そのような特許請求される主題は、添付の特許請求の範囲およびその等価物の範囲にある、全ての態様も含みうることが、意図されている。
【符号の説明】
【００８６】
100 建物情報の概略図
104 注記情報
200 建物情報の概略図
206 使用不可能な領域
208 建物の外側の領域
210 経路案内グラフ
302 建物情報
304 建物地図ファイル
306 データ
308 建物道案内ファイル
312 経路案内グラフ
314 注記情報
316 接続グラフ
502 点のグリッド
1400 機器
1402 プロセッサ
1404 メモリ
1406 通信インターフェース
1408 電源
1410 他の構成要素
1412 命令
1412a 経路案内グラフ命令
1412b 建物情報
1412c 建物道案内ファイル
【特許請求の範囲】
【請求項１】
建物構造の少なくとも一部を表現する建物情報を表す電気信号を得るステップと、
前記建物情報に点のグリッドを重畳するステップと、
前記重畳された点のグリッドと前記建物情報とに少なくとも一部基づいて、少なくとも1つの経路案内グラフを表す電気信号を生成するステップと
を含む、方法。
【請求項２】
前記重畳された点のグリッドの隣接点の少なくとも一部を障害物のない接続で相互接続するステップ
をさらに含む、請求項1に記載の方法。
【請求項３】
前記障害のない接続が、前記建物情報の前記建物構造と交差しない接続を含む、請求項2に記載の方法。
【請求項４】
前記重畳された点のグリッドの点が前記少なくとも1つの経路案内グラフのノードを含み、前記障害のない接続が前記少なくとも1つの経路案内グラフのエッジを含む、請求項3に記載の方法。
【請求項５】
前記重畳された点のグリッドと、前記建物情報の1つまたは複数の壁とに少なくとも一部基づいて、前記建物情報の複数の独立の領域を決定するステップ
をさらに含む、請求項1に記載の方法。
【請求項６】
前記建物情報の扉を閉じた状態で模擬するステップと、
前記建物情報の前記建物構造と交差しない障害のない接続により、前記重畳された点のグリッドの隣接点の少なくとも一部を相互接続するステップであって、前記建物構造が、閉じた状態で模擬された前記扉を含む、ステップと
をさらに含む、請求項5に記載の方法。
【請求項７】
前記相互接続するステップが、
前記重畳された点のグリッドから複数の互いに接続されていないグラフを形成するステップ
を含む、請求項6に記載の方法であって、前記複数の互いに接続されていないグラフが、前記複数の独立の領域を含む、方法。
【請求項８】
前記建物情報の前記建物構造の外側にある少なくとも1つの点を識別するステップと、
前記少なくとも1つの点に少なくとも一部基づいて、前記建物情報の前記建物構造の外側にある少なくとも1つの独立の領域を、前記複数の独立の領域から確定するステップと
をさらに含む、請求項5に記載の方法。
【請求項９】
少なくとも1つの独立の領域に少なくとも一部基づいて、前記建物情報の前記建物構造の1つもしくは複数の入口および/または出口を決定するステップであって、前記少なくとも1つの独立の領域が、前記重畳された点のグリッドを用いて、前記建物構造の外側にあると確定される、ステップ
をさらに含む、請求項1に記載の方法。
【請求項１０】
どの1つまたは複数の独立の領域が使用可能か、および、1つまたは複数の独立の領域が使用不可能かどうかを、複数の独立の領域から判定するステップ
をさらに含む、請求項1に記載の方法。
【請求項１１】
前記建物情報の扉を開いた状態で模擬するステップと、
前記建物情報の前記建物構造と交差しない障害のない接続により、前記重畳された点のグリッドの隣接点の少なくとも一部を相互接続するステップと
をさらに含む、請求項10に記載の方法。
【請求項１２】
前記判定するステップが、
前記重畳された点のグリッドの相互接続された点を通過することによって、前記複数の独立の領域の所与の独立の領域に外側の点から到達可能である場合に、前記所与の独立の領域が使用可能な独立の領域であると判定するステップと、
前記重畳された点のグリッドの相互接続された点を通過することによって、前記複数の独立の領域の所与の独立の領域に外側の点から到達可能ではない場合に、前記所与の独立の領域が使用不可能な独立の領域であると判定するステップと
をさらに含む、請求項11に記載の方法。
【請求項１３】
前記複数の独立の領域の所与の独立の領域に直接接続される扉の所定の閾値に少なくとも一部基づいて、前記建物情報の1つまたは複数の廊下を複数の独立の領域から検出するステップ
をさらに含む、請求項1に記載の方法。
【請求項１４】
前記建物情報からの注記情報を少なくとも1つの接続グラフに重畳し、注記された建物情報を有する前記少なくとも1つの経路案内グラフを生成するステップ
をさらに含む、請求項1に記載の方法。
【請求項１５】
前記少なくとも1つの経路案内グラフを用いて、前記建物構造に関する道案内情報をモバイル機器に提供するステップ
をさらに含む、請求項1に記載の方法。
【請求項１６】
専用のコンピューティング機器に前記方法を実施するように指示するための命令を、前記専用のコンピューティング機器によって実行するステップ
をさらに含む、請求項1に記載の方法。
【請求項１７】
命令を保存するための少なくとも1つのメモリと、
前記命令を実行して、
建物構造の少なくとも一部を表現する建物情報を得、
前記建物情報に点のグリッドを重畳し、
前記重畳された点のグリッドと前記建物情報とに少なくとも一部基づいて、少なくとも1つの経路案内グラフを作成する
ための、1つまたは複数のプロセッサと
を含む、専用のコンピューティング機器。
【請求項１８】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記重畳された点のグリッドの隣接点の少なくとも一部を障害物のない接続で相互接続する、請求項17の記載の機器。
【請求項１９】
前記障害のない接続が、前記建物情報の前記建物構造と交差しない接続を含む、請求項18に記載の機器。
【請求項２０】
前記重畳された点のグリッドの点が前記少なくとも1つの経路案内グラフのノードを含み、前記障害のない接続が前記少なくとも1つの経路案内グラフのエッジを含む、請求項19に記載の機器。
【請求項２１】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記重畳された点のグリッドと、前記建物情報の1つまたは複数の壁とに少なくとも一部基づいて、前記建物情報の複数の独立の領域を決定する、請求項17に記載の機器。
【請求項２２】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記建物情報の扉を閉じた状態で模擬し、
前記建物情報の前記建物構造と交差しない障害のない接続により、前記重畳された点のグリッドの隣接点の少なくとも一部を相互接続し、前記建物構造が、閉じた状態で模擬された前記扉を含む、請求項21に記載の機器。
【請求項２３】
隣接点の前記少なくとも一部を相互接続するために、前記1つまたは複数のプロセッサがさらに、
前記重畳された点のグリッドから複数の互いに接続されていないグラフを形成する
ことによって、前記障害のない接続を用いて前記命令を実行する、請求項22に記載の機器であって、前記複数の互いに接続されていないグラフが、前記複数の独立の領域を含む、機器。
【請求項２４】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記建物情報の前記建物構造の外側にある少なくとも1つの点を識別し、
前記少なくとも1つの点に少なくとも一部基づいて、前記建物情報の前記建物構造の外側にある少なくとも1つの独立の領域を、前記複数の独立の領域から確定する、請求項21に記載の機器。
【請求項２５】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
少なくとも1つの独立の領域に少なくとも一部基づいて、前記建物情報の前記建物構造の1つもしくは複数の入口および/または出口を決定し、前記少なくとも1つの独立の領域が、前記重畳された点のグリッドを用いて、前記建物構造の外側にあると確定される、請求項17に記載の機器。
【請求項２６】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
どの1つまたは複数の独立の領域が使用可能か、および、1つまたは複数の独立の領域が使用不可能かどうかを、複数の独立の領域から判定する、請求項17に記載の機器。
【請求項２７】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記建物情報の扉を開いた状態で模擬し、
前記建物情報の前記建物構造と交差しない障害のない接続により、前記重畳された点のグリッドの隣接点の少なくとも一部を相互接続する、請求項26に記載の機器。
【請求項２８】
どの1つまたは複数の独立の領域が使用可能か、および、1つまたは複数の独立の領域が使用不可能かどうかを判定するために、前記1つまたは複数のプロセッサがさらに、
前記重畳された点のグリッドの相互接続された点を通過することによって、前記複数の独立の領域の所与の独立の領域に外側の点から到達可能である場合に、前記所与の独立の領域が使用可能な独立の領域であると判定し、
前記重畳された点のグリッドの相互接続された点を通過することによって、前記複数の独立の領域の所与の独立の領域に外側の点から到達可能ではない場合に、前記所与の独立の領域が使用不可能な独立の領域であると判定する
ことによって、前記命令を実行する、請求項27に記載の機器。
【請求項２９】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記複数の独立の領域の所与の独立の領域に直接接続される扉の所定の閾値に少なくとも一部基づいて、前記建物情報の1つまたは複数の廊下を複数の独立の領域から検出する、請求項17に記載の機器。
【請求項３０】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記建物情報からの注記情報を少なくとも1つの接続グラフに重畳し、注記された建物情報を有する前記少なくとも1つの経路案内グラフを生成する、請求項17に記載の機器。
【請求項３１】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記少なくとも1つの経路案内グラフを用いて、前記建物構造に関する道案内情報をモバイル機器に提供する、請求項17に記載の機器。
【請求項３２】
建物構造の少なくとも一部を表現する建物情報を取得し、
前記建物情報に点のグリッドを重畳し、
前記重畳された点のグリッドおよび前記建物情報に少なくとも一部基づいて、少なくとも1つの経路案内グラフを作成する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、少なくとも1つの記憶媒体を含む、物品。
【請求項３３】
前記少なくとも1つの記憶媒体がさらに、
前記重畳された点のグリッドの隣接点の少なくとも一部を障害物のない接続で相互接続する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項32に記載の物品。
【請求項３４】
前記障害のない接続が、前記建物情報の前記建物構造と交差しない接続を含む、請求項33に記載の物品。
【請求項３５】
前記重畳された点のグリッドの点が前記少なくとも1つの経路案内グラフのノードを含み、前記障害のない接続が前記少なくとも1つの経路案内グラフのエッジを含む、請求項34に記載の物品。
【請求項３６】
前記少なくとも1つの記憶媒体が、
前記重畳された点のグリッドと、前記建物情報の1つまたは複数の壁とに少なくとも一部基づいて、前記建物情報の複数の独立の領域を決定する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項32に記載の物品。
【請求項３７】
前記少なくとも1つの記憶媒体が、
前記建物情報の扉を閉じた状態で模擬し、
前記建物情報の前記建物構造と交差しない障害のない接続により、前記重畳された点のグリッドの隣接点の少なくとも一部を相互接続する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項36に記載の物品であって、前記建物構造が、閉じた状態で模擬された前記扉を含む、物品。
【請求項３８】
隣接点の前記少なくとも一部を相互接続するために、前記少なくとも1つの記憶媒体が、
前記重畳された点のグリッドから複数の互いに接続されていないグラフを形成する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項37に記載の物品であって、前記複数の互いに接続されていないグラフが、前記複数の独立の領域を含む、物品。
【請求項３９】
前記少なくとも1つの記憶媒体が、
前記建物情報の前記建物構造の外側にある少なくとも1つの点を識別し、
前記少なくとも1つの点に少なくとも一部基づいて、前記建物情報の前記建物構造の外側にある少なくとも1つの独立の領域を、前記複数の独立の領域から確定する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項36に記載の物品。
【請求項４０】
前記少なくとも1つの記憶媒体が、
少なくとも1つの独立の領域に少なくとも一部基づいて、前記建物情報の前記建物構造の1つもしくは複数の入口および/または出口を決定する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項32に記載の物品であって、前記少なくとも1つの独立の領域が、前記重畳された点のグリッドを用いて、前記建物構造の外側にあると確定される、物品。
【請求項４１】
前記少なくとも1つの記憶媒体が、
どの1つまたは複数の独立の領域が使用可能か、および、1つまたは複数の独立の領域が使用不可能かどうかを、複数の独立の領域から判定する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項32に記載の物品。
【請求項４２】
前記少なくとも1つの記憶媒体が、
前記建物情報の扉を開いた状態で模擬し、
前記建物情報の前記建物構造と交差しない障害のない接続により、前記重畳された点のグリッドの隣接点の少なくとも一部を相互接続する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項41に記載の物品。
【請求項４３】
どの1つまたは複数の独立の領域が使用可能か、および、1つまたは複数の独立の領域が使用不可能かどうかを判定するために、前記少なくとも1つの記憶媒体が、
前記重畳された点のグリッドの相互接続された点を通過することによって、前記複数の独立の領域の所与の独立の領域に外側の点から到達可能である場合に、前記所与の独立の領域が使用可能な独立の領域であると判定し、
前記重畳された点のグリッドの相互接続された点を通過することによって、前記複数の独立の領域の所与の独立の領域に外側の点から到達可能ではない場合に、前記所与の独立の領域が使用不可能な独立の領域であると判定する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項42に記載の物品。
【請求項４４】
前記少なくとも1つの記憶媒体が、
前記複数の独立の領域の所与の独立の領域に直接接続される扉の所定の閾値に少なくとも一部基づいて、前記建物情報の1つまたは複数の廊下を複数の独立の領域から検出する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項32に記載の物品。
【請求項４５】
前記少なくとも1つの記憶媒体が、
前記建物情報からの注記情報を少なくとも1つの接続グラフに重畳し、注記された建物情報を有する前記少なくとも1つの経路案内グラフを生成する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項32に記載の物品。
【請求項４６】
前記少なくとも1つの記憶媒体が、
前記少なくとも1つの経路案内グラフを用いて、前記建物構造に関する道案内情報をモバイル機器に提供する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項32に記載の物品。
【請求項４７】
建物構造の少なくとも一部を表現する建物情報を得るための手段と、
前記建物情報に点のグリッドを重畳するための手段と、
前記重畳された点のグリッドと前記建物情報とに少なくとも一部基づいて、少なくとも1つの経路案内グラフを作成するための手段と
を含む、装置。
【請求項４８】
前記重畳された点のグリッドの隣接点の少なくとも一部を、障害のない接続により相互接続するための手段
をさらに含む、請求項47に記載の装置。
【請求項４９】
前記障害のない接続が、前記建物情報の前記建物構造と交差しない接続を含む、請求項48に記載の装置。
【請求項５０】
前記重畳された点のグリッドの点が前記少なくとも1つの経路案内グラフのノードを含み、前記障害のない接続が前記少なくとも1つの経路案内グラフのエッジを含む、請求項49に記載の装置。
【請求項５１】
前記重畳された点のグリッドと、前記建物情報の1つまたは複数の壁とに少なくとも一部基づいて、前記建物情報の複数の独立の領域を決定するための手段
をさらに含む、請求項47に記載の装置。
【請求項５２】
前記建物情報の扉を閉じた状態で模擬するための手段と、
前記建物情報の前記建物構造と交差しない障害のない接続により、前記重畳された点のグリッドの隣接点の少なくとも一部を相互接続するための手段であって、前記建物構造が、閉じた状態で模擬された前記扉を含む、手段と
をさらに含む、請求項51に記載の装置。
【請求項５３】
前記隣接点の少なくとも一部を前記相互接続するための手段が、
前記重畳された点のグリッドから複数の互いに接続されていないグラフを形成するための手段
を含む、請求項52に記載の装置であって、前記複数の互いに接続されていないグラフが、前記複数の独立の領域を含む、装置。
【請求項５４】
前記建物情報の前記建物構造の外側にある少なくとも1つの点を識別するための手段と、
前記少なくとも1つの点に少なくとも一部基づいて、前記建物情報の前記建物構造の外側にある少なくとも1つの独立の領域を、前記複数の独立の領域から確定するための手段と
をさらに含む、請求項51に記載の装置。
【請求項５５】
少なくとも1つの独立の領域に少なくとも一部基づいて、前記建物情報の前記建物構造の1つもしくは複数の入口および/または出口を決定するための手段であって、前記少なくとも1つの独立の領域が、前記重畳された点のグリッドを用いて、前記建物構造の外側にあると確定される、手段
をさらに含む、請求項47に記載の装置。
【請求項５６】
どの1つまたは複数の独立の領域が使用可能か、および、1つまたは複数の独立の領域が使用不可能かどうかを、複数の独立の領域から判定するための手段
をさらに含む、請求項47に記載の装置。
【請求項５７】
前記建物情報の扉を開いた状態で模擬するための手段と、
前記建物情報の前記建物構造と交差しない障害のない接続により、前記重畳された点のグリッドの隣接点の少なくとも一部を相互接続するための手段と
をさらに含む、請求項56に記載の装置。
【請求項５８】
どの1つまたは複数の独立の領域が使用可能か、および、1つまたは複数の独立の領域が使用不可能かどうかを、前記判定するための手段が、
前記重畳された点のグリッドの相互接続された点を通過することによって、前記複数の独立の領域の所与の独立の領域に外側の点から到達可能である場合に、前記所与の独立の領域が使用可能な独立の領域であると判定するための手段と、
前記重畳された点のグリッドの相互接続された点を通過することによって、前記複数の独立の領域の所与の独立の領域に外側の点から到達可能ではない場合に、前記所与の独立の領域が使用不可能な独立の領域であると判定するための手段と
を含む、請求項57に記載の装置。
【請求項５９】
前記複数の独立の領域の所与の独立の領域に直接接続される扉の所定の閾値に少なくとも一部基づいて、前記建物情報の1つまたは複数の廊下を複数の独立の領域から検出するための手段
をさらに含む、請求項47に記載の装置。
【請求項６０】
前記建物情報からの注記情報を少なくとも1つの接続グラフに重畳し、注記された建物情報を有する前記少なくとも1つの経路案内グラフを生成するための手段
をさらに含む、請求項47に記載の装置。
【請求項６１】
前記少なくとも1つの経路案内グラフを用いて、前記建物構造に関する道案内情報をモバイル機器に提供するための手段
をさらに含む、請求項47に記載の装置。
【請求項１】
建物構造の少なくとも一部を表現する建物情報を表す電気信号を得るステップと、
前記建物情報に点のグリッドを重畳するステップと、
前記重畳された点のグリッドと前記建物情報とに少なくとも一部基づいて、少なくとも1つの経路案内グラフを表す電気信号を生成するステップと
を含む、方法。
【請求項２】
前記重畳された点のグリッドの隣接点の少なくとも一部を障害物のない接続で相互接続するステップ
をさらに含む、請求項1に記載の方法。
【請求項３】
前記障害のない接続が、前記建物情報の前記建物構造と交差しない接続を含む、請求項2に記載の方法。
【請求項４】
前記重畳された点のグリッドの点が前記少なくとも1つの経路案内グラフのノードを含み、前記障害のない接続が前記少なくとも1つの経路案内グラフのエッジを含む、請求項3に記載の方法。
【請求項５】
前記重畳された点のグリッドと、前記建物情報の1つまたは複数の壁とに少なくとも一部基づいて、前記建物情報の複数の独立の領域を決定するステップ
をさらに含む、請求項1に記載の方法。
【請求項６】
前記建物情報の扉を閉じた状態で模擬するステップと、
前記建物情報の前記建物構造と交差しない障害のない接続により、前記重畳された点のグリッドの隣接点の少なくとも一部を相互接続するステップであって、前記建物構造が、閉じた状態で模擬された前記扉を含む、ステップと
をさらに含む、請求項5に記載の方法。
【請求項７】
前記相互接続するステップが、
前記重畳された点のグリッドから複数の互いに接続されていないグラフを形成するステップ
を含む、請求項6に記載の方法であって、前記複数の互いに接続されていないグラフが、前記複数の独立の領域を含む、方法。
【請求項８】
前記建物情報の前記建物構造の外側にある少なくとも1つの点を識別するステップと、
前記少なくとも1つの点に少なくとも一部基づいて、前記建物情報の前記建物構造の外側にある少なくとも1つの独立の領域を、前記複数の独立の領域から確定するステップと
をさらに含む、請求項5に記載の方法。
【請求項９】
少なくとも1つの独立の領域に少なくとも一部基づいて、前記建物情報の前記建物構造の1つもしくは複数の入口および/または出口を決定するステップであって、前記少なくとも1つの独立の領域が、前記重畳された点のグリッドを用いて、前記建物構造の外側にあると確定される、ステップ
をさらに含む、請求項1に記載の方法。
【請求項１０】
どの1つまたは複数の独立の領域が使用可能か、および、1つまたは複数の独立の領域が使用不可能かどうかを、複数の独立の領域から判定するステップ
をさらに含む、請求項1に記載の方法。
【請求項１１】
前記建物情報の扉を開いた状態で模擬するステップと、
前記建物情報の前記建物構造と交差しない障害のない接続により、前記重畳された点のグリッドの隣接点の少なくとも一部を相互接続するステップと
をさらに含む、請求項10に記載の方法。
【請求項１２】
前記判定するステップが、
前記重畳された点のグリッドの相互接続された点を通過することによって、前記複数の独立の領域の所与の独立の領域に外側の点から到達可能である場合に、前記所与の独立の領域が使用可能な独立の領域であると判定するステップと、
前記重畳された点のグリッドの相互接続された点を通過することによって、前記複数の独立の領域の所与の独立の領域に外側の点から到達可能ではない場合に、前記所与の独立の領域が使用不可能な独立の領域であると判定するステップと
をさらに含む、請求項11に記載の方法。
【請求項１３】
前記複数の独立の領域の所与の独立の領域に直接接続される扉の所定の閾値に少なくとも一部基づいて、前記建物情報の1つまたは複数の廊下を複数の独立の領域から検出するステップ
をさらに含む、請求項1に記載の方法。
【請求項１４】
前記建物情報からの注記情報を少なくとも1つの接続グラフに重畳し、注記された建物情報を有する前記少なくとも1つの経路案内グラフを生成するステップ
をさらに含む、請求項1に記載の方法。
【請求項１５】
前記少なくとも1つの経路案内グラフを用いて、前記建物構造に関する道案内情報をモバイル機器に提供するステップ
をさらに含む、請求項1に記載の方法。
【請求項１６】
専用のコンピューティング機器に前記方法を実施するように指示するための命令を、前記専用のコンピューティング機器によって実行するステップ
をさらに含む、請求項1に記載の方法。
【請求項１７】
命令を保存するための少なくとも1つのメモリと、
前記命令を実行して、
建物構造の少なくとも一部を表現する建物情報を得、
前記建物情報に点のグリッドを重畳し、
前記重畳された点のグリッドと前記建物情報とに少なくとも一部基づいて、少なくとも1つの経路案内グラフを作成する
ための、1つまたは複数のプロセッサと
を含む、専用のコンピューティング機器。
【請求項１８】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記重畳された点のグリッドの隣接点の少なくとも一部を障害物のない接続で相互接続する、請求項17の記載の機器。
【請求項１９】
前記障害のない接続が、前記建物情報の前記建物構造と交差しない接続を含む、請求項18に記載の機器。
【請求項２０】
前記重畳された点のグリッドの点が前記少なくとも1つの経路案内グラフのノードを含み、前記障害のない接続が前記少なくとも1つの経路案内グラフのエッジを含む、請求項19に記載の機器。
【請求項２１】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記重畳された点のグリッドと、前記建物情報の1つまたは複数の壁とに少なくとも一部基づいて、前記建物情報の複数の独立の領域を決定する、請求項17に記載の機器。
【請求項２２】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記建物情報の扉を閉じた状態で模擬し、
前記建物情報の前記建物構造と交差しない障害のない接続により、前記重畳された点のグリッドの隣接点の少なくとも一部を相互接続し、前記建物構造が、閉じた状態で模擬された前記扉を含む、請求項21に記載の機器。
【請求項２３】
隣接点の前記少なくとも一部を相互接続するために、前記1つまたは複数のプロセッサがさらに、
前記重畳された点のグリッドから複数の互いに接続されていないグラフを形成する
ことによって、前記障害のない接続を用いて前記命令を実行する、請求項22に記載の機器であって、前記複数の互いに接続されていないグラフが、前記複数の独立の領域を含む、機器。
【請求項２４】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記建物情報の前記建物構造の外側にある少なくとも1つの点を識別し、
前記少なくとも1つの点に少なくとも一部基づいて、前記建物情報の前記建物構造の外側にある少なくとも1つの独立の領域を、前記複数の独立の領域から確定する、請求項21に記載の機器。
【請求項２５】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
少なくとも1つの独立の領域に少なくとも一部基づいて、前記建物情報の前記建物構造の1つもしくは複数の入口および/または出口を決定し、前記少なくとも1つの独立の領域が、前記重畳された点のグリッドを用いて、前記建物構造の外側にあると確定される、請求項17に記載の機器。
【請求項２６】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
どの1つまたは複数の独立の領域が使用可能か、および、1つまたは複数の独立の領域が使用不可能かどうかを、複数の独立の領域から判定する、請求項17に記載の機器。
【請求項２７】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記建物情報の扉を開いた状態で模擬し、
前記建物情報の前記建物構造と交差しない障害のない接続により、前記重畳された点のグリッドの隣接点の少なくとも一部を相互接続する、請求項26に記載の機器。
【請求項２８】
どの1つまたは複数の独立の領域が使用可能か、および、1つまたは複数の独立の領域が使用不可能かどうかを判定するために、前記1つまたは複数のプロセッサがさらに、
前記重畳された点のグリッドの相互接続された点を通過することによって、前記複数の独立の領域の所与の独立の領域に外側の点から到達可能である場合に、前記所与の独立の領域が使用可能な独立の領域であると判定し、
前記重畳された点のグリッドの相互接続された点を通過することによって、前記複数の独立の領域の所与の独立の領域に外側の点から到達可能ではない場合に、前記所与の独立の領域が使用不可能な独立の領域であると判定する
ことによって、前記命令を実行する、請求項27に記載の機器。
【請求項２９】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記複数の独立の領域の所与の独立の領域に直接接続される扉の所定の閾値に少なくとも一部基づいて、前記建物情報の1つまたは複数の廊下を複数の独立の領域から検出する、請求項17に記載の機器。
【請求項３０】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記建物情報からの注記情報を少なくとも1つの接続グラフに重畳し、注記された建物情報を有する前記少なくとも1つの経路案内グラフを生成する、請求項17に記載の機器。
【請求項３１】
前記1つまたは複数のプロセッサがさらに、前記命令を実行して、
前記少なくとも1つの経路案内グラフを用いて、前記建物構造に関する道案内情報をモバイル機器に提供する、請求項17に記載の機器。
【請求項３２】
建物構造の少なくとも一部を表現する建物情報を取得し、
前記建物情報に点のグリッドを重畳し、
前記重畳された点のグリッドおよび前記建物情報に少なくとも一部基づいて、少なくとも1つの経路案内グラフを作成する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、少なくとも1つの記憶媒体を含む、物品。
【請求項３３】
前記少なくとも1つの記憶媒体がさらに、
前記重畳された点のグリッドの隣接点の少なくとも一部を障害物のない接続で相互接続する
ように1つまたは複数のプロセッサによって実行可能な命令を保存した、請求項32に記載の物品。
【請求項３４】
前記障害のない接続が、前記建物情報の前記建物構造と交差しない接続を含む、請求項33に記載の物品。
【請求項３５】
前記重畳された点のグリッドの点が前記少なくとも1つの経路案内グラフのノードを含み、前記障害のない接続が前記少なくとも1つの経路案内グラフのエッジを含む、請求項34に記載の物品。
【請求項３６】
前記少なくとも1つの記憶媒体が、
前記重畳された点のグリッドと、前記建物情報の1つまたは複数の壁とに少なくとも一部基づいて、前記建物情報の複数の独立の領域を決定する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項32に記載の物品。
【請求項３７】
前記少なくとも1つの記憶媒体が、
前記建物情報の扉を閉じた状態で模擬し、
前記建物情報の前記建物構造と交差しない障害のない接続により、前記重畳された点のグリッドの隣接点の少なくとも一部を相互接続する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項36に記載の物品であって、前記建物構造が、閉じた状態で模擬された前記扉を含む、物品。
【請求項３８】
隣接点の前記少なくとも一部を相互接続するために、前記少なくとも1つの記憶媒体が、
前記重畳された点のグリッドから複数の互いに接続されていないグラフを形成する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項37に記載の物品であって、前記複数の互いに接続されていないグラフが、前記複数の独立の領域を含む、物品。
【請求項３９】
前記少なくとも1つの記憶媒体が、
前記建物情報の前記建物構造の外側にある少なくとも1つの点を識別し、
前記少なくとも1つの点に少なくとも一部基づいて、前記建物情報の前記建物構造の外側にある少なくとも1つの独立の領域を、前記複数の独立の領域から確定する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項36に記載の物品。
【請求項４０】
前記少なくとも1つの記憶媒体が、
少なくとも1つの独立の領域に少なくとも一部基づいて、前記建物情報の前記建物構造の1つもしくは複数の入口および/または出口を決定する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項32に記載の物品であって、前記少なくとも1つの独立の領域が、前記重畳された点のグリッドを用いて、前記建物構造の外側にあると確定される、物品。
【請求項４１】
前記少なくとも1つの記憶媒体が、
どの1つまたは複数の独立の領域が使用可能か、および、1つまたは複数の独立の領域が使用不可能かどうかを、複数の独立の領域から判定する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項32に記載の物品。
【請求項４２】
前記少なくとも1つの記憶媒体が、
前記建物情報の扉を開いた状態で模擬し、
前記建物情報の前記建物構造と交差しない障害のない接続により、前記重畳された点のグリッドの隣接点の少なくとも一部を相互接続する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項41に記載の物品。
【請求項４３】
どの1つまたは複数の独立の領域が使用可能か、および、1つまたは複数の独立の領域が使用不可能かどうかを判定するために、前記少なくとも1つの記憶媒体が、
前記重畳された点のグリッドの相互接続された点を通過することによって、前記複数の独立の領域の所与の独立の領域に外側の点から到達可能である場合に、前記所与の独立の領域が使用可能な独立の領域であると判定し、
前記重畳された点のグリッドの相互接続された点を通過することによって、前記複数の独立の領域の所与の独立の領域に外側の点から到達可能ではない場合に、前記所与の独立の領域が使用不可能な独立の領域であると判定する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項42に記載の物品。
【請求項４４】
前記少なくとも1つの記憶媒体が、
前記複数の独立の領域の所与の独立の領域に直接接続される扉の所定の閾値に少なくとも一部基づいて、前記建物情報の1つまたは複数の廊下を複数の独立の領域から検出する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項32に記載の物品。
【請求項４５】
前記少なくとも1つの記憶媒体が、
前記建物情報からの注記情報を少なくとも1つの接続グラフに重畳し、注記された建物情報を有する前記少なくとも1つの経路案内グラフを生成する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項32に記載の物品。
【請求項４６】
前記少なくとも1つの記憶媒体が、
前記少なくとも1つの経路案内グラフを用いて、前記建物構造に関する道案内情報をモバイル機器に提供する
ように1つまたは複数のプロセッサによって実行可能な命令をさらに保存した、請求項32に記載の物品。
【請求項４７】
建物構造の少なくとも一部を表現する建物情報を得るための手段と、
前記建物情報に点のグリッドを重畳するための手段と、
前記重畳された点のグリッドと前記建物情報とに少なくとも一部基づいて、少なくとも1つの経路案内グラフを作成するための手段と
を含む、装置。
【請求項４８】
前記重畳された点のグリッドの隣接点の少なくとも一部を、障害のない接続により相互接続するための手段
をさらに含む、請求項47に記載の装置。
【請求項４９】
前記障害のない接続が、前記建物情報の前記建物構造と交差しない接続を含む、請求項48に記載の装置。
【請求項５０】
前記重畳された点のグリッドの点が前記少なくとも1つの経路案内グラフのノードを含み、前記障害のない接続が前記少なくとも1つの経路案内グラフのエッジを含む、請求項49に記載の装置。
【請求項５１】
前記重畳された点のグリッドと、前記建物情報の1つまたは複数の壁とに少なくとも一部基づいて、前記建物情報の複数の独立の領域を決定するための手段
をさらに含む、請求項47に記載の装置。
【請求項５２】
前記建物情報の扉を閉じた状態で模擬するための手段と、
前記建物情報の前記建物構造と交差しない障害のない接続により、前記重畳された点のグリッドの隣接点の少なくとも一部を相互接続するための手段であって、前記建物構造が、閉じた状態で模擬された前記扉を含む、手段と
をさらに含む、請求項51に記載の装置。
【請求項５３】
前記隣接点の少なくとも一部を前記相互接続するための手段が、
前記重畳された点のグリッドから複数の互いに接続されていないグラフを形成するための手段
を含む、請求項52に記載の装置であって、前記複数の互いに接続されていないグラフが、前記複数の独立の領域を含む、装置。
【請求項５４】
前記建物情報の前記建物構造の外側にある少なくとも1つの点を識別するための手段と、
前記少なくとも1つの点に少なくとも一部基づいて、前記建物情報の前記建物構造の外側にある少なくとも1つの独立の領域を、前記複数の独立の領域から確定するための手段と
をさらに含む、請求項51に記載の装置。
【請求項５５】
少なくとも1つの独立の領域に少なくとも一部基づいて、前記建物情報の前記建物構造の1つもしくは複数の入口および/または出口を決定するための手段であって、前記少なくとも1つの独立の領域が、前記重畳された点のグリッドを用いて、前記建物構造の外側にあると確定される、手段
をさらに含む、請求項47に記載の装置。
【請求項５６】
どの1つまたは複数の独立の領域が使用可能か、および、1つまたは複数の独立の領域が使用不可能かどうかを、複数の独立の領域から判定するための手段
をさらに含む、請求項47に記載の装置。
【請求項５７】
前記建物情報の扉を開いた状態で模擬するための手段と、
前記建物情報の前記建物構造と交差しない障害のない接続により、前記重畳された点のグリッドの隣接点の少なくとも一部を相互接続するための手段と
をさらに含む、請求項56に記載の装置。
【請求項５８】
どの1つまたは複数の独立の領域が使用可能か、および、1つまたは複数の独立の領域が使用不可能かどうかを、前記判定するための手段が、
前記重畳された点のグリッドの相互接続された点を通過することによって、前記複数の独立の領域の所与の独立の領域に外側の点から到達可能である場合に、前記所与の独立の領域が使用可能な独立の領域であると判定するための手段と、
前記重畳された点のグリッドの相互接続された点を通過することによって、前記複数の独立の領域の所与の独立の領域に外側の点から到達可能ではない場合に、前記所与の独立の領域が使用不可能な独立の領域であると判定するための手段と
を含む、請求項57に記載の装置。
【請求項５９】
前記複数の独立の領域の所与の独立の領域に直接接続される扉の所定の閾値に少なくとも一部基づいて、前記建物情報の1つまたは複数の廊下を複数の独立の領域から検出するための手段
をさらに含む、請求項47に記載の装置。
【請求項６０】
前記建物情報からの注記情報を少なくとも1つの接続グラフに重畳し、注記された建物情報を有する前記少なくとも1つの経路案内グラフを生成するための手段
をさらに含む、請求項47に記載の装置。
【請求項６１】
前記少なくとも1つの経路案内グラフを用いて、前記建物構造に関する道案内情報をモバイル機器に提供するための手段
をさらに含む、請求項47に記載の装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公表番号】特表２０１３−５０６８５１（Ｐ２０１３−５０６８５１Ａ）
【公表日】平成２５年２月２８日（２０１３．２．２８）
【国際特許分類】
【出願番号】特願２０１２−５３２３７５（Ｐ２０１２−５３２３７５）
【出願日】平成２２年１０月１日（２０１０．１０．１）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０５１２２６
【国際公開番号】ＷＯ２０１１／０４１７５５
【国際公開日】平成２３年４月７日（２０１１．４．７）
【出願人】（５０７３６４８３８）クアルコム，インコーポレイテッド (446)
【Ｆターム（参考）】
【公表日】平成２５年２月２８日（２０１３．２．２８）
【国際特許分類】
【出願日】平成２２年１０月１日（２０１０．１０．１）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０５１２２６
【国際公開番号】ＷＯ２０１１／０４１７５５
【国際公開日】平成２３年４月７日（２０１１．４．７）
【出願人】（５０７３６４８３８）クアルコム，インコーポレイテッド (446)
【Ｆターム（参考）】
[ Back to top ]