(57)【要約】【課題】空間内において指定された範囲の情報を高速に取得することを目的とする。【解決手段】空間探索木格納部は空間探索木を格納し、末端ノードにはオブジェクトの属性情報が対応づけられ、上位ノードには下位のすべての末端ノードの属性情報に応じて生成された合算属性情報が対応づけられている。探索制御部は、前記空間内の一部を指定した探索範囲に基づき、前記空間探索木の根ノードから下位ノードに向けて再帰的に探索し、前記探索範囲と重なる外包直方体が割り当てられたノードを探索する。前記枝刈部は、前記探索制御部により検出されたノードが、あらかじめ与えられた探索条件を満たさない第1ノードである場合は、前記第1ノードより下位への探索を行わないことを決定する。前記出力部は、前記第1ノードの合算属性情報と、前記探索制御部により検出された末端ノードの属性情報とに基づき、探索結果を出力する。【選択図】図１
2014182624.tif 000002
【特許請求の範囲】
【請求項１】
空間に配置された複数のオブジェクトのそれぞれの外包直方体が末端ノードに割り当てられ、上位ノードに前記上位ノードの直下の各下位ノードに割り当てられた外包直方体を包含する外包直方体が割り当てられた、空間探索木を格納するための第1格納部と、
前記オブジェクトの属性情報を前記末端ノードの属性情報として格納し、前記上位ノードごとに前記上位ノードの下位に存在するすべての末端ノードの属性情報に応じて決定された合算属性情報を格納するための第2格納部と、
前記空間内の一部を指定した探索範囲に基づき、前記空間探索木の根ノードから下位ノードに向けて再帰的に探索し、前記探索範囲と重なる外包直方体が割り当てられたノードを探索する探索制御部と、
前記探索制御部により検出されたノードが、あらかじめ与えられた探索条件を満たさない第1ノードである場合は、前記第1ノードより下位への探索を行わないことを決定する枝刈部と、
前記第1ノードの合算属性情報と、前記探索制御部により検出された末端ノードの属性情報とに基づき、探索結果を出力する出力部と、
を備えたデータ管理装置。
【請求項２】
前記上位ノードの合算属性情報は、前記上位ノードの下位に存在するすべての末端ノードの属性情報の加算を含む
請求項1に記載のデータ管理装置。
【請求項３】
前記出力部は、前記第1ノードの合算属性情報と、前記探索制御部により検出された末端ノードの属性情報の総和を計算し、総和値を前記探索結果として出力する
請求項2に記載のデータ管理装置。
【請求項４】
前記上位ノードの合算属性情報は、前記上位ノードの下位に存在するすべての末端ノードの属性情報の加算と、前記上位ノードの下位に存在するすべての末端ノードの総数を含む
請求項1に記載のデータ管理装置。
【請求項５】
前記出力部は、前記第1ノードの下位に存在するすべての末端ノードと前記探索制御部により検出された末端ノードの属性情報の平均を計算し、前記平均を前記探索結果として出力する
請求項4に記載のデータ管理装置。
【請求項６】
前記上位ノードの合算属性情報は、前記上位ノードの下位に存在するすべての末端ノードのうち、前記末端ノードの属性情報に応じて選択されたN個の末端ノードに対応するオブジェクトの識別情報を含む
請求項1に記載のデータ管理装置。
【請求項７】
前記出力部は、前記第1ノードの合算属性情報と、前記探索制御部により検出された末端ノードの属性情報に基づき、N個のオブジェクトを選択し、選択したオブジェクトの識別情報を前記探索結果として出力する
請求項6に記載のデータ管理装置。
【請求項８】
前記上位ノードの合算属性情報は、前記上位ノードの下位に存在するすべての末端ノードの属性情報の平均を含む
請求項1に記載のデータ管理装置。
【請求項９】
前記あらかじめ与えられた探索条件は、前記探索により検出されたノードに割り当てられた外包直方体が前記探索範囲に完全には含まれないことである
請求項1ないし8のいずれか一項に記載のデータ管理装置。
【請求項１０】
前記属性情報は色を表し、
前記出力部は、前記第1ノードの最小外包体を前記第1ノードの合算属性情報の色で描画し、前記探索制御部により検出された末端ノードの外包直方体またはオブジェクトを、前記末端ノードの属性情報の色で描画したレンダリングデータを、前記探索結果として出力する
請求項8に記載のデータ管理装置。
【請求項１１】
前記あらかじめ与えられた探索条件は、前記探索により検出されたノードの最小外包直方体が、画面にレンダリングした時に所定サイズの画素領域単位に収まらないことである
請求項10に記載のデータ管理装置。
【請求項１２】
登録するオブジェクトの情報を入力するオブジェクト入力部と、
前記オブジェクトの外包直方体を生成し、前記外包直方体を割り当てた末端ノードを前記空間探索木に追加するオブジェクト登録制御部と、
追加した末端ノードの直上の上位ノードから前記根ノードに至るまでの各ノードの合算属性情報を、前記登録するオブジェクトの属性情報に基づいて更新する更新部と
を備えた請求項1ないし11のいずれか一項に記載のデータ管理装置。
【請求項１３】
空間に配置された複数のオブジェクトのそれぞれの外包直方体が末端ノードに割り当てられ、上位ノードに前記上位ノードの直下の各下位ノードに割り当てられた外包直方体を包含する外包直方体が割り当てられた、空間探索木を格納する第1格納部からデータを読み出すステップと、
前記末端ノードの属性情報として前記オブジェクトの属性情報を格納し、前記上位ノードごとに前記上位ノードの下位に存在するすべての末端ノードの属性情報に応じて決定された合算属性情報を格納する第2格納部からデータを読み出すステップと、
前記空間内の一部を指定した探索範囲に基づき、前記空間探索木の根ノードから下位ノードに向けて再帰的に探索し、前記探索範囲と重なる外包直方体が割り当てられたノードを探索する探索制御ステップと、
前記探索制御ステップにより検出されたノードが、あらかじめ与えられた探索条件を満たさない第1ノードである場合は、前記第1ノードより下位への探索を行わないことを決定する枝刈ステップと、
前記第1ノードの合算属性情報と、前記探索制御ステップにより検出された末端ノードの属性情報とに基づき、探索結果を出力する出力ステップと、
を備えたデータ管理方法。
【請求項１４】
空間に配置された複数のオブジェクトのそれぞれの外包直方体が末端ノードに割り当てられ、上位ノードに前記上位ノードの直下の各下位ノードに割り当てられた外包直方体を包含する外包直方体が割り当てられた、空間探索木を格納する第1格納部からデータを読み出すステップと、
前記末端ノードの属性情報として前記オブジェクトの属性情報を格納し、前記上位ノードごとに前記上位ノードの下位に存在するすべての末端ノードの属性情報に応じて決定された合算属性情報を格納する第2格納部からデータを読み出すステップと、
前記空間内の一部を指定した探索範囲に基づき、前記空間探索木の根ノードから下位ノードに向けて再帰的に探索し、前記探索範囲と重なる外包直方体が割り当てられたノードを探索する探索制御ステップと、
前記探索制御ステップにより検出されたノードが、あらかじめ与えられた探索条件を満たさない第1ノードである場合は、前記第1ノードより下位への探索を行わないことを決定する枝刈ステップと、
前記第1ノードの合算属性情報と、前記探索制御ステップにより検出された末端ノードの属性情報とに基づき、探索結果を出力する出力ステップと、
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、データ管理装置およびその方法、ならびにプログラムに関する。
【背景技術】
【０００２】
地理情報システムにおいては、発電機器から近隣の地物まで、様々な詳細度のオブジェクトの集合（シーンと呼ぶ）を扱い、指定した範囲内の情報を正確かつ高速に集計することが重要である。
【０００３】
指定した範囲に収まるオブジェクトが少数の場合、既存の空間索引技術を用いて対象範囲のオブジェクトを単純に全て抽出し、集計すればよかった。しかし、情景を俯瞰するような範囲を指定した場合（俯瞰的集計）、その範囲に多数のオブジェクトが含まれるため、オブジェクトを全て列挙すると、高速さが犠牲になる。
【０００４】
2Ｄ（次元）で集計する場合は、同種のオブジェクトの集合（ビルや地形等）ごとに詳細度を決め、俯瞰的集計では詳細なオブジェクトの集計を省略することでこの問題を回避していた（この手法を「デクラッタリング」と呼ぶ）。しかし3Dの場合、同種のオブジェクトでも、高度によって集計対象かどうかが変わったり、視点近くのオブジェクトは詳細に、遠くのオブジェクトは粗く集計する必要があったりする。
【０００５】
3Dの既存手法では、1つのシーンに対し複数の詳細度のデータを用意し、視点からの距離に応じてデータを使い分ける（視点の近くの集計などでは詳細なデータ、遠くでは粗いデータを用いる）。この方法は多数のデータを用意する必要があるため、オブジェクトの正確さを犠牲にしてデータサイズを減らし、テクスチャによって見た目上の正確さを上げている。しかし集計情報では見た目の正確さではなく、数値的な正確さが要求されるため、この従来手法は用いることができない。
【０００６】
したがって、様々な詳細度のオブジェクトの集合に対する抽出・集計処理を正確かつ高速に行うことを可能にし、地理情報システムに置いて指定範囲の人口の総和を求めたり、指定範囲の発電システムの総発電量を求めたり、指定した視界の情景を高速に表示したりできることが望まれていた。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特許登録第3267590号
【特許文献２】特開2011-191430号公報
【特許文献３】特許登録第4171884号
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明の実施形態は、空間内において指定された範囲のオブジェクトの情報を高速に取得することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の実施形態としてのデータ管理装置は、第１格納部と、第２格納部と、探索制御部と、枝刈部と、出力部とを備える。
【００１０】
前記第１格納部は、空間に配置された複数のオブジェクトのそれぞれの外包直方体が末端ノードに割り当てられ、上位ノードに前記上位ノードの直下の各下位ノードに割り当てられた外包直方体を包含する外包直方体が割り当てられた、空間探索木を格納する。
【００１１】
前記第２格納部は、前記オブジェクトの属性情報を前記末端ノードの属性情報として格納し、前記上位ノードごとに前記上位ノードの下位に存在するすべての末端ノードの属性情報に応じて決定された合算属性情報を格納する。
【００１２】
前記探索制御部は、前記空間内の一部を指定した探索範囲に基づき、前記空間探索木の根ノードから下位ノードに向けて再帰的に探索し、前記探索範囲と重なる外包直方体が割り当てられたノードを検出する。
【００１３】
前記枝刈部は、前記探索制御部により検出されたノードが、あらかじめ与えられた探索条件を満たさない第1ノードである場合は、前記第1ノードより下位への探索を行わないことを決定する。
【００１４】
前記出力部は、前記第1ノードの合算属性情報と、前記探索制御部により検出された末端ノードの属性情報とに基づき、探索結果を出力する。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施例に係るデータ管理装置のブロック図。
【図２】図1の装置に対し、オブジェクトを登録するための処理部を追加したブロック図。
【図３】オブジェクト探索のフローチャート。
【図４】図3のステップS103で行う探索の詳細なフローチャート。
【図５】オブジェクトの登録処理のフローチャート。
【図６】図5のステップS302で行う探索の詳細なフローチャート。
【図７】15地域の集合を示す。
【図８】図7の地域集合に対して生成された空間探索木を示す。
【図９】図7の地域集合に人口1万人の地域Pを追加登録した状態を示す。
【図１０】図9の地域集合に対して生成された空間探索木を示す。
【図１１】発電プラントの集合を示す。
【図１２】図11の発電プラント集合に対して生成された空間探索木を示す。
【図１３】図11の発電プラント集合に対して生成された空間探索木の別の例を示す図。
【図１４】パネルA〜Hの集合を示す。
【図１５】図14のパネル集合に対して生成された空間探索木を示す。
【図１６】レンダリング結果を示す。
【発明を実施するための形態】
【００１６】
まず、本発明の実施形態の技術的背景について説明する。
【００１７】
従来技術における空間索引木の探索では、条件（クエリと呼ぶ）を満たすオブジェクトすべてを列挙していた。クエリの例としては、「指定された範囲とオーバーラップをもつオブジェクトを抽出」、「指定された範囲に含まれるオブジェクトを抽出」、「指定された範囲を完全に含むオブジェクトを抽出」などがある。これは、以下のように実現されていた。
【００１８】
すなわち、空間探索木のノードごとに記録された最小外包直方体（Minimum Bounded Box; MBB）が、条件で指定された範囲と重複を持たない場合は、その子ノードの探索を枝刈りする（すなわちその子ノードの探索を行わない）が、重複を持つ場合は常に、その子ノードに対して再帰的に探索を行っていた。このため高速さが犠牲になっていた。
【００１９】
本発明の実施形態では、ノードごとにあらかじめその下位のすべての末端ノードの属性情報に基づいて合算属性情報を定めておく。ノードごとに記録された最小外包直方体（MBB）が、クエリで指定された範囲と重複を持つ場合、別途指定された探索条件を満たすかどうかを判断する。満たさない場合は探索を打ち切り、そのノードの子ノードの探索は行わない。その代わりに、当該ノードの合算属性情報を、探索を省略した子ノード以下の探索の代替として用いることで、探索の正確さを補う。なお、本実施形態でも、従来技術と同様、クエリで指定された範囲と重複を持たないノードより下位の探索は行わない。
【００２０】
以下、図面を参照しながら、本発明の実施例を説明する。
【００２１】
（実施例A）
図1に本発明の実施例に係る3Dデータ管理装置のブロック図を示す。
【００２２】
合算属性情報付き空間探索木格納装置106は、手動または自動で構築された合算属性情報付き空間探索木を格納している。空間探索木の末端ノード（葉ノード）にはオブジェクトの最小外包直方体が割り当てられており、末端以外のノードである上位ノードは、その上位ノードに接続されている各下位ノードの最小外方直方体を包含する最小外包直方体が割り当てられている。このような空間探索木は、オブジェクトの最小外包直方体を求め、空間的に距離の近いオブジェクトをまとめて最小外包直方体（MBB）を計算することを繰り返すことで生成できる。なお、最小外包直方体以外の直方体、あるいは直方体以外の形を用いてもよい。  
空間探索木のすべてのノードには、属性情報が付与されている。特に、中間または根ノードに付与されている属性情報は、合算属性情報と呼ばれる。合算属性情報付き空間探索木格納装置106のうち、空間探索木本体を格納した部分は第１格納部、各ノードの属性情報を格納した部分は第２格納部に対応する。
【００２３】
ノード読出部104は、オブジェクト探索制御部102からの指示に基づき、合算属性情報付き空間探索木格納装置106から、空間探索木のノードのデータや、ノードに付与されている属性情報・合算属性情報を読み出す。ノード読出部104は、読み出したデータを、オブジェクト探索制御部102および合算属性情報枝刈部103に送る。
【００２４】
対象範囲・探索条件入力部101は、空間の一部を指定した探索範囲（対象範囲）と、探索条件（対象条件）を入力するための手段である。
【００２５】
オブジェクト探索制御部102は、空間探索木のノードから、対象範囲と重複を持つノードを、探索条件が満たされる限り再帰的に探索する。ノードの葉に到達した場合は、その葉ノード（オブジェクト）に付属するオブジェクトの属性情報を読み出し、これまでの集計結果との合算を行う。合算属性情報枝刈部103が、探索条件が満たされないノード（根ノードまたは中間ノード）に到達されたことを検出したら、そのノードの子ノード以下の探索打ち切りをオブジェクト探索制御部102に指示する。オブジェクト探索制御部102は、当該ノードの合算属性情報をノード読出部104を介して読み出し、これまでの集計結果と合算を行う。以上の探索処理をすべて完了したら、探索結果出力部105が最終的に、集計結果（探索結果）を出力する。
【００２６】
図2は、図1の装置に対し、オブジェクトを登録するための処理部を追加したブロック図を示す。
【００２７】
オブジェクト入力部201は、登録するオブジェクトの情報を入力する。
【００２８】
オブジェクト登録制御部202は、オブジェクトを登録するための制御を行う。ノード作成・更新部204は、空間探索木の適切な位置に末端ノードを生成・追加し、当該ノードの属性情報を設定することで、従来の空間探索木技術と同じように、オブジェクトを登録する。また、合算属性情報更新部203は、関連するノード（たとえば登録したノードから根ノードまでにある各ノード）の合算属性情報の更新を行う。
【００２９】
以下、具体例を用いて、本実施例の動作を説明する。
【００３０】
本実施例では、初期状態として、図7に示す15地域が登録された状態を考える。なお各地域は矩形を有し、それ自体が最小外包直方体になっている。各地域（オブジェクト）の属性情報として人口（この例では、すべて1万人）が付与されている。この時、合算属性情報付き空間探索木格納装置は、図8に示すような空間探索木を格納している。
【００３１】
なお、ここでは、各ノードは高々4個の子ノードを持つものとしたが、この数は自由に変えてよい。また、末端ノードが、それぞれ地域（すなわちオブジェクト）に対応づけられる。なお、本例ではオブジェクトは2次元を有するが、3次元でも同様にして実施可能である。
【００３２】
ここで、図9に示すように、人口1万人の地域Pを追加登録することを考える。このときオブジェクトの登録処理の流れを説明する。登録処理は、図2の右に示した各処理部が行う。図5に本処理のフローチャートを示す。
【００３３】
まず、登録オブジェクトを入力する（S301）。ここでは名称「地域P」、人口「1万人」というデータを入力する。
【００３４】
次に、ノードを登録する位置を決定する。これは図6に示すサブフローチャートの処理によって行われる。この位置決定は、従来の空間探索木のオブジェクト登録と同じ動作である。すなわち、図8の空間探索木に対して、まず一番上のノードの子ノード4つに対し、地域Pを追加登録したときにノードの最小外包直方体の拡張が最も小さくて済む子ノードを選ぶ（S401）。ここでは最も右のノードが選ばれる。同様の操作を繰り返し、葉ノードの1つ上のノードに至ったら、そのノードを登録ノードとして、図5のフローチャートに戻る。
【００３５】
その登録ノードに空きスロットがあるかどうかをみる（S303）。今回は各ノードは4個の子ノードを持つことができ、この登録ノードは現在3個の子ノードしか持たないため、空きスロットはあると見なされる。よって、オブジェクトを、その登録ノードの子ノードとして登録し（S306）、図10に示す空間探索木を得る（ただしこの時点では中間ノードおよび根ノードの合算属性情報は更新されていない）。そして、登録ノードから根ノードに至るまで逆に木を辿っていき、合算属性情報を更新していく（S307）。
【００３６】
本例では合算ルーチンとして、子ノードの属性情報の単純な和を採用する。すなわち、地域M〜Pの人口の総和（4万人）を、登録ノードの合算属性情報として更新する。さらに上のノードに移動し、同様の操作を行い、根ノードの合算属性情報15万人を、16万人に書き換える。以上で登録の動作は完了する。なお、ステップS303で空きスロットがないと判断された場合は、登録ノードを分割して新たなノードを生成し（S304）、新ノードおよび分割ノード、さらにこれらの上位の中間ノードおよび根ノードの合算属性情報を計算する（S305）。
【００３７】
ここで、図7で円で示した対象範囲を用いて、この対象範囲に重複を持つ地域の人口の総和を集計処理として求めることを考える。
【００３８】
探索条件は「当該ノードの最小外包直方体が対象範囲に完全には含まれない（一部のみ含まれる）こと」とする。
【００３９】
図3にオブジェクト探索のフローチャートを示す。まず、対象範囲と探索条件として上に示した情報を表すデータを入力する（S101、S102）。図10に示す空間探索木を根ノードから探索していく（S103）。
【００４０】
図4にステップS103で行う探索の詳細なフローチャートを示す。図7から分かるように、根ノードが持つ最小外包直方体（地域Aから地域Pまですべてを含む直方体）は対象範囲に重なり（S201のYES）、根ノードはオブジェクトではない（葉ノードではない）ため（S202の「中間ノード」）、根ノードが探索条件を満たすか判定する（S203）。
【００４１】
根ノードは明らかに完全には対象範囲に含まれないため、探索条件は満たされるため（S204のYES）、探索は続けられる（S205）。
【００４２】
次に、根ノードの子ノードのうち、左端の子ノード（子としてオブジェクトを持つ）に探索を進め、同様の処理を繰り返し（S201〜S205）、末端ノード（オブジェクト）に探索を進める（S202の「オブジェクト」）。地域Aと地域Cは対象範囲と重複を全く持たないため、集計対象ではない。一方、地域Bと地域Dは対象範囲と重複を持つため、集計対象である。よって、ここまでで地域Bと地域Dの人口の和（2万人）を集計情報として取得する（S208、S209）。
【００４３】
根ノードの子ノードのうち、左から2番目の子ノードの探索に移り、このノードは地域E〜Hを完全に包含するか判定する（S201、S202、S203）。地域E〜Hは対象範囲に完全に含まれるため、探索条件は満たされない（S204）。よって、枝刈りが発生する。すなわち、この下の各ノード（地域E〜H）を個々に検査・探索することは行わない。代わりに、このノードが持っている合算属性情報（4万人）を集計対象とする（S206、S207）。現在の集計情報は6万人となる。
【００４４】
関連技術では、地域E〜Hを個々に探索し合算することでこの情報（4万人）を得ていたが、本実施例では枝刈りを行うことで、情報の正確さが損なわれずに、処理の高速化が図れていることがわかる。
【００４５】
さらに根ノードの子ノードのうち左から3つめ、4つめの子ノードは、1つめの子ノードと同様に探索が行われ、地域J、地域M、地域Nが集計対象と判定される。これにより、集計情報は9万人となる。これですべての探索が終了し、全体の集計結果として9万人という計算結果が返される。
【００４６】
（実施例B）
本実施例では、指定された範囲内の発電プラントの発電量平均を集計処理として求める場合を示す。
【００４７】
本実施例の基本的な動作は実施例Aと同様である。異なるのは、合算属性情報が、平均を計算するための情報（総和および個数の組）である点である。
【００４８】
本実施例、および後述の実施例Cでは、図11に示す発電プラントA〜Hの集合を題材として説明する。
【００４９】
これらを空間探索木として表現したものが図12である。なお、ここでは各ノードの子ノード数の上限として2を設定したが、この値は自由に変更可能である。
【００５０】
各ノードは合算属性情報として、そのノード以下に所属する発電プラントの発電量の総和と個数を持っている。これを総和/個数という表記で表している。
【００５１】
ここで、図11に楕円で示した対象範囲を用いて、この範囲と重複を持つ発電プラントの発電量平均を集計する。
【００５２】
探索条件としては、実施例Aと同様、「当該ノードの最小外包直方体が対象範囲に完全には含まれないこと」とする。
【００５３】
根ノードの左側の子ノードは、プラントA〜Dの最小外包直方体を持ち、これは対象範囲に完全に含まれるので、探索条件を満たさない（図4のステップ204のNO）。よって、探索を打ち切り、現在の集計情報は10/4となる（S206、S207）。
【００５４】
根ノードの右側の子ノードの探索に移る。このノードは探索条件を満たすので（S204のYES）、さらに子ノードを探索していく。11/2の属性情報を持つ子ノードは、プラントE、Fの最小外包直方体を持ち、これは対象範囲と全く重なりを持たないので、集計対象とならない。
【００５５】
次に、15/2の属性情報を持つ子ノードは、プラントG、Hの最小外包直方体を持ち、これは対象範囲と重なりを持つが、探索条件も満たすので（S204のYES）、さらに子ノードを探索する。
【００５６】
プラントGは集計対象であるので、プラントGの属性情報として7/1を集計結果に加え、現在の集計情報は17/5となる（S202の「オブジェクト」、S208、S209）。プラントHは対象範囲と重なりを持たず、集計対象ではない。
【００５７】
なお、対象範囲と少しでも重なりのあるオブジェクト（プラント）を集計対象にしているが、対象範囲に完全に包含されるオブジェクトのみ集計対象にすることも可能である。
【００５８】
以上で全ての集計がおわり、集計情報は17/5となる。この総和をこの個数で除算し、約3.4という平均を集計結果として出力する。
【００５９】
（実施例C）
本実施例では、指定された範囲内の発電プラントのうち、発電量の多い上位3プラントを集計処理として求める場合を示す。
【００６０】
本実施例の基本的な動作は、実施例Bと同様である。異なるのは、合算属性情報が、上位3件の発電プラントの名称（識別情報）である点である。
【００６１】
実施例Bと同様、図11に示す発電プラントA〜Hの集合を題材として説明する。これらを空間探索木として表現したものが図13である。なお、ここでは各ノードの子ノード数の上限として2を設定したが、この値は自由に変更可能である。
【００６２】
根ノードおよび各中間ノードは合算属性情報として、そのノード以下に所属する発電プラントのうち、発電量の多い上位3プラントの名称を持っている。そのノード以下に所属する発電プラントが3件に満たない場合は、全てのプラントを発電量の多い順に持っている。
【００６３】
ここで、図11に楕円で示した対象範囲を用いて、この範囲と重複を持つ発電プラントのうち、発電量の多い上位3プラントを集計する。
【００６４】
探索条件としては、実施例Aと同様、「当該ノードの最小外包直方体が対象範囲に完全には含まれないこと」とする。
【００６５】
根ノードの左側の子ノードは、プラントA〜Dの最小外包直方体を持ち、これは対象範囲に完全に含まれるので、探索条件を満たさない（図4のステップ204のNO）。よって探索を打ち切り、現在の集計情報はD,C,Bとなる（S206、S207）。
【００６６】
根ノードの右側の子ノードの探索に移る。このノードは探索条件を満たすので（S204のYES）、さらに子ノードを探索していく。F,Eの属性情報を持つ子ノードは、プラントE、Fの最小外包直方体を持ち、これは対象範囲と全く重なりを持たないので、集計対象とならない。
【００６７】
次にH,Gの属性情報を持つ子ノードは、プラントG、Hの最小外包直方体を持ち、これは対象範囲と重なりを持つが探索条件も満たすので（S204のYES）、さらに子ノードを探索する。
【００６８】
プラントGは集計対象であるので、プラントGの属性情報としてGを集計結果に加える（S202の「オブジェクト」、S208、S209）。この時、発電量の多い上位3プラントのみを保持し、4位以下になったプラント名は捨てる。具体的な方法としては、単純な比較、件数が多い場合はマージソートがふさわしい。これにより、現在の集計情報はG,D,Cとなる。プラントHは対象範囲と重なりを持たず、集計対象ではない。
【００６９】
以上で全ての集計が終わり、集計情報はG,D,Cとなる。
【００７０】
（実施例D）
最後に、実施例Dでは、3D空間上に配置されたパネルの集合をレンダリングして画像表示する場合を示す。なおこのパネルの実体としては、太陽光発電のパネルを想定しているが、これに限らない。
【００７１】
図14に示すパネルA〜Hの集合を題材として説明する。パネルA〜Hは3次元の形状を有するが、図14では簡単のため、2次元の最小外包直方体により表示している。パネルAのみが赤く（RGBで#FF0000）、他のパネルは青い（RGBで#0000FF）。
【００７２】
これらを空間探索木として表現したものが図15である。根ノードおよび各中間ノードには、その子ノードの色の平均色が合算属性情報として記録されている。例えば、パネルA（#FF0000）とパネルB（#0000FF）の平均色は#7F007Fである。
【００７３】
なお、ここでは各ノードの子ノード数の上限として2を設定したが、この値は自由に変更可能である。
【００７４】
以上のパネルの集合を、図14に示すカメラの方向から、レンダリングを行う。このカメラの視界が対象範囲である。
【００７５】
探索条件としては、「ノードの最小外包直方体が、画面にレンダリングした時に最小画素単位に収まる大きさにならない」である。最小画素単位は一例であり、より一般的に、「ノードの最小外包直方体が、画面にレンダリングした時に所定サイズの画素領域単位に収まる大きさにならない」としてもよい。
【００７６】
図15に示す空間探索木を根ノードから探索し、発見されたオブジェクト（またはノード）をレンダリング対象とする。具体的なレンダリング方法は、CPUを用いる方法や、GPUを用いる方法など様々な方法が考えられる。
【００７７】
まず、根ノードの子ノードのうち左側のノード（合算属性情報として#3F00BEを持つもの）が探索条件を満たすか検査する（S203）。ここでは探索条件を満たす（図4のS204のYES）とする。
【００７８】
次に、さらに子ノード（合算属性情報として#7F007Fを持つもの）が探索条件を満たすか検査する（S203）。ここでは探索条件を満たさないものとする（S204のNO）。枝刈りが発生し、パネルA、Bを個々にレンダリングすることは行わず、代わりに当該ノードの最小外包直方体を、合算属性情報として記録された色を用いて、画面にレンダリングする（S206、S207）。
【００７９】
本来はパネルA、Bを個別に描画するはずなので、正確でないレンダリングとなるが、このノードが探索条件を満たさなかったことから、パネルA、Bを正しく描画していたとしても最小画素単位に重ねてレンダリングすることになるため、生成される画像に大きな変化は発生しない。
【００８０】
さらに他のノード・オブジェクトをレンダリングしていく。他のオブジェクトの探索条件の判定では、すべて探索条件が満たされたとする（S204のYES）。
【００８１】
以上により、集計情報として図16に示すレンダリング結果が得られる。パネルA、Bが最小画素単位としてつぶれて表示されていることに注意せよ。このように、レンダリング結果の大勢に影響がないパネルの詳細な描画を省くことができるため、レンダリングが高速に行える。
【００８２】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【図１】
2014182624.tif 000003
【図２】
2014182624.tif 000004
【図３】
2014182624.tif 000005
【図４】
2014182624.tif 000006
【図５】
2014182624.tif 000007
【図６】
2014182624.tif 000008
【図７】
2014182624.tif 000009
【図８】
2014182624.tif 000010
【図９】
2014182624.tif 000011
【図１０】
2014182624.tif 000012
【図１１】
2014182624.tif 000013
【図１２】
2014182624.tif 000014
【図１３】
2014182624.tif 000015
【図１４】
2014182624.tif 000016
【図１５】
2014182624.tif 000017
【図１６】
2014182624.tif 000018