データベースを生成する方法、ナビゲーション装置、及び、高さ情報を定める方法
【課題】ナビゲーション装置内で使用されるデータベース（１０）を生成する方法を提供すること。
【解決手段】上記方法では、表面分割図の１つのタイルにそれぞれ関連する、第１データ構造（１１）内の項目（１３〜１８）が生成される。少なくとも１つの定義済みのタイル型と各々のタイル上の３次元地形の比較に基づいて、定義済みのタイル型に対する識別子（１９）、又は、各々のタイル上の地形を記述するデータのどちらかが、その項目中に保存される。データベース（１０）を使用して高さ座標を定める方法と、データベース（１０）を含むナビゲーション装置も提供される。
【解決手段】上記方法では、表面分割図の１つのタイルにそれぞれ関連する、第１データ構造（１１）内の項目（１３〜１８）が生成される。少なくとも１つの定義済みのタイル型と各々のタイル上の３次元地形の比較に基づいて、定義済みのタイル型に対する識別子（１９）、又は、各々のタイル上の地形を記述するデータのどちらかが、その項目中に保存される。データベース（１０）を使用して高さ座標を定める方法と、データベース（１０）を含むナビゲーション装置も提供される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、ナビゲーション装置における高さ情報の利用に関連する方法及び装置に関する。本発明の実施形態は、特に、ナビゲーション装置用のデータベースを生成する方法、ナビゲーション装置、及び、地形の高さ情報を定める方法に関する。本発明の実施形態は、特に、地形の３次元表示を出力するのに利用され得るような方法及び装置に関する。
【背景技術】
【０００２】
地形の高さ情報は、ナビゲーション装置にますます幅広く利用されている。そのような高さ情報が利用され得る典型的な一分野は、３次元地図の出力である。電子地図を出力するのに、光学式出力装置が利用され得る。電子地図は、小型及び／又は携帯式装置のスクリーン上に表示され得るので、多目的に利用可能であり、嵩張らないという利点がある。３次元（３Ｄ）地図、即ち、斜視表示は、認識の質が高いので、利用者にとって特に価値のあるものであり得る。即ち、通りの交差点等の環境領域を認識することは、３次元地図が出力される場合、従来の２次元表示に比べて容易になり得る。
【０００３】
高さ情報が利用され得る別の典型的分野として、ナビゲーション用途又は運転者補助が挙げられる。例示説明として、路線検索に利用される、燃料消費費用等の様々な費用関数は、対象とされる高低差に依存し得る。高さ情報により、確定された道路を渡る際に包含される高低差を知ることができる。高低差の燃料消費又は他の運転者補助機能への影響が、考慮され得る。
【０００４】
そのような高さ情報を利用するためには、ナビゲーション装置内に表面の幾何形状についての情報を保存しなければならない。様々な制約を考慮する必要がある。他方では、記憶空間の要件は、適度に保たれなければならない。他方では、３次元地形を示すデータの形式は、ナビゲーション装置内で容易に利用可能な計算資源及び時間を用いて、斜視図を生成するのを可能にするものあるべきである。この目的のために、表面構造をデジタル立体モデル（ＤＥＭ）データとして保存することができる。ＤＥＭデータは、各々が不規則三角形網（ＴＩＮ）である、三角区画を含んでもよい。これにより、ＤＥＭデータを利用して、地形の表示を実行時に効率的に生成することができる。
【０００５】
高性能な地形の視覚化のための様々な技術は、ＤＥＭデータが継ぎ目なく、拡張領域を包含することを必要とする。即ち、ＤＥＭデータが利用できないような穴又は間隙があってはならない。従来の取り組みでは、この要求のために、いずれの高さ変化もない領域に使用される記憶空間の量が大きくなり得る。これは、特に、表面分割図を使用して実行時間での性能を向上させる場合に当てはまる。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従って、ＤＥＭデータ用の記憶空間の要件を削減するのを可能にする方法及びナビゲーション装置が必要である。特に、データを構成するのに表面分割図を使用して、ＤＥＭデータ用の記憶空間の要件を削減するのを可能にする方法及び装置が必要である。
【課題を解決するための手段】
【０００７】
この要求は、独立請求項中に詳述されるような方法及びナビゲーション装置により対処される。従属請求項は、実施形態を定める。
【０００８】
一態様によれば、ナビゲーション装置用のデータベースを生成する方法が提供される。３次元地形を定めるデータを取得する。取得されたデータに基づいて、複数のタイルを含む表面分割図を利用して第１データ構造を生成する。表面分割図の各々のタイルに対して、それぞれ、第１データ構造内に項目を生成する。あるタイルに対して項目を生成するためには、各々のタイル内に含まれる３次元地形の一部分を、第２データ構造内に含まれる少なくとも１つの定義済みのタイル型と比較する。その比較結果に基づいて、その項目中に３次元地形の一部分を定めるデータ、又は、第２データ構造内に含まれる定義済みのタイル型に対する識別子のうちの１つを項目に保存するために選択する。第１データ構造及び第２データ構造は、データベース内に保存される。
【０００９】
本方法において、各々のタイル内の３次元地形の一部分を定める完全な集合のＤＥＭデータをデータベース内に保存することを必ずしも必要としない。あるタイルの地形を、定義済みのタイル型（単数）又は定義済みのタイル型（複数）と比較して、少なくとも平面方向の位置が互いに対して一致する場合、全ての頂点の座標３組を含む完全な情報を保存するのではなく、各々の定義済みのタイル型へのポインタを保存することで十分であり得る。これにより、頻繁に発生するタイル型に対する記憶空間を節約することができる。例示説明として、地形がいかなる有意の高さ変化も示さないタイルは、平らな地形を定めるタイル型へのポインタにより、表記されてもよい。データを構成するのに表面分割図を尚も利用しながら、従って、関連する性能面の利益を保存しながら、記憶空間の要件が削減され得る。平らな地形又は少数の平坦面を有する地形等の、複数の異なるタイルに見出される定義済みのタイル型を保存する必要があるのは、一度のみである。
【００１０】
項目中に保存される「３次元地形の一部分を定めるデータ」は、それ自体で、３次元表面の完全な記述を与えるデータであり、そのデータと、第２データ構造からの情報を組み合わせる必要はない。
【００１１】
３次元地形を定める表面メッシュの頂点の座標は、３次元地形を定めるデータから取り出されてもよく、３次元地形を定めるデータに基づいて生成されてもよい。各々の頂点は、３次元情報が利用可能であるように、平面座標と高さ座標の一組をそれぞれ有する。表面分割図の各々のタイルに対して、第１データ構造内の項目は、それぞれ、そのタイル上に位置する表面メッシュの全ての頂点の平面座標が、各々の定義済みのタイル型内の頂点の平面座標に対応する場合、その定義済みのタイル型に対する識別子を含むように生成されてもよい。複数の定義済みのタイル型がある場合、１つの定義済みのタイル型に対する識別子は、その識別子に対する表面メッシュの頂点の平面座標が、その定義済みのタイル型の座標に対応するように、保存されてもよい。平面座標は、本明細書で用いられる場合、重力ベクトルに直交する２方向の座標である。頂点の相対平面座標は、本明細書で用いられる場合、タイル上の表面メッシュと定義済みのタイル型の両方に対して、相対位置、即ち、全ての組の頂点の間の距離ベクトルのｘ座標及びｙ座標が同じである場合、定義済みのタイル型内の頂点の平面座標「に対応する」。
【００１２】
したがって、各々のタイルの形態を記述するために、定義済みのタイル型に対する識別子を保存してもよい。表面メッシュの形態（即ち、そのｘｙ面への投影）と定義済みのタイル型を整合させることにより、形態の情報を含む定義済みのタイル型に対する識別子を保存することで、記憶空間を削減することができる。これにより、より多くのタイルに対して、そのような識別子を利用することができる。
【００１３】
表面分割図のタイルに対して、３次元地形の一部分を定めるデータ又は定義済みのタイル型に対する識別子のいずれを保存するべきかの決定は、表面メッシュの形態に基づいて行われてもよい。その形態は、各々のメッシュ内の表面メッシュの頂点の平面座標により定義される。その形態は、表面メッシュのｘｙ面への投影であってもよい。３次元地形の一部分を定めるデータ又は定義済みのタイル型に対する識別子のいずれを保存するべきかの決定は、そのタイル内の表面メッシュの形態が、定義済みのタイル型に整合しているかに基づいて行われてもよい。これにより、同じ形態を有するタイルが、高さ方向で互いにずれている場合でも、表面メッシュについての情報を効率的に嵩張らずに保存することができる。
【００１４】
タイル上に位置する表面メッシュの全ての頂点の平面座標が、定義済みのタイル型（複数可）のうちのどの頂点の平面座標にも対応しない場合、各々のタイル上の３次元地形の一部分を定めるデータが、第１データ構造の項目中に保存されてもよい。このデータは、各々のタイルに対する全てのＤＥＭデータを含むことができる。このデータは、１つ又は複数の不規則三角形網（ＴＩＮ）が含まれてもよい。そのデータには、粗い解像度レベルでのタイルに対する表面メッシュを定める２つのＴＩＮと、細かい解像度レベルでのタイルに対する表面メッシュを定める追加の４つのＴＩＮが含まれてもよい。これにより、正方形のタイルを、２つの三角形（粗い解像度レベル）に又は４つの三角形（細かい解像度レベル）に細分化することができ、ＴＩＮは、それらの三角形の各々に対して定義される。
【００１５】
タイル上に位置する頂点の高さ座標に基づいて、定義済みのタイル型に対する識別子に加えて、そのタイル上に位置する少なくとも１つの頂点の高さ座標が、第１データ構造内に保存されるべきかが判定され得る。これにより、必要な場合にのみ、高さ情報を選択的に保存することができ、記憶空間の要件を更に削減することができる。
【００１６】
タイル上に位置するいずれかの組の頂点の高さ座標が、既定の閾値を超えて互いに異なる場合、タイル上に位置する全ての頂点の高さ座標は、第１データ構造内の項目中に保存され得る。その閾値は、ゼロに設定されてもよい。即ち、全ての頂点の高さ座標は、タイル上の全ての頂点の高さが同じでない限り、そのタイルに対応する第１データ構造の項目中に保存されてもよい。それにより、高さデータが忠実に表示され得る。
【００１７】
タイル上に位置する全ての頂点の高さ座標が、最大既定の閾値だけ互いに異なる場合、第１データ構造内の項目中に保存され得る高さ変位値は、最大限１つである。閾値値は、ゼロに等しいように設定されてもよい。即ち、タイル上に位置する全ての頂点の高さが同じである場合、そのタイルに対して保存され得る高さ変位値は、最大限１つである。それにより、記憶空間の要件が、更に削減され得る。
【００１８】
全ての頂点の高さ座標が既定値の高さと異なる場合は、１つの高さ変位値が、第１データ構造内の項目中に保存され得る。タイル上に位置する全ての頂点の高さ座標が、全て、既定値の高さと等しい場合は、高さ変位値が、第１データ構造内の項目中に保存され得ない。高さの既定値は、ゼロ高さであってもよい。それにより、海面で平らな地形を示すタイルに対して、高さ座標を保存することは全く必要ない。海面から外れた平らな地形を示すタイルを記述するには、１つの高さ変位値を適切なタイル型に対する識別子と組み合わせることで十分である。
【００１９】
第１データ構造内の項目は、それぞれ、各々のタイルに固有のタイル識別子を含むように生成されてもよい。固有のタイル識別子は、タイル識別子を利用して、その中心又は隅等のそのタイルの特徴点の座標を定め得るようなものであってもよい。
【００２０】
タイル上に位置する全ての頂点が、そのタイルの境界に、特に、隅に位置する場合、第１データ構造内に保存するために、定義済みのタイル型に対する識別子を選択してもよい。それにより、定義済みのタイル型に対する識別子を利用して、少なくとも、平らな地形を示すタイルが示され得る。
【００２１】
第２データ構造内に含まれる各々の定義済みのタイル型は、あるタイル型を指し示すことができない場合に第１データ構造内のタイルを記述するのに利用されるデータ形式に対応するように定義された、データ形式を有してもよい。例示説明として、各々の定義済みのタイル型は、それぞれ、複数の頂点の平面座標と、各々が隅として３つの頂点をそれぞれ有する、三角面を記述する指標の配列とを含んでもよい。それらの面を記述する指標の配列は、頂点配列内の項目へのポインタを含んでもよい。
【００２２】
第２データ構造内の定義済みのタイル型は、利用者により定義されてもよい。例示説明として、タイルの隅にのみ頂点があるような定義済みのタイル型が、１つのみ事前に定義されてもよい。代わりに、複数の異なるタイルに対する表面メッシュを分析することにより、１つ又は幾つかの定義済みのタイル型が自動的に生成されてもよい。頂点の所定の形態が、既定の回数を超えて発生する場合、対応するタイル型が、自動的に定義され、第２データ構造内に保存されてもよい。
【００２３】
別の態様によれば、３次元地形を示すデータベースが提供される。そのデータベースは、各々が表面分割図のタイルに固有のタイル識別子を含む、複数の項目を有する第１データ構造と、少なくとも１つの定義済みのタイル型を定義する第２データ構造とを含む。第１データ構造内の各々の項目は、第２データ構造内の定義済みのタイル型へのポインタ、又は、各々のタイル内の地形を直接記述するデータのうちの１つを含む。地形を直接記述するデータには、複数の頂点に対する３組の頂点座標の配列が含まれてもよい。地形を直接記述するデータには、各々のタイルに対して複数の三角面を定義する頂点指標の配列が更に含まれてもよい。
【００２４】
データベースの第１データ構造内の各々の項目は、それぞれ、１つのタイルに関連してもよい。
【００２５】
定義済みのタイル型へのポインタを含み得る第１データ構造内の各々の項目は、選択的に、高さ座標を含まないか、１つの高さ座標を含むか、又は、１を超える高さ座標を含むことができる。第１データ構造内の各々の項目は、各々のタイル上の表面メッシュの頂点のいずれの平面座標も含まないようなものであり得る。
【００２６】
別の態様によれば、ナビゲーション装置が提供される。ナビゲーション装置は、３次元地形を表し、第１データ構造と第２データ構造と含むデータベースを含む。第１データ構造は、各々が表面分割図のタイルに固有のタイル識別子を含む、複数の項目を有する。第２データ構造は、少なくとも１つの定義済みのタイル型を定義する。ナビゲーション装置は、データベースに結合された処理装置を有する。その処理装置は、タイルに固有の識別子を利用して、第１データ構造の項目にアクセスし、アクセスされた項目が、第２データ構造内に保存された定義済みのタイル型に対する型識別子を含んでいるかを判定するように設定されている。処理装置は、次に、項目が型識別子を含む場合、定義済みのタイル型についての情報を第２データ構造から選択的に取り出すように設定されている。処理装置は、第１データ構造のアクセスされた項目に基づいて、項目が型識別子を含む場合は、第２データ構造内に含まれる定義済みのタイル型に基づいて、１つ又は複数の場所の高さ座標を定めるように設定されている。
【００２７】
このナビゲーション装置では、第１データ構造内のタイルの項目に、タイル型へのポインタ又は各々のタイル上のＤＥＭを直接記述するデータのうちの１つが選択的に含まれてもよい。各々のタイルに対して、完全なＤＥＭデータを保存する必要はない。例示説明として、表面メッシュのいずれも頂点も内部に含まないタイルは、それぞれ、第１データ構造内の項目が、第２データ構造へのポインタを含み得る。それにより、記憶空間の要件が削減され得る。
【００２８】
ナビゲーション装置は、光学式出力装置を含んでもよい。処理装置は、光学式出力装置を制御し、所与のタイル上に位置するＤＥＭの一部分を表示するように設定され得る。処理装置は、各々のタイルに対する第１データ構造内の項目中に含まれるデータと、第１データ構造内の項目が、定義済みのタイル型に対する識別子を含む場合、この項目が指し示すタイル型の定義との両方を利用して、光学式出力装置を制御し得る。処理装置は、項目が、定義済みのタイル型に対する識別子を含まない場合、第１データ構造内の項目中に含まれるデータのみを利用して、光学式出力装置を制御し得る。
【００２９】
定義済みのタイル型へのポインタを含む第１データ構造内の各々の項目は、選択的に、高さ座標を含まないか、１つの高さ座標を含むか、又は、１を超える高さ座標を含むことができる。
【００３０】
処理装置は、項目が型識別子を含む場合、取り出された、定義済みのタイル型についての情報に基づいて、表面メッシュの複数の頂点に対して一対の平面座標をそれぞれ定め、第１データ構造の項目に基づいて、頂点の高さ座標を定めるように設定され得る。それにより、定義済みのタイル型が点の形態を定めるのに使用され得るのに対し、高さ情報は、第１データ構造内の対応する項目から取り出され得る。これにより、多目的利用の可能性が向上する。
【００３１】
第１データ構造の項目が、型識別子と高々１つの高さ座標とを含む場合、処理装置は、表面メッシュの頂点の高さ座標を同じ値に定めるように設定され得る。従って、平らなタイルでは、第１データ構造内の項目中に保存する必要のある高さ座標は、最大限１つである。
【００３２】
処理装置は、第１データ構造の項目が型識別子と複数の高さ座標とを含む場合、頂点に対して異なる高さ座標を定めるように設定され得る。
【００３３】
定義済みのタイル型に対する識別子を含まないデータベースの項目は、それぞれ、表面メッシュの頂点の座標３組についての情報を含んでもよい。そのような項目は、表面メッシュの三角面を定義する頂点指標の配列を更に含んでもよい。
【００３４】
データベースは、いずれか１つの態様又は実施形態のデータベースを生成する方法を利用して生成される、データベースであってもよい。
【００３５】
別の態様によれば、ナビゲーション装置内で高さ情報を定める方法が提供される。そのナビゲーション装置は、各々が表面分割図のタイルに固有のタイル識別子を含む、複数の項目を有する第１データ構造と、少なくとも１つの定義済みタイル型を定義する第２データ構造とを含む、データベースを有する。１つ以上の場所に対する高さ情報を定めるためには、タイルに固有の識別子を使用して、第１データ構造の項目にアクセスする。項目が、第２データ構造内に保存された定義済みのタイル型に対する型識別子を含んでいるかを判定する。項目が型識別子を含む場合、定義済みのタイル型についての情報は、第２データ構造から取得される。１つ又は複数の場所の高さ座標は、第１データ構造のアクセスされた項目に基づいて定められてもよく、項目が型識別子を含む場合は、第２データ構造内に含まれる定義済みのタイル型に基づいて定められてもよい。
【００３６】
本方法では、第２データ構造内の定義済みのタイル型は、第１データ構造内のタイルの項目により参照され得る。定義済みのタイル型に対する識別子を含む各々のタイルでは、全てのＤＥＭデータを個別に保存する必要はない。例示説明として、表面メッシュのいずれの頂点も内部に含まないタイルは、それぞれ、第１データ構造内に、第２データ構造へのポインタを含む項目を有し得る。それにより、記憶空間の要件が削減され得る。
【００３７】
第２データ構造内の定義済みのタイル型は、表面メッシュの頂点の形態を定め得る。即ち、定義済みのタイル型には、各々のタイル上の頂点の相対平面座標についての情報が含まれ得る。必要であれば、第１データ構造内の各々の項目中に、頂点の高さ座標についての情報が個別に保存されてもよい。例示説明として、タイルの地形が平らであるが、既定値の高さ（海面等）から外れている場合は、各々のタイルに対して、第１データ構造内の各々の項目中に１つの高さ座標を保存してもよい。タイルが、その内部にいずれの頂点も含まないが、その隅での頂点の高さが異なる場合は、第１データ構造内の各々の項目中に４つの座標を保存してもよい。
【００３８】
１つ以上の場所の定められた高さ座標は、３次元地形の視覚化、経路を渡る際に発生する費用の算出、経路検索等のような、様々な目的に利用され得る。
【００３９】
上述の特徴と以下に説明される特徴は、指示された各々の組み合わせについてばかりでなく、他の組み合わせでも又は単独でも利用することができると理解されるべきである。
【００４０】
実施形態の上述の及び他の特徴は、実施形態の以下の詳細な記述から、付属の図面と関連して読む際に更に明らかになる。図面では、同様の参照番号は、同様の要素を指す。
例えば本発明は以下の項目を提供する。
（項目１）
ナビゲーション装置（１）用のデータベースを生成する方法（１０）であって、上記方法が、
３次元地形を定めるデータを取り出すことと、
取り出されたデータに基づいて、複数のタイル（２３〜２６；３１〜３４）を含む表面分割図（２０）を使用して第１データ構造（１１）を生成することとであって、上記表面分割図（２０）の各々のタイル（２３〜２６；３１〜３４）に対して、項目（１３〜１８）が、上記第１データ構造（１１）内にそれぞれ生成され、上記項目をそれぞれ生成することは、
上記タイル（２３〜２６；３１〜３４）内に含まれる上記３次元地形の一部分を、第２データ構造（１２）内に含まれる少なくとも１つの定義済みのタイル型と比較することと、
上記比較の結果に基づいて、上記項目中に保存するために、上記３次元地形の一部分を定めるデータ、又は、上記第２データ構造（１２）内に含まれる定義済みのタイル型に対する識別子（１９）のうちの１つを選択することと
を含み、
上記第１データ構造（１１）と上記第２データ構造（１２）とを上記データベース（１０）内に保存することと
を含む、方法。
（項目２）
上記３次元地形を定める表面メッシュの頂点（４１〜５０）の座標が、上記３次元地形を定める上記データから取り出されるか、又は、３次元地形を定めるデータに基づいて生成され、上記頂点（４１〜５０）の各々が、平面座標と高さ座標の一組をそれぞれ有し、
上記表面分割図（２０）の各々のタイル（２３〜２６；３１〜３４）に対して、上記タイル（２３〜２６；３１〜３４）上に位置する全ての頂点（４１〜５０）の相対平面座標が、定義済みのタイル型内の頂点（５５〜５８）の平面座標に対応する場合、上記項目（１４、１６、１７）が、上記第２データ構造（１２）内に含まれる、上記定義済みのタイル型に対する識別子（１９）をそれぞれ含むように生成される、
上記項目に記載の方法。
（項目３）
上記方法が、
上記タイル（２３〜２６；３１〜３４）上に位置する上記頂点（４１〜５０）の高さ座標に基づいて、上記定義済みのタイル型に対する上記識別子（１９）に加えて、上記タイル（２３〜２６；３１〜３４）上に位置する少なくとも１つの頂点（４１〜５０）の高さ座標が、上記第１データ構造（１１）内に保存されるべきかを判定すること
を更に含む、上記項目のいずれかに記載の方法。
（項目４）
上記タイル（３１）上に位置するいずれかの組の頂点（４１、４６、４７、５０）の高さ座標が、既定の閾値を超えて互いに異なる場合、上記タイル（３３）上に位置する全ての頂点（４１、４６、４７、５０）の高さ座標が、上記第１データ構造（１１）の項目（１７）中に保存される、上記項目のいずれかに記載の方法。
（項目５）
上記タイル（３１、３２、３４）上に位置する全ての頂点（４１〜５０）の高さ座標が、最大限既定の閾値だけ互いに異なる場合、上記タイル（３１、３２、３４）上に位置する全ての頂点（４１〜５０）に対して、最大限１つの高さ変位値が、上記第１データ構造（１１）の上記項目（１４、１６）中に保存される、上記項目のいずれかに記載の方法。
（項目６）
全ての頂点（４７〜５０）の上記高さ座標が、既定値の高さと異なる場合、１つの高さ変位値が、上記第１データ構造（１１）内の上記項目（１６）中に保存され、
全ての頂点（４１〜４６）の上記高さ座標が、上記既定値の高さと等しい場合、高さ変位値が、上記第１データ構造（１１）内の上記項目（１４）中に保存されない、
上記項目のいずれかに記載の方法。
（項目７）
上記３次元地形の一部分を定める上記データ、又は、上記識別子（１９）のうちの上記１つが、上記タイル（２３〜２６；３１〜３４）上に位置する全ての頂点（４１〜５０）の高さ座標とは独立して選択される、上記項目のいずれかに記載の方法。
（項目８）
上記タイル（２３〜２６；３１〜３４）上に位置する全ての頂点（４１〜５０）が、上記タイル（２３〜２６；３１〜３４）の境界に、特に、隅に位置する場合、上記第１データ構造（１１）内に保存するために、定義済みのタイル型に対する上記識別子（１９）を選択する、上記項目のいずれかに記載の方法。
（項目９）
上記第２データ構造（１２）内に含まれる各々の定義済みのタイル型が、複数の頂点（４１〜５０）の平面座標と、隅として３つの上記頂点（４１〜５０）をそれぞれ有する三角面を記述する指標の配列とを含む、上記項目のいずれかに記載の方法。
（項目１０）
３次元地形を表し、各々が表面分割図（２０）のタイル（２３〜２６；３１〜３４）に固有のタイル識別子を含む、複数の項目（１３〜１８）を有する、第１データ構造（１１）と、少なくとも１つの定義済みのタイル型を定義する第２データ構造（１２）とを含むデータベース（１０）と、
タイル（２３〜２６；３１〜３４）に上記固有のタイル識別子を使用して、上記第１データ構造（１１）の項目にアクセスし、
上記アクセスされた項目が、上記第２データ構造（１２）内に保存された定義済みのタイル型に対する型識別子（１９）を含んでいるかを判定し、
上記項目が上記型識別子（１９）を含む場合、上記定義済みのタイル型についての情報を上記第２データ構造（１２）から選択的に取り出し、
上記第１データ構造（１１）の上記アクセスされた項目（１３〜１８）に基づいて、上記項目（１３〜１８）が上記型識別子（１９）を含む場合は、上記第２データ構造（１２）内に含まれる上記定義済みのタイル型に基づいて、１つ又は複数の場所の高さ座標を定めるように
設定されている、上記データベース（１０）に結合された処理装置（２）と
を含む、ナビゲーション装置（１）。
（項目１１）
上記項目（１４、１６、１７）が型識別子（１９）を含む場合に、上記処理装置（２）が、上記取り出された上記定義済みのタイル型についての情報に基づいて、表面メッシュの頂点（４１〜５０）の一組の平面座標をそれぞれ定め、上記第１データ構造（１１）の上記項目（１４、１６、１７）に基づいて、上記頂点（４１〜５０）の高さ座標をそれぞれ定めるように設定されている、上記項目のいずれかに記載のナビゲーション装置（１）。
（項目１２）
上記第１データ構造（１１）の上記項目（１４、１６）が、上記型識別子（１９）と高々１つの高さ座標とを含む場合、上記頂点（４１〜４６、４７〜５０）の高さ座標を同じ値に定めるように上記処理装置（２）が設定されている、上記項目のいずれかに記載のナビゲーション装置（１）。
（項目１３）
上記第１データ構造（１１）の上記項目（１７）が、上記型識別子（１９）と複数の高さ座標とを含む場合に、上記頂点（４１〜５０）に対して異なる高さの座標を定めるように上記処理装置（２）が設定されている、上記項目のいずれかに記載のナビゲーション装置（１）。
（項目１４）
定義済みのタイル型に対する識別子（１９）を含まない上記データベース（１０）の項目（１３、１５、１８）が、表面メッシュの頂点（４１〜５０）の座標３組についての情報を含む、上記項目のいずれかに記載のナビゲーション装置（１）。
（項目１５）
ナビゲーション装置（１）内で高さ情報を定める方法であって、上記ナビゲーション装置（１）が、各々が表面分割図（２０）のタイル（２３〜２６；３１〜３４）に固有のタイル識別子を含む、複数の項目（１３〜１８）を有する第１データ構造（１１）と、少なくとも１つの定義済みタイル型を定義する第２データ構造（１２）とを含む、データベース（１０）を有し、上記方法が、
タイル（２３〜２６；３１〜３４）に固有の識別子を使用して、上記第１データ構造（１１）の項目（１３〜１８）にアクセスすることと、
上記項目（１４、１６、１７）が、上記第２データ構造（１２）内に保存された定義済みのタイル型に対する型識別子（１９）を含んでいるかを判定することと、
上記判定の結果に基づいて、上記項目（１４、１６、１７）が上記型識別子（１９）を含む場合、上記第２データ構造（１２）から、上記定義済みのタイル型についての情報を取得することと、
上記第１データ構造（１１）のアクセスされた項目（１３〜１８）に基づいて、および上記項目（１４、１６、１７）が上記型識別子（１９）を含む場合は、上記第２データ構造（１２）内に含まれる上記定義済みのタイル型に基づいて、１つ又は複数の場所の高さ座標を定めることと
を含む、方法。
【００４１】
摘要
ナビゲーション装置内で使用されるデータベース（１０）を生成する方法では、表面分割図の１つのタイルにそれぞれ関連する、第１データ構造（１１）内の項目（１３〜１８）が生成される。少なくとも１つの定義済みのタイル型と各々のタイル上の３次元地形の比較に基づいて、定義済みのタイル型に対する識別子（１９）、又は、各々のタイル上の地形を記述するデータのどちらかが、その項目中に保存される。データベース（１０）を使用して高さ座標を定める方法と、データベース（１０）を含むナビゲーション装置も提供される。
【図面の簡単な説明】
【００４２】
【図１】ナビゲーション装置の概略的ブロック図である。
【図２】データベースの概略的表示である。
【図３】表示分割法が重ねられた地形の平面図である。
【図４】データベースを用いた３次元地形の再構築を示している斜視図である。
【図５】タイルの頂点を示す平面図である。
【図６】データベースを生成する方法の流れ図である。
【図７】図６の方法に用いられ得るデータベース内に項目を生成する手続を示す。
【図８】タイル型の別の典型的形態を示す平面図である。
【発明を実施するための形態】
【００４３】
図１は、実施形態によるナビゲーション装置１を概略的に示す。ナビゲーション装置１は、ナビゲーション装置１の操作を制御する処理装置２を含む。処理装置２は、例えば、１つ以上のマイクロプロセッサ、デジタル信号プロセッサ又は用途特定集積回路の形態の中心処理ユニットを含んでもよい。処理装置２は、グラフィックプロセッサを含み得る。ナビゲーション装置１は、記憶装置３内に保存されるデータベース１０を更に含む。記憶装置３は、ランダムアクセスメモリ、フラッシュメモリ又はハードドライブ、さらに、コンパクトディスク（ＣＤ）、ＤＶＤ、メモリカード等の脱着可能なメモリのような、様々な種類のメモリのいずれか１つ又はいずれかの組み合わせを含んでもよい。ナビゲーション装置１は、光学式出力装置４も含む。ナビゲーション装置１は、位置センサ及び／又は無線受信機及び／又は入力インターフェース５等の追加の部品を含んでもよい。
【００４４】
記憶装置３は、３次元地形を定めるデータベース１０を保存する。３次元マップを生成し、即ち、地形を視覚化し、燃料消費又は道路に関連する他の費用等を確定するために、処理装置２によりデータベース１０内のデータを使用することができる。
【００４５】
以下に詳細に説明されるように、データベース１０内のデータは、表面分割図に従って構成される。データベース１０は、第１データ構造と第２データ構造とを含む。第１データ構造は、各々が表面分割図の１つのタイルに関連している、複数の項目を有する。第１データ構造内の各々の項目は、固有のタイル識別子を有する。加えて、第１データ構造内の各々の項目は、各々のタイル内のデジタル立体モデル（ＤＥＭ）を直接定義するデータ、又は、定義済みのタイル型に対する識別子のどちらかを含む。定義済みのタイル型に対するそのような識別子が含まれる場合、第１データ構造の項目中の情報は、第２データ構造内の情報と組み合わせられない限り、単独では、タイルに対して表面を再構築することができない。第２データ構造は、第１データ構造内の項目により参照される定義済みタイル型についての情報を含む。
【００４６】
第１データ構造内の項目が、各々のタイル内にＤＥＭを直接記述するデータを含む場合、項目は、頂点の座標３組の配列を含んでもよい。その項目は、不規則三角形網（ＴＩＮ）の三角面を定義する、頂点の指標の別の配列を更に含んでもよい。１つのタイルに対して、１を超えるＴＩＮが定義されてもよい。例示説明として、２つのＴＩＮを使用して、粗い解像度でタイル内の地形を定めてもよく、４つのＴＩＮを使用して、細かい解像度でタイル内の地形を定めてもよい。定義済みのタイル型を参照することにより、タイル内に表面メッシュの形態を定めることができない場合、このデータの全てを第１データ構造内に含んでもよい。
【００４７】
第１データ構造内の項目は、定義済みのタイル型に対する識別子を含む場合、各々のタイル内の表面メッシュの形態についてのいずれの情報も含んでいない。即ち、タイルの１つの特徴点（中心又は所与の隅等）の平面位置は、固有のタイル識別子から導かれ得る。次に、表面メッシュの頂点の平面位置は、項目中で参照される定義済みのタイル型を使用して導かれ得る。
【００４８】
第１データ構造内の項目は、定義済みのタイル型に対する識別子を含む場合、それにも関わらず、１つ以上の高さ座標を含んでもよい。タイル上に位置する全ての頂点の座標３組を定めるために、第１項目中に含まれる高さ座標（複数可）を、第１データ構造内の項目により参照される定義済みのタイル型により定義される表面メッシュの形態と組み合わせることができる。
【００４９】
定義済みのタイル型の数と種類は、考慮される用途に適切であるように選択され得る。幾つかの実装では、その隅に表面メッシュの頂点があるが、その内部に頂点のないタイルを示す、１つの定義済みのタイル型のみが使用される。そのような定義済みのタイル型は、平らな地形上の表面メッシュの形態を記述する。そのような定義済みのタイル型は、粗い解像度レベルで、多くのタイルに対する表面メッシュの形態も記述する。例示説明として、多くのナビゲーション装置用データベースは、１０又はそれ以上の解像度レベル等の、数多くの解像度レベルを使用する。少なくとも最も粗いレベルでは、解像度は、地形が、タイルの隅にのみ位置する頂点により適切に定義され得るようなものである。
【００５０】
以下に、１つの定義済みのタイル型を使用した実装を示すが、より多くの数の定義済みのタイル型を、他の実装に使用してもよい。
【００５１】
図２は、データベース１０の概略図である。データベース１０は、ナビゲーション装置１に使用され得る。データベース１０は、３次元地形を示す。複数の異なる解像度レベルを与えることが望まれる場合、以下に説明されるデータ構造は、各々の解像度レベルに対して与えられ得る。代わりに、複数の異なる解像度レベルに、独立した第１データ構造１１が与えられ得るのに対し、複数の異なる解像度レベルに、１つの第２データ構造１２が使用され得る。
【００５２】
データベース１０は、第１データ構造１１と第２データ構造１２とを有する。第１データ構造１１では、複数の項目１３〜１８が保存される。項目１３〜１８の各々は、それぞれ、表面分割図の１つのタイルと関連している。第２データ構造１２は、タイル型を定義するデータを含む。第２データ構造１２内のデータは、第１データ構造の項目中のＤＥＭデータに使用される形式に対応するデータ形式を有し得るが、高さ情報が省かれている。
【００５３】
各々の項目１３〜１８は、固有のタイル識別子を含む。タイルＩＤ１、タイルＩＤ２等で示される固有のタイル識別子は、タイルの１つの特徴点（例えば、中心又は隅）のｘ座標及びｙ座標を定めるのを可能にするようなものである。
【００５４】
第１データ構造内の副次集合１３、１５及び１８は、それぞれ、各々のタイル上のＤＥＭの一部分を直接定義するデータを含む。様々なデータ形式が使用されてもよい。実装では、項目１３、１５及び１８内のＤＥＭデータは、それぞれ、１つ又は複数のＴＩＮを定義してもよい。各々のＴＩＮに対して、ＤＥＭデータは、頂点座標の３組の配列と、頂点配列のどの頂点が、それぞれ、表面メッシュの三角面を形成するかを定める頂点指標の配列とを含んでもよい。ＤＥＭデータは、三角面に対する法線ベクトルの配列等の追加の情報を含んでもよい。
【００５５】
項目１３、１５又は１８により示されるタイルのうちの１つに、１つ以上の場所の高さを定めるために、各々の項目１３、１５又は１８にアクセスする。１つ以上の場所の高さは、第２データ構造１２とは独立して、ＤＥＭデータから定められてもよい。
【００５６】
第１データ構造内の項目１４、１６及び１７の別の副次集合は、それぞれ、第２データ構造１２内に保存された定義済みのタイル型に対する、「型１」で示される識別子１９を含む。これらの項目１４、１６及び１７は、ＤＥＭの様々な頂点の頂点座標の３組を含んでいない。項目１４、１６及び１７は、各々のタイル内の表面メッシュの形態についての情報を含んでいない。即ち、項目１４、１６及び１７内に、互いに対する表面メッシュの頂点のｘ座標及びｙ座標を保存する必要はない。
【００５７】
項目１４等の、定義済みのタイル型に対する識別子１９を含む幾つかの項目は、いずれの高さ座標も含み得ない。これは、各々の定義済みのタイル型により定められる表面メッシュの全ての頂点が、既定値の高さに位置することを示す。既定値の高さは、海面であってもよい。
【００５８】
項目１６等の、定義済みのタイル型に対する識別子１９を含む幾つかの項目は、１つの高さ情報のみを含み得る。これは、各々の定義済みのタイル型により定められる表面メッシュの全ての頂点が、既定値の高さから外れた同じ高さに位置することを示す。それにより、１つの単一の高さ変位値のみを使用して、既定値の高さから外れた平らな地形が示され得る。
【００５９】
項目１７等の、定義済みのタイル型に対する識別子１９を含む幾つかの項目は、１以上の高さ座標を含んでもよい。各々の定義済みタイル型の各々の頂点に対する１つの高さ座標は、関連する項目１７内に保存されてもよい。そのようなデータ構造は、各々の定義済みタイル型により定められる表面メッシュの頂点が、全て、各々のタイル上の同じ高さに位置しない場合に使用されてもよい。それにより、頂点の形態（即ち、相対的なｘ位置及びｙ位置）が、定義済みのタイル型のうちの１つに整合するとの条件で、平坦ではない地形が示され得る。
【００６０】
第２データ構造１２は、定義済みのタイル型についての情報を含む。この情報は、一般に、第１データ構造内の項目１３、１５及び１８に対してＤＥＭデータが保存される形式と同じであり得る。しかしながら、定義済みのタイル型が、表面メッシュの形態についての情報のみを含む場合、高さ情報は、第２データ構造１２にはなくてもよい。例示説明として、第２データ構造１２は、各々の定義済みのタイル型に対する頂点の平面座標の２組を定める配列を含んでもよい。頂点の平面座標は、タイルの中心又はその隅のうちの１つ等のタイルの定義済みの場所に対して計測される。第２データ構造１２は、どの頂点が、ＴＩＮの三角面を形成するのかを定める頂点指標の配列を更に含み得る。タイル型が、タイルの隅にのみ頂点があるような型に対応する場合、頂点指標の指標配列は、組み合わせでタイル全体を包含する、２つの三角面を定義し得る。
【００６１】
項目１４、１６又は１７により示されるタイルのうちの１つに、１つ以上の場所の高さを定めるために、各々の項目１４、１６又は１７にアクセスする。タイル型を定義する対応するデータは、定義済みのタイル型に対する識別子１９を使用して、第２データ構造１２から取得される。固有のタイル識別子を使用して、タイルの特徴点のｘ及びｙの絶対位置を定めることができる。第２データ構造内に含まれる、参照されたタイル型に対する頂点の相対平面位置についての情報を使用して、各々のタイル上の表面メッシュの全ての頂点のｘ座標及びｙ座標を定めることができる。第１データ構造内のその対応する項目が、１つ以上の高さ座標を有するか否かに基づいて、頂点の高さ座標を定めることができる。例示説明として、第１データ構造内の項目に高さ座標がない場合は、全ての頂点に対するｚ値を、既定値の高さ（例えば、海面）に設定する。第１データ構造内の項目に１つの高さ座標がある場合は、全ての頂点に対するｚ値をその値に設定する。第１データ構造内の項目に１つの高さ座標がある場合は、様々な頂点に対するｚ値を、各々の項目１７内に含まれる様々な値に設定する。第１データ構造１１内の項目１７の中の高さ値の序列は、この場合、第２データ構造１２内の頂点配列内に頂点が列挙されるような序列に対応し得る。
【００６２】
第１データ構造１１内の項目のＤＥＭデータを使用して、又は、第１データ構造１１内の項目を、第２データ構造１２と組み合わせて使用してそのように定められた高さ情報を、様々な目的に使用することができる。例示説明として、地形を３次元で視覚化することができる。異なる経路に関連する燃料消費等の費用を、高低差を考慮して算出することができる。
【００６３】
図３は、地形の平面図である。その地形の上に、表面分割図２０が重ねられている。地形は、湖又は海２１等の、平らな領域を含む。地形は、河川２２等の平らな追加の領域を含み得る。
【００６４】
ＤＥＭデータを保存する従来の取り組みでは、各々のタイルに対する表面メッシュが、保存されることになる。これは、タイルが、平らであり、海２１又は河川２２により完全に覆われる場合でも、タイルの隅の頂点に対して座標３組を保存する必要があることになる。
【００６５】
定義済みのタイル型を使用することにより、記憶空間が削減され得る。タイルの内部に頂点がないような定義済みのタイル型を使用して、そのタイル型を参照することにより、タイルの内部で平らである地形の形態を定めることができる。
【００６６】
図３に示される地形では、タイル２３〜２５に対して第１データ構造内に生成されるデータ項目は、隅にのみ頂点があるような定義済みのタイル型に対する識別子を含み得る。タイル２３〜２５は、海面に位置しているので、第１データ構造の各々の項目中に、いずれの高さ座標も保存する必要はない。
【００６７】
同様に、タイル２６に対する第１データ構造内で生成されるデータ項目は、隅にのみ頂点があるような定義済みのタイル型に対する識別子を含むことができる。タイル２６が海面よりも上に又は下に位置する場合、第１データ構造の各々の項目中に、１つの単一の高さ座標を保存することができる。
【００６８】
データベースを生成する場合と、そのデータベースから地形を再構築する場合の両方で、１つ以上の定義済みのタイル型を用いる技術を使用してもよい。
【００６９】
図４は、データベースが、図１及び図２を参照して記載されたように設定される場合の、データベースからの地形の再構築を示している概略斜視図である。
【００７０】
図示されるのは、複数のタイル３１〜３４に対する表面メッシュである。データベースの第１データ構造内の各々のタイル３１〜３４に対する項目は、タイルの隅のみ頂点があるようなタイル型へのポインタを含み得る。
【００７１】
タイル３１上に位置する頂点４１〜４４のｘ及びｙの絶対座標は、固有のタイル識別子から導かれ得る、中心等のタイル３１の特徴点の位置と、第２データ構造内に保存されている頂点の相対位置を組み合わせることにより定められ得る。頂点４１〜４４のｚ座標は、再び、第１データ構造内のタイル３１に対する項目に基づいて定められ得る。その項目にいずれのｚ座標もない場合、全ての頂点４１〜４４の高さは、既定値の高さに設定される。既定値の高さは、海面であり得る。
【００７２】
同様に、第１データ構造内のタイル３２に対する項目は、いずれのｚ座標値も含み得ない。それに応じて、タイル３２の隅での頂点４３〜４６の高さは、既定値の高さに、例えば、海面に設定される。
【００７３】
第１データ構造内のタイル３３に対する項目は、４つのｚ座標を含んでもよい。タイル３３上に位置する頂点４１、４２、４７及び５０のｘ座標及びｙ座標は、固有のタイル識別子から導かれ得る中心等のタイル３３の特徴点の位置を、各々のタイル型に対する第２データ構造内に保存された頂点の相対位置と組み合わせることにより定められてもよい。頂点４１、４２、４７及び５０のｚ座標は、タイル３３に対する第１データ構造内の項目中に与えられた値に設定される。それにより、地面に平行ではないが、タイルの内部にいずれの頂点もないような表面メッシュの一部分も示され得る。
【００７４】
第１データ構造内のタイル３４に対する項目は、１つのｚ座標値のみを含み得る。それに応じて、タイル３４の隅での全ての頂点４７〜５０の高さは、タイル３４に対する第１データ構造内の項目中に保存されたｚ座標値に設定される。
【００７５】
頂点の相互配置の形態が定義済みのタイル型に対応するタイルでは、定義済みのタイル型により定義される形態を、もしあれば、第１データ構造の項目中に保存された高さ座標と組み合わせることにより、各々のタイル上の表面メッシュが、そのように再構築され得る。
【００７６】
逆に、図４に示されるように、１つのＴＩＮ又は幾つかのＴＩＮの形態の表面メッシュから始めて、第１データ構造内の項目を生成することができる。各々のタイル上の表面メッシュの頂点の形態は、それぞれ、定義済みのタイル型（単数又は複数）と比較され得る。
【００７７】
第２データ構造内の定義済みのタイル型を定義は、面５１及び５２等の三角面を定義する指標配列を含んでもよい。第２データ構造からのデータを使用して、ＤＥＭデータが第１データ構造内に直接保存されている、タイルに対して使用可能なデータに対応する様々なタイル上における表面メッシュの表現を得ることができる。
【００７８】
図５は、中心５４と隅に頂点５５〜５８とを有するタイルを平面図で示す。
【００７９】
第１データ構造１１は、中心５４又はタイルの別の特徴点の位置が、固有のタイル識別子から導かれ得るようなものであり得る。第２データ構造は、特徴点に対して計測された、頂点５５〜５８の平面座標を含んでいる。従って、頂点の絶対平面（ｘ及びｙ）座標は、上述のように定められ得る。
【００８０】
図６は、データベースを生成する方法６０の流れ図である。方法６０は、コンピュータ等の電子処理装置により実行される。方法６０は、データベースがナビゲーション装置に配備される前に実行され得る。
【００８１】
６１では、３次元地形を定めるデータが取得される。データは、表面メッシュを含んでもよい。データは、１つ又は複数のＴＩＮ（複数可）を定義してもよい。ＴＩＮ（複数可）は、表面分割図上で定められてもよい。他の実装では、データは、例えば、まだ表面メッシュの形態ではない、衛星画像中の高さ値であってもよい。この場合、１つ又は複数のＴＩＮが、３次元地形を示すように定められてもよい。対応する表面分割図も定めてもよい。
【００８２】
６２では、表面分割図のタイルが選択される。方法６０は、表面分割図の複数のタイルを通じて、繰り返されてもよい。この場合、６２で選択されたタイルは、第１繰り返しでの、表面分割図の隅でのタイルであってもよい。
【００８３】
６３では、各々のタイル上のＴＩＮ（複数可）の表面メッシュは、１つ又は複数の定義済みのタイル型と比較される。各々のタイル上のＴＩＮ（複数可）は、複数の頂点を含む。この比較ステップでは、各々のタイル上のＴＩＮ（複数可）の頂点の相対平面座標が定められ得る。続いて、各々のタイル上の表面メッシュの形態を定める頂点の相対平面座標が、１つ又は複数の定義済みのタイル型と比較され得る。各々のタイル上のＴＩＮ（複数可）の頂点の形態が、定義済みのタイル型（複数可）のうちの１つに整合するかを判定する。
【００８４】
例示説明として、タイルの隅でのみ頂点があるような１つの定義済みの型のみを使用する場合、タイル上のＴＩＮ（複数可）の頂点形態は、タイルの内部に頂点がなく、タイルの隅に全ての頂点が位置する場合にのみ、定義済みのタイル型に整合する。
【００８５】
タイル内の頂点形態が、定義済みのタイル型に整合しない場合、本方法は、６４へ進む。６４では、タイル上のＴＩＮ（複数可）の一部分を記述するＤＥＭデータが、データベースの第１データ構造内の項目中に保存される。ＤＥＭデータは、全ての頂点に対する頂点座標の座標３組を有する頂点配列と、頂点のうちのどれが、それぞれ、様々な三角面を形成するのかを記述する指標配列とを含むことができる。第１データ構造内の項目は、各々のタイルに対する固有の識別子を更に含む。
【００８６】
タイル内の頂点形態が、定義済みのタイル型に整合する場合、本方法は、６５へ進む。６５では、各々のタイルに対する項目が、第１データ構造内に生成される。項目は、各々のタイル上のＴＩＮ（複数可）の頂点形態に整合するタイル型を指し示す識別子を含む。その項目は、様々な頂点に対する平面座標を含んでいない。第１データ構造内の項目は、各々のタイルに固有の識別子を更に含む。タイル上の頂点の高さ座標に依存して、全ての頂点が既定値の高さに位置する場合、項目は、高さ座標を含まないように生成され得る。全ての頂点が、既定値の高さとは異なる同じ高さに位置する場合、項目は、１つの高さ座標を含むように生成され得る。頂点の全てが、同じ高さには位置していない場合、項目は、各々の頂点に対して１つの高さ座標を含むように生成され得る。
【００８７】
６６では、各々のタイルに対して項目が生成されたかを判定する。追加のタイルがある場合、方法は、６２に戻る。
【００８８】
各々のタイルに対して、第１データ構造内の項目がそれぞれ生成されている場合、６７で、第１データ構造及び第２データ構造が保存され、そのようにしてデータベースを生成する。
【００８９】
図７は、図６の方法を追加的に説明する手続７０の流れ図である。図７の手続は、タイルの隅でのみ頂点があるような定義済みのタイル型が１つしかない場合、図６の方法でステップ６４〜６５を実施するために使用され得る。
【００９０】
７１では、各々のタイル上の表面メッシュの全ての頂点が、タイルの隅に位置しているかを判定する。
【００９１】
タイルの隅に位置しない頂点が少なくとも１つある場合、本方法は、７２に進む。７２では、固有のタイル識別子と、１つ又は複数のＴＩＮ（複数可）を定義するデータとを含む項目が、タイルに対して生成される。ＴＩＮ（複数可）は、１つ又は複数の頂点配列と、様々な三角面を定義する指標配列とを含んでもよい。次に、本方法６０は、６６に続く。
【００９２】
全ての頂点がタイルの隅に位置する場合、手続は、７３へ進む。７３では、固有のタイル識別子と、定義済みのタイル型に対する識別子とを含む項目が、タイルに対して生成される。
【００９３】
７４では、全ての頂点の高さ座標が同じであるかを判定する。
【００９４】
全ての頂点の高さ座標が同じではない場合、手続は、７５に進む。７５では、タイル上に位置する全ての頂点の高さ座標が、第１データ構造内の項目中に保存される。
【００９５】
全ての頂点の高さ座標が同じである場合、手続は、７６に進む。７６では、全ての頂点の高さ座標が既定値に対応しているかを判定する。既定値は、海面であり得る。
【００９６】
タイル上に位置する全ての頂点の高さ座標が既定値に等しくない場合、本手続は、７７に進む。７７では、全ての頂点の（同じ）高さ座標に対応する１つの高さ値が、第１データ構造内の項目中に保存される。次に、本方法６０は、６６に続く。
【００９７】
タイル上に位置する全ての頂点の高さ座標が、既定値に等しくない場合、本手続は、７８に進む。７８では、各々のタイルに対する項目は、変更されずに残される。即ち、いかなる高さ座標も、項目中に書き込まれない。次に、本方法６０は、６６に続く。
【００９８】
タイルの隅でのみ頂点があるようなタイル型の使用が、幾つかの実施形態に示されているが、より多くの数のタイル型を使用してもよい。タイル型（単数又は複数）は、各々のタイル上の表面メッシュの頂点に対して様々な形態を定義することができる。
【００９９】
図８は、別の典型的な形態を有するタイル型８０を示す。様々な定義済みのタイル型を使用することができる。例示説明として、図８に示されるように、定義済みのタイル型が、四角形のタイルが２つの三角形に分割されているような形態を有するものであってもよい。その結果得られる三角形の各々は、地形表面の高さの変化に対応する必要がある場合、再び、対称的に２つに分割され得る。定義済みのタイル型は、組み合わせで正方形のタイルを覆う直角二等辺三角形によってのみタイル全体が覆われるような形態の集合から、それぞれ選択されてもよい。
【０１００】
実施形態による方法及び装置が、詳細に記載されたが、他の実施形態では、変更がなされてもよい。例示説明として、１つの定義済みのタイル型の使用が、幾つかの実施形態に関連して示されているが、より多くの数の定義済みのタイル型を使用してもよい。
【０１０１】
更なる例示説明として、表面メッシュの形態のみを記述する定義済みのタイル型が記載されたが、ある高さ情報を含む定義済みのタイル型を使用することもできる。
【０１０２】
本発明の実施形態は、ナビゲーション装置に用いられるデータベースを生成するのに使用され得るが、それに限定されない。そのようなデータベースは、例えば、経路検索又は他の運転者補助用途のために、ナビゲーション装置の光学式出力装置を介して３次元地形を視覚化するように用いられてもよいが、それに限定されない。
【技術分野】
【０００１】
本発明の実施形態は、ナビゲーション装置における高さ情報の利用に関連する方法及び装置に関する。本発明の実施形態は、特に、ナビゲーション装置用のデータベースを生成する方法、ナビゲーション装置、及び、地形の高さ情報を定める方法に関する。本発明の実施形態は、特に、地形の３次元表示を出力するのに利用され得るような方法及び装置に関する。
【背景技術】
【０００２】
地形の高さ情報は、ナビゲーション装置にますます幅広く利用されている。そのような高さ情報が利用され得る典型的な一分野は、３次元地図の出力である。電子地図を出力するのに、光学式出力装置が利用され得る。電子地図は、小型及び／又は携帯式装置のスクリーン上に表示され得るので、多目的に利用可能であり、嵩張らないという利点がある。３次元（３Ｄ）地図、即ち、斜視表示は、認識の質が高いので、利用者にとって特に価値のあるものであり得る。即ち、通りの交差点等の環境領域を認識することは、３次元地図が出力される場合、従来の２次元表示に比べて容易になり得る。
【０００３】
高さ情報が利用され得る別の典型的分野として、ナビゲーション用途又は運転者補助が挙げられる。例示説明として、路線検索に利用される、燃料消費費用等の様々な費用関数は、対象とされる高低差に依存し得る。高さ情報により、確定された道路を渡る際に包含される高低差を知ることができる。高低差の燃料消費又は他の運転者補助機能への影響が、考慮され得る。
【０００４】
そのような高さ情報を利用するためには、ナビゲーション装置内に表面の幾何形状についての情報を保存しなければならない。様々な制約を考慮する必要がある。他方では、記憶空間の要件は、適度に保たれなければならない。他方では、３次元地形を示すデータの形式は、ナビゲーション装置内で容易に利用可能な計算資源及び時間を用いて、斜視図を生成するのを可能にするものあるべきである。この目的のために、表面構造をデジタル立体モデル（ＤＥＭ）データとして保存することができる。ＤＥＭデータは、各々が不規則三角形網（ＴＩＮ）である、三角区画を含んでもよい。これにより、ＤＥＭデータを利用して、地形の表示を実行時に効率的に生成することができる。
【０００５】
高性能な地形の視覚化のための様々な技術は、ＤＥＭデータが継ぎ目なく、拡張領域を包含することを必要とする。即ち、ＤＥＭデータが利用できないような穴又は間隙があってはならない。従来の取り組みでは、この要求のために、いずれの高さ変化もない領域に使用される記憶空間の量が大きくなり得る。これは、特に、表面分割図を使用して実行時間での性能を向上させる場合に当てはまる。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従って、ＤＥＭデータ用の記憶空間の要件を削減するのを可能にする方法及びナビゲーション装置が必要である。特に、データを構成するのに表面分割図を使用して、ＤＥＭデータ用の記憶空間の要件を削減するのを可能にする方法及び装置が必要である。
【課題を解決するための手段】
【０００７】
この要求は、独立請求項中に詳述されるような方法及びナビゲーション装置により対処される。従属請求項は、実施形態を定める。
【０００８】
一態様によれば、ナビゲーション装置用のデータベースを生成する方法が提供される。３次元地形を定めるデータを取得する。取得されたデータに基づいて、複数のタイルを含む表面分割図を利用して第１データ構造を生成する。表面分割図の各々のタイルに対して、それぞれ、第１データ構造内に項目を生成する。あるタイルに対して項目を生成するためには、各々のタイル内に含まれる３次元地形の一部分を、第２データ構造内に含まれる少なくとも１つの定義済みのタイル型と比較する。その比較結果に基づいて、その項目中に３次元地形の一部分を定めるデータ、又は、第２データ構造内に含まれる定義済みのタイル型に対する識別子のうちの１つを項目に保存するために選択する。第１データ構造及び第２データ構造は、データベース内に保存される。
【０００９】
本方法において、各々のタイル内の３次元地形の一部分を定める完全な集合のＤＥＭデータをデータベース内に保存することを必ずしも必要としない。あるタイルの地形を、定義済みのタイル型（単数）又は定義済みのタイル型（複数）と比較して、少なくとも平面方向の位置が互いに対して一致する場合、全ての頂点の座標３組を含む完全な情報を保存するのではなく、各々の定義済みのタイル型へのポインタを保存することで十分であり得る。これにより、頻繁に発生するタイル型に対する記憶空間を節約することができる。例示説明として、地形がいかなる有意の高さ変化も示さないタイルは、平らな地形を定めるタイル型へのポインタにより、表記されてもよい。データを構成するのに表面分割図を尚も利用しながら、従って、関連する性能面の利益を保存しながら、記憶空間の要件が削減され得る。平らな地形又は少数の平坦面を有する地形等の、複数の異なるタイルに見出される定義済みのタイル型を保存する必要があるのは、一度のみである。
【００１０】
項目中に保存される「３次元地形の一部分を定めるデータ」は、それ自体で、３次元表面の完全な記述を与えるデータであり、そのデータと、第２データ構造からの情報を組み合わせる必要はない。
【００１１】
３次元地形を定める表面メッシュの頂点の座標は、３次元地形を定めるデータから取り出されてもよく、３次元地形を定めるデータに基づいて生成されてもよい。各々の頂点は、３次元情報が利用可能であるように、平面座標と高さ座標の一組をそれぞれ有する。表面分割図の各々のタイルに対して、第１データ構造内の項目は、それぞれ、そのタイル上に位置する表面メッシュの全ての頂点の平面座標が、各々の定義済みのタイル型内の頂点の平面座標に対応する場合、その定義済みのタイル型に対する識別子を含むように生成されてもよい。複数の定義済みのタイル型がある場合、１つの定義済みのタイル型に対する識別子は、その識別子に対する表面メッシュの頂点の平面座標が、その定義済みのタイル型の座標に対応するように、保存されてもよい。平面座標は、本明細書で用いられる場合、重力ベクトルに直交する２方向の座標である。頂点の相対平面座標は、本明細書で用いられる場合、タイル上の表面メッシュと定義済みのタイル型の両方に対して、相対位置、即ち、全ての組の頂点の間の距離ベクトルのｘ座標及びｙ座標が同じである場合、定義済みのタイル型内の頂点の平面座標「に対応する」。
【００１２】
したがって、各々のタイルの形態を記述するために、定義済みのタイル型に対する識別子を保存してもよい。表面メッシュの形態（即ち、そのｘｙ面への投影）と定義済みのタイル型を整合させることにより、形態の情報を含む定義済みのタイル型に対する識別子を保存することで、記憶空間を削減することができる。これにより、より多くのタイルに対して、そのような識別子を利用することができる。
【００１３】
表面分割図のタイルに対して、３次元地形の一部分を定めるデータ又は定義済みのタイル型に対する識別子のいずれを保存するべきかの決定は、表面メッシュの形態に基づいて行われてもよい。その形態は、各々のメッシュ内の表面メッシュの頂点の平面座標により定義される。その形態は、表面メッシュのｘｙ面への投影であってもよい。３次元地形の一部分を定めるデータ又は定義済みのタイル型に対する識別子のいずれを保存するべきかの決定は、そのタイル内の表面メッシュの形態が、定義済みのタイル型に整合しているかに基づいて行われてもよい。これにより、同じ形態を有するタイルが、高さ方向で互いにずれている場合でも、表面メッシュについての情報を効率的に嵩張らずに保存することができる。
【００１４】
タイル上に位置する表面メッシュの全ての頂点の平面座標が、定義済みのタイル型（複数可）のうちのどの頂点の平面座標にも対応しない場合、各々のタイル上の３次元地形の一部分を定めるデータが、第１データ構造の項目中に保存されてもよい。このデータは、各々のタイルに対する全てのＤＥＭデータを含むことができる。このデータは、１つ又は複数の不規則三角形網（ＴＩＮ）が含まれてもよい。そのデータには、粗い解像度レベルでのタイルに対する表面メッシュを定める２つのＴＩＮと、細かい解像度レベルでのタイルに対する表面メッシュを定める追加の４つのＴＩＮが含まれてもよい。これにより、正方形のタイルを、２つの三角形（粗い解像度レベル）に又は４つの三角形（細かい解像度レベル）に細分化することができ、ＴＩＮは、それらの三角形の各々に対して定義される。
【００１５】
タイル上に位置する頂点の高さ座標に基づいて、定義済みのタイル型に対する識別子に加えて、そのタイル上に位置する少なくとも１つの頂点の高さ座標が、第１データ構造内に保存されるべきかが判定され得る。これにより、必要な場合にのみ、高さ情報を選択的に保存することができ、記憶空間の要件を更に削減することができる。
【００１６】
タイル上に位置するいずれかの組の頂点の高さ座標が、既定の閾値を超えて互いに異なる場合、タイル上に位置する全ての頂点の高さ座標は、第１データ構造内の項目中に保存され得る。その閾値は、ゼロに設定されてもよい。即ち、全ての頂点の高さ座標は、タイル上の全ての頂点の高さが同じでない限り、そのタイルに対応する第１データ構造の項目中に保存されてもよい。それにより、高さデータが忠実に表示され得る。
【００１７】
タイル上に位置する全ての頂点の高さ座標が、最大既定の閾値だけ互いに異なる場合、第１データ構造内の項目中に保存され得る高さ変位値は、最大限１つである。閾値値は、ゼロに等しいように設定されてもよい。即ち、タイル上に位置する全ての頂点の高さが同じである場合、そのタイルに対して保存され得る高さ変位値は、最大限１つである。それにより、記憶空間の要件が、更に削減され得る。
【００１８】
全ての頂点の高さ座標が既定値の高さと異なる場合は、１つの高さ変位値が、第１データ構造内の項目中に保存され得る。タイル上に位置する全ての頂点の高さ座標が、全て、既定値の高さと等しい場合は、高さ変位値が、第１データ構造内の項目中に保存され得ない。高さの既定値は、ゼロ高さであってもよい。それにより、海面で平らな地形を示すタイルに対して、高さ座標を保存することは全く必要ない。海面から外れた平らな地形を示すタイルを記述するには、１つの高さ変位値を適切なタイル型に対する識別子と組み合わせることで十分である。
【００１９】
第１データ構造内の項目は、それぞれ、各々のタイルに固有のタイル識別子を含むように生成されてもよい。固有のタイル識別子は、タイル識別子を利用して、その中心又は隅等のそのタイルの特徴点の座標を定め得るようなものであってもよい。
【００２０】
タイル上に位置する全ての頂点が、そのタイルの境界に、特に、隅に位置する場合、第１データ構造内に保存するために、定義済みのタイル型に対する識別子を選択してもよい。それにより、定義済みのタイル型に対する識別子を利用して、少なくとも、平らな地形を示すタイルが示され得る。
【００２１】
第２データ構造内に含まれる各々の定義済みのタイル型は、あるタイル型を指し示すことができない場合に第１データ構造内のタイルを記述するのに利用されるデータ形式に対応するように定義された、データ形式を有してもよい。例示説明として、各々の定義済みのタイル型は、それぞれ、複数の頂点の平面座標と、各々が隅として３つの頂点をそれぞれ有する、三角面を記述する指標の配列とを含んでもよい。それらの面を記述する指標の配列は、頂点配列内の項目へのポインタを含んでもよい。
【００２２】
第２データ構造内の定義済みのタイル型は、利用者により定義されてもよい。例示説明として、タイルの隅にのみ頂点があるような定義済みのタイル型が、１つのみ事前に定義されてもよい。代わりに、複数の異なるタイルに対する表面メッシュを分析することにより、１つ又は幾つかの定義済みのタイル型が自動的に生成されてもよい。頂点の所定の形態が、既定の回数を超えて発生する場合、対応するタイル型が、自動的に定義され、第２データ構造内に保存されてもよい。
【００２３】
別の態様によれば、３次元地形を示すデータベースが提供される。そのデータベースは、各々が表面分割図のタイルに固有のタイル識別子を含む、複数の項目を有する第１データ構造と、少なくとも１つの定義済みのタイル型を定義する第２データ構造とを含む。第１データ構造内の各々の項目は、第２データ構造内の定義済みのタイル型へのポインタ、又は、各々のタイル内の地形を直接記述するデータのうちの１つを含む。地形を直接記述するデータには、複数の頂点に対する３組の頂点座標の配列が含まれてもよい。地形を直接記述するデータには、各々のタイルに対して複数の三角面を定義する頂点指標の配列が更に含まれてもよい。
【００２４】
データベースの第１データ構造内の各々の項目は、それぞれ、１つのタイルに関連してもよい。
【００２５】
定義済みのタイル型へのポインタを含み得る第１データ構造内の各々の項目は、選択的に、高さ座標を含まないか、１つの高さ座標を含むか、又は、１を超える高さ座標を含むことができる。第１データ構造内の各々の項目は、各々のタイル上の表面メッシュの頂点のいずれの平面座標も含まないようなものであり得る。
【００２６】
別の態様によれば、ナビゲーション装置が提供される。ナビゲーション装置は、３次元地形を表し、第１データ構造と第２データ構造と含むデータベースを含む。第１データ構造は、各々が表面分割図のタイルに固有のタイル識別子を含む、複数の項目を有する。第２データ構造は、少なくとも１つの定義済みのタイル型を定義する。ナビゲーション装置は、データベースに結合された処理装置を有する。その処理装置は、タイルに固有の識別子を利用して、第１データ構造の項目にアクセスし、アクセスされた項目が、第２データ構造内に保存された定義済みのタイル型に対する型識別子を含んでいるかを判定するように設定されている。処理装置は、次に、項目が型識別子を含む場合、定義済みのタイル型についての情報を第２データ構造から選択的に取り出すように設定されている。処理装置は、第１データ構造のアクセスされた項目に基づいて、項目が型識別子を含む場合は、第２データ構造内に含まれる定義済みのタイル型に基づいて、１つ又は複数の場所の高さ座標を定めるように設定されている。
【００２７】
このナビゲーション装置では、第１データ構造内のタイルの項目に、タイル型へのポインタ又は各々のタイル上のＤＥＭを直接記述するデータのうちの１つが選択的に含まれてもよい。各々のタイルに対して、完全なＤＥＭデータを保存する必要はない。例示説明として、表面メッシュのいずれも頂点も内部に含まないタイルは、それぞれ、第１データ構造内の項目が、第２データ構造へのポインタを含み得る。それにより、記憶空間の要件が削減され得る。
【００２８】
ナビゲーション装置は、光学式出力装置を含んでもよい。処理装置は、光学式出力装置を制御し、所与のタイル上に位置するＤＥＭの一部分を表示するように設定され得る。処理装置は、各々のタイルに対する第１データ構造内の項目中に含まれるデータと、第１データ構造内の項目が、定義済みのタイル型に対する識別子を含む場合、この項目が指し示すタイル型の定義との両方を利用して、光学式出力装置を制御し得る。処理装置は、項目が、定義済みのタイル型に対する識別子を含まない場合、第１データ構造内の項目中に含まれるデータのみを利用して、光学式出力装置を制御し得る。
【００２９】
定義済みのタイル型へのポインタを含む第１データ構造内の各々の項目は、選択的に、高さ座標を含まないか、１つの高さ座標を含むか、又は、１を超える高さ座標を含むことができる。
【００３０】
処理装置は、項目が型識別子を含む場合、取り出された、定義済みのタイル型についての情報に基づいて、表面メッシュの複数の頂点に対して一対の平面座標をそれぞれ定め、第１データ構造の項目に基づいて、頂点の高さ座標を定めるように設定され得る。それにより、定義済みのタイル型が点の形態を定めるのに使用され得るのに対し、高さ情報は、第１データ構造内の対応する項目から取り出され得る。これにより、多目的利用の可能性が向上する。
【００３１】
第１データ構造の項目が、型識別子と高々１つの高さ座標とを含む場合、処理装置は、表面メッシュの頂点の高さ座標を同じ値に定めるように設定され得る。従って、平らなタイルでは、第１データ構造内の項目中に保存する必要のある高さ座標は、最大限１つである。
【００３２】
処理装置は、第１データ構造の項目が型識別子と複数の高さ座標とを含む場合、頂点に対して異なる高さ座標を定めるように設定され得る。
【００３３】
定義済みのタイル型に対する識別子を含まないデータベースの項目は、それぞれ、表面メッシュの頂点の座標３組についての情報を含んでもよい。そのような項目は、表面メッシュの三角面を定義する頂点指標の配列を更に含んでもよい。
【００３４】
データベースは、いずれか１つの態様又は実施形態のデータベースを生成する方法を利用して生成される、データベースであってもよい。
【００３５】
別の態様によれば、ナビゲーション装置内で高さ情報を定める方法が提供される。そのナビゲーション装置は、各々が表面分割図のタイルに固有のタイル識別子を含む、複数の項目を有する第１データ構造と、少なくとも１つの定義済みタイル型を定義する第２データ構造とを含む、データベースを有する。１つ以上の場所に対する高さ情報を定めるためには、タイルに固有の識別子を使用して、第１データ構造の項目にアクセスする。項目が、第２データ構造内に保存された定義済みのタイル型に対する型識別子を含んでいるかを判定する。項目が型識別子を含む場合、定義済みのタイル型についての情報は、第２データ構造から取得される。１つ又は複数の場所の高さ座標は、第１データ構造のアクセスされた項目に基づいて定められてもよく、項目が型識別子を含む場合は、第２データ構造内に含まれる定義済みのタイル型に基づいて定められてもよい。
【００３６】
本方法では、第２データ構造内の定義済みのタイル型は、第１データ構造内のタイルの項目により参照され得る。定義済みのタイル型に対する識別子を含む各々のタイルでは、全てのＤＥＭデータを個別に保存する必要はない。例示説明として、表面メッシュのいずれの頂点も内部に含まないタイルは、それぞれ、第１データ構造内に、第２データ構造へのポインタを含む項目を有し得る。それにより、記憶空間の要件が削減され得る。
【００３７】
第２データ構造内の定義済みのタイル型は、表面メッシュの頂点の形態を定め得る。即ち、定義済みのタイル型には、各々のタイル上の頂点の相対平面座標についての情報が含まれ得る。必要であれば、第１データ構造内の各々の項目中に、頂点の高さ座標についての情報が個別に保存されてもよい。例示説明として、タイルの地形が平らであるが、既定値の高さ（海面等）から外れている場合は、各々のタイルに対して、第１データ構造内の各々の項目中に１つの高さ座標を保存してもよい。タイルが、その内部にいずれの頂点も含まないが、その隅での頂点の高さが異なる場合は、第１データ構造内の各々の項目中に４つの座標を保存してもよい。
【００３８】
１つ以上の場所の定められた高さ座標は、３次元地形の視覚化、経路を渡る際に発生する費用の算出、経路検索等のような、様々な目的に利用され得る。
【００３９】
上述の特徴と以下に説明される特徴は、指示された各々の組み合わせについてばかりでなく、他の組み合わせでも又は単独でも利用することができると理解されるべきである。
【００４０】
実施形態の上述の及び他の特徴は、実施形態の以下の詳細な記述から、付属の図面と関連して読む際に更に明らかになる。図面では、同様の参照番号は、同様の要素を指す。
例えば本発明は以下の項目を提供する。
（項目１）
ナビゲーション装置（１）用のデータベースを生成する方法（１０）であって、上記方法が、
３次元地形を定めるデータを取り出すことと、
取り出されたデータに基づいて、複数のタイル（２３〜２６；３１〜３４）を含む表面分割図（２０）を使用して第１データ構造（１１）を生成することとであって、上記表面分割図（２０）の各々のタイル（２３〜２６；３１〜３４）に対して、項目（１３〜１８）が、上記第１データ構造（１１）内にそれぞれ生成され、上記項目をそれぞれ生成することは、
上記タイル（２３〜２６；３１〜３４）内に含まれる上記３次元地形の一部分を、第２データ構造（１２）内に含まれる少なくとも１つの定義済みのタイル型と比較することと、
上記比較の結果に基づいて、上記項目中に保存するために、上記３次元地形の一部分を定めるデータ、又は、上記第２データ構造（１２）内に含まれる定義済みのタイル型に対する識別子（１９）のうちの１つを選択することと
を含み、
上記第１データ構造（１１）と上記第２データ構造（１２）とを上記データベース（１０）内に保存することと
を含む、方法。
（項目２）
上記３次元地形を定める表面メッシュの頂点（４１〜５０）の座標が、上記３次元地形を定める上記データから取り出されるか、又は、３次元地形を定めるデータに基づいて生成され、上記頂点（４１〜５０）の各々が、平面座標と高さ座標の一組をそれぞれ有し、
上記表面分割図（２０）の各々のタイル（２３〜２６；３１〜３４）に対して、上記タイル（２３〜２６；３１〜３４）上に位置する全ての頂点（４１〜５０）の相対平面座標が、定義済みのタイル型内の頂点（５５〜５８）の平面座標に対応する場合、上記項目（１４、１６、１７）が、上記第２データ構造（１２）内に含まれる、上記定義済みのタイル型に対する識別子（１９）をそれぞれ含むように生成される、
上記項目に記載の方法。
（項目３）
上記方法が、
上記タイル（２３〜２６；３１〜３４）上に位置する上記頂点（４１〜５０）の高さ座標に基づいて、上記定義済みのタイル型に対する上記識別子（１９）に加えて、上記タイル（２３〜２６；３１〜３４）上に位置する少なくとも１つの頂点（４１〜５０）の高さ座標が、上記第１データ構造（１１）内に保存されるべきかを判定すること
を更に含む、上記項目のいずれかに記載の方法。
（項目４）
上記タイル（３１）上に位置するいずれかの組の頂点（４１、４６、４７、５０）の高さ座標が、既定の閾値を超えて互いに異なる場合、上記タイル（３３）上に位置する全ての頂点（４１、４６、４７、５０）の高さ座標が、上記第１データ構造（１１）の項目（１７）中に保存される、上記項目のいずれかに記載の方法。
（項目５）
上記タイル（３１、３２、３４）上に位置する全ての頂点（４１〜５０）の高さ座標が、最大限既定の閾値だけ互いに異なる場合、上記タイル（３１、３２、３４）上に位置する全ての頂点（４１〜５０）に対して、最大限１つの高さ変位値が、上記第１データ構造（１１）の上記項目（１４、１６）中に保存される、上記項目のいずれかに記載の方法。
（項目６）
全ての頂点（４７〜５０）の上記高さ座標が、既定値の高さと異なる場合、１つの高さ変位値が、上記第１データ構造（１１）内の上記項目（１６）中に保存され、
全ての頂点（４１〜４６）の上記高さ座標が、上記既定値の高さと等しい場合、高さ変位値が、上記第１データ構造（１１）内の上記項目（１４）中に保存されない、
上記項目のいずれかに記載の方法。
（項目７）
上記３次元地形の一部分を定める上記データ、又は、上記識別子（１９）のうちの上記１つが、上記タイル（２３〜２６；３１〜３４）上に位置する全ての頂点（４１〜５０）の高さ座標とは独立して選択される、上記項目のいずれかに記載の方法。
（項目８）
上記タイル（２３〜２６；３１〜３４）上に位置する全ての頂点（４１〜５０）が、上記タイル（２３〜２６；３１〜３４）の境界に、特に、隅に位置する場合、上記第１データ構造（１１）内に保存するために、定義済みのタイル型に対する上記識別子（１９）を選択する、上記項目のいずれかに記載の方法。
（項目９）
上記第２データ構造（１２）内に含まれる各々の定義済みのタイル型が、複数の頂点（４１〜５０）の平面座標と、隅として３つの上記頂点（４１〜５０）をそれぞれ有する三角面を記述する指標の配列とを含む、上記項目のいずれかに記載の方法。
（項目１０）
３次元地形を表し、各々が表面分割図（２０）のタイル（２３〜２６；３１〜３４）に固有のタイル識別子を含む、複数の項目（１３〜１８）を有する、第１データ構造（１１）と、少なくとも１つの定義済みのタイル型を定義する第２データ構造（１２）とを含むデータベース（１０）と、
タイル（２３〜２６；３１〜３４）に上記固有のタイル識別子を使用して、上記第１データ構造（１１）の項目にアクセスし、
上記アクセスされた項目が、上記第２データ構造（１２）内に保存された定義済みのタイル型に対する型識別子（１９）を含んでいるかを判定し、
上記項目が上記型識別子（１９）を含む場合、上記定義済みのタイル型についての情報を上記第２データ構造（１２）から選択的に取り出し、
上記第１データ構造（１１）の上記アクセスされた項目（１３〜１８）に基づいて、上記項目（１３〜１８）が上記型識別子（１９）を含む場合は、上記第２データ構造（１２）内に含まれる上記定義済みのタイル型に基づいて、１つ又は複数の場所の高さ座標を定めるように
設定されている、上記データベース（１０）に結合された処理装置（２）と
を含む、ナビゲーション装置（１）。
（項目１１）
上記項目（１４、１６、１７）が型識別子（１９）を含む場合に、上記処理装置（２）が、上記取り出された上記定義済みのタイル型についての情報に基づいて、表面メッシュの頂点（４１〜５０）の一組の平面座標をそれぞれ定め、上記第１データ構造（１１）の上記項目（１４、１６、１７）に基づいて、上記頂点（４１〜５０）の高さ座標をそれぞれ定めるように設定されている、上記項目のいずれかに記載のナビゲーション装置（１）。
（項目１２）
上記第１データ構造（１１）の上記項目（１４、１６）が、上記型識別子（１９）と高々１つの高さ座標とを含む場合、上記頂点（４１〜４６、４７〜５０）の高さ座標を同じ値に定めるように上記処理装置（２）が設定されている、上記項目のいずれかに記載のナビゲーション装置（１）。
（項目１３）
上記第１データ構造（１１）の上記項目（１７）が、上記型識別子（１９）と複数の高さ座標とを含む場合に、上記頂点（４１〜５０）に対して異なる高さの座標を定めるように上記処理装置（２）が設定されている、上記項目のいずれかに記載のナビゲーション装置（１）。
（項目１４）
定義済みのタイル型に対する識別子（１９）を含まない上記データベース（１０）の項目（１３、１５、１８）が、表面メッシュの頂点（４１〜５０）の座標３組についての情報を含む、上記項目のいずれかに記載のナビゲーション装置（１）。
（項目１５）
ナビゲーション装置（１）内で高さ情報を定める方法であって、上記ナビゲーション装置（１）が、各々が表面分割図（２０）のタイル（２３〜２６；３１〜３４）に固有のタイル識別子を含む、複数の項目（１３〜１８）を有する第１データ構造（１１）と、少なくとも１つの定義済みタイル型を定義する第２データ構造（１２）とを含む、データベース（１０）を有し、上記方法が、
タイル（２３〜２６；３１〜３４）に固有の識別子を使用して、上記第１データ構造（１１）の項目（１３〜１８）にアクセスすることと、
上記項目（１４、１６、１７）が、上記第２データ構造（１２）内に保存された定義済みのタイル型に対する型識別子（１９）を含んでいるかを判定することと、
上記判定の結果に基づいて、上記項目（１４、１６、１７）が上記型識別子（１９）を含む場合、上記第２データ構造（１２）から、上記定義済みのタイル型についての情報を取得することと、
上記第１データ構造（１１）のアクセスされた項目（１３〜１８）に基づいて、および上記項目（１４、１６、１７）が上記型識別子（１９）を含む場合は、上記第２データ構造（１２）内に含まれる上記定義済みのタイル型に基づいて、１つ又は複数の場所の高さ座標を定めることと
を含む、方法。
【００４１】
摘要
ナビゲーション装置内で使用されるデータベース（１０）を生成する方法では、表面分割図の１つのタイルにそれぞれ関連する、第１データ構造（１１）内の項目（１３〜１８）が生成される。少なくとも１つの定義済みのタイル型と各々のタイル上の３次元地形の比較に基づいて、定義済みのタイル型に対する識別子（１９）、又は、各々のタイル上の地形を記述するデータのどちらかが、その項目中に保存される。データベース（１０）を使用して高さ座標を定める方法と、データベース（１０）を含むナビゲーション装置も提供される。
【図面の簡単な説明】
【００４２】
【図１】ナビゲーション装置の概略的ブロック図である。
【図２】データベースの概略的表示である。
【図３】表示分割法が重ねられた地形の平面図である。
【図４】データベースを用いた３次元地形の再構築を示している斜視図である。
【図５】タイルの頂点を示す平面図である。
【図６】データベースを生成する方法の流れ図である。
【図７】図６の方法に用いられ得るデータベース内に項目を生成する手続を示す。
【図８】タイル型の別の典型的形態を示す平面図である。
【発明を実施するための形態】
【００４３】
図１は、実施形態によるナビゲーション装置１を概略的に示す。ナビゲーション装置１は、ナビゲーション装置１の操作を制御する処理装置２を含む。処理装置２は、例えば、１つ以上のマイクロプロセッサ、デジタル信号プロセッサ又は用途特定集積回路の形態の中心処理ユニットを含んでもよい。処理装置２は、グラフィックプロセッサを含み得る。ナビゲーション装置１は、記憶装置３内に保存されるデータベース１０を更に含む。記憶装置３は、ランダムアクセスメモリ、フラッシュメモリ又はハードドライブ、さらに、コンパクトディスク（ＣＤ）、ＤＶＤ、メモリカード等の脱着可能なメモリのような、様々な種類のメモリのいずれか１つ又はいずれかの組み合わせを含んでもよい。ナビゲーション装置１は、光学式出力装置４も含む。ナビゲーション装置１は、位置センサ及び／又は無線受信機及び／又は入力インターフェース５等の追加の部品を含んでもよい。
【００４４】
記憶装置３は、３次元地形を定めるデータベース１０を保存する。３次元マップを生成し、即ち、地形を視覚化し、燃料消費又は道路に関連する他の費用等を確定するために、処理装置２によりデータベース１０内のデータを使用することができる。
【００４５】
以下に詳細に説明されるように、データベース１０内のデータは、表面分割図に従って構成される。データベース１０は、第１データ構造と第２データ構造とを含む。第１データ構造は、各々が表面分割図の１つのタイルに関連している、複数の項目を有する。第１データ構造内の各々の項目は、固有のタイル識別子を有する。加えて、第１データ構造内の各々の項目は、各々のタイル内のデジタル立体モデル（ＤＥＭ）を直接定義するデータ、又は、定義済みのタイル型に対する識別子のどちらかを含む。定義済みのタイル型に対するそのような識別子が含まれる場合、第１データ構造の項目中の情報は、第２データ構造内の情報と組み合わせられない限り、単独では、タイルに対して表面を再構築することができない。第２データ構造は、第１データ構造内の項目により参照される定義済みタイル型についての情報を含む。
【００４６】
第１データ構造内の項目が、各々のタイル内にＤＥＭを直接記述するデータを含む場合、項目は、頂点の座標３組の配列を含んでもよい。その項目は、不規則三角形網（ＴＩＮ）の三角面を定義する、頂点の指標の別の配列を更に含んでもよい。１つのタイルに対して、１を超えるＴＩＮが定義されてもよい。例示説明として、２つのＴＩＮを使用して、粗い解像度でタイル内の地形を定めてもよく、４つのＴＩＮを使用して、細かい解像度でタイル内の地形を定めてもよい。定義済みのタイル型を参照することにより、タイル内に表面メッシュの形態を定めることができない場合、このデータの全てを第１データ構造内に含んでもよい。
【００４７】
第１データ構造内の項目は、定義済みのタイル型に対する識別子を含む場合、各々のタイル内の表面メッシュの形態についてのいずれの情報も含んでいない。即ち、タイルの１つの特徴点（中心又は所与の隅等）の平面位置は、固有のタイル識別子から導かれ得る。次に、表面メッシュの頂点の平面位置は、項目中で参照される定義済みのタイル型を使用して導かれ得る。
【００４８】
第１データ構造内の項目は、定義済みのタイル型に対する識別子を含む場合、それにも関わらず、１つ以上の高さ座標を含んでもよい。タイル上に位置する全ての頂点の座標３組を定めるために、第１項目中に含まれる高さ座標（複数可）を、第１データ構造内の項目により参照される定義済みのタイル型により定義される表面メッシュの形態と組み合わせることができる。
【００４９】
定義済みのタイル型の数と種類は、考慮される用途に適切であるように選択され得る。幾つかの実装では、その隅に表面メッシュの頂点があるが、その内部に頂点のないタイルを示す、１つの定義済みのタイル型のみが使用される。そのような定義済みのタイル型は、平らな地形上の表面メッシュの形態を記述する。そのような定義済みのタイル型は、粗い解像度レベルで、多くのタイルに対する表面メッシュの形態も記述する。例示説明として、多くのナビゲーション装置用データベースは、１０又はそれ以上の解像度レベル等の、数多くの解像度レベルを使用する。少なくとも最も粗いレベルでは、解像度は、地形が、タイルの隅にのみ位置する頂点により適切に定義され得るようなものである。
【００５０】
以下に、１つの定義済みのタイル型を使用した実装を示すが、より多くの数の定義済みのタイル型を、他の実装に使用してもよい。
【００５１】
図２は、データベース１０の概略図である。データベース１０は、ナビゲーション装置１に使用され得る。データベース１０は、３次元地形を示す。複数の異なる解像度レベルを与えることが望まれる場合、以下に説明されるデータ構造は、各々の解像度レベルに対して与えられ得る。代わりに、複数の異なる解像度レベルに、独立した第１データ構造１１が与えられ得るのに対し、複数の異なる解像度レベルに、１つの第２データ構造１２が使用され得る。
【００５２】
データベース１０は、第１データ構造１１と第２データ構造１２とを有する。第１データ構造１１では、複数の項目１３〜１８が保存される。項目１３〜１８の各々は、それぞれ、表面分割図の１つのタイルと関連している。第２データ構造１２は、タイル型を定義するデータを含む。第２データ構造１２内のデータは、第１データ構造の項目中のＤＥＭデータに使用される形式に対応するデータ形式を有し得るが、高さ情報が省かれている。
【００５３】
各々の項目１３〜１８は、固有のタイル識別子を含む。タイルＩＤ１、タイルＩＤ２等で示される固有のタイル識別子は、タイルの１つの特徴点（例えば、中心又は隅）のｘ座標及びｙ座標を定めるのを可能にするようなものである。
【００５４】
第１データ構造内の副次集合１３、１５及び１８は、それぞれ、各々のタイル上のＤＥＭの一部分を直接定義するデータを含む。様々なデータ形式が使用されてもよい。実装では、項目１３、１５及び１８内のＤＥＭデータは、それぞれ、１つ又は複数のＴＩＮを定義してもよい。各々のＴＩＮに対して、ＤＥＭデータは、頂点座標の３組の配列と、頂点配列のどの頂点が、それぞれ、表面メッシュの三角面を形成するかを定める頂点指標の配列とを含んでもよい。ＤＥＭデータは、三角面に対する法線ベクトルの配列等の追加の情報を含んでもよい。
【００５５】
項目１３、１５又は１８により示されるタイルのうちの１つに、１つ以上の場所の高さを定めるために、各々の項目１３、１５又は１８にアクセスする。１つ以上の場所の高さは、第２データ構造１２とは独立して、ＤＥＭデータから定められてもよい。
【００５６】
第１データ構造内の項目１４、１６及び１７の別の副次集合は、それぞれ、第２データ構造１２内に保存された定義済みのタイル型に対する、「型１」で示される識別子１９を含む。これらの項目１４、１６及び１７は、ＤＥＭの様々な頂点の頂点座標の３組を含んでいない。項目１４、１６及び１７は、各々のタイル内の表面メッシュの形態についての情報を含んでいない。即ち、項目１４、１６及び１７内に、互いに対する表面メッシュの頂点のｘ座標及びｙ座標を保存する必要はない。
【００５７】
項目１４等の、定義済みのタイル型に対する識別子１９を含む幾つかの項目は、いずれの高さ座標も含み得ない。これは、各々の定義済みのタイル型により定められる表面メッシュの全ての頂点が、既定値の高さに位置することを示す。既定値の高さは、海面であってもよい。
【００５８】
項目１６等の、定義済みのタイル型に対する識別子１９を含む幾つかの項目は、１つの高さ情報のみを含み得る。これは、各々の定義済みのタイル型により定められる表面メッシュの全ての頂点が、既定値の高さから外れた同じ高さに位置することを示す。それにより、１つの単一の高さ変位値のみを使用して、既定値の高さから外れた平らな地形が示され得る。
【００５９】
項目１７等の、定義済みのタイル型に対する識別子１９を含む幾つかの項目は、１以上の高さ座標を含んでもよい。各々の定義済みタイル型の各々の頂点に対する１つの高さ座標は、関連する項目１７内に保存されてもよい。そのようなデータ構造は、各々の定義済みタイル型により定められる表面メッシュの頂点が、全て、各々のタイル上の同じ高さに位置しない場合に使用されてもよい。それにより、頂点の形態（即ち、相対的なｘ位置及びｙ位置）が、定義済みのタイル型のうちの１つに整合するとの条件で、平坦ではない地形が示され得る。
【００６０】
第２データ構造１２は、定義済みのタイル型についての情報を含む。この情報は、一般に、第１データ構造内の項目１３、１５及び１８に対してＤＥＭデータが保存される形式と同じであり得る。しかしながら、定義済みのタイル型が、表面メッシュの形態についての情報のみを含む場合、高さ情報は、第２データ構造１２にはなくてもよい。例示説明として、第２データ構造１２は、各々の定義済みのタイル型に対する頂点の平面座標の２組を定める配列を含んでもよい。頂点の平面座標は、タイルの中心又はその隅のうちの１つ等のタイルの定義済みの場所に対して計測される。第２データ構造１２は、どの頂点が、ＴＩＮの三角面を形成するのかを定める頂点指標の配列を更に含み得る。タイル型が、タイルの隅にのみ頂点があるような型に対応する場合、頂点指標の指標配列は、組み合わせでタイル全体を包含する、２つの三角面を定義し得る。
【００６１】
項目１４、１６又は１７により示されるタイルのうちの１つに、１つ以上の場所の高さを定めるために、各々の項目１４、１６又は１７にアクセスする。タイル型を定義する対応するデータは、定義済みのタイル型に対する識別子１９を使用して、第２データ構造１２から取得される。固有のタイル識別子を使用して、タイルの特徴点のｘ及びｙの絶対位置を定めることができる。第２データ構造内に含まれる、参照されたタイル型に対する頂点の相対平面位置についての情報を使用して、各々のタイル上の表面メッシュの全ての頂点のｘ座標及びｙ座標を定めることができる。第１データ構造内のその対応する項目が、１つ以上の高さ座標を有するか否かに基づいて、頂点の高さ座標を定めることができる。例示説明として、第１データ構造内の項目に高さ座標がない場合は、全ての頂点に対するｚ値を、既定値の高さ（例えば、海面）に設定する。第１データ構造内の項目に１つの高さ座標がある場合は、全ての頂点に対するｚ値をその値に設定する。第１データ構造内の項目に１つの高さ座標がある場合は、様々な頂点に対するｚ値を、各々の項目１７内に含まれる様々な値に設定する。第１データ構造１１内の項目１７の中の高さ値の序列は、この場合、第２データ構造１２内の頂点配列内に頂点が列挙されるような序列に対応し得る。
【００６２】
第１データ構造１１内の項目のＤＥＭデータを使用して、又は、第１データ構造１１内の項目を、第２データ構造１２と組み合わせて使用してそのように定められた高さ情報を、様々な目的に使用することができる。例示説明として、地形を３次元で視覚化することができる。異なる経路に関連する燃料消費等の費用を、高低差を考慮して算出することができる。
【００６３】
図３は、地形の平面図である。その地形の上に、表面分割図２０が重ねられている。地形は、湖又は海２１等の、平らな領域を含む。地形は、河川２２等の平らな追加の領域を含み得る。
【００６４】
ＤＥＭデータを保存する従来の取り組みでは、各々のタイルに対する表面メッシュが、保存されることになる。これは、タイルが、平らであり、海２１又は河川２２により完全に覆われる場合でも、タイルの隅の頂点に対して座標３組を保存する必要があることになる。
【００６５】
定義済みのタイル型を使用することにより、記憶空間が削減され得る。タイルの内部に頂点がないような定義済みのタイル型を使用して、そのタイル型を参照することにより、タイルの内部で平らである地形の形態を定めることができる。
【００６６】
図３に示される地形では、タイル２３〜２５に対して第１データ構造内に生成されるデータ項目は、隅にのみ頂点があるような定義済みのタイル型に対する識別子を含み得る。タイル２３〜２５は、海面に位置しているので、第１データ構造の各々の項目中に、いずれの高さ座標も保存する必要はない。
【００６７】
同様に、タイル２６に対する第１データ構造内で生成されるデータ項目は、隅にのみ頂点があるような定義済みのタイル型に対する識別子を含むことができる。タイル２６が海面よりも上に又は下に位置する場合、第１データ構造の各々の項目中に、１つの単一の高さ座標を保存することができる。
【００６８】
データベースを生成する場合と、そのデータベースから地形を再構築する場合の両方で、１つ以上の定義済みのタイル型を用いる技術を使用してもよい。
【００６９】
図４は、データベースが、図１及び図２を参照して記載されたように設定される場合の、データベースからの地形の再構築を示している概略斜視図である。
【００７０】
図示されるのは、複数のタイル３１〜３４に対する表面メッシュである。データベースの第１データ構造内の各々のタイル３１〜３４に対する項目は、タイルの隅のみ頂点があるようなタイル型へのポインタを含み得る。
【００７１】
タイル３１上に位置する頂点４１〜４４のｘ及びｙの絶対座標は、固有のタイル識別子から導かれ得る、中心等のタイル３１の特徴点の位置と、第２データ構造内に保存されている頂点の相対位置を組み合わせることにより定められ得る。頂点４１〜４４のｚ座標は、再び、第１データ構造内のタイル３１に対する項目に基づいて定められ得る。その項目にいずれのｚ座標もない場合、全ての頂点４１〜４４の高さは、既定値の高さに設定される。既定値の高さは、海面であり得る。
【００７２】
同様に、第１データ構造内のタイル３２に対する項目は、いずれのｚ座標値も含み得ない。それに応じて、タイル３２の隅での頂点４３〜４６の高さは、既定値の高さに、例えば、海面に設定される。
【００７３】
第１データ構造内のタイル３３に対する項目は、４つのｚ座標を含んでもよい。タイル３３上に位置する頂点４１、４２、４７及び５０のｘ座標及びｙ座標は、固有のタイル識別子から導かれ得る中心等のタイル３３の特徴点の位置を、各々のタイル型に対する第２データ構造内に保存された頂点の相対位置と組み合わせることにより定められてもよい。頂点４１、４２、４７及び５０のｚ座標は、タイル３３に対する第１データ構造内の項目中に与えられた値に設定される。それにより、地面に平行ではないが、タイルの内部にいずれの頂点もないような表面メッシュの一部分も示され得る。
【００７４】
第１データ構造内のタイル３４に対する項目は、１つのｚ座標値のみを含み得る。それに応じて、タイル３４の隅での全ての頂点４７〜５０の高さは、タイル３４に対する第１データ構造内の項目中に保存されたｚ座標値に設定される。
【００７５】
頂点の相互配置の形態が定義済みのタイル型に対応するタイルでは、定義済みのタイル型により定義される形態を、もしあれば、第１データ構造の項目中に保存された高さ座標と組み合わせることにより、各々のタイル上の表面メッシュが、そのように再構築され得る。
【００７６】
逆に、図４に示されるように、１つのＴＩＮ又は幾つかのＴＩＮの形態の表面メッシュから始めて、第１データ構造内の項目を生成することができる。各々のタイル上の表面メッシュの頂点の形態は、それぞれ、定義済みのタイル型（単数又は複数）と比較され得る。
【００７７】
第２データ構造内の定義済みのタイル型を定義は、面５１及び５２等の三角面を定義する指標配列を含んでもよい。第２データ構造からのデータを使用して、ＤＥＭデータが第１データ構造内に直接保存されている、タイルに対して使用可能なデータに対応する様々なタイル上における表面メッシュの表現を得ることができる。
【００７８】
図５は、中心５４と隅に頂点５５〜５８とを有するタイルを平面図で示す。
【００７９】
第１データ構造１１は、中心５４又はタイルの別の特徴点の位置が、固有のタイル識別子から導かれ得るようなものであり得る。第２データ構造は、特徴点に対して計測された、頂点５５〜５８の平面座標を含んでいる。従って、頂点の絶対平面（ｘ及びｙ）座標は、上述のように定められ得る。
【００８０】
図６は、データベースを生成する方法６０の流れ図である。方法６０は、コンピュータ等の電子処理装置により実行される。方法６０は、データベースがナビゲーション装置に配備される前に実行され得る。
【００８１】
６１では、３次元地形を定めるデータが取得される。データは、表面メッシュを含んでもよい。データは、１つ又は複数のＴＩＮ（複数可）を定義してもよい。ＴＩＮ（複数可）は、表面分割図上で定められてもよい。他の実装では、データは、例えば、まだ表面メッシュの形態ではない、衛星画像中の高さ値であってもよい。この場合、１つ又は複数のＴＩＮが、３次元地形を示すように定められてもよい。対応する表面分割図も定めてもよい。
【００８２】
６２では、表面分割図のタイルが選択される。方法６０は、表面分割図の複数のタイルを通じて、繰り返されてもよい。この場合、６２で選択されたタイルは、第１繰り返しでの、表面分割図の隅でのタイルであってもよい。
【００８３】
６３では、各々のタイル上のＴＩＮ（複数可）の表面メッシュは、１つ又は複数の定義済みのタイル型と比較される。各々のタイル上のＴＩＮ（複数可）は、複数の頂点を含む。この比較ステップでは、各々のタイル上のＴＩＮ（複数可）の頂点の相対平面座標が定められ得る。続いて、各々のタイル上の表面メッシュの形態を定める頂点の相対平面座標が、１つ又は複数の定義済みのタイル型と比較され得る。各々のタイル上のＴＩＮ（複数可）の頂点の形態が、定義済みのタイル型（複数可）のうちの１つに整合するかを判定する。
【００８４】
例示説明として、タイルの隅でのみ頂点があるような１つの定義済みの型のみを使用する場合、タイル上のＴＩＮ（複数可）の頂点形態は、タイルの内部に頂点がなく、タイルの隅に全ての頂点が位置する場合にのみ、定義済みのタイル型に整合する。
【００８５】
タイル内の頂点形態が、定義済みのタイル型に整合しない場合、本方法は、６４へ進む。６４では、タイル上のＴＩＮ（複数可）の一部分を記述するＤＥＭデータが、データベースの第１データ構造内の項目中に保存される。ＤＥＭデータは、全ての頂点に対する頂点座標の座標３組を有する頂点配列と、頂点のうちのどれが、それぞれ、様々な三角面を形成するのかを記述する指標配列とを含むことができる。第１データ構造内の項目は、各々のタイルに対する固有の識別子を更に含む。
【００８６】
タイル内の頂点形態が、定義済みのタイル型に整合する場合、本方法は、６５へ進む。６５では、各々のタイルに対する項目が、第１データ構造内に生成される。項目は、各々のタイル上のＴＩＮ（複数可）の頂点形態に整合するタイル型を指し示す識別子を含む。その項目は、様々な頂点に対する平面座標を含んでいない。第１データ構造内の項目は、各々のタイルに固有の識別子を更に含む。タイル上の頂点の高さ座標に依存して、全ての頂点が既定値の高さに位置する場合、項目は、高さ座標を含まないように生成され得る。全ての頂点が、既定値の高さとは異なる同じ高さに位置する場合、項目は、１つの高さ座標を含むように生成され得る。頂点の全てが、同じ高さには位置していない場合、項目は、各々の頂点に対して１つの高さ座標を含むように生成され得る。
【００８７】
６６では、各々のタイルに対して項目が生成されたかを判定する。追加のタイルがある場合、方法は、６２に戻る。
【００８８】
各々のタイルに対して、第１データ構造内の項目がそれぞれ生成されている場合、６７で、第１データ構造及び第２データ構造が保存され、そのようにしてデータベースを生成する。
【００８９】
図７は、図６の方法を追加的に説明する手続７０の流れ図である。図７の手続は、タイルの隅でのみ頂点があるような定義済みのタイル型が１つしかない場合、図６の方法でステップ６４〜６５を実施するために使用され得る。
【００９０】
７１では、各々のタイル上の表面メッシュの全ての頂点が、タイルの隅に位置しているかを判定する。
【００９１】
タイルの隅に位置しない頂点が少なくとも１つある場合、本方法は、７２に進む。７２では、固有のタイル識別子と、１つ又は複数のＴＩＮ（複数可）を定義するデータとを含む項目が、タイルに対して生成される。ＴＩＮ（複数可）は、１つ又は複数の頂点配列と、様々な三角面を定義する指標配列とを含んでもよい。次に、本方法６０は、６６に続く。
【００９２】
全ての頂点がタイルの隅に位置する場合、手続は、７３へ進む。７３では、固有のタイル識別子と、定義済みのタイル型に対する識別子とを含む項目が、タイルに対して生成される。
【００９３】
７４では、全ての頂点の高さ座標が同じであるかを判定する。
【００９４】
全ての頂点の高さ座標が同じではない場合、手続は、７５に進む。７５では、タイル上に位置する全ての頂点の高さ座標が、第１データ構造内の項目中に保存される。
【００９５】
全ての頂点の高さ座標が同じである場合、手続は、７６に進む。７６では、全ての頂点の高さ座標が既定値に対応しているかを判定する。既定値は、海面であり得る。
【００９６】
タイル上に位置する全ての頂点の高さ座標が既定値に等しくない場合、本手続は、７７に進む。７７では、全ての頂点の（同じ）高さ座標に対応する１つの高さ値が、第１データ構造内の項目中に保存される。次に、本方法６０は、６６に続く。
【００９７】
タイル上に位置する全ての頂点の高さ座標が、既定値に等しくない場合、本手続は、７８に進む。７８では、各々のタイルに対する項目は、変更されずに残される。即ち、いかなる高さ座標も、項目中に書き込まれない。次に、本方法６０は、６６に続く。
【００９８】
タイルの隅でのみ頂点があるようなタイル型の使用が、幾つかの実施形態に示されているが、より多くの数のタイル型を使用してもよい。タイル型（単数又は複数）は、各々のタイル上の表面メッシュの頂点に対して様々な形態を定義することができる。
【００９９】
図８は、別の典型的な形態を有するタイル型８０を示す。様々な定義済みのタイル型を使用することができる。例示説明として、図８に示されるように、定義済みのタイル型が、四角形のタイルが２つの三角形に分割されているような形態を有するものであってもよい。その結果得られる三角形の各々は、地形表面の高さの変化に対応する必要がある場合、再び、対称的に２つに分割され得る。定義済みのタイル型は、組み合わせで正方形のタイルを覆う直角二等辺三角形によってのみタイル全体が覆われるような形態の集合から、それぞれ選択されてもよい。
【０１００】
実施形態による方法及び装置が、詳細に記載されたが、他の実施形態では、変更がなされてもよい。例示説明として、１つの定義済みのタイル型の使用が、幾つかの実施形態に関連して示されているが、より多くの数の定義済みのタイル型を使用してもよい。
【０１０１】
更なる例示説明として、表面メッシュの形態のみを記述する定義済みのタイル型が記載されたが、ある高さ情報を含む定義済みのタイル型を使用することもできる。
【０１０２】
本発明の実施形態は、ナビゲーション装置に用いられるデータベースを生成するのに使用され得るが、それに限定されない。そのようなデータベースは、例えば、経路検索又は他の運転者補助用途のために、ナビゲーション装置の光学式出力装置を介して３次元地形を視覚化するように用いられてもよいが、それに限定されない。
【特許請求の範囲】
【請求項１】
ナビゲーション装置（１）用のデータベースを生成する方法（１０）であって、前記方法が、
３次元地形を定めるデータを取り出すことと、
取り出されたデータに基づいて、複数のタイル（２３〜２６；３１〜３４）を含む表面分割図（２０）を使用して第１データ構造（１１）を生成することとであって、前記表面分割図（２０）の各々のタイル（２３〜２６；３１〜３４）に対して、項目（１３〜１８）が、前記第１データ構造（１１）内にそれぞれ生成され、前記項目をそれぞれ生成することは、
前記タイル（２３〜２６；３１〜３４）内に含まれる前記３次元地形の一部分を、第２データ構造（１２）内に含まれる少なくとも１つの定義済みのタイル型と比較することと、
前記比較の結果に基づいて、前記項目中に保存するために、前記３次元地形の一部分を定めるデータ、又は、前記第２データ構造（１２）内に含まれる定義済みのタイル型に対する識別子（１９）のうちの１つを選択することと
を含み、
前記第１データ構造（１１）と前記第２データ構造（１２）とを前記データベース（１０）内に保存することと
を含む、方法。
【請求項２】
前記３次元地形を定める表面メッシュの頂点（４１〜５０）の座標が、前記３次元地形を定める前記データから取り出されるか、又は、３次元地形を定めるデータに基づいて生成され、前記頂点（４１〜５０）の各々が、平面座標と高さ座標の一組をそれぞれ有し、
前記表面分割図（２０）の各々のタイル（２３〜２６；３１〜３４）に対して、前記タイル（２３〜２６；３１〜３４）上に位置する全ての頂点（４１〜５０）の相対平面座標が、定義済みのタイル型内の頂点（５５〜５８）の平面座標に対応する場合、前記項目（１４、１６、１７）が、前記第２データ構造（１２）内に含まれる、前記定義済みのタイル型に対する識別子（１９）をそれぞれ含むように生成される、
請求項１に記載の方法。
【請求項３】
前記方法が、
前記タイル（２３〜２６；３１〜３４）上に位置する前記頂点（４１〜５０）の高さ座標に基づいて、前記定義済みのタイル型に対する前記識別子（１９）に加えて、前記タイル（２３〜２６；３１〜３４）上に位置する少なくとも１つの頂点（４１〜５０）の高さ座標が、前記第１データ構造（１１）内に保存されるべきかを判定すること
を更に含む、請求項２に記載の方法。
【請求項４】
前記タイル（３１）上に位置するいずれかの組の頂点（４１、４６、４７、５０）の高さ座標が、既定の閾値を超えて互いに異なる場合、前記タイル（３３）上に位置する全ての頂点（４１、４６、４７、５０）の高さ座標が、前記第１データ構造（１１）の項目（１７）中に保存される、請求項３に記載の方法。
【請求項５】
前記タイル（３１、３２、３４）上に位置する全ての頂点（４１〜５０）の高さ座標が、最大限既定の閾値だけ互いに異なる場合、前記タイル（３１、３２、３４）上に位置する全ての頂点（４１〜５０）に対して、最大限１つの高さ変位値が、前記第１データ構造（１１）の前記項目（１４、１６）中に保存される、請求項３に記載の方法。
【請求項６】
全ての頂点（４７〜５０）の前記高さ座標が、既定値の高さと異なる場合、１つの高さ変位値が、前記第１データ構造（１１）内の前記項目（１６）中に保存され、
全ての頂点（４１〜４６）の前記高さ座標が、前記既定値の高さと等しい場合、高さ変位値が、前記第１データ構造（１１）内の前記項目（１４）中に保存されない、
請求項５に記載の方法。
【請求項７】
前記３次元地形の一部分を定める前記データ、又は、前記識別子（１９）のうちの前記１つが、前記タイル（２３〜２６；３１〜３４）上に位置する全ての頂点（４１〜５０）の高さ座標とは独立して選択される、請求項２〜６のいずれか１項に記載の方法。
【請求項８】
前記タイル（２３〜２６；３１〜３４）上に位置する全ての頂点（４１〜５０）が、前記タイル（２３〜２６；３１〜３４）の境界に、特に、隅に位置する場合、前記第１データ構造（１１）内に保存するために、定義済みのタイル型に対する前記識別子（１９）を選択する、請求項２〜６のいずれか１項に記載の方法。
【請求項９】
前記第２データ構造（１２）内に含まれる各々の定義済みのタイル型が、複数の頂点（４１〜５０）の平面座標と、隅として３つの前記頂点（４１〜５０）をそれぞれ有する三角面を記述する指標の配列とを含む、請求項１〜６のいずれか１項に記載の方法。
【請求項１０】
３次元地形を表し、各々が表面分割図（２０）のタイル（２３〜２６；３１〜３４）に固有のタイル識別子を含む、複数の項目（１３〜１８）を有する、第１データ構造（１１）と、少なくとも１つの定義済みのタイル型を定義する第２データ構造（１２）とを含むデータベース（１０）と、
タイル（２３〜２６；３１〜３４）に前記固有のタイル識別子を使用して、前記第１データ構造（１１）の項目にアクセスし、
前記アクセスされた項目が、前記第２データ構造（１２）内に保存された定義済みのタイル型に対する型識別子（１９）を含んでいるかを判定し、
前記項目が前記型識別子（１９）を含む場合、前記定義済みのタイル型についての情報を前記第２データ構造（１２）から選択的に取り出し、
前記第１データ構造（１１）の前記アクセスされた項目（１３〜１８）に基づいて、前記項目（１３〜１８）が前記型識別子（１９）を含む場合は、前記第２データ構造（１２）内に含まれる前記定義済みのタイル型に基づいて、１つ又は複数の場所の高さ座標を定めるように
設定されている、前記データベース（１０）に結合された処理装置（２）と
を含む、ナビゲーション装置（１）。
【請求項１１】
前記項目（１４、１６、１７）が型識別子（１９）を含む場合に、前記処理装置（２）が、前記取り出された前記定義済みのタイル型についての情報に基づいて、表面メッシュの頂点（４１〜５０）の一組の平面座標をそれぞれ定め、前記第１データ構造（１１）の前記項目（１４、１６、１７）に基づいて、前記頂点（４１〜５０）の高さ座標をそれぞれ定めるように設定されている、請求項１０に記載のナビゲーション装置（１）。
【請求項１２】
前記第１データ構造（１１）の前記項目（１４、１６）が、前記型識別子（１９）と高々１つの高さ座標とを含む場合、前記頂点（４１〜４６、４７〜５０）の高さ座標を同じ値に定めるように前記処理装置（２）が設定されている、請求項１１に記載のナビゲーション装置（１）。
【請求項１３】
前記第１データ構造（１１）の前記項目（１７）が、前記型識別子（１９）と複数の高さ座標とを含む場合に、前記頂点（４１〜５０）に対して異なる高さの座標を定めるように前記処理装置（２）が設定されている、請求項１１に記載のナビゲーション装置（１）。
【請求項１４】
定義済みのタイル型に対する識別子（１９）を含まない前記データベース（１０）の項目（１３、１５、１８）が、表面メッシュの頂点（４１〜５０）の座標３組についての情報を含む、請求項１０〜１３のいずれか１項に記載のナビゲーション装置（１）。
【請求項１５】
ナビゲーション装置（１）内で高さ情報を定める方法であって、前記ナビゲーション装置（１）が、各々が表面分割図（２０）のタイル（２３〜２６；３１〜３４）に固有のタイル識別子を含む、複数の項目（１３〜１８）を有する第１データ構造（１１）と、少なくとも１つの定義済みタイル型を定義する第２データ構造（１２）とを含む、データベース（１０）を有し、前記方法が、
タイル（２３〜２６；３１〜３４）に固有の識別子を使用して、前記第１データ構造（１１）の項目（１３〜１８）にアクセスすることと、
前記項目（１４、１６、１７）が、前記第２データ構造（１２）内に保存された定義済みのタイル型に対する型識別子（１９）を含んでいるかを判定することと、
前記判定の結果に基づいて、前記項目（１４、１６、１７）が前記型識別子（１９）を含む場合、前記第２データ構造（１２）から、前記定義済みのタイル型についての情報を取得することと、
前記第１データ構造（１１）のアクセスされた項目（１３〜１８）に基づいて、および前記項目（１４、１６、１７）が前記型識別子（１９）を含む場合は、前記第２データ構造（１２）内に含まれる前記定義済みのタイル型に基づいて、１つ又は複数の場所の高さ座標を定めることと
を含む、方法。
【請求項１】
ナビゲーション装置（１）用のデータベースを生成する方法（１０）であって、前記方法が、
３次元地形を定めるデータを取り出すことと、
取り出されたデータに基づいて、複数のタイル（２３〜２６；３１〜３４）を含む表面分割図（２０）を使用して第１データ構造（１１）を生成することとであって、前記表面分割図（２０）の各々のタイル（２３〜２６；３１〜３４）に対して、項目（１３〜１８）が、前記第１データ構造（１１）内にそれぞれ生成され、前記項目をそれぞれ生成することは、
前記タイル（２３〜２６；３１〜３４）内に含まれる前記３次元地形の一部分を、第２データ構造（１２）内に含まれる少なくとも１つの定義済みのタイル型と比較することと、
前記比較の結果に基づいて、前記項目中に保存するために、前記３次元地形の一部分を定めるデータ、又は、前記第２データ構造（１２）内に含まれる定義済みのタイル型に対する識別子（１９）のうちの１つを選択することと
を含み、
前記第１データ構造（１１）と前記第２データ構造（１２）とを前記データベース（１０）内に保存することと
を含む、方法。
【請求項２】
前記３次元地形を定める表面メッシュの頂点（４１〜５０）の座標が、前記３次元地形を定める前記データから取り出されるか、又は、３次元地形を定めるデータに基づいて生成され、前記頂点（４１〜５０）の各々が、平面座標と高さ座標の一組をそれぞれ有し、
前記表面分割図（２０）の各々のタイル（２３〜２６；３１〜３４）に対して、前記タイル（２３〜２６；３１〜３４）上に位置する全ての頂点（４１〜５０）の相対平面座標が、定義済みのタイル型内の頂点（５５〜５８）の平面座標に対応する場合、前記項目（１４、１６、１７）が、前記第２データ構造（１２）内に含まれる、前記定義済みのタイル型に対する識別子（１９）をそれぞれ含むように生成される、
請求項１に記載の方法。
【請求項３】
前記方法が、
前記タイル（２３〜２６；３１〜３４）上に位置する前記頂点（４１〜５０）の高さ座標に基づいて、前記定義済みのタイル型に対する前記識別子（１９）に加えて、前記タイル（２３〜２６；３１〜３４）上に位置する少なくとも１つの頂点（４１〜５０）の高さ座標が、前記第１データ構造（１１）内に保存されるべきかを判定すること
を更に含む、請求項２に記載の方法。
【請求項４】
前記タイル（３１）上に位置するいずれかの組の頂点（４１、４６、４７、５０）の高さ座標が、既定の閾値を超えて互いに異なる場合、前記タイル（３３）上に位置する全ての頂点（４１、４６、４７、５０）の高さ座標が、前記第１データ構造（１１）の項目（１７）中に保存される、請求項３に記載の方法。
【請求項５】
前記タイル（３１、３２、３４）上に位置する全ての頂点（４１〜５０）の高さ座標が、最大限既定の閾値だけ互いに異なる場合、前記タイル（３１、３２、３４）上に位置する全ての頂点（４１〜５０）に対して、最大限１つの高さ変位値が、前記第１データ構造（１１）の前記項目（１４、１６）中に保存される、請求項３に記載の方法。
【請求項６】
全ての頂点（４７〜５０）の前記高さ座標が、既定値の高さと異なる場合、１つの高さ変位値が、前記第１データ構造（１１）内の前記項目（１６）中に保存され、
全ての頂点（４１〜４６）の前記高さ座標が、前記既定値の高さと等しい場合、高さ変位値が、前記第１データ構造（１１）内の前記項目（１４）中に保存されない、
請求項５に記載の方法。
【請求項７】
前記３次元地形の一部分を定める前記データ、又は、前記識別子（１９）のうちの前記１つが、前記タイル（２３〜２６；３１〜３４）上に位置する全ての頂点（４１〜５０）の高さ座標とは独立して選択される、請求項２〜６のいずれか１項に記載の方法。
【請求項８】
前記タイル（２３〜２６；３１〜３４）上に位置する全ての頂点（４１〜５０）が、前記タイル（２３〜２６；３１〜３４）の境界に、特に、隅に位置する場合、前記第１データ構造（１１）内に保存するために、定義済みのタイル型に対する前記識別子（１９）を選択する、請求項２〜６のいずれか１項に記載の方法。
【請求項９】
前記第２データ構造（１２）内に含まれる各々の定義済みのタイル型が、複数の頂点（４１〜５０）の平面座標と、隅として３つの前記頂点（４１〜５０）をそれぞれ有する三角面を記述する指標の配列とを含む、請求項１〜６のいずれか１項に記載の方法。
【請求項１０】
３次元地形を表し、各々が表面分割図（２０）のタイル（２３〜２６；３１〜３４）に固有のタイル識別子を含む、複数の項目（１３〜１８）を有する、第１データ構造（１１）と、少なくとも１つの定義済みのタイル型を定義する第２データ構造（１２）とを含むデータベース（１０）と、
タイル（２３〜２６；３１〜３４）に前記固有のタイル識別子を使用して、前記第１データ構造（１１）の項目にアクセスし、
前記アクセスされた項目が、前記第２データ構造（１２）内に保存された定義済みのタイル型に対する型識別子（１９）を含んでいるかを判定し、
前記項目が前記型識別子（１９）を含む場合、前記定義済みのタイル型についての情報を前記第２データ構造（１２）から選択的に取り出し、
前記第１データ構造（１１）の前記アクセスされた項目（１３〜１８）に基づいて、前記項目（１３〜１８）が前記型識別子（１９）を含む場合は、前記第２データ構造（１２）内に含まれる前記定義済みのタイル型に基づいて、１つ又は複数の場所の高さ座標を定めるように
設定されている、前記データベース（１０）に結合された処理装置（２）と
を含む、ナビゲーション装置（１）。
【請求項１１】
前記項目（１４、１６、１７）が型識別子（１９）を含む場合に、前記処理装置（２）が、前記取り出された前記定義済みのタイル型についての情報に基づいて、表面メッシュの頂点（４１〜５０）の一組の平面座標をそれぞれ定め、前記第１データ構造（１１）の前記項目（１４、１６、１７）に基づいて、前記頂点（４１〜５０）の高さ座標をそれぞれ定めるように設定されている、請求項１０に記載のナビゲーション装置（１）。
【請求項１２】
前記第１データ構造（１１）の前記項目（１４、１６）が、前記型識別子（１９）と高々１つの高さ座標とを含む場合、前記頂点（４１〜４６、４７〜５０）の高さ座標を同じ値に定めるように前記処理装置（２）が設定されている、請求項１１に記載のナビゲーション装置（１）。
【請求項１３】
前記第１データ構造（１１）の前記項目（１７）が、前記型識別子（１９）と複数の高さ座標とを含む場合に、前記頂点（４１〜５０）に対して異なる高さの座標を定めるように前記処理装置（２）が設定されている、請求項１１に記載のナビゲーション装置（１）。
【請求項１４】
定義済みのタイル型に対する識別子（１９）を含まない前記データベース（１０）の項目（１３、１５、１８）が、表面メッシュの頂点（４１〜５０）の座標３組についての情報を含む、請求項１０〜１３のいずれか１項に記載のナビゲーション装置（１）。
【請求項１５】
ナビゲーション装置（１）内で高さ情報を定める方法であって、前記ナビゲーション装置（１）が、各々が表面分割図（２０）のタイル（２３〜２６；３１〜３４）に固有のタイル識別子を含む、複数の項目（１３〜１８）を有する第１データ構造（１１）と、少なくとも１つの定義済みタイル型を定義する第２データ構造（１２）とを含む、データベース（１０）を有し、前記方法が、
タイル（２３〜２６；３１〜３４）に固有の識別子を使用して、前記第１データ構造（１１）の項目（１３〜１８）にアクセスすることと、
前記項目（１４、１６、１７）が、前記第２データ構造（１２）内に保存された定義済みのタイル型に対する型識別子（１９）を含んでいるかを判定することと、
前記判定の結果に基づいて、前記項目（１４、１６、１７）が前記型識別子（１９）を含む場合、前記第２データ構造（１２）から、前記定義済みのタイル型についての情報を取得することと、
前記第１データ構造（１１）のアクセスされた項目（１３〜１８）に基づいて、および前記項目（１４、１６、１７）が前記型識別子（１９）を含む場合は、前記第２データ構造（１２）内に含まれる前記定義済みのタイル型に基づいて、１つ又は複数の場所の高さ座標を定めることと
を含む、方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１２−２３４５３４（Ｐ２０１２−２３４５３４Ａ）
【公開日】平成２４年１１月２９日（２０１２．１１．２９）
【国際特許分類】
【出願番号】特願２０１２−９７０８２（Ｐ２０１２−９７０８２）
【出願日】平成２４年４月２０日（２０１２．４．２０）
【出願人】（５０４１４７９３３）ハーマン ベッカー オートモーティブ システムズ ゲーエムベーハー (165)
【Ｆターム（参考）】
【公開日】平成２４年１１月２９日（２０１２．１１．２９）
【国際特許分類】
【出願日】平成２４年４月２０日（２０１２．４．２０）
【出願人】（５０４１４７９３３）ハーマン ベッカー オートモーティブ システムズ ゲーエムベーハー (165)
【Ｆターム（参考）】
[ Back to top ]