JP3598183B2 - 多次元データ管理方法、多次元データ管理装置、多次元データ管理プログラムを記録した媒体 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、２次元乃至はそれ以上の多次元空間中で位置の決まる多次元データの管理に適した多次元データ管理方法、多次元データ管理装置および多次元データ管理プログラムを記録した媒体に関するものである。より具体的には、平面あるいは空間内における図形データや、複数の属性を有する統計的なデータを個々の属性を各次元に対応させることにより、登録、削除、修正、検索（例えば、範囲検索、最近傍値検索）などの処理を、単独であるいは適宜組み合わせて実施することのできる多次元データ管理装置、方法およびそのプログラムを記録した媒体に関する。
【０００２】
【従来の技術】
従来から、複数の属性を有するデータをコンピュータを用いて管理する手法が数多く提案されている。例えば、画像処理、コンピュータビジョン、図面管理などの分野においては、ベクトル、点、記号などの大量の図形要素により表される膨大な図面をコンピュータにより管理し、データの登録、削除を行ったり、所望の図面を検索し、変更する作業が必要とされている。このようなデータ管理として、従来から知られていたものに、固定グリッド法がある。この固定グリッド法は、空間を固定の領域に分割して、各領域単位でデータを管理するものである。この固定グリッド法は、データが定まっている場合には、空間検索が高速に行えてメモリ効率も良い。しかし、例えば設備データのように頻繁に追加削除されるデータに対しては、領域の分割が固定のため分割領域ごとのデータ数のばらつきが大きくなる。そのため、全くデータが存在しない領域についても、他の領域と同様に検索処理を行ったり、データの蓄積領域を確保する必要があり、検索速度が上がらず、メモリ効率も低くなる。
【０００３】
このような固定グリッド法の問題点を解消し、多次元データの効率的管理や高速な検索を目的として、空間分割に基づく階層的なデータ構造が着目され、種々の提案がなされている。例えば、特開平３−４８９７４号公報に示された図形データ管理装置は、多次元空間中の大量の図形の位置情報及び属性を、３分木構造を有するＭＤ木の理論を適用して分割・構造化することにより、表示領域の変更に伴うデータ検索速度の向上を図るものである。また、同様な手法として、２次元データに対する２ｎ分割木を使用したｑｕａｄ−ｔｒｅｅ法も知られている。
【０００４】
［１．ＭＤ木による方法］
ＭＤ木による方法では、木は、図４２に示すように、末端の葉Ｌと内部ノードＩの２種類のノードとポインタから構成されている。データを配置する空間は再帰的に分割され、各ノードは分割された空間に対応付けられる。すなわち、親ノードは、すべての子ノードの空間を包含する最小の（ｎ次元）長方形に対応する。また、データはすべて末端の葉Ｌに蓄積される。内部ノードは、初期状態をのぞき、２つ以上３つ以下の子ノードを持つように設定され、子ノード数が３を越える場合には、内部ノードを分割し、この条件を満足するように設定されている。
【０００５】
各葉に蓄積できるデータ数をデータ容量Ｐと呼び、ある葉にＰ＋１個目のデータが投入されると、そのノードに対応する空間は分割される。例えば、図４３に示すように、Ｐ＝３とし、空間内に１から６のデータが図４３（Ａ）のように配置されているとすると、この空間は分割軸Ｘ１によって２分割される。このような分割された空間は、図４３（Ｂ）のような木構造に対応しており、各空間に対応する各葉にはそれぞれ１，４，５と２，３，６の３個のデータがそれぞれ蓄積されている。
この状態で新たなデータ７が投入されると、各葉にはそれ以上データを蓄積することはできないので、データ７が投入された側の領域は図４３（Ａ）の第２の分割軸Ｙ１によって分割される。この領域の分割に対応して、木構造においても分割された領域に対応する葉を分割し、新しい葉を作成すると共に、この葉に対応する子ノードを追加する。
【０００６】
このようにすると葉の数が増加した分、新たなデータ７の投入が可能となり、さらにデータ８の投入も可能となる。さらに、データ９の投入すると、データ９を投入領域に対応する葉には、それ以上のデータを投入する余地がないので、この投入領域を３回目の分割軸Ｘ２によって分割すると共に、対応する新しい葉を作成する。ところが、ＭＤ木による分割では、１つの親ノードが３つの子ノードしか持つことができないように設定されているため、図４３（Ｃ）のノードＣに対応する葉を分割して新しい葉を作成する場合には、内部ノードそのものを、図４３（Ｄ）のように分割する必要がある。
【０００７】
このような木構造を有するＭＤ木では、内部ノードの分割により、データの分布状態や投入順序にかかわりなく、木の根（ＲＯＯＴ）からすべての葉までの距離が等しいため、木構造としてのバランスが良く、検索効率がよい利点がある。また、どの葉にも必ず（Ｐ＋１）／２のデータが蓄積されるため、固定グリッド法に比較して、メモリの利用効率も向上する。
【０００８】
［２．ｑｕａｄ−ｔｒｅｅ法］
ｑｕａｄ−ｔｒｅｅ法では、領域を２次元平面の各軸に平行な面で４等分割する。分割された１つの空間に含まれるデータ数がＰ以下になるまで再帰的に分割を繰り返し、この過程を４分木として記憶する。このｑｕａｄ−ｔｒｅｅ法は、例えば、ＡＣＭ Ｃｏｍｐｕｔｉｎｇ Ｓｕｒｖｅｙｓ， Ｖｏｌ，２０，Ｎｏ．４ Ｄｅｃｅｍｂｅｒ １９８８に記載されている。
【０００９】
この分割法では、葉の分割時にそれに対応する子ノードを新設するだけであるため、ＭＤ木法のように内部ノードの分割時に新規なＲＯＯＴを作成する作業は不要であり、木構造の管理は容易となる。また、領域を等分割するため、分割位置は簡単に特定でき、ＭＤ木法のように個々の分割軸を記憶しておく必要はない。
【００１０】
一方、ｑｕａｄ−ｔｒｅｅ法では、データの分布を無視した等面積分割が行われるため、データの分布が一様でない場合に、木のバランス性およびメモリの利用効率が極端に低下する。
【００１１】
［３．範囲検索、最近傍データ検索］
前記のようなＭＤ木法やｑｕａｄ−ｔｒｅｅ法によって空間を階層的に分割するデータの管理方法においても、通常のデータ管理方法と同様に、範囲検索や最近傍データ検索が要求される。すなわち、範囲検索は、一定の値の範囲に属するデータを検索するものである。また、最近傍データ検索は、例えば、図形の中心点やカーソル、各データの平均値や中心値などのある特定の値から最も近い値を持つデータを検索するものである。
【００１２】
図４４に最近傍データ検索の一例を挙げる。この例は、平面図形データを管理する装置において、登録されたデータである図形要素の指定が容易に行えるようにカーソルに最も近い図形要素を常に色替え表示するものである。この例では、図４４（Ａ）に示すようにカーソル位置に対応する点Ｑを含む領域に対応する葉を求め、その葉の中で点Ｑに最も近いデータ１を求める。次に、点Ｑとデータ１の距離Ｄ１に含まれるデータを範囲検索を利用して他の葉の中から検索し、点Ｑとの距離Ｄ２がより近いデータ３を得る。以下、指定範囲をＤ２に変更し検索を続ける。
【００１３】
【発明が解決しようとする課題】
［１．分割手法による問題点］
ところで、前記のようなＭＤ木法においては、葉の分割における空間分割法は、Ｘ−Ｙ−Ｘ−Ｙ・・のように巡回的に分割軸を選択したり、あるいは長方形の辺の長さにより分割軸を選択するなどの方法があるが、基本的には、データ量によって分割する可変面積（容積）分割を基本としている。しかしながら、このような可変面積分割は、分割軸の位置が一定でないため、分割作業時に分割位置の算定に時間がかかると共に、各分割軸の座標を記憶しておく必要があり、その分だけ必要な記憶領域が増大する欠点があった。また、完全平衡木を作成するために、内部ノードの分割時に分割する葉に対応するノードを新設するだけでなく、新設したノードから遡ってＲＯＯＴとなるノードを新設する必要があり、分割する葉に対応するノードのみを新設すれば良い他の方法に比較して、木構造の管理が複雑化する欠点があった。
【００１４】
［２．末端の葉のみのデータ登録による問題点］
さらに、前記ＭＤ木法やｑｕａｄ−ｔｒｅｅ法などの従来の技術では、木構造の末端に存在する各葉にだけデータを蓄積するものであるため、領域内に投入するデータが他の領域にもまたがる場合には、複数の領域に重複登録されるデータ数が多くなり、それに伴って個々の領域内に存在すると判定されるデータ数が大きくなるため、その分領域の分割数も多くなる。すなわち、図４５に示すように、線分Ｌが領域Ｂ，Ｃ，Ｄにまたがって存在する場合、この線分はＬは各領域に対応するすべての葉に登録される。しかし、各葉に登録できるデータ数はあらかじめＰに設定されているので、重複分だけ余分にデータ数が領域に投入されているのと同じことになり、そのために領域の分割数が多くなり、分割領域に対応する内部ノードや葉の数も多くなる。その結果、木構造が複雑がすると共に、必要とするメモリの増大や、検索効率の低下を招く欠点があった。特に、工事設計、設備管理、図面管理などのように、異なった長さ、面積、容積などを有する多数の図形データを管理する場合には、従来技術のように末端の葉に各領域に属するデータをすべて登録し、かつデータ数によって領域を分割していると、ほとんどの図形データが重複登録の対象となり、メモリの利用効率が極端に低下する。
【００１５】
さらに、前記の従来技術では、末端の葉を分割する基準を、その葉に登録するデータ数が予め設定された値Ｐを越えるか否かによっていた。そのため、重複登録が多いと、末端の葉を分割しても分割後の葉に登録されたデータ数が分割前の葉に登録されたデータ数に比較してほとんど減少せず、その結果、さらに分割を繰り返す必要性が生じ、記憶領域の限度まで際限なく分割が行われてしまう欠点もあった。
【００１６】
また、ＭＤ木法では、データ数が等しくなるように領域を分割するため、結果として分割軸による図形データの分割を避けることもあるが、ｑｕａｄ−ｔｒｅｅ法では、データの分布を無視した等面積分割が行われるため、図形データの分割を避けるように分割軸を配置することはできない。そのため、一定のサイズを有する図形データが分割される機会が多くなり、重複登録の可能性がより高くなっていた。
【００１７】
［３．中間ノードへの登録］
これを改善するために、ｑｕａｄ−ｔｒｅｅ法では、次のような手法が採用されている。まず、前記ＡＣＭ Ｃｏｍｐｕｔｉｎｇ Ｓｕｒｖｅｙｓ， Ｖｏｌ，２０，Ｎｏ．４ Ｄｅｃｅｍｂｅｒ １９８８の第２９９頁のＦｉｇｕｒｅ１９．に記載の手法は、図４６に記載のような図形データＡ−Ｇをｑｕａｄ−ｔｒｅｅによって管理する場合に、２以上の領域にまたがる図形については、中間ノードに登録することにより、重複登録を避けている。すなわち、図形データＡ，Ｅは全領域（全世界）を４分割してなる領域の複数にまたがるために、これらの領域を包含する全領域に対応する親ノード１に登録される。同様に、領域をまたがる図形データＢ，Ｃ，Ｄはそれらをすべて包含する領域に対応するノード３に、図形データＧはノード５に対応する。そして、またがることのない図形データＦは、最も細分化された領域に対応するノード１５に登録される。
【００１８】
確かにこのような従来技術では複数領域にまたがったデータの重複登録は完全に解消される利点はある。しかし、このような手法では、図形データＨのように複数の領域にまたがる部分がごく少ないデータであっても、その複数の領域を包含する上位の領域に対応するノードに登録することになる。その結果、上位の領域内に登録するデータが多くなり、データ検索の範囲が広くなって、検索効率が低下する。すなわち、広大な範囲を持つ上位の領域全体を検索するよりも、たとえ重複登録の結果検索対象領域の数は多くなっても範囲の狭い複数の領域を検索する方が、検索を高速に行えるからである。
【００１９】
このような重複登録を完全に避ける手法の問題点を解決するために、前記の文献第３０１頁のＦｉｇｕｒｅ ２１．には、中間ノードへの登録を行うと同時に重複登録も可能とした手法も提案されている。この手法を図４７により説明する。
【００２０】
例えば、図形データＧは、それを含む最小の領域は全領域を４分割した際の右下の領域５＃に属するので、この領域をさらに４分割してその境界Ｘ１で図形Ｇを２つの図形データＧ１，Ｇ２に分割する。そして、分割されたそれぞれの図形データＧ１，Ｇ２について、それを包含する最小の領域１０＃，１１＃を求める。この場合、図形データＦが属する領域１４＃と同じサイズまで領域の分割を行うと、図形データＧの分割された部分はＧ１，Ｇ２さらに分割されることになるため、「図形データを包含する最小の領域を判定した後、１回だけ図形データの分割を行う」という条件に反する。そのため、図形データＧは、領域１０＃，１１＃に対応するノード１０，１１に登録する。
【００２１】
ここで、ノード１１は中間ノードであり、この中間ノード１１にデータを登録することにより、それよりも中間ノード１１の子ノードである末端のノード１５，１６にデータを重複して登録するよりも、検索速度を向上できる。一方、図形データＧが存在する２つのノード１０，１１の両方に図形データＧを登録することにより、検索対象範囲を図形データＧが属する最小の領域５＃よりもより狭い領域６＃，７＃に対応するノード６，７に限定することが可能になる。
【００２２】
ところが、この従来技術は、図形データの分割を１回しか行わないことを条件としているために、１つのデータについての重複登録が１回で済むという利点はあるものの、パイプライン、送電線、交通路などのように長尺の図形データのように、重複数が多くなったとしても分割して登録したいデータを処理するには不適当であった。
【００２３】
［４．最近傍データ検索時の問題点］
また、前記の従来技術では、最近傍データ検索を行う場合に、指定された点Ｑを含む葉を求め、その葉の中で最も近いデータを求めてから、そのデータと指定された点Ｑとの距離を利用して範囲検索を行っていた。しかし、ＭＤ木法のように、各葉の内部に必ずデータが存在する場合には、このような手法を利用することは可能である。しかし、ｑｕａｄ−ｔｒｅｅ法のように、領域を等分割するものでは、分割された領域内にデータが存在しない場合があり、そのような場合には、前記のような手法では最近傍データの検索を行うことが不可能であった。
【００２４】
［５．発明の目的］
本発明は前記のような従来技術の問題点を解決するために提案されたもので、その目的は、末端の葉を分割するか否かの判定を行うことにより、それ以上分割してもデータ管理上のメリットがない場合には、分割を行わないことによって、メモリの利用効率の向上と検索処理の高速化を可能とすることにある。
【００２５】
本発明の他の目的は、一定の条件下で、内部ノードにもデータを登録すると共に過剰な重複登録を抑制することにより、複数の分割領域にまたがるようなデータについての検索速度の向上および記憶領域の節約を可能とすることにある。
【００２６】
本発明の他の目的は、１個あるいは複数個の分割された領域を包含する一定の範囲を定め、この範囲内に属するデータを迅速に検索することにある。
本発明の他の目的は、指定した点の最近傍に位置するデータを検索する処理に当たって、指定した点を含む分割された領域内に最近傍データが存在しない場合でも、他の領域内の最近傍データを迅速に検索することにある。
本発明の他の目的は、２のＮ乗分木で領域の分割を管理すると共に、各領域を等面積（等容積）に分割することにより、領域の分割および領域の合併作業を容易に実施できると共に、分割位置を記憶することを不要として利用するメモリ領域を低減することにある。
【００２７】
本発明の他の目的は、２のＮ乗分木で領域の分割を管理すると共に、各領域をデータ数に依存することなく、一定の分割規則（制限された範囲内におけるランダムな分割も含む）にしたがって分割することにより、領域の分割作業を容易に実施することにある。
【００３２】
【課題を解決するための手段】
前記の目的を達成するため、請求項１の発明は、コンピュータの所定の領域に配置される複数の多次元データを管理する多次元データ管理方法において、前記所定の領域の中の第１の領域が、その子領域である第２の領域に階層的に分割されている場合に、前記第２の領域に前記多次元データを割り当てたときの状態と、前記第１の領域に前記多次元データを割り当てたときの状態とに基づいて示される併合許容条件を満たすか否かを判断し、前記併合許容条件を満たすと判断した場合には、前記第２の領域を前記第１の領域に併合し、前記第１の領域に前記多次元データを割り当てることを特徴とする。
【００３３】
請求項３の発明は、請求項１の発明を装置の観点から把握したものであり、コンピュータの所定の領域に配置される複数の多次元データを管理する多次元データ管理装置において、請求項１の発明の各段階に対応する手段として、併合許容条件を満たすか否かを判断する手段と、第２の領域を第１の領域に併合する手段と、第１の領域に多次元データを割り当てる手段とを備えたことを特徴とする。
【００３４】
請求項５の発明は、請求項１、３の発明を記録媒体の観点から把握したものであり、コンピュータの所定の領域に配置される複数の多次元データを管理する多次元データ管理プログラムを記録した記録媒体であって、プログラムが、コンピュータに、請求項１の発明の各段階に対応する処理として、併合許容条件を満たすか否かを判断する処理と、第２の領域を第１の領域に併合する処理と、第１の領域に多次元データを割り当てる処理と、を行わせることを特徴とする。
【００３５】
以上のような請求項１、３、５の発明によれば、管理対象となる多次元データが含まれる第２の領域を併合してその親領域である第１の領域に多次元データを割り当てることに、データ管理上のメリットがあるか否かを判断し、メリットがある場合にはその併合を行うことによって、メモリの利用効率の向上と、データ検索処理の高速化が可能となる。
【００３６】
請求項２の発明は、コンピュータの所定の領域に配置される複数の多次元データを管理する多次元データ管理方法において、前記所定の領域の中の第１の領域を、その子領域である第２の領域に階層的に分割する場合に、前記第１の領域に前記多次元データを割り当てたときの状態と、前記第２の領域に前記多次元データを割り当てたときの状態とに基づいて示される分割許容条件を満たすか否かを判断し、前記分割許容条件を満たすと判断した場合には、前記第１の領域を前記第２の領域に階層的に分割し、前記第２の領域に前記多次元データを割り当て、また、前記第２の領域に前記多次元データを割り当てたときの状態と、前記第１の領域に前記多次元データを割り当てたときの状態とに基づいて示される併合許容条件を満たすか否かを判断し、前記併合許容条件を満たすと判断した場合には、前記第２の領域を前記第１の領域に併合し、前記第１の領域に前記多次元データを割り当てることを特徴とする。
【００３７】
請求項４の発明は、請求項２の発明を装置の観点から把握したものであり、コンピュータの所定の領域に配置される複数の多次元データを管理する多次元データ管理装置において、請求項２の発明の各段階に対応する手段として、分割許容条件を満たすか否かを判断する手段と、第１の領域を第２の領域に階層的に分割する手段と、併合許容条件を満たすか否かを判断する手段と、第２の領域を第１の領域に併合する手段と、第１の領域および第２の領域の少なくとも一方に多次元データを割り当てる手段とを備えたことを特徴とする。
【００３８】
請求項６の発明は、請求項２、４の発明を記録媒体の観点から把握したものであり、コンピュータの所定の領域に配置される複数の多次元データを管理する多次元データ管理プログラムを記録した記録媒体であって、プログラムが、コンピュータに、請求項２の発明の各段階に対応する処理として、分割許容条件を満たすか否かを判断する処理と、第１の領域を第２の領域に階層的に分割する処理と、第２の領域に多次元データを割り当てる処理と、併合許容条件を満たすか否かを判断する処理と、第２の領域を第１の領域に併合する処理と、第１の領域に多次元データを割り当てる処理と、を行わせることを特徴とする。
【００３９】
以上のような請求項２、４、６の発明によれば、管理対象となる多次元データが含まれる第１の領域をさらに分割してその子領域である第２の領域に多次元データを割り当てることに、データ管理上のメリットがあるか否かを判断し、また、管理対象となる多次元データが含まれる第２の領域を併合してその親領域である第１の領域に多次元データを割り当てることに、データ管理上のメリットがあるか否かを判断し、データ管理上で最適な領域に多次元データを割り当てることによって、メモリの利用効率の向上と、データ検索処理の高速化が可能となる。
【００４０】
本発明における一つの態様は、請求項２の多次元データ管理方法において、前記分割許容条件が、前記第２の領域に所属する多次元データ数の和と、前記第１の領域に所属する多次元データ数とを比較して、分割するか否かを判定するものである。請求項４の多次元データ管理装置において、同様の分割許容条件を用いることも可能であり、それもまた、本発明における一つの態様である。
【００４１】
本発明における一つの態様は、請求項２の多次元データ管理方法において、前記分割許容条件が、前記第１の領域に所属する多次元データ数と、前記第２の領域の中の複数の領域に所属する多次元データ数とを比較して、分割するか否かを判定するものである。請求項４の多次元データ管理装置において、同様の分割許容条件を用いることも可能であり、それもまた、本発明における一つの態様である。
【００４２】
本発明における一つの態様は、請求項１または２の多次元データ管理方法において、前記併合許容条件が、前記第２の領域に所属する多次元データ数の和と、前記第１の領域に所属する多次元データ数とを比較して、併合するか否かを判定するものである。請求項３または４の多次元データ管理装置において、同様の併合許容条件を用いることも可能であり、それもまた、本発明における一つの態様である。
【００４３】
本発明における一つの態様は、請求項１または２の多次元データ管理方法において、前記併合許容条件が、前記第１の領域に所属する多次元データ数と、前記第２の領域の中の複数の領域に所属する多次元データ数とを比較して、併合するか否かを判定するものである。請求項３または４の多次元データ管理装置において、同様の併合許容条件を用いることも可能であり、それもまた、本発明における一つの態様である。
【００４４】
本発明における一つの態様は、請求項１または２の多次元データ管理方法において、前記併合許容条件が、前記第２の領域に登録できる多次元データ数を一定値以下に設定し、親領域を同じくする第２の領域のそれぞれに登録された多次元データ数がいずれも前記設定値未満の場合に、前記第２の領域を併合するものである。請求項３または４の多次元データ管理装置において、同様の併合許容条件を用いることも可能であり、それもまた、本発明における一つの態様である。
【００４５】
以上のように分割許容条件や併合許容条件を限定した各態様によれば、数値によって明確に定義した分割許容条件あるいは併合許容条件を用いることにより、領域の分割あるいは併合を行った場合にデータ管理上のメリットがあるか否かを数値に基づいて客観的に判断することができる。
【００４６】
本発明における一つの態様は、請求項２の多次元データ管理方法において、前記第１の領域の分割時に、前記多次元データを、分割によって生じた第２の領域および前記第１の領域のいずれに再登録すべきかを判断して、再登録を行うものである。請求項４の多次元データ管理装置において、第１の領域の分割時に、同様の再登録先に関する判断および再登録を行うことも可能であり、それもまた、本発明における一つの態様である。
【００４７】
以上のような再登録先の判断を行う各態様によれば、第１の領域の分割時に、多次元データを第１の領域および第２の領域のいずれに再登録することにデータ管理上のメリットがあるか否かを判断し、メリットがない場合には、第１の領域および第２の領域の両方に重複して登録しないようにすることにより、過剰な重複登録を抑制して記憶領域を節約すると共に、複数の領域にまたがる多次元データについての検索速度を向上できる。
【００４８】
本発明における一つの態様は、請求項２の多次元データ管理方法において、再登録先の判断を行う場合に、前記多次元データを前記第１の領域および第２の領域のいずれに再登録すべきかを判断する条件が、前記多次元データが前記第１の領域を完全に含んでいないことを条件とするものである。請求項４の多次元データ管理装置において、再登録先の判断を行う場合に、再登録先を判断する条件として同様の条件を用いることも可能であり、それもまた、本発明における一つの態様である。
【００４９】
本発明における一つの態様は、請求項２の多次元データ管理方法において、再登録先の判断を行う場合に、前記多次元データを前記第１の領域および第２の領域のいずれに再登録すべきかを判断する条件が、前記多次元データが重なっている前記第２の領域の数が、予め設定された数以下であることを条件とするものである。請求項４の多次元データ管理装置において、再登録先の判断を行う場合に、再登録先を判断する条件として同様の条件を用いることも可能であり、それもまた、本発明における一つの態様である。
【００５０】
本発明における一つの態様は、請求項２の多次元データ管理方法において、再登録先の判断を行う場合に、前記多次元データを前記第１の領域および第２の領域のいずれに再登録すべきかを判断する条件が、前記多次元データごとに重複登録される領域の数の上限を定め、前記第２の領域に登録しても、重複登録数が前記上限以下であることを条件とするものである。請求項４の多次元データ管理装置において、再登録先の判断を行う場合に、再登録先を判断する条件として同様の条件を用いることも可能であり、それもまた、本発明における一つの態様である。
【００５１】
以上のように再登録先を判断する条件を限定した各態様によれば、再登録先を判断する条件として、明確に定義した条件を用いることにより、特定の領域への再登録を行うことにデータ管理上のメリットがあるか否かをその明確な条件に基づいて客観的に判断することができる。
【００６１】
本発明における一つの態様は、請求項１または２の多次元データ管理方法において、前記所定の領域内において指定された範囲に属する多次元データを検索する範囲検索ステップを含むものである。請求項３または４の多次元データ管理装置において、前記範囲検索ステップに対応する範囲検索手段を備えることも可能であり、それもまた、本発明における一つの態様である。
【００６２】
以上のような多次元データの範囲検索を行う各態様によれば、１個あるいは複数個の分割された領域を包含する一定の範囲を定め、この範囲内に属するデータを迅速に検索することができる。
【００６３】
本発明における一つの態様は、請求項１または２の多次元データ管理方法において、前記所定の領域内において指定された点に最も近い多次元データを検索する最近傍データの検索ステップを含むものである。請求項３または４の多次元データ管理装置において、前記最近傍データの検索ステップに対応する最近傍データの検索手段を備えることも可能であり、それもまた、本発明における一つの態様である。
【００６４】
本発明における一つの態様は、請求項１または２の多次元データ管理方法において、前記最近傍データの検索ステップが、前記指定された点を含む最小の領域に多次元データが登録されていない場合に、最近傍データの候補が１つ決定されるまで検索範囲を拡大するステップを含むものである。請求項３または４の多次元データ管理装置において、前記最近傍データの検索手段が、前記検索範囲を拡大するステップに対応する機能を有することも可能であり、それもまた、本発明における一つの態様である。
【００６５】
以上のような最近傍データの検索を行う各態様によれば、指定した点の最近傍に位置する最近傍データを迅速に検索することができる。特に、検索範囲を拡大するステップまたは機能を有する態様によれば、指定された点を含む最小の領域に多次元データが登録されていない場合であっても、検索範囲を拡大することに より、最近傍データを迅速に検出することができる。
【００６６】
【発明の実施の形態】
以下、本発明の実施形態について、図面を参照して具体的に説明する。なお、以下の実施形態は、電力系統の配電線図のような２次元データの管理・検索についてのものである。
【００６７】
［１．用語の説明］
各実施形態について説明する前に、本明細書中で用いられる種々の用語について説明する。
【００６８】
（ａ）「データの管理」：
データの登録・削除、メッシュの分割・併合、データの検索（例えば、矩形検索、最近傍データ検索）などのデータを処理する１つあるいは複数の手続きを包含する。
【００６９】
（ｂ）「世界座標範囲または世界範囲」：
データを管理する空間の範囲のことをいう。通常、データ格納領域の初期時に与えられた範囲である。
【００７０】
（ｃ）「図形」：
多次元空間内で座標によって表示される多次元データの１つであって、本実施の形態では、２次元空間内に配置された点、線、面などの図形要素の単独あるいは組み合わせからなるデータを指す。図形は、その図形が世界座標範囲でどのような位置／領域を占めているかを表わす数値データを持っている。この図形データは与えられたままデータ領域にコピーされる。なお、３次元空間内においては、立体図形を指すことは言うまでもない。
図形には、図形要素の組み合わせからなる比較的小さな図形（本実施の形態ではサブ図形と呼ぶ）と、このサブ図形をさらに組み合わせてなるより大きな図形（本実施の形態ではスーパー図形と呼ぶ）がある。本実施の形態において、登録、削除、検索などの管理対象となる図形には、図形要素、サブ図形、スーパー図形のいずれもが含まれる。図形をどのような態様で管理するかは、管理の目的、コンピュータの記憶領域の大小、検索速度、分割するメッシュの階層レベルなどによって適宜選択することができる。
【００７１】
（ｄ）「メッシュ」：
世界座標範囲が２のＮ乗分割されてできる空間を言う。従来技術の説明で使用したデータが属する領域と同じ。本発明の第１実施形態ないし第３実施形態では図形という２次元データを管理するため、世界座標範囲を４分割（繰り返し４分割された場合も含む）された結果できる四角形をいう。
世界座標範囲全体自体もメッシュと呼ぶ。ある程度の数の図形データがデータ格納領域に登録された状態では、世界座標範囲はいくつかのメッシュに分割されている。通常、図形の詰まったところは細かく小さいメッシュに分割され、図形の少ないところは大きなメッシュに分割される。
【００７２】
Ｎ次元空間における分割では、各次元について２分割するので、メッシュは２のＮ乗分割される。世界範囲から始まって細かく分割されるメッシュを２のＮ乗分木を用いて管理する。２のＮ乗分木のデータ構造もデータ領域上に載せる。２のＮ乗分木の各ノードから対応するメッシュに関する情報が容易に得られる。
【００７３】
（ｅ）「木構造」：
メッシュ分割された世界座標範囲は４分木で管理され、世界座標範囲内の各メッシュは４分木の１つのノードに対応する。逆に、４分木のどのノードも、メッシュ分割された世界座標範囲のいずれか１つのメッシュに対応する。例えば、与えられたデータ格納領域の初期時には、前記世界座標範囲には図形は一つもなく、世界座標範囲全体を指すたった１個のノード（根ノード）からなる４分木だけを構成する。
ノードとメッシュは１対１に対応し、メッシュの分割・併合に伴ってノードの追加・削除を行うことによってこの対応が維持される。各ノードは対応するメッシュが存在する時は、そのメッシュデータを指していて、存在しないときはどこも指さない。メッシュ分割の時は、与えられた飯データ領域を指し、合併しメッシュがなくなったときはどこも指さないようにノードは変わる。おな、ノードの追加・削除を動的に行わず、あらかじめ定められた４分木乗でメッシュと対応付けられているノードの範囲のみを管理することもできるが、その場合はこの限りでない。
具体的には、世界座標範囲全体を示す四角形のメッシュは「根ノード」に対応し、根ノードの４つの子ノードは世界座標範囲の四角形を４分割した４つのメッシュに対応する。例えば、メッシュＭがメッシュｍ０〜ｍ３に４分割されているとき、メッシュＭに対応するノードＮはメッシュｍ０〜ｍ３に対応するノードｎ０〜ｎ３をすぐ下の子ノードとして持つ。以下の実施形態では、メッシュの親子関係が分かるように、子メッシュの番号を親メッシュの番号の４倍プラス０，１，２，３とし、４分割したメッシュの左下、左上、右下、右上の順にその番号を付する。すなわち、ｍ０＝４Ｍ，ｍ１＝４Ｍ＋１，ｍ２＝４Ｍ＋２，ｍ３＝４Ｍ＋３である。
【００７４】
逆に、メッシュに対応するノードを決定する方法としては、例えば４分木の根ノードから出発して、与えられたメッシュを含むメッシュに対応する子ノードに順次降りて行き、与えられたメッシュに一致するメッシュに対応するノードに至る方法がある。いずれにせよ、ノードとメッシュは１対１に対応するから、その対応を実現する方法には種々の形態があり、いずれの方法を採用してもメッシュ及びノードが一意に決定される。
なお、管理するデータの種類によっては、４分木は１本とは限らず、表示倍率別あるいは図形種類別に用意することもある。
【００７５】
（ｆ）「末端ノードと内ノード」：
葉ノードに対応するメッシュは分割されておらず、このメッシュを「末端メッシュ」と呼ぶ。これに対し、内ノードに対応するメッシュは必ず分割済みである。また、図形は末端メッシュに所属するものとし、末端メッシュに対応する葉ノードは、そのメッシュに所属する全図形リストを持つ。さらに、図形が占める領域とメッシュの領域の重なりがあるとき、「図形はメッシュに所属する」という。なお、内ノードは「中間ノード」とも呼ばれ、これに対応するめしは「中間メッシュ」「被分割メッシュ」呼ばれる。
【００７６】
（ｇ）「メッシュの状態データ」：
１つノードを指定すると、そのノードに対応するメッシュがどれであるかを検索する手段（後述するメッシュ検索手段）があるが、この手段としては、例えば、メッシュの座標を計算で割り出したり、メッシュのデータを直接ノードが持つことにより実現される。
【００７７】
例えば、各ノードが直接対応するメッシュに関するデータを持つ方法がある。このデータを「メッシュの状態データ」と呼ぶ。このデータはデータ領域上に置かれ、対応するメッシュが存在するノードにはそのデータ格納領域を指すポインタを格納すればよい。一方、対応するメッシュがないノードは何も指さない（ヌルを指すポインタを格納する）。このメッシュの状態データ図３に示すような構造をしており、は、図形のリストを状態データとして持つ。この図形リストから具体的な図形データ（座標、色、幅、種類など）にアクセスすることが容易となる。その他、状態データとして、メッシュと重なりのある図形数や、種類毎の所属する図形数などを持つ場合もある。なお、以下の実施形態では、所属図形数を状態データとして持っている。
【００７８】
ここで、図形がメッシュに登録されているとは、図形データがメッシュの所属図形リストに入っていることを言い、図形がメッシュに所属するとは、単に図形がメッシュには言っているだけでなく、メッシュの下層の子メッシュにも登録されていることを言う。また、所属図形数とは、メッシュそれ自体に登録されている図形と、そのメッシュより下層の子メッシュに登録されている図形を重複なく数えることを言う。所属図形リストとは、メッシュに登録されている図形（図形要素やサブ図形）のリストを意味する。
【００７９】
また、メッシュデータとして、葉ノードと内ノードが持つ情報の種類が異なることもある。これは、内ノードには所属する図形リストを保持させる必要がないことによるが、データ領域に余裕があれば、内ノードにも所属する図形リストを保持させることもできる。なお、ノードが持つメッシュの状態データは、与えられたデータ領域上に格納される。
【００８０】
（ｈ）「メッシュの分割」：
葉ノードＮに対応する末端メッシュＭは、一定の条件（例えば、そのメッシュに所属する図形数が一定数を超えたとき）を満たすと４分割される。そして、４分割によって生じる４つのメッシュ（ｍ０〜ｍ３）に対応するノードが４つ（ｎ０〜ｎ３）作られ、それらはノードＮの子ノードになる。つまり、ノードＮは内ノードになり、４つのノード（ｎ０〜ｎ３）が葉ノードになる。メッシュＭに所属している図形のうち、分割後のメッシュ（ｍ０〜ｍ３）に所属すべき図形は分割後のメッシュに所属させる。メッシュＭの所属のままでよい図形はそのままで良い。メッシュＭ，ｍ０，ｍ１，ｍ２，ｍ３の状態データを各対応ノードで更新する。
一方、内ノードＮに対応するメッシュＭは必ず分割されている。メッシュＭが一定の条件（例えば、そのメッシュに所属する図形数が一定数を下回ったとき）を満たしたとき、メッシュＭに対応するノードの子ノード、孫ノードを抹消する。その結果、メッシュＭは未分割のメッシュになり、対応ノードは葉ノードになる。そして、メッシュＭ以下の末端メッシュに所属していた図形をメッシュＭに所属させる。これにより、ノードＮが持つメッシュＭの状態データは、所属図形リストを持つことになる。
【００８１】
［２．各実施形態とコンピュータ］
本発明の各実施形態はコンピュータ上に実現され、実施形態の各機能は、所定の手順（プログラム）がこのコンピュータを制御することで実現される。
本明細書における各「手段」は、実施形態の各機能に対応する概念的なもので、必ずしも特定のハードウェアやソフトウェア・ルーチンに１対１には対応しない。同一のハードウェア要素が、場合によって異なった手段を構成する。例えば、コンピュータは、ある命令を実行するときにある手段となり、別の命令を実行するときは別の手段となりうる。また、一つの手段が、わずか１命令によって実現される場合もあれば、多数の命令によって実現される場合もある。したがって、本明細書では、以下、実施形態の各機能を有する仮想的回路ブロック（手段）を想定して実施形態を説明する。また、本実施形態における各手順の各ステップは、その性質に反しない限り、実行順序を変更し、複数同時に実行し、また、実行ごとに異なった順序で実行してもよい。このような順序の変更は、例えば、ユーザが実行可能な処理を選択するなどメニュー形式のインターフェース手法によって実現することができる。
【００８２】
［３．第１実施形態］
第１実施形態は、前記第１の目的を達成するための発明に関するものであり、請求項１〜請求項３に記載の多次元データ管理方法、請求項５〜７に記載の多次元データ管理装置及び請求項９〜１１に記載のプログラムを記録した媒体に対応するものである。
【００８３】
第１実施形態は、末端メッシュのみに図形を登録すると共に、末端メッシュの分割を所定の条件下で行うことにより、データ管理の観点から見て非効率的なメッシュの分割を抑制することで、メモリの使用効率の向上を可能としたものである。
【００８４】
すなわち、末端メッシュの分割を許容する所定の条件としては、例えば、次のようなものがある。
（ａ）所属図形が一定数以上である。
（ｂ）分割した場合、子メッシュの所属図形数の和が、分割前の親メッシュの所属図形数のｍ倍未満である。
（ｃ）分割した場合、３つ以上の子メッシュに所属する図形の数が、所属図形数のｎ％未満である。
なお、ｍの典型的な値は、２倍（４分割だから、４以上は無意味である）、ｎの典型的な値は例えば３０％に設定することができる。
【００８５】
木構造を利用したデータ管理方法において、前記（ａ）の条件のみを用いるのは公知である。第１実施形態では、この（ａ）の条件に（ｂ）ないし（ｃ）の条件を併用することによって、図形の複数メッシュへの重複登録を抑制し、分割に伴う所要記憶領域の増加を抑制している。使用すべき条件としては、（ｂ）（ｃ）のような形のものだけではなく、（ａ）のみの条件を用いて分割を行った場合に比較して、個々の図形についてあるいは全図形に関して平均的に１つの図形あたりの所属（登録）メッシュ数を減少させるような効果を持つものならば、どのような条件を用いても良い。例えば、（ｂ）のｍの値を所属図形の種類別の数の比率に基づいて決定したり、非常に長い線分のようにもともとある程度の数のメッシュへの重複登録が避けられないタイプの図形を除外して（ｂ）あるいは（ｃ）の条件をチェックするなど、種々考えられる。
【００８６】
（ａ）の条件に基づいて分割を行うことの効果は、より小さなメッシュにより少ない図形を登録することにより、第２実施形態において、矩形検索で矩形に重なると判定されたメッシュから図形を取り出して矩形への所属をチェックする際に、矩形に所属しないと判定される図形を減少させることによって、処理の高速化を図るものである。また、最近傍検索においても、１つのメッシュ所属する図形数が少なければ、最近傍図形を決定するまでに検索調査される図形数が減少することによって高速化が図られる。
【００８７】
しかしながら、前記（ｂ）（ｃ）の条件を併用しないで（ａ）の条件によって資源の許す限り無制限に分割を進めれば、多数重なり合って存在するある程度の大きさを有する図形を登録した場合には、１つの図形の所属メッシュは非常に多数になり、近接するメッシュに所属している図形には共通のものが多いという状況が生じる。このような状況では、分割による個々のメッシュの所属図形の現象が十分はかられないばかりか、検索に際して既にチェックした図形を再度チェックする、あるいは既にチェックしたものと判定して捨象するという無駄な作業の割合が増加し、所要記憶領域の増加のみならず処理速度の低下をも招く。
【００８８】
これに対して、（ｂ）（ｃ）の条件を併用すれば、１つの図形あたりの所属メッシュ数を著しく増加させるような分割を抑制することができ、所要記憶領域の増加を抑制し、かつ検索処理の速度を向上させる（低下させない）という効果がある。さらには、分割／併合の頻度が減少することによって、登録／削除の処理も高速化される。
【００８９】
末端メッシュの分割に対応して、併合の場合の所定の条件としては、次のようなものを用いることができる。
（ｄ）親メッシュの所属図形が一定数未満である。
（ｅ）併合した場合、子メッシュの所属図形数の和が、親メッシュの所属図形数のｍ｀倍以上である。
（ｆ）併合した場合、３つ以上の子メッシュに所属する図形の数が、所属図形数のｎ％以上である。
（ｄ）は分割の（ａ）に対応する条件で、（ｄ）のみを用いるのは公知である。（ｅ）を併用する場合、登録において（ｂ）を併用したとすれば、ｍ｀をｍに対してどの程度に設定するかで併合の発生を抑制し得る。ｍ｀がｍに対して大きければ併合が生じにくく、小さければ併合が生じやすい。同様に、（ｆ）と（ｃ）を用いる場合、ｎ｀がｎに対して大きければ併合が生じにくく、小さければ併合が生じ易い。
【００９０】
なお、併合を判定する前記の条件は、併用せず単独で用いても良い。すなわち、（ｅ）のみを用いて併合の可否を判定しても良い。（ｄ）の条件を用いないとすれば、登録の結果として併合すべきメッシュが生じることもあるので、登録処理時において、末端メッシュの所属図形リストに図形を加えた後に、メッシュの分割処理を試みるだけでなく、メッシュの併合処理も合わせて試みることが効果的である。
【００９１】
また、（ｅ）の条件判定を行う場合、第１実施形態においては各メッシュの所属図形数は得られるようになっているので、メッシュ状態データはそのままでよい。（ｂ）に関しては、末端メッシュの状態データの一部として子メッシュの所属図形数の和を保持するカウンタを設け、登録処理時において末端メッシュを分割して作成する子メッシュについて図形の所属をチェックし、所属すればそのカウンタを増すなどの手段を講じて、判定が迅速に行えるようにすれば効果的である。
【００９２】
［３−１．第１実施形態の構成］
図１は、第１実施形態の構成を示す機能ブロック図である。
【００９３】
すなわち、本実施形態の多次元データ管理装置は、中央処理装置１に接続されたキーボードマウスその他の入力装置２、ディスプレイやプリンタ、外部ファイルなどの出力装置３、本発明のデータ管理プログラム６や管理データを保存する記憶装置５、データ管理プログラム６の実行・記憶領域であるメインメモリ５を備えている。
【００９４】
メッシュデータ記憶手段７は、多次元空間を複数のメッシュに階層的に分割し、分割された各階層のメッシュを木構造の各ノードに対応させ、各メッシュと各ノードとの対応関係を記憶する。すなわち、分割された各メッシュに前記多次元データに関する情報を登録する。前記多次元データ記憶手段８は、管理対象となる複数の多次元データを多次元空間内に配置し、各多次元データの値を多次元空間内における座標として登録する。
【００９５】
これら各記憶手段によってファイル装置あるいはメインメモリのデータ格納領域に記録される各データの一例を図２乃至図４に示す。なお、データ格納領域は、アクセスが早いものが望ましく、コンピュータのメインメモリ上に確保することが非常に好ましい。また、前記「４分木管理領域」には、４分木のノードに対応するメッシュ番号が付されており、そのノードが末端メッシュの場合には、メッシュデータを格納している領域を指すポインタが記されている。
【００９６】
このデータ格納領域は、一例として図２に示すように、パラメータ格納領域、図形キー管理、４分木管理構造、メッシュデータおよび図形データの格納領域などから構成されている。前記パラメータ格納領域に格納されるパラメータとしては、世界座標範囲、各メッシュに登録する最大の図形数、４分木を分割する際の最大分割レベル数、メッシュの分割・合併の条件を定める各種の値（メッシュ分割する図形数、メッシュ合併する図形数など）、図形に種類がある時その内容、４分木が複数ある場合その判別、データサイズ、空き領域の先頭などが格納されている。
【００９７】
メッシュデータは、一例として図３に示すように、所属図形数、最大図形数（所属図形数がこの数より大きくなったら、そのメッシュは４分割される）、所属図形リストを備えており、この所属図形リストに、所属する図形のデータの前記データ格納領域上における格納領域を示すポインタを登録する。なお、本実施形態においては、末端メッシュでないメッシュは、前記所属図形リストは持たないものとする。
【００９８】
さらに、サブ図形の組合わせで構成される図形データの場合には、図４に示したように、サブ図形単位でメッシュに所属させることにより、サブ図形を分けて別個の図形データとして格納するよりもデータ領域を節約できる。また、一つにまとまった図形はまとめた方が人間の感覚に合致するし、画面への表示は大きくまとまっている方が速いというメリットもある。
【００９９】
データ管理プログラム６は、木構造管理手段９、多次元データ登録削除手段１０、メッシュデータ登録削除手段１１、メッシュ分割手段１２、分割判定手段１３、メッシュ併合手段１４および併合判定手段１５を備えている。
【０１００】
木構造管理手段９は、前記多次元空間を複数のメッシュに階層的に分割し、分割された各階層のメッシュを木構造の各ノードに対応させ、各メッシュと各ノードとの対応関係を管理する。この木構造管理手段９においては、世界座標範囲の中のメッシュを４分木のノードと対応させ、そのノードから対応するメッシュに関するデータが格納されているデータ領域を指す。第１実施形態では、４分木ノードとメッシュの対応付けは、メッシュの番号と４分木のノードの番号を同一にすることにより実現している。例えば、あるメッシュの４分割後の４つのメッシュの番号を、分割前のメッシュの番号の４倍プラス０，１，２，３，とし、左下、左上、右下、右上の順に番号を付けることとする。これにより、メッシュの親子関係が簡単に分かり、また、メッシュの番号から計算によりメッシュの座標が求まり、分割レベルも求まる。
【０１０１】
また、木構造管理手段９は、４分木から検索対象メッシュが末端メッシュ（４分木の葉ノード）であるか否かを判定し、検索対象メッシュがカバーする範囲（左下と右上の座標）を指示し、検索対象メッシュの分割レベルを示す。この場合、全図形データに「図形キー」と呼ばれるユニークな図形ＩＤ番号を付し、その図形キーに基づいて全図形を管理し、図形キーが与えられると該当図形のデータ格納場所を検索することができる。また、図形データを格納するデータ領域を、図形データの大きさに合わせて確保する。さらに、図形データの座標とメッシュの座標を使って、検索対象図形が検索対象メッシュに入っているか否かを判定する。
【０１０２】
多次元データ登録削除手段１０は、前記多次元データ記憶手段８に多次元データを登録・削除する。メッシュデータ登録削除手段１１は、メッシュデータ記憶手段７に作用して、前記各メッシュのうち、少なくとも前記木構造の末端のノードに対応する末端メッシュに、その末端メッシュに対応する前記多次元データに関する情報を登録または削除する。
【０１０３】
これらの各手段により、本発明では、前記各メッシュデータ記憶手段に登録された情報に基づいて前記多次元データ記憶手段に蓄積されている多次元データを管理する。
【０１０４】
本発明においては、前記のような構成を有する多次元データ管理装置において、次の構成を備えたことを特徴とする。まず、メッシュ分割手段１２は、前記末端メッシュに登録できる多次元データ数を一定値以下に設定し、末端メッシュに登録する多次元データ数が前記設定値を超えた場合にその末端メッシュを分割する。分割判定手段１３は、このメッシュ分割手段による末端メッシュの分割処理に当たり、予め設定された分割許容条件にしたがって分割の可否を判定する。メッシュ併合手段１４は、前記末端メッシュの親メッシュに登録できる多次元データ数を一定値以下に設定し、前記親メッシュに所属する多次元データ数が前記設定値未満の場合に、その末端メッシュの併合を試行する。併合判定手段１５は、前記末端メッシュをその兄弟メッシュと共に親メッシュに併合するステップの試行に当たり、予め設定された併合許容条件にしたがって併合の可否を判定する。
【０１０５】
具体的には、前記分割判定手段１３としては、
（ａ）分割後の子メッシュに所属する多次元データ数の和と、分割前の親メッシュに所属する多次元データ数とを比較して、分割の可否を判定するもの、
（ｂ）親メッシュに所属する多次元データ数と、前記親メッシュから分割された子メッシュの中の複数の子メッシュに所属する多次元データ数とを比較して、分割の可否を判定するもの、
が使用できる。
【０１０６】
前記併合判定手段１５としては、
（ａ）併合前の各子メッシュに所属する多次元データ数の和と、併合後の親メッシュに所属する多次元データ数とを比較して、併合の可否を判定するもの、
（ｂ）併合後の親メッシュに所属する多次元データ数と、これら子メッシュの中の複数の子メッシュに所属する多次元データ数とを比較して、併合の可否を判定するもの、
（ｃ）前記末端メッシュに登録できる多次元データ数を一定値以下に設定し、親メッシュを同じくする各末端メッシュに登録された多次元データ数がいずれも前記設定値未満の場合に、その末端メッシュの併合を実行するもの、
が使用できる。
【０１０７】
［３−２．第１実施形態の作用］
以下前記のような構成を有する第１実施形態の多次元データ管理装置の作用並びに、これに対応する多次元データ管理方法について、図５乃至図７の木構造とメッシュとの関係、図８のスタックの機能、図９乃至図１５のフローチャートに従って説明する。
【０１０８】
［３−２−１．データ領域への図形の登録処理］
データ領域に新たな図形を登録する処理は、図９に示したフローチャートにしたがって実行される。以下、各ステップごとに説明する。
【０１０９】
（ステップ９０１）
登録する図形データに合ったデータ領域を確保する。
【０１１０】
（ステップ９０２）
データ領域が確保できたか否かが判断され、データ領域が確保できた場合には、次のステップに進み、データ領域が確保できない場合には、データ領域への図形の登録はできず、この処理は終了する。
【０１１１】
（ステップ９０３）
ステップ９０２でデータ領域が確保できた場合には、図形データを確保したデータ領域にコピーする。
【０１１２】
（ステップ９０４）
図形キー管理エリアにその図形を加える。
【０１１３】
（ステップ９０５）
図形キー管理エリアに図形を加えることができたか否かが判断され、加えることができた場合には、次のステップ９０６に進み、一方、加えることができない場合には、ステップ９０９に進む。
【０１１４】
（ステップ９０６）
図形キー管理エリアに図形を加えることができた場合には、その図形をメッシュに登録する。
【０１１５】
（ステップ９０７）
図形をメッシュに登録できたが否かが判断され、登録できた場合には、データ領域への図形の登録は完了する。一方、登録できなかった場合には、次のステップに進む。
【０１１６】
（ステップ９０８）
登録処理の過程で変化したメッシュを元に戻して、図形データを削除し、この処理を終了する。
【０１１７】
（ステップ９０９）
ステップ９０５で図形キー管理エリアに図形を加えることができなかった場合には、ステップ９０３においてデータ領域にコピーした図形データを消し、データ領域への図形の登録処理を終了する。
【０１１８】
ここで、「登録処理の過程で変化したメッシュ」とは、例えば、そのメッシュに所属する図形の数が増えた結果、４分割されたメッシュ等をいう。したがって、本処理によって、結果的に図形の登録ができなかった場合には、すべてのデータは元の状態に戻される。
【０１１９】
なお、図９に示したフローチャートの内、ステップ９０６の「図形をメッシュに登録する処理」、及びステップ９０８の「図形をデータ領域から削除する処理」については、後述する。
【０１２０】
［３−２−２．メッシュデータへの図形の登録処理］
全世界を再帰的に分割したメッシュに新たな図形を登録する処理は、図１０に示したフローチャートにしたがって実行される。本実施例では図形を末端メッシュにのみ登録する。以下、各ステップごとに説明する。
【０１２１】
（ステップ１００１）
メッシュスタックを空にする。
【０１２２】
（ステップ１００２）
メッシュスタックに世界全体（全世界１）をメッシュとして入れる。
【０１２３】
（ステップ１００３）
メッシュスタックが空か否かを判断し、空の場合には本処理を終了する。一方、空でない場合には次のステップに進む。なお、ここでは、前ステップにおいて、全世界１が入っているので次のステップに進む。
【０１２４】
（ステップ１００４）
メッシュスタックからメッシュを一つ取り出し、現メッシュとする。すなわち、ここでは全世界１が取り出される。
【０１２５】
（ステップ１００５）
現メッシュと図形が重なっているか否かを判断し、重なっていない場合にはステップ１００３に戻る。一方、重なっている場合には次のステップに進む。ここでは、全世界１は登録すべき図形ａと重なっているので、次のステップに進む。
【０１２６】
（ステップ１００６）
現メッシュの所属図形数を増やす。ここでは、全世界１のメッシュデータの所属図形数を、図形ａの分として１つ増やす。
【０１２７】
（ステップ１００７）
現メッシュが末端のメッシュであるか否かが判断され、末端メッシュである場合には、ステップ１００９に進む。一方、末端メッシュでない場合には、ステップ１００８に進む。ここで、全世界１がすでに４〜７のメッシュに分割されており、４〜７が末端メッシュであるとすると、現メッシュである全世界１は末端メッシュではないので、ステップ１００８へ進む。
【０１２８】
（ステップ１００８）
現メッシュを４分割した４つのメッシュをメッシュスタックに入れ、ステップ１００４へ戻る。すなわち、ここでは、全世界１を４分割した４〜７のメッシュをメッシュスタックに入れ、ステップ１００４へ戻る。そして、ステップ１００４において、メッシュスタックからメッシュを順に一つずつ取り出して現メッシュとし、上記ステップ１００５〜ステップ１００７の処理を各メッシュについて行う。この例では、メッシュスタックからメッシュ７を取り出し、現メッシュとしてステップ１００５へ進む。このメッシュ７は、図５に示したように、登録する図形ａと重なっているので、ステップ１００６及びステップ１００７に進み、ステップ１００７でメッシュ７は末端メッシュであると判断され、ステップ１００９に進む。
【０１２９】
（ステップ１００９）
現メッシュの所属図形リストに登録する図形を加える。
【０１３０】
（ステップ１０１０）
現メッシュについて、後述する「メッシュの分割処理」がなされ、ステップ１００３へ戻る。この例では、他のメッシュ６、５、４は、いずれも図形ａと重ならないので、ステップ１００３〜ステップ１００５を順次繰り返し、すべての末端メッシュのチェックが終了すると、ステップ１００３でメッシュスタックが空になるので、本処理を終了する。結局、末端メッシュ７に図形ａが登録される。
【０１３１】
なお、後述する「メッシュの分割処理」において、現メッシュが４分割されると、現メッシュは親メッシュになるので、前記ステップ１００９でメッシュ７の所属図形リストに加えた図形ａは、メッシュ７の所属図形リストから削除される。
【０１３２】
［３−２−３．データ領域からの図形の削除処理］
データ領域から所定の図形を削除する処理は、図１１に示したフローチャートにしたがって実行される。以下、各ステップごとに説明する。
【０１３３】
（ステップ１１０１）
後述する「図形をメッシュから削除する処理」がなされる。
【０１３４】
（ステップ１１０２）
図形キー管理エリアから該当図形を除く。
【０１３５】
（ステップ１１０３）
図形データ格納場所にあるデータを消去して、本処理を終了する。
【０１３６】
［３−２−４．メッシュからの図形の削除処理］
メッシュから所定の図形を削除する処理は、図１２に示したフローチャートにしたがって実行される。以下、各ステップごとに説明する。
【０１３７】
（ステップ１２０１）
メッシュスタックを空にする。
【０１３８】
（ステップ１２０１）
メッシュスタックに世界全体（全世界１）をメッシュとして入れる。
【０１３９】
（ステップ１２０３）
メッシュスタックが空か否かを判断し、空の場合には本処理を終了する。一方、空でない場合には次のステップに進む。なお、ここでは、前ステップにおいて、全世界１が入っているので次のステップに進む。
【０１４０】
（ステップ１２０４）メッシュスタックからメッシュを一つ取り出し、現メッシュとする。すなわち、ここでは全世界１が取り出される。
【０１４１】
（ステップ１２０５）
現メッシュと図形が重なっているか否かを判断し、重なっていない場合にはステップ１２０３に戻る。一方、重なっている場合には次のステップに進む。ここでは、全世界１は登録すべき図形ａと重なっているので、次のステップに進む。
【０１４２】
（ステップ１２０６）
現メッシュの所属図形数を減らす。ここでは、全世界１のメッシュデータの所属図形数を、図形ａの分として１つ減らす。
【０１４３】
（ステップ１２０７）
現メッシュが末端のメッシュであるか否かが判断され、末端メッシュである場合には、ステップ１２０９に進む。一方、末端メッシュでない場合には、ステップ１２０８に進む。ここで、全世界１がすでに４〜７のメッシュに分割されており、４〜７が末端メッシュであるとすると、現メッシュである全世界１は末端メッシュではないので、ステップ１２０８へ進む。
【０１４４】
（ステップ１２０８）
現メッシュを４分割した４つのメッシュをメッシュスタックに入れ、ステップ１２０４へ戻る。すなわち、ここでは、全世界１を４分割した４〜７のメッシュをメッシュスタックに入れ、ステップ１２０４へ戻る。そして、ステップ１２０４において、メッシュスタックからメッシュを順に一つずつ取り出して現メッシュとし、上記ステップ１２０５〜ステップ１２０７の処理を各メッシュについて行う。この例では、メッシュスタックからメッシュ７を取り出し、現メッシュとしてステップ１２０５へ進む。このメッシュ７は、図５に示したように、削除する図形ａと重なっているので、ステップ１２０６及びステップ１２０７に進み、ステップ１２０７でメッシュ７は末端メッシュであると判断され、ステップ１２０９に進む。
【０１４５】
（ステップ１２０９）
現メッシュの所属図形リストから図形を削除する。
【０１４６】
（ステップ１２１０）
現メッシュについて、後述する「メッシュの併合処理」がなされ、ステップ１２０３へ戻る。この例では、他のメッシュ６、５、４は、いずれも図形ａと重ならないので、ステップ１２０３〜ステップ１２０５を順次繰り返し、すべての末端メッシュのチェックが終了すると、ステップ１２０３でメッシュスタックが空になるので、本処理を終了する。結局、末端メッシュ７から図形ａが削除される。
【０１４７】
なお、後述する「メッシュの併合処理」において、現メッシュが併合されると、親メッシュ（全世界１）が現メッシュになるので、前記ステップ１２０９でメッシュ７の所属図形リストから削除された図形ａは、親メッシュ１からも削除され、親メッシュの所属図形数が一つ減少する。
【０１４８】
［３−２−５．データ領域における図形データの修正処理］
データ領域に記憶された図形データを修正する処理は、図１３に示したフローチャートにしたがって実行される。なお、修正の前後で、図形を同定する図形キーは不変である。以下、各ステップごとに説明する。
【０１４９】
（ステップ１３０１）
旧図形データを図形キーから検索する。
【０１５０】
（ステップ１３０２）
修正後の新図形データのためのデータ領域を確保する。
【０１５１】
（ステップ１３０３）
データ領域が確保できたか否かが判断され、データ領域が確保できた場合には、次のステップに進む。一方、データ領域が確保できない場合には、データ領域への新図形の登録はできず、この処理は終了する。
【０１５２】
（ステップ１３０４）
新図形データを確保したデータ領域にコピーする。
【０１５３】
（ステップ１３０５）
図形キー管理エリアに登録されている旧図形データへのポインタと新図形データへのポインタを置き換える。
【０１５４】
（ステップ１３０６）
新図形をメッシュに登録する。
【０１５５】
（ステップ１３０７）
新図形をメッシュに登録できたか否かが判断され、登録できた場合にはステップ１３０８へ進み、登録できなかった場合には、ステップ１３１０へ進む。
【０１５６】
（ステップ１３０８）
旧図形をメッシュから削除する。
【０１５７】
（ステップ１３０９）
図形データ格納場所にある旧図形データを消去して、本処理を終了する。
【０１５８】
（ステップ１３１０）
前記ステップ１３０７において、新図形をメッシュに登録できなかった場合には、登録処理の過程で変化したメッシュを元に戻して、新図形データを削除する。
【０１５９】
（ステップ１３１１）
図形キー管理エリアにおいて置き換えた新図形データへのポインタを旧図形データへのポインタに戻し、本処理を終了する。すなわち、本処理によって、結果的に修正後の新図形の登録ができなかった場合には、すべてのデータは元の状態に戻される。
【０１６０】
［３−２−６．メッシュの分割処理］
末端のメッシュに登録された図形数が一定数を越えた場合に行われるメッシュの分割処理は、図１４に示したフローチャートにしたがって実行される。以下、各ステップごとに説明する。
【０１６１】
（ステップ１４０１）
分割メッシュスタックを空にする。
【０１６２】
（ステップ１４０２）
分割メッシュスタックに現メッシュを入れる。
【０１６３】
（ステップ１４０３）
分割メッシュスタックからメッシュを一つ取り出し、親メッシュとする。
【０１６４】
（ステップ１４０４）
別途説明した所定の分割条件に照らして、親メッシュを分割して良いか否かが判断され、分割して良い場合には次のステップ１４０５に進む。一方、分割すべきでない場合には、ステップ１４１７に進み、分割メッシュスタックが空か否かが判断され、空の場合には本処理は終了し、空でない場合にはステップ１４０３へ戻る。
【０１６５】
（ステップ１４０５）
前記ステップ１４０４において、親メッシュを分割して良いと判断された場合には、そのメッシュを４分割する。
【０１６６】
（ステップ１４０６）
４分割された各子メッシュについてメッシュデータ領域を確保する。
【０１６７】
（ステップ１４０７）
すべての子メッシュについて、メッシュデータ領域が確保されたか否かが判断され、確保された場合には次のステップに進み、一方、４つのメッシュの内、いずれか一つでもメッシュデータ領域が確保されない場合には、ステップ１４０９に進む。
【０１６８】
（ステップ１４０８）
４分割されたすべてのメッシュについてメッシュデータ領域が確保された場合には、親メッシュに登録されている図形の内から一つの図形を選択する。
【０１６９】
（ステップ１４０９）
ステップ１４０７において、４つのメッシュの内、いずれか一つでもメッシュデータ領域が確保されない場合には、メッシュの４分割処理はできないので、確保されたメッシュデータ領域を元に戻し、本処理を終了する。
【０１７０】
（ステップ１４１０）
４分割されたメッシュから一つの子メッシュを選択する。
【０１７１】
（ステップ１４１１）
ステップ１４０８において選択された図形が、その子メッシュに重なるか否かが判断され、重なる場合にはステップ１４１２に進み、重ならない場合にはステップ１４１３に進む。
【０１７２】
（ステップ１４１２）
ステップ１４１１において図形がその子メッシュに重なると判断された場合には、その図形をその子メッシュに登録する。具体的には、子メッシュの所属図形数を増やし、所属図形リストに図形を加える。
【０１７３】
（ステップ１４１３）
ステップ１４１１において図形がその子メッシュに重ならないと判断された場合には、上記ステップ１４０７及びステップ１４１２の処理がすべての子メッシュについてなされたか否かが判断され、まだなされていない場合にはステップ１４１０に戻り、一方、すべての子メッシュについて終了している場合には、次のステップに進む。
【０１７４】
（ステップ１４１４）
親メッシュに登録されていたすべての図形について、ステップ１４１０〜ステップ１４１３の処理がなされたか否かが判断され、まだなされていない場合にはステップ１４０８に戻り、一方、すべての図形について終了している場合には、次のステップに進む。
【０１７５】
（ステップ１４１５）
上記のようにして、親メッシュに登録されていたすべての図形について処理が終了した後、親メッシュの所属図形リストのデータ領域を消去する。
【０１７６】
（ステップ１４１６）
４つの子メッシュを分割メッシュスタックに入れ、ステップ１４０３に戻る。
【０１７７】
［３−２−７．メッシュの併合処理］
末端のメッシュに登録された図形数が一定数以下になった場合に行われるメッシュの併合処理は、図１５に示したフローチャートにしたがって実行される。以下、各ステップごとに説明する。
【０１７８】
（ステップ１５０１）
現メッシュの親のメッシュを「親メッシュ」、現メッシュを含む親メッシュの４つの子メッシュを「子メッシュ」（４個）とする。
【０１７９】
（ステップ１５０２）
別途説明した所定の併合条件に照らして、４つの子メッシュを親メッシュに併合して良いか否かが判断され、併合して良い場合には次のステップ１５０３に進む。一方、併合すべきでない場合には本処理は終了する。
【０１８０】
（ステップ１５０３）
前記ステップ１５０２で親メッシュに併合して良いと判断された場合には、親メッシュにメッシュデータ領域を割り当てる。
【０１８１】
（ステップ１５０４）
子メッシュの一つを選択する。
【０１８２】
（ステップ１５０５）子メッシュの所属図形リストから図形を一つ選ぶ。
【０１８３】
（ステップ１５０６）
親メッシュの所属図形リストに、その図形がすでに含まれているか否かが判断され、含まれていない場合には次のステップに進み、一方、すでに含まれている場合には、ステップ１５０８に進む。
【０１８４】
（ステップ１５０７）
親メッシュの所属図形リストに図形を加える。
【０１８５】
（ステップ１５０８）
子メッシュに所属するすべての図形を処理したか否かが判断され、未処理の図形がある場合にはステップ１５０５へ戻り、すべての図形について処理が終了している場合には、次のステップに進む。
【０１８６】
（ステップ１５０９）
４つの子メッシュのすべてを処理したか否かが判断され、未処理の子メッシュがある場合にはステップ１５０４へ戻り、すべての子メッシュについて処理が終了している場合には、次のステップに進む。
【０１８７】
（ステップ１５１０）
親メッシュを現メッシュとし、ステップ１５０１へ戻る。
【０１８８】
［３−３．第１実施形態の効果］
前記の様な構成を有する第１実施形態は、次のような効果を有する。すなわち、固定メッシュからデータ密度によってメッシュを分割し、その大きさを変えるので、無駄なデータ領域が減り、主記憶装置上でデータを扱うことができる。また、４分木で分割を管理するので、メッシュへのアクセスがスムーズに実行でき、階層を下る検索により、無駄な条件判断を減らすことができる。さらに、データの股がりによって、末端メッシュだけでなく内メッシュにもデータを入れることができるので、メッシュ１つ当りのデータ数が減り、無駄なデータ領域を減らすことができる。
【０１８９】
また、メッシュの分割を無制限に進めると指数オーダーでデータ領域を消費するので、分割レベルの限界を設けることにより、有限なデータ領域を節約することができる。また、１メッシュ当りのデータ数が少ないときは、メッシュの分割を解消してメッシュを合併するので、データ密度に応じた分割レベルを保つことができる。さらに、メッシュの分割を解消した結果、使わなくなったデータ領域を再利用することができる。また、サブ図形の組合わせで構成される図形データの場合に、サブ図形単位でメッシュに所属させることとしたため、データ領域をさらに節約することができる。
【０１９０】
このように本実施形態の多次元データ管理装置によれば、データ領域を大幅に節約することができるので、計算機の主記憶上でデータを扱うことができ、高速なデータアクセスが可能となる。
【０１９１】
［３−４．第１実施形態の変形例］
第１実施形態では図１に示すように、メッシュ分割手段１２と分割反対手段１３、およびメッシュ併合手段１４と併合判定手段１５の両方を設けたが、いずれか一方の組み合わせのみを設けても良い。
【０１９２】
［４．第２実施形態］
第２実施形態は、前記第１実施形態と同様に４分木ノード、メッシュ状態データ、図形検索キーデータ、図形データを記憶領域上に配置し、利用する。第１実施形態と異なるのは、末端メッシュでない被分割メッシュの状態データにも所属図形リストを含める点である。すなわち、４分木構造において被分割メッシュに対応する中間ノードについても図形データを登録することにより、末端メッシュに登録された図形だけでなく、被分割メッシュに登録された図形をも検索対象とするものである。また、被分割メッシュにも図形を登録する手法としては、末端メッシュを分割する際に子メッシュに登録するのが適切でない図形を親メッシュに残すようにしたものである。
【０１９３】
このような第２実施形態においては、前記第１実施形態における図形のメッシュへの登録、メッシュの４分割、図形のメッシュからの削除、およびメッシュの併合の手法が次のように変更される。
【０１９４】
第２実施形態では、被分割メッシュの状態データにも所属図形リストを含めるが、そのリストに実際に図形が登録されている状態は、次のようなメッシュ分割フローの処理によって作り出される。前記第１実施形態とは異なるこの分割処理の特徴は、図形の所属を親メッシュから子メッシュに移す際に、親メッシュに所属するすべての図形を無条件に移すのではなく、所定の条件に照らして子メッシュに移すのが適切と判断された図形のみを移し、適切でないと判断された図形については親メッシュに所属させたままにしておく点である（図１６、図５及び図６を参照）。
【０１９５】
ここで、「所定の条件（図形の登録先変更条件）に照らして図形を子メッシュに移して良いか？」という判定に係る所定の条件とは、無条件に子メッシュに移した場合に比較して１つの図形あたりの複数メッシュへの重複登録を抑制するような条件であり、例えば次のようなものである。なお、これらの条件は単独で用いても良いし、複数を併用しても良い。
【０１９６】
（ａ）図形がその親メッシュを完全に含んでいない。
【０１９７】
（ｂ）図形が重なっている子メッシュが２つ以下である。
【０１９８】
（ｃ）図形ごとに重複登録メッシュ数の上限が定められており、子メッシュへの登録（移動）を行っても重複登録数が上限以下である。
【０１９９】
（ｄ）図形の種類・大きさなどの属性によって登録して良い最小のメッシュの大きさが定められており、子メッシュの大きさがその最小メッシュの大きさ以上である。
【０２００】
これらの条件によって、メッシュ分割における図形の登録メッシュの増加が抑制されると共に、子メッシュに登録を変更する図形の数が減少するため、分割処理自体も高速化される。例えば、図形の面積（大きさ）・形状に応じて予め登録すべき最小のメッシュを決めておき、条件（ｄ）を採用して判定を行いつつ図形の登録を進めれば、メッシュの分割が進んでも１つの図形はその図形の面積（大きさ）に比例する数以下の、その図形に予め定められた最小のメッシュ以上に大きさのメッシュにのみ登録される。これによって、過剰な重複登録を抑制して記憶領域を節約すると共に、検索処理の速度の低下を防止することができる。
【０２０１】
例えば、矩形の形状の図形に関しては、メッシュの短辺がその図形の短辺より長い最も小さなメッシュを、その図形を登録して良い最小のメッシュとして設定するという方法がある。この方法に従えば、細長い矩形は長手方向に小さな多数のメッシュに所属するので、検索時にそのメッシュが選択された場合に最終的な検索結果として選ばれる割合が高まって検索効率が向上する。いたずらに上位の大きなメッシュに属させておけば、メッシュが選ばれる割合が大きい反面その図形が最終的な検索結果として選ばれる割合が減少し、検索効率の悪化を招く。この方法では、予測可能な範囲である程度多数のメッシュに重複登録されるが、無制限に著しく記憶領域を浪費することはなく、検索効率が劣化することはない。縦横の長さが極端に違わない矩形に関しては、最も重複が多くなっても数個のメッシュに所属するだけで済む。この方法を採用した場合の長所は、検索において所属メッシュが選択された場合に、最終的な検索結果としてその図形が採用される割合を細長い矩形とそうでない矩形で極端に違わないようにする効果が得られることである。
【０２０２】
細長い図形の場合と類似の効果は、線分を扱う場合にも得られる。例えば、メッシュの短辺が線分の長さのｎ分の１以上である最小のメッシュをその線分を登録して良い最小のメッシュとする方法が考えられる。その線分は、多くとも４ｎ個よりは少ない数のメッシュに重複登録されるに過ぎない。
【０２０３】
（ｃ）を採用した場合、１つの図形について重複登録メッシュ数が制限されるので、記憶領域の節約には非常に有効である。しかも、所属メッシュの大きさにはばらつきがあっても良いから、重複登録数の上限以下であれば、図形の密度に応じて分割されていくので、さらに細かなメッシュへの登録を進めることができ、検索効率の向上を図ることができる。
【０２０４】
［４−１．第２実施形態の構成］
図１７は、本発明の第２実施形態の構成を示す機能ブロック図である。すなわち、本実施形態の多次元データ検索装置は、第１実施形態に示した多次元データ管理装置の構成要素に加えて、前記メッシュデータ登録削除手段１１およびメッシュ分割手段１２に関連して、メッシュデータ再登録手段１６と再登録メッシュ判定手段１７が設けられていることを特徴とする。このメッシュデータ再登録手段１６は、末端メッシュの分割時において、前記各メッシュのうち、前記木構造の末端のノードに対応する分割によって生じた子メッシュと、前記末端ノードの親ノードに対応する分割によって生じた親メッシュいずれかに多次元データを登録しなおすものである。また、再登録メッシュ判定手段１７は、末端メッシュの分割時において、１つの図形あたりの複数メッシュへの重複登録を抑制する条件に従って、前記多次元データを分割によって生じた子メッシュと分割によって生じた親メッシュのいずれに登録しなおすかを判定する。
【０２０５】
前記再登録メッシュ判定手段１７としては、
（ａ）前記多次元データがその親メッシュを完全に含んでいないことを重複登録を抑制する条件とするもの、
（ｂ）前記多次元データが重なっている子メッシュ数が予め設定された数以下であることを重複登録を抑制する条件とするもの、
（ｃ）前記多次元データごとに重複メッシュ数の上限が定められており、子メッシュへの登録を行っても重複登録数が上限以下であることを重複登録を抑制する条件とするものが使用される。
【０２０６】
［４−２．第２実施形態の作用］
以下前記のような構成を有する第２実施形態の多次元データ管理装置の作用並びに、これに対応する多次元データ管理方法について、図１６〜１７の木構造とメッシュとの関係を示す図、および図１８のフローチャートにしたがって、中間ノードに図形データを登録する第１の方法について説明する。
なお、この中間ノードに図形データを登録する第１の方法は、第１実施形態において説明した「末端メッシュの分割処理」において、子メッシュに登録するのが適切でない図形を、中間ノードに相当する親メッシュに残すようにするものである。また、図１８に示したフローチャートは、図１４に示した［メッシュの分割処理］フローに一部の処理（ステップ１８１８）を追加したものなので、この変更部分について説明する。
【０２０７】
（ステップ１８１８）
図１８に示したように、ステップ１８０８において、親メッシュに登録されている図形の内から選択された一つの図形について、別途説明した図形の登録先変更条件に照らして、図形を子メッシュに移して良いか否かが判断され、子メッシュに移して良い場合には、ステップ１８１０に進む。その結果、ステップ１８１０〜ステップ１８１２の処理によって、図形が子メッシュに登録される。一方、ステップ１８１８において、図形を子メッシュに移すことは適切でないと判断された場合には、ステップ１８１４に進む。その結果、その図形は子メッシュには登録されず、親メッシュに登録されたままの状態に保持される。そして、ステップ１８１４において、親メッシュに所属するすべての図形について、ステップ１８１８、ステップ１８１０〜ステップ１８１３の処理がなされたか否かが判断される。
【０２０８】
［４−３．第２実施形態の変形例］
第２実施形態では、図１７に示すように、メッシュ分割手段１２と分割反対手段１３、およびメッシュ併合手段１４と併合判定手段１５を設けたが、これらの一方の組のみを設けても良いし、両者を省くこともできる。
【０２０９】
［５．第３実施形態］
第３実施形態は、前記第２実施形態と同様に被分割メッシュにも図形を登録するものであるが、末端メッシュの分割時ではなく、図形の登録時に適切なメッシュを選んで登録するものである。すなわち、第３実施形態では、被分割メッシュの状態データにも所属図形リストを含めるが、第２実施形態とは異なって、その状態は図形の登録処理の過程によって直接に作成され、分割という付随処理の結果生じるものではない。
【０２１０】
なお、この第３実施形態においては、メッシュ分割処理は再帰的でなくても良く、親メッシュからの登録図形の移動を伴わない形で、単に４つの子メッシュを作成し、子メッシュの所属図形リストは空のままにしておくという形でも実施できる。もちろん、第２実施形態のように所定の条件を吟味した上で分割し、さらに所定の条件を満たす図形を子メッシュに移しても良い。
【０２１１】
ところで、この第３実施形態において、「所定の条件（図形の登録先変更条件）に照らして現メッシュに図形を登録して良いか？」という判定に係る「所定の条件」とは、例えば次のようなものである（図１９及び図２０参照）。
（ａ）図形が重なり合っている現メッシュの子メッシュが３個以上である。
（ｂ）図形の種類、大きさなどの属性によって登録して良い最小のメッシュの大きさが決まっており、現メッシュの子メッシュの大きさがその最小のメッシュ未満である。
（ｃ）図形の種類、大きさなどの属性によって登録して良い最大のメッシュの大きさが決まっており、現メッシュの親メッシュの大きさがその最大のメッシュを越えている。
（ｄ）図形ごとに重複登録メッシュ数の上限が定められており、子メッシュへの登録を行うと重複登録数の上限を越えてしまう。
（ｅ）図形の面積が現メッシュのα％を占める。面積のない線分などの場合には、現メッシュの中心からの距離がメッシュの短辺の１／２の長さのβ％以内である。
【０２１２】
これらの条件は単独で用いても良いし、複数を併用してそのすべてが成立したら条件を満足したものと判定しても良い。また、複数を併用していずれか１つが成立したら条件を満足したものとしても良い。
【０２１３】
例えば、（ａ）と（ｅ）を併用して両方が成立したら条件を満足するとして使用した際に、αが例えば１０％というような値に設定されているとすれば、図１９に示したように、すべての子メッシュ２−４に重なっているが、現メッシュ１に比較して大きさが非常に小さい図形Ｆ１は（ｅ）の条件を満たさないために現メッシュよりもさらに小さなメッシュに所属するように促される。一方、図２０に示したように、メッシュに比較してある程度大きい面積の図形Ｆ２、すなわち図形の面積は現メッシュの１０％以上あるが、現メッシュの周辺に存在する図形Ｆ２は（ａ）の条件を満たさないためにさらに小さなメッシュに所属するように促される。
【０２１４】
このようにして、メッシュの中心を含みかつメッシュ中のある程度の面積を占めるような状況でのみ図形がメッシュに登録されるので、後述する最近傍図形検索手続きにおいて、図形を探索する範囲が狭められて検索が効率化されるという効果が得られる。
【０２１５】
また、（ｂ）の条件を図形ごとに適切に設定することにより、図形がその大きさに比較してあまりに大きなメッシュに所属して検索効率を低下させることを防ぐことができる。さらには、（ｃ）の条件を図形ごとに適切に設定することにより、図形がその大きさに比較してあまりに小さな多数のメッシュに重複登録されることを避け、検索の効率化および記憶領域の節約を図ることができる。
【０２１６】
なお、（ｂ）および（ｅ）の条件は、図形の属性によって一方的に決まる場合ばかりでなく、現メッシュの所属図形数などのメッシュ側の状況を吟味して判定するなど、より柔軟かつ多様な変形例が種々考えられる。
【０２１７】
上述のように、第３実施形態は、前記登録に係る所定の条件として図形の属性に応じた条件を設定することによって、図形のメッシュへの重複登録を制限あるいは抑制する効果を得ると共に、検索手続きの効率化を図ることを可能にするものである。
【０２１８】
１つの木構造に対応させたデータ管理方法及び装置において、木構造を構成する各ノード部分に種々の図形を登録する際に、同一の手続きによって図形ごとやその種類ごとに異なる条件を採用することを特徴とするものであり、これによって、従来技術のｑｕａｄ−ｔｒｅｅ法やその変形例のように、中間ノードに図形を登録させる場合にどの図形であっても画一的な分割手法を使用していたものに比較して、より優れた記憶領域の有効利用と検索処理の高速化が可能になる。
【０２１９】
［５−１．第３実施形態の構成］
図２１は、本発明の第３実施形態の構成を示す機能ブロック図である。すなわち、本実施形態の多次元データ検索装置は、第１実施形態に示した多次元データ管理装置の構成要素に加えて、前記メッシュデータ登録削除手段１１およびメッシュ分割手段１２に関連して、末端あるいは中間メッシュへのデータ登録手段１８と登録位置判定手段１９を備えていることを特徴とする。データ登録手段１８は、前記各メッシュのうち、前記木構造の末端のノードに対応する末端メッシュと、前記末端ノードの親ノードに対応する中間メッシュの少なくとも一方に多次元データを登録する。登録位置判定手段１９は、多次元データの登録時において、登録する多次元データの状態に従って、前記多次元データを末端メッシュと中間メッシュのどこに登録するかを判定する。
【０２２０】
前記登録位置判定手段１９としては、
（ａ）前記多次元データが重なり合っている子メッシュ数に応じて登録するメッシュを選択するもの、
（ｂ）前記多次元データによって登録すべきメッシュの大きさの限度が決まっており、このメッシュの大きさの限度に従って前記多次元データを登録するメッシュを選択するもの、
（ｃ）前記多次元データごとに重複登録メッシュ数の限度が定められており、この限度に従って前記多次元データを登録するメッシュを選択するもの、
（ｄ）前記多次元空間内における前記多次元データの大きさと、前記多次元空間内における所定のメッシュの大きさとの比較から、前記多次元データを登録するメッシュを選択するもの、が使用できる。
【０２２１】
［５−２．第３実施形態の作用］
以下前記のような構成を有する第３実施形態の多次元データ管理装置の作用並びに、これに対応する多次元データ管理方法について、図１９，２０によって、その条件を説明すると共に、図２２に示したフローチャートにしたがって、中間ノードに図形データを登録する第２の方法について説明する。なお、この中間ノードに図形データを登録する第２の方法は、第２実施形態と異なり、図形の登録時に適切なメッシュを選んで登録するものである。以下、各ステップごとに説明する。
【０２２２】
（ステップ２２０１）
メッシュスタックを空にする。
【０２２３】
（ステップ２２０２）
メッシュスタックに世界全体（全世界１）をメッシュとして入れる。
【０２２４】
（ステップ２２０３）
メッシュスタックからメッシュを一つ取り出し、現メッシュとする。
【０２２５】
（ステップ２２０４）
現メッシュと図形が重なっているか否かを判断し、重なっていない場合にはステップ２２０３に戻る。一方、重なっている場合には次のステップに進む。
【０２２６】
（ステップ２２０５）
現メッシュの所属図形数を増やす。
【０２２７】
（ステップ２２０６）
後述する図形の登録先変更条件に照らして、現メッシュに図形を登録して良いか否かが判断され、登録して良い場合には、次のステップ２２０７に進む。一方、現メッシュに図形を登録することが適切でないと判断された場合には、ステップ２２０９に進む。
【０２２８】
（ステップ２２０７）
現メッシュの所属図形リストに図形を加える。
【０２２９】
（ステップ２２０８）
メッシュスタックが空か否かを判断し、空の場合には本処理を終了する。一方、空でない場合にはステップ２２０３に戻る。
【０２３０】
（ステップ２２０９）
ステップ２２０６において、現メッシュに図形を登録することが適切でないと判断された場合には、現メッシュが末端のメッシュであるか否かが判断され、末端メッシュである場合には、ステップ２２１０に進む。一方、末端メッシュでない場合には、ステップ２２１２に進む。
【０２３１】
（ステップ２２１０）
ステップ２２０９において現メッシュが末端のメッシュである場合には、メッシュ分割処理によって、現メッシュの４分割を試みる。
【０２３２】
（ステップ２２１１）
現メッシュが４分割できたか否かが判断され、分割できた場合にはステップ２２１３に進み、分割できない場合にはステップ２２０７に戻る。
【０２３３】
（ステップ２２１２）
ステップ２２０９において現メッシュが末端のメッシュでない場合には、現メッシュを４分割する。
【０２３４】
（ステップ２２１３）
ステップ２２１１及びステップ２２１２において現メッシュを４分割した場合には、４分割したメッシュをメッシュスタックに入れ、ステップ２２０３へ戻る。
【０２３５】
［５−３．第３実施形態の変形例］
第３実施形態では、図２１に示すように、メッシュ分割手段１２と分割反対手段１３、およびメッシュ併合手段１４と併合判定手段１５を設けたが、これらの一方の組のみを設けても良いし、両者を省くこともできる。
【０２３６】
［６．第４実施形態］
矩形検索とは、与えられた矩形の枠内にある図形を全て探し出すことをいう。具体的には、まず、世界座標範囲内の矩形とメッシュを与えたとき、矩形とメッシュの重なりの有無が判定され、矩形と重なりを有するメッシュが検索される。次に、そのメッシュに含まれる図形と矩形の領域の重なりの有無が判定され、与えられた矩形の枠内にある図形が全て検索される。
【０２３７】
［６−１．第４実施形態の構成］
図２９は、本発明の第４実施形態の構成を示す機能ブロック図である。すなわち、本実施形態の多次元データ検索装置は、前記各実施形態に示した多次元データ管理装置の構成要素に加えて、前記コンピュータの記憶領域内に蓄積されている多次元データを管理する装置が、前記多次元空間内における指定された範囲を対象とし、この指定された範囲内に属する多次元データを検索する範囲検索手段２０を含むことを特徴とする。
【０２３８】
この範囲検索手段２０は、入力装置２から入力されたメッシュの座標と矩形の座標を使って、メッシュと矩形の領域が重なっているか否かを判定するメッシュ／矩形領域重なり判定手段２０１と、図形データの座標と矩形の座標を使って、図形が矩形に入っているか否かを判定する図形／矩形所属判定手段２０２と、データ領域上に、固定パラメータを格納したり、初期４分木（根ノードしかない４分木）を作成したり、図形キー管理領域を構成する際にデータ領域を初期化するデータ領域初期化手段２０３と、与えられた一点を含む末端メッシュを検索するメッシュ検索手段２０４とを備えている。
【０２３９】
この範囲検索手段２０による検索結果は、前記出力装置３に出力される。すなわち、本実施形態においては、前記検索結果は、入力装置２および出力装置３において、検索を使用する側が用意したデータ領域に検索結果を書き込むことにより実現される。例えば、矩形検索の場合、矩形内にある図形のデータ格納領域の場所を指すポインタのリストを返し、また、最近傍図形検索の場合は、図形のデータ領域を指すポインタと距離と最近傍点を返すように構成されている。なお、前記メッシュ／矩形枠重なり判定手段１２においては、矩形にすっぽり含まれるメッシュや矩形をすっぽり含むメッシュは、「重なっている」と言わないこととする。さらに、メッシュ検索手段１６においては、与えられた一点がメッシュの境界上に乗っているときは、存在するならば右上のメッシュ、上のメッシュ、右のメッシュ、下のメッシュ、左のメッシュに含まれるとする。メッシュ／矩形領域重なり判定手段１１とメッシュ／矩形枠重なり判定手段１２とによって、世界座標範囲内の矩形とメッシュを与えたとき、矩形とメッシュの重なりを、次の４つの場合について判定することができる。
【０２４０】
すなわち、（ａ）メッシュが矩形を含む、（ｂ）メッシュが矩形に含まれる、（ｃ）メッシュと矩形の重なりがある、（ｄ）メッシュと矩形の重なりがないの４つの場合について判定がなされる。したがって、この手段を繰り返し使うことによって、矩形と重なりのあるメッシュを全て探し出すことができる。また、前記（ａ）が判定できると、他のメッシュを判定する必要がなくなり、４分木で言えば、横方向に検索を広げなくて済む。さらに（ｂ）が判定できると、そのメッシュが分割されていたとき、分割された４つのメッシュを判定する必要がなくなる。４分木で言えば、縦方向に検索を進めなくて済むというメリットがある。
【０２４１】
［６−２．第４実施形態の作用］
以下前記のような構成を有する第４実施形態の多次元データ管理装置の作用並びにこれに対応する多次元データ管理方法について、図２３によってそ木構造を説明すると共に、図２４〜２８のフローチャートに従って説明する。
【０２４２】
［６−２−１．中間メッシュにも末端メッシュにも図形を登録する場合の矩形検索］
上記第２実施形態及び第３実施形態において説明した中間メッシュにも図形を登録する場合の矩形検索は、図２５及び図２６に示したフローチャートにしたがって実行される。以下、各ステップごとに説明する。
【０２４３】
まず、図２５に示したフローチャートは、検索する矩形にかかっているすべてのメッシュを探し出す処理の流れを示したものである。
【０２４４】
（ステップ２５０１）
検索する矩形及び検索結果格納図形リストをセットする。すなわち、検索する矩形のセットは、矩形の左下と右上の座標をセットすることによりなされ、また、検索結果格納図形リストのセットは、記憶領域のポインタをセットすることによりなされる。なお、この検索する矩形と検索結果格納図形リストは、矩形検索を行なう側から与えられる。
【０２４５】
（ステップ２５０２）
探し出したメッシュリストを入れておく空のメッシュリストを用意する。
【０２４６】
（ステップ２５０３、ステップ２５０４）
処理すべきメッシュの順番を覚えておくためのメッシュスタックを空にして用意し、まず世界全体のメッシュ１をこのスタックに入れる。
【０２４７】
（ステップ２５０５）
スタックが空か否かが判断され、スタックが空であれば、図２６に示す図形が矩形に入っているか否かの検索処理へ進む。このとき、矩形と重なりのある中間メッシュと末端メッシュのリストができている。一方、スタックが空でなければ、次のステップ２５０６に進む。この例では、検索を始めた直後であり世界全体のメッシュ１がスタックにあるので、ステップ２５０６に進む。
【０２４８】
（ステップ２５０６）
スタックから１つメッシュを取り出す。この例では、世界全体のメッシュ１が取り出され、スタックは空の状態になる。
【０２４９】
（ステップ２５０７）
取り出したメッシュが矩形と重なっているか否かを判断し、重なっていないならば、スタックが空か否かの判断ステップ２５０５へ戻る。一方、重なっているならば、次のステップ２５０８へ進む。ここでは、世界全体のメッシュ１と矩形の重なりを判断し、重なっているのでステップ２５０８へ進む。なお、本実施形態においては、メッシュの座標を４分木で管理し、また、メッシュ番号を規則的に付けていることから、メッシュの座標を容易に計算できるため、メッシュの座標と矩形の座標からメッシュが矩形と重なっているか否かの判断は容易である。
【０２５０】
（ステップ２５０８）
メッシュをメッシュリストに加える。ここでは、世界全体のメッシュ１だけのメッシュリストができる。
【０２５１】
（ステップ２５０９）
メッシュが末端メッシュか否かを判断し、末端メッシュならばステップ２５０５へ戻る。一方、末端メッシュでなければ４分割された子メッシュがあるので、それらについても調べる必要があるため、次のステップ２５１０へ進む。本例では、世界全体メッシュ１は末端メッシュでないので、ステップ２５１０に進む。なお、メッシュが末端メッシュか否かの判断は、４分木から容易に分かる。
【０２５２】
（ステップ２５１０）
メッシュを４分割した４つの子メッシュをスタックに入れ、ステップ２５０５に戻る。本例では、世界全体の子メッシュ７、６、５、４をスタックに入れる。スタック内は、上から７、６、５、４と並ぶ。本例では、ステップ２５０５での判断は、スタックは空ではないので、ＮＯとなり、ステップ２５０６へ進む。
【０２５３】
以下、図２３に示した例に基づいて、本処理をさらに詳しく説明する。
【０２５４】
ステップ２５０６においてスタックから１つ取り出す場合、末尾のメッシュ４が取り出され、スタックは７、６、５になる。ここで、図２３に示したように、メッシュ４と矩形は重なっているので（ステップ２５０７）、メッシュリストにメッシュ４を加える（ステップ２５０８）。その結果、メッシュリストは１、４になる。続いて、ステップ２５０９において、メッシュ４は末端メッシュなのでステップ２５０５へ戻る。
【０２５５】
ステップ２５０５において、まだスタックは空でないので、ステップ２５０６でスタックから次のメッシュを１つ取り出す。ここではメッシュ５が取り出され、スタックは、７、６になる。ここで、図２３に示したように、メッシュ５と矩形は重ならないので（ステップ２５０７）、ステップ２５０５に戻る。
【０２５６】
ステップ２５０５に戻ってもまだスタックは空でないので、スタックから次のメッシュを１つ取り出す。ここではメッシュ６が取り出され、スタックは７のみになる。ここで、図２３に示したように、メッシュ６と矩形は重なっているので、メッシュリストにメッシュ６を加える（ステップ２５０８）。その結果、メッシュリストは、１、４、６になる。続いて、ステップ２５０９において、メッシュ６は末端メッシュでないので、ステップ２５１０でメッシュの６の４つの子メッシュ２７、２６、２５、２４をスタックに入れた後、ステップ２５０５に戻る。その結果、スタックは７、２７、２６、２５、２４になる。
【０２５７】
ステップ２５０６において、次にスタックから取り出されるのは２４であるが、これは矩形と重なりがない（ステップ２５０７）ので、再びステップ２５０５に戻る。次にメッシュ２５が取り出されるが、図２３に示したように、このメッシュ２５は矩形と重なりがある（ステップ２５０７）ため、メッシュ２５はメッシュリストに加えられる（ステップ２５０８）。その結果、メッシュリストは１、４、６、２５になる。また、このメッシュ２５は末端メッシュなので（ステップ２５０９）、このままステップ２５０５に戻る。この時点で、スタックは７、２７、２６になっている。
【０２５８】
さらに、ステップ２５０６において、スタックからメッシュ２６が取り出されるが、図２３に示したように、このメッシュ２６は矩形と重ならない（ステップ２５０７）。続いて、ステップ２５０６において、スタックからメッシュ２７が取り出されるが、このメッシュ２７も矩形と重ならない（ステップ２５０７）。この時点で、スタックは７になる。
【０２５９】
次に、ステップ２５０６において、スタックからメッシュ７を取り出すと、スタックは空になる。また、図２３に示したように、このメッシュ７も矩形と重ならない（ステップ２５０７）。ここでステップ２５０５へ戻るとスタックが空なので、ＹＥＳの方へ進む（すなわち、図２６に示す図形が矩形に入っているか否かの検索処理へ進む）。なお、この時、メッシュリストには１、４、６、２５が入っており、これが矩形にかかっている全メッシュのリストである。
【０２６０】
図２６に示したフローチャートは、図２５で挙げられたメッシュリストのメッシュを１つずつ調べて、図形が矩形に入っているか否かを検索する処理の流れを示したものである。
【０２６１】
（ステップ２６０１）
メッシュリスト内のすべてのメッシュに対して、矩形内に含まれる図形を集める処理を行ない、すべてのメッシュに対してこの処理が終わっている場合には、矩形検索は終了する。一方、未処理のメッシュが残っている場合には、次のステップ２６０２へ進む。
【０２６２】
（ステップ２６０２）
まだ図形を探していない未処理のメッシュをメッシュリストから１つ選ぶ。本例では、メッシュリストに１、４、６、２５が入っているので、まずメッシュ１から始める。
【０２６３】
（ステップ２６０３）
メッシュに登録されているすべての図形に対して、後述するステップ２６０４〜ステップ２６０７の処理が終了しているならば、ステップ２６０１に戻る。一方、未処理の図形があれば、次のステップ２６０４に進む。本例では、メッシュ１には図形が１つもないので、処理済みとみなされ、ステップ２６０１に戻る。次に、ステップ２６０２においてメッシュ４が選ばれる。
【０２６４】
（ステップ２６０４）
メッシュに登録されている図形の中から未処理の図形を１つ選ぶ。ここでは、図２３に示したように、メッシュ４の図形ｃを選ぶ。
【０２６５】
（ステップ２６０５）
ステップ２６０４において選んだ図形がすでに検索結果格納図形リストに入っているか否かが判断され、入っているならば何もせずにステップ２６０３に戻る。一方、検索結果格納図形リストに入っていなければ、次のステップ２６０６に進む。本例では、検索結果格納図形リストは初期時は空であり、図形ｃは入っていない。したがって、ステップ２６０６に進む。なお、この処理は、図形データに調査済マークを付けることによっても実現できる。
【０２６６】
（ステップ２６０６）
ステップ２６０４において選んだ図形が矩形に入っているか否かが判断され、入っていれば、次のステップ２６０７に進む。一方、入ってなければステップ２６０３へ戻る。本例の図形ｃは矩形に入っているので、ステップ２６０７に進む。なお、この条件判断は行わなくてもよいこともある。つまり、矩形に入っているか否かに関係なく図形リストに加える場合もある。図形表示を行なう場合、ディスプレイの外の図形を表示してもまったく見えないので、表示について影響ないからである。グラフィック表示が大変高速ならばこの判断を省くことは有効である。
【０２６７】
（ステップ２６０７）
検索結果格納図形リストに図形データポインタを加え、その後ステップ２６０３に戻る。その結果、図形ｃが検索結果格納図形リストに加わる。ここでは図形ｃだけの図形リストができる。
【０２６８】
以下、図２３に示した例に基づいて、本処理をさらに詳しく説明する。
【０２６９】
すなわち、図形ｃが検索結果格納図形リストに加えられた後、ステップ２６０３に戻る。図２３に示したように、メッシュ４にはさらに図形ｄがあるので、ステップ２６０４に進み、この図形ｄが選ばれる（ステップ２６０４）。次に、ステップ２６０５において、図形ｄは検索結果格納図形リストにないと判断され、ステップ２６０６に進む。ここで、図形ｄは矩形に入っているので、検索結果格納図形リストに加えられる（ステップ２６０７）。その結果、検索結果格納図形リストは、ｃ、ｄになる。
次に、ステップ２６０３に戻り、メッシュ４に登録されているすべての図形についての処理が終了したと判断され、さらにステップ２６０１に戻る。ステップ２６０１において、まだメッシュ６と２５について処理が済んでいないので、ステップ２６０２に進み、本例ではメッシュ６を選ぶ。図１６及び図２３に示したように、このメッシュ６には図形ｈだけが登録されている。ステップ２６０４において、この図形ｈが選ばれる。
【０２７０】
次に、ステップ２６０５において、図形ｈは検索結果格納図形リストにないと判断され、ステップ２６０６に進む。ここで、図形ｈは矩形に入っているので、検索結果格納図形リストに加えられる（ステップ２６０７）。その結果、検索結果格納図形リストは、ｃ、ｄ、ｈになる。
次に、ステップ２６０３に戻り、メッシュ６に登録されているすべての図形についての処理が終了したと判断され、ステップ２６０１に戻る。ステップ２６０１において、まだメッシュ２５について処理が済んでいないので、ステップ２６０２に進み、メッシュ２５が選ばれる。図１６及び図２３に示したように、このメッシュ２５には未処理の図形ｄ、ｉがあるので（ステップ２６０３）、ステップ２６０４に進む。なお、図形ｈは、図１６に示したように、中間メッシュであるメッシュ６に登録されており、メッシュ２５には登録されていないので、ここでは検索の対象とはならない。
【０２７１】
ステップ２６０４において図形ｄが選ばれるが、この図形ｄはすでに検索結果格納図形リストにあるので、ステップ２６０３に戻る。一方、図形ｉは検索結果格納図形リストにないので（ステップ２６０５）、ステップ２６０６に進む。このステップ２６０６において、図形ｉは矩形に入っていないので、ステップ２６０３に戻る。このようにして、メッシュ２５内のすべての図形の処理が終わったので、ステップ２６０１に戻る。
【０２７２】
そして、メッシュリスト内のすべてのメッシュに対して処理が終わったので、本処理を終了する。この時点で、検索結果格納図形リストは、図形ｃ、ｄ、ｈとなる。
【０２７３】
［６−２−２．サブ図形を扱うとき］
表示側の都合上、図形が複数の構成要素からなることがある。一般に、図形は数種類の複数の単純な図形（サブ図形）から構成される。例えば、配電線は、複数の線分の集まりである。この場合、表示側は、配電線を１つ１つの線分に分けて管理しない。１つの図形として扱う方が人間の感覚に合っているからである。表示の上でも、線分を線分の数だけ描画することを繰り返すよりも、線分の集まりとして一度に表示する方が効率が良い。このようなサブ図形で構成される図形を「スーパー図形」と呼ぶ。
【０２７４】
１つの図形データが複数のサブ図形から構成されている場合、図形キー（ＩＤ）はスーパー図形に対してのみ１つだけ発番される。また、４分木のメッシュデータの所属図形リストは、図形データではなくサブ図形のデータ領域を指す。ただし、サブ図形のデータ領域を指してはいるが、元のスーパー図形がどれか分かるようにサブ図形を指すポインタをつくる。例えば、サブ図形を指すのに、元のスーパー図形のデータ領域の場所と、そこからのサブ図形のデータ領域へのオフセットを対にして、サブ図形へのポインタとする。このようにポインタを作ると、サブ図形も元のスーパー図形も分かる。このポインタを使ってメッシュへの登録はサブ図形単位に行なうことができる。
【０２７５】
このようにサブ図形単位に登録することは、後述する最近傍検索で利益がある。その理由は、複数の単純な図形（サブ図形）からなる図形は、通常大きな図形になることが多く、複数のメッシュにまたがる場合が多い傾向があるからである。例えば、２つのサブ図形Ａ，Ｂ（２本の線分）からなるスーパー図形Ａを例に考える。なお、線分Ａ，Ｂはそれぞれたった１つのメッシュｍ、ｎにしか登録されていないとする。しかし、スーパー図形Ａから見ると、この図形は２つのメッシュｍ、ｎにまたがっていることになる。
【０２７６】
ここで、矩形にはちょうどスーパー図形Ａしか存在せず、最近傍検索を行なう中心点がメッシュｍにあるとする。サブ図形に分けないでスーパー図形単位で登録している場合には、スーパー図形Ａがメッシュｍに登録されているということしか情報はなく、線分Ａ，Ｂがどのように位置しているかは分からないため、中心点からの距離計算を行うには、線分Ａ，Ｂ両方に対して行なうことになる。すなわち、スーパー図形Ａが最近傍図形であることを得るのに、２回線分に対する距離計算を行なわねばならない。
【０２７７】
一方、サブ図形に分けて登録すると、メッシュｍには線分Ａのみが登録されていて、線分Ｂは登録されていないので、距離計算は線分Ａに対してだけ行われる。この距離を半径とする円に他のメッシュが入ってなければ、線分に対する距離計算を１回するだけで最近傍図形であることを得る。最近傍図形を返すときは、サブ図形Ａの元のスーパー図形Ａを返す。なぜなら、もともと表示側はスーパー図形単位でデータを与えているからである。
【０２７８】
このようなサブ図形を扱う場合に、上記矩形検索処理で変わるところを述べる。すなわち、図２６において、ステップ２６０３、ステップ２６０４、ステップ２６０６の「図形」という言葉は「サブ図形」と変わる。また、図２５のステップ２５０１，図２６のステップ２６０５の「検索結果格納図形リスト」は、スーパー図形のリストである。さらに、ステップ２６０５の条件は「そのサブ図形が検索結果格納スーパー図形リスト内のスーパー図形のサブ図形であるか」と書き直し、また、ステップ２６０７の図形データポインタは、スーパー図形のポインタと書き直す。
【０２７９】
［６−２−３．末端メッシュにのみ図形を登録する場合の矩形検索］
図２５及び図２６に示した「中間メッシュにも末端メッシュにも図形を登録する場合の矩形検索」に対して、「末端メッシュに図形を登録する場合の矩形検索」は、図２８に示したフローチャートにしたがって実行される。なお、この処理の流れは図２５に類似しているので（図２８のステップ２８０１〜ステップ２８０７は、図２５のステップ２５０１〜ステップ２５０７と同じ）、以下、相違点について説明する。
【０２８０】
（ステップ２８０７）
取り出したメッシュが矩形と重なっているか否かを判断し、重なっていないならば、スタックが空か否かの判断ステップ２８０５へ戻る。一方、重なっているならば、次のステップ２８０８へ進む。
【０２８１】
（ステップ２８０８）
メッシュが末端メッシュか否かを判断し、末端メッシュならばステップ２８０９へ進み、一方、末端メッシュでなければ４分割された子メッシュがあるので、それらについても調べる必要があるため、次のステップ２８１０へ進む。
【０２８２】
（ステップ２８０９）
メッシュをメッシュリストに加え、ステップ２８０５に戻る。
【０２８３】
（ステップ２８１０）
メッシュを４分割した４つの子メッシュをスタックに入れ、ステップ２８０５に戻る。
【０２８４】
すなわち、矩形検索のスピードは検索にかかるデータ数にほぼ比例するため、データ密度が小さいにもかかわらず多くの検索時間がかかることがなくなり、データ密度に見合った矩形検索速度を得ることができる。また、４分木の階層を下る検索により、無駄な条件判断が減るので、矩形検索速度が高速化される。
【０２８５】
［６−３．第４実施形態の変形例］
第４実施形態では、図２４に示すように、メッシュ分割手段１２と分割反対手段１３、およびメッシュ併合手段１４と併合判定手段１５を設けたが、これらの一方の組のみを設けても良いし、両者を省くこともできる。また、範囲検索手段２０を第３実施形態に組み合わせる代わりに、第２実施形態に組み合わせても良い。
【０２８６】
［７．第５実施形態］
最近傍図形検索とは、一点と矩形を指定し、その点に最も近い矩形内の図形を１つ検索し、最近傍図形のデータ格納ポイント、距離、その距離を図った図形上の座標を出力することをいう。なお、この一点を「中心点」、矩形を「検索範囲」と呼ぶ。
【０２８７】［最近傍（スーパー）図形検索の概要］
最近傍（スーパー）図形検索とは、矩形と一点（中心点と呼ぶ）が与えられたとき、矩形内のスーパー図形のうち中心点に最も近いスーパー図形（最近傍図形と呼ぶ）を探し出す操作をいう。また、この最近傍図形検索は、例えば、画面に表示される設備図のうち、マウスカーソルに最も近い設備を見つけて、その色を目立たせるような状況で使われる。この場合、画面の範囲が矩形になり、マウスカーソルの位置が中心点になる。
【０２８８】
通常、中心点は矩形内に入っているものであるが、この最近傍図形検索においては、中心点が矩形に入っていない場合でも、中心点に最も近い矩形内のスーパー図形を探し出すことができる。
【０２８９】
（１）検索対象地点（図３１に示したように、矩形内に中心点があれば中心点、中心点が矩形外にある場合には、中心点に最も近い矩形上の一点）の周辺で、１つ以上のサブ図形を見つけて、最近傍サブ図形を一時的に設定する。
【０２９０】
検索対象地点の周辺から１つ以上のサブ図形を見つける手続きは、次のように行われる。まず、検索対象地点を含む末端メッシュから調べる。この末端メッシュにサブ図形がなければ、サブ図形が存在するまで４分木を親メッシュへ遡る。４分木の根ノードまで（世界全体メッシュ）まで遡ってもサブ図形が見つからなければ、はじめの末端メッシュの周辺のメッシュへ検索範囲を広げる。この検索範囲を検索枠と呼ぶ。
【０２９１】
これら周辺の末端メッシュにもサブ図形がなければ、末端メッシュから親メッシュへ遡って調べる。サブ図形を１つ以上調べるまで、検索枠を周囲へ広げて末端メッシュから探し、親メッシュへ遡ることを繰り返す。検索枠を周囲へ広げ続けて、矩形をすっぽり囲むほど大きくなっても、その検査枠内にサブ図形がなければ、最近傍サブ図形が見つけられずに終了する。
【０２９２】
以下に示すフローチャートにおいては、末端メッシュに図形がなかったときには、まず親メッシュへ遡り、それでも図形がなかったときに、末端メッシュの周辺に検索範囲を広げるようにしているが、逆に、まず末端メッシュの周辺に検索範囲を広げてから、次に親メッシュを探すように処理の順序を変えてもよい。
【０２９３】
また、中心点から遠い図形を検索対象としたくないので、図形がなかったときの検索するメッシュを選ぶ順序を次のようにする。すなわち、メッシュの選ぶ順序は、短形と重なるメッシュそれぞれにおいて中心点から最も離れた地点（最遠点）を見つけて、中心点との最遠点の距離が近いメッシュ順とする。しかし、実際には、図形がない場合は、もともと図形の密度が小さいところで最近傍図形検索を行なうことになる。そのため多少遠いところを一時的な最近傍図形と設定しても、検索する図形数が少ないので実行時間に問題はない。
【０２９４】
（２）一時的な最近傍図形への距離を半径とし、中心点を中心とする円を作り、その円の中の図形からより近い図形を探す。この場合、何らかの最近傍サブ図形が見つかる。このサブ図形から元のスーパー図形が分かり、スーパー図形を返す。
【０２９５】
［７−１．第５実施形態の構成］
図２９は、本発明の第５実施形態の構成を示す機能ブロック図である。すなわち、本実施形態の多次元データ検索装置は、前記各実施形態に示した多次元データ管理装置の構成要素に加えて、前記コンピュータの記憶領域内に蓄積されている多次元データを管理するステップが、前記多次元空間内における指定された点に最も近い多次元データを検索する最近傍データの検索手段２１を含むことを特徴とする。第５実施形態において、前記最近傍データの検索手段２１としては、前記指定された点を含む最小のメッシュに多次元データが登録されていない場合に、前記最小のメッシュの親メッシュ、最小のメッシュに隣接するメッシュ、親メッシュの親メッシュ、隣接するメッシュの親メッシュ、隣接するメッシュに隣接する他のメッシュのごとく、再帰的に最近傍データの候補が１つ決定されるまで検索範囲を拡大するものを使用する。
【０２９６】
また、この最近傍データ検索手段２１は、前記範囲検索手段２０と同様に、入力装置２から入力されたメッシュの座標と矩形の座標を使って、メッシュと矩形の領域が重なっているか否かを判定するメッシュ／矩形領域重なり判定手段２１１と、図形データの座標と矩形の座標を使って、図形が矩形に入っているか否かを判定する図形／矩形所属判定手段２１２と、図形の座標データを使って、与えられた一点（中心座標）との距離を計算し、その中心座標に最も近い図形上の座標を求める距離計算手段２１３と、データ領域上に、固定パラメータを格納したり、初期４分木（根ノードしかない４分木）を作成したり、図形キー管理領域を構成する際にデータ領域を初期化するデータ領域初期化手段２１４と、与えられた一点を含む末端メッシュを検索するメッシュ検索手段２１５とを備えている。
【０２９７】
［７−２．第５実施形態の作用］
以下前記のような構成を有する第５実施形態の多次元データ管理装置の作用並びに、これに対応する多次元データ管理方法について、図３０，３１の最近傍データの説明図と、図３２〜４１のフローチャートに従って説明する。
【０２９８】
［７−２−１．最近傍図形検索．．．その１］
図３２〜図３８は、中間メッシュにもサブ図形を登録するときの最近傍図形検索の処理の流れを示すフローチャートである。
【０２９９】
以下、最近傍（スーパー）図形検索の処理の流れを、図３０及び図３２〜図３８を参照して、各ステップごとに説明する。
【０３００】
（ステップ３２０１．．．図３２参照）
中心点と矩形をセットする。例えば、図３０に示したように中心点と矩形をセットする。
【０３０１】
（ステップ３２０２）
検索過程で見つける最近傍サブ図形について記憶するところを初期化する。
最近傍サブ図形＝無し◎最近傍点＝無し◎最短距離＝無限大（または、世界全体で引ける最も長い線分の長さより長い長さ）
ここで、「最近傍サブ図形」は、検索過程で見つけた最も近いサブ図形であり、「最近傍点」は、そのサブ図形上で中心点に最も近い点である。また、「最短距離」は、そのサブ図形への中心点からの距離である。すなわち、「最短距離」は最近傍点と中心点の距離である。
【０３０２】
（ステップ３２０３）
中心点から最も近い矩形内の点（検索対象地点）を見つける。すなわち、矩形内に中心点があるときは検索対象地点は中心点である。一方、中心点が矩形外にあるときは、中心点と矩形の間の距離計算を行なえば得られる。図３０に示したように、本例では、中心点そのものが検索対象地点になる。
【０３０３】
（ステップ３２０４）
検索対象地点のある末端メッシュを見つける。これが検索を始めるメッシュとなる。なお、この末端メッシュを見つける方法は、検索対象地点の座標から４分木を使って得られる。本例では、メッシュ５が見つかる。
【０３０４】
（ステップ３２０５）
見つけた末端メッシュを、これまでに調べた範囲を示す矩形（検索枠と呼ぶ）とする。例では、全世界を４分割した左上４分の１の四角形（メッシュ５）が検索枠となる。
【０３０５】
（ステップ３２０６）
検索のループのために、今見つけた末端メッシュだけからなる検索対象メッシュリストを作る。例では、検索対象メッシュリストは５となる。
【０３０６】
（ステップ３２０７）
検索対象メッシュリストから順にメッシュを１つ取り出し、現メッシュとする。例では、メッシュ５が選ばれる。そして、このメッシュ５に登録されているサブ図形から調べる。
【０３０７】
（ステップ３２０８）
まず、図形を調べる前に、現メッシュが検索済みか否かを判断する。この処理は、検索済メッシュリストに現メッシュが入っているかどうかを調べることで分かる。そして、検索済みならば次のステップ３２０９へ進み、未検索ならば、図３３に示したステップ３３０１へ進む。例では、検索を始めたところなので、メッシュ５は未検索であるため、ステップ３３０１へ進む。
【０３０８】
ここからは、メッシュに登録されているサブ図形を調べる処理についての説明である。
【０３０９】
（ステップ３３０１．．．図３３参照）
検索済メッシュリストに現メッシュを加える。例では、検索済メッシュリストは、５だけからなる。
【０３１０】
（ステップ３３０２）
現メッシュにサブ図形が登録されているか否かを判断し、現メッシュにサブ図形が登録されていなければ、図３４に示した根ノードへ遡るフローへ進む。一方、現メッシュにサブ図形がある場合には、次のステップ３３０３に進む。例では、図３０に示したように、現メッシュ５は図形ｂを１つ持っているので、ステップ３３０３に進む。
【０３１１】
（ステップ３３０３）
現メッシュに登録されているサブ図形を順に調べる。ここでは、サブ図形を１つずつ取ってきて現図形とする。例では、メッシュ５の図形ｂを現図形とする。
【０３１２】
（ステップ３３０４）
すでに調べたサブ図形のリスト（調査済サブ図形リスト）に現図形があるか否かを調べ、あるならば、この現図形への処理をスキップし、ステップ３３１１へ進む。一方、調査済サブ図形リストに現図形がないならば、現図形への処理へ移り、ステップ３３０５へ進む。なお、メッシュまたがりのあるサブ図形のとき、このステップで（ＹＥＳ）に進むことがある。例では、図形ｂは検索済サブ図形リストにないので、ステップ３３０５へ進む。
【０３１３】
（ステップ３３０５）
現図形を２度調べないように、調査済サブ図形リストに現図形を加える。例では、調査済サブ図形リストは、図形ｂだけからなる。
【０３１４】
（ステップ３３０６）
現図形が矩形に入っているか否かを調べ、矩形に入っていなければ、処理を行なうことは無駄なので、ステップ３３１１へスキップする。一方、矩形に入っていれば、距離計算のステップ３３０７へ進む。例では、図形ｂは矩形内に入っているので、距離計算のステップ３３０７へ進む。
【０３１５】
（ステップ３３０７）
中心点から現図形への距離を計算し、図形上の最も近い点（近傍点）を計算する。この処理に対しては、座標からの計算手段が用意されている。例では、図３０に示したように、図形ｂに対して距離計算手段で計算すると、距離はＬで、近傍点は点Ｖと分かる。距離、遠近の定義は多次元データの種類に依存する。例では、ユークリッド距離である。
【０３１６】
（ステップ３３０８）
計算した距離とこれまでの最短距離を比較し、計算した距離がこれまでの最短距離より小さければ、最近傍サブ図形、最近傍点、最短距離を更新するステップ３３０９へ進む。一方、計算した距離がこれまでの最短距離と等しいか大きければ、何もせずにステップ３３１１に進む。本例では、今のところ最短距離は無限大なので、図形ｂの方が距離が小さいので、ステップ３３０９へ進む。
【０３１７】
（ステップ３３０９）
最近傍サブ図形、最近傍点、最短距離を更新する。例の場合、最近傍サブ図形＝図形ｂ、最近傍点＝点Ｖ、最短距離＝距離Ｌに更新される。
【０３１８】
（ステップ３３１０）
最短距離が０かどうか調べ、もし０ならば、もうこれより小さい距離はありえないので、ここで検索を打ち切り、ステップ３３１２へ進む。一方、０でないならば、ステップ３３１１へ進む。例では、図形ｂは距離が０でないので、ステップ３３１１へ進む。
【０３１９】
（ステップ３３１１）
現メッシュ内の登録サブ図形全てについてのループの終了条件の判断である。全てのサブ図形について処理が終わってなければ、ステップ３３０３へ戻る。一方、全てのサブ図形について処理が終わっている場合には、図３２のステップ３２１１へ進み、検索対象メッシュリストの全てについて、処理したか否かを判断する。例の場合、メッシュ５の全図形について処理が終わったので、次のメッシュについて調べるか否かを判断するステップ３２１１へ進む。
【０３２０】
（ステップ３３１２）
ここでは検索結果を返す。最近傍の図形としてサブ図形が得られている。検索結果としては、スーパー図形を返す必要があるので、サブ図形の元のスーパー図形のデータへのポインタに直す。それと合わせて最短距離と最近傍点を返す。
【０３２１】
ここからは、ステップ３３０２で調べるメッシュに図形が１つもなかったり、ステップ３２０８でメッシュが検索済の場合の処理についての説明である。
【０３２２】
（ステップ３２０９）
ステップ３３０２で調べるメッシュに図形が１つもなかったり、ステップ３２０８でメッシュが検索済ならば、図３２のステップ３２０９へ進む。ステップ３２０９からステップ３２１０へのループでは、メッシュに調べるべき図形があるまで、親メッシュへ遡る。このステップ３２０９は、遡って行って根ノード（世界全体）まで来たらループを中断するための判断である。すなわち、メッシュが世界全体でなければ、親メッシュへ遡るステップ３２１０へ進み、世界全体ならば、次の末端メッシュを調べるためのフローへ進む。
【０３２３】
（ステップ３２１０）
親メッシュを調べるため、現メッシュを親メッシュに置き換える。そしてステップ３２０８へ進む。
【０３２４】
（ステップ３２１１）
世界全体まで遡った場合、ステップ３２０９からステップ３２１１へ進んでいる。ここで、検索対象メッシュリストのメッシュ全てに対して処理が終わっているか否かが判断され、処理が終わってなければステップ３２０７へ戻る。一方、終わっていれば次のステップ３２１２へ進む。例の場合、検索対象メッシュリストにはメッシュ５だけしかなく、メッシュ５の処理が終わっているので、ステップ３２１２へ進む。
【０３２５】
（ステップ３２１２）
ここで、１つ以上のサブ図形について距離計算を行なったか否かを判断し、分岐する。すなわち、最近傍図形＝無しのままでなければ、サブ図形１つ以上に対して距離計算をしたことを意味する。一方、最近傍図形＝無しならば、まだ１つもサブ図形に対して距離計算をしていないことになる。サブ図形１つ以上に対して距離計算をしていれば、これまでの最短距離、最近傍点、最近傍サブ図形があることになる。そして、このステップの次は、この最短距離を半径とする円内のサブ図形を調べるフローステップ３４０１へ進む。
【０３２６】
上述したように、図３２のステップ３２１２において、サブ図形に対して一度も距離計算をしていなければ、検索対象メッシュリスト内のメッシュすべてと、それぞれのメッシュから親メッシュへ遡ってもサブ図形が１つも見つからなかったことを意味する。そのため、この先のフロー（図３６に示したステップ３６０３から）では、検索枠を広げて検索し直すための準備を行なう。簡単に言うと、これまで調べた末端メッシュの範囲を少し広げて、新たな末端メッシュのリストを作って検索対象メッシュリストとする。ただし、範囲を広げた結果、検索枠が矩形より大きくなったときには、最近傍検索は終了する。この点について、図３９を参照してより具体的に説明する。すなわち、はじめ、検索枠はメッシュＺの四角に設定される。そして、メッシュＺを検索して、親メッシュをさかのぼっても図形がないときは、回りを探す。この検索枠と接するか、重なる末端メッシュで、検索済みではなく、矩形と重なるのはメッシュＡ〜Ｈである。メッシュＡ〜Ｈの中で最小のメッシュＢの縦幅、横幅分だけ検索枠を広げる。すると、図３９に示したように、旧検索枠（太実線）から新検索枠（一点鎖線）に広がる。さらに、メッシュＡ〜Ｈとその親メッシュに図形がないならば、新検索枠を使ってメッシュリストを作る。メッシュリストは、メッシュＩ〜Ｍになり、新たな検索枠（新々検索枠）は点線で囲んだ部分となる。
【０３２７】
以下、この処理を各ステップごとに説明する。
【０３２８】
（ステップ３６０１）
このステップへは、図３２に示したステップ３２１２から来る。なお、このステップにおけるメッシュリストの作成の詳細なルーチンについては、図３７に示し、後述する。はじめにこのステップに到達したときは、検索枠は検索対象地点のある末端メッシュである。この末端メッシュの回りの末端メッシュを検索対象にしたいので、検索枠に接するか重なる末端メッシュを探す。そして、これらの中の矩形に重ならないメッシュと検索済のメッシュを除いて検索対象メッシュリストとする。
【０３２９】
もし、検索対象メッシュリストにメッシュが１つもなければ、検索枠が十分に広がって、矩形より大きくなっていることを意味する。本例の矩形の場合、メッシュ５に図形がなければ、メッシュ５の回りの末端メッシュ２８、２９が検索対象メッシュリストになる。なお、メッシュ４、メッシュ２５もメッシュ５の回りの末端メッシュであるが、矩形に重なっていないので対象外である。
【０３３０】
（ステップ３６０２）
検索対象メッシュリストにメッシュあるか否かが判断され、メッシュが１つもなければ、検索すべきメッシュがもうないことを意味し、検索結果として返るのは、最近傍図形がないということである。一方、検索対象メッシュリストにメッシュがあれば、ステップ３６０３に進む。
【０３３１】
（ステップ３６０３）
ここでは、新たな検索対象メッシュリスト内のメッシュの中で最小のメッシュの縦幅、横幅分だけ検索枠を縦にも横にも正負両方向に広げる。このように広げると、次に再び図形が１つもなくて検索対象メッシュリストを作るとき、近いところにあるメッシュから順に検索対象メッシュリストに加わることになる。検索対象メッシュリストができているので、図３２のステップ３２０７へ戻ってメッシュに対する処理を行なう。
【０３３２】
このように、図３２、図３３及び図３６に示したフローチャートにしたがって最近傍図形検索を行なうと、１つの最近傍サブ図形候補が見つかるか、最近傍図形がないという結果が返るかどちらかになる。そして、最近傍図形候補が１つ見つかっていると、図３２のステップ３２１２から（ＮＯ）の分岐へ進み、図３４のステップ３４０１へ到達する。
【０３３３】
（ステップ３４０１）
このステップに到達した場合には、最近傍サブ図形が１つ見つかっているが、これより近いものがないかどうかを調べなければならない。このために中心点を中心として、最短距離を半径とする円を作り、それにかかるメッシュを調べる。このステップでは、その円と重なりかつ矩形と重なるメッシュ（末端も中間も）を検索し、検索対象メッシュリストとする。このメッシュ検索のルーチンについては、図３８に詳細に表わし、後述する。本例では、メッシュ１，５，７，２８，２９が検索対象メッシュリストに含まれる。
【０３３４】
（ステップ３４０２）
検索対象メッシュリスト内のメッシュを１つずつ調べるため、メッシュを１つ取って現メッシュとする。
【０３３５】
（ステップ３４０３）
現メッシュが検索済か否かを調べる。すなわち、検索済メッシュリスト内に現メッシュがあるか否かを調べれば良い。そして、現メッシュが検索済ならば、メッシュに対する処理をスキップして、図３５のステップ３５０６へ進む。一方、検索済でなければ次のステップ３４０４に進む。例の場合、メッシュ５が検索済リストにあるので、メッシュ５の処理の時に、図３５のステップ３５０６へスキップする。
【０３３６】
（ステップ３４０４）
現メッシュを検索済メッシュリストに加える（なお、検索したメッシュリストが必要なければこのステップはなくてもよい）。
【０３３７】
（ステップ３４０５）
現メッシュに登録サブ図形があるか否かを判断し、あれば、図形の処理へ進み、なければ、図３５のステップ３５０６へスキップする。例では、メッシュ１，７がステップ３５０６へスキップすることになる。
【０３３８】
（ステップ３４０６）
現メッシュに登録されているサブ図形１つ１つへの処理を始める。すなわち、現メッシュに登録されているサブ図形を１つ選んで、現図形とする。例では、メッシュ２８の処理の場合、図形ｉが選ばれ、メッシュ２９の処理の場合、図形ａが選ばれる。
【０３３９】
（ステップ３４０７）
現図形が調査済か否かを調べる。これは、調査済サブ図形リストを調べれば分かる。そして、調査済ならば、図３５のステップ３５０５へスキップし、調査済でなければ、次のステップ３４０８へ進み、現図形への処理を行う。例では、図形ｉは調査済ではないので、ステップ３４０８へ進む。また、図形ａも調査済ではないので、同様にステップ３４０８へ進む。
【０３４０】
（ステップ３４０８）
メッシュまたがりがある場合に２度計算しないように、調査済サブ図形リストに現図形を加える。
【０３４１】
（ステップ３４０９）
距離計算をする前に、現図形が矩形に入っているか否かを調べ、矩形に入っていれば距離計算へ進み、矩形に入ってなければ、図３５のステップ３５０５へスキップする。本例では、図形ｉの場合、矩形に入っていないので、距離計算をせずにステップ３５０５へスキップする。一方、図形ａの場合、矩形に入っているので、ステップ３４１０で距離計算を行なう。
【０３４２】
（ステップ３４１０）
中心点からの距離、近傍点を距離計算手段によって計算する。図形ａの距離はＫ、近傍点は点Ｕと計算される。
【０３４３】
（ステップ３５０１．．．図３５参照）
距離計算した結果を、これまでの最短距離と比べる。これまでの最短距離と等しいか大きければ、何もせずにステップ３５０５に進む。一方、これまでの最短距離より小さければ、最近傍サブ図形更新のフローへ進む。本例では、図形ａの場合、これまでの最短距離より距離が短いので、ステップ３５０２へ進み更新する。
【０３４４】
（ステップ３５０２）
最近傍サブ図形、最近傍点、最短距離を更新する。例の場合、最近傍サブ図形＝図形ａ、最近傍点＝点Ｕ、最短距離＝距離Ｋとなる。
【０３４５】
（ステップ３５０３）
最短距離が０かどうか調べる。もし０ならば、もうこれより小さい距離はありえないので、ここで検索を打ち切り、ステップ３５０４へ進む。０でないならば、ステップ３５０５へ進む。例の図形ａの場合、距離が０でないので、ステップ３５０５へ進む。
【０３４６】
（ステップ３５０４）
ここでは検索結果を返す。最近傍の図形としてサブ図形が得られているため、検索結果としては、スーパー図形を返す必要があるので、サブ図形の元のスーパー図形のデータへのポインタに直す。それと合わせて最短距離と最近傍点を返す。
【０３４７】
（ステップ３５０５）
現メッシュに登録されている登録サブ図形全てについてのループの終了条件の判断である。すべてのサブ図形について処理が終わっていなければ、図３４のステップ３４０６へ戻り、次の図形を調べる。一方、すべてのサブ図形について終わっていれば、次のステップ３５０６に進む。
【０３４８】
（ステップ３５０６）
検索対象メッシュリストのメッシュ全てに対して処理を終えたか否かが判断され、すべてのメッシュについて処理を終えたら、次のステップ３５０７へ進む。一方、終えていければ、図３４のステップ３４０２に戻り、次のメッシュへの処理を行なう。
【０３４９】
（ステップ３５０７）
ここでは検索結果を返す。最近傍の図形としてサブ図形が得られているため、検索結果としては、スーパー図形を返す必要があるので、サブ図形の元のスーパー図形のデータへのポインタに直す。それと合わせて最短距離と最近傍点を返す。本例の場合は、最後には、「図形ａが最近傍図形である」との結果を得る。
【０３５０】
ここで、図３７を参照して、図３６のステップ３６０１におけるメッシュリストの作成のルーチンについて、さらに詳しく説明する。すなわち、図３６のステップ３６０１においては、その時点で設定されている検索枠と接するか、重なる末端メッシュのうち、検索済メッシュリストになく、且つ、矩形と重なるものを探し出して、新たな検索対象メッシュリストとする場合を示している。
【０３５１】
なお、この処理は、上述した矩形検索での、矩形に重なるメッシュリストの作成のフローチャート（図２５）とほぼ同じである。違う点は、メッシュリストを作成するステップに至るまでに、２つ条件分岐（ステップ３７０７、ステップ３７０９）が加わっている点である。
【０３５２】
また、このフローでは、末端メッシュだけがメッシュリストに加わえられるが、ステップ３７１０とステップ３７１１の順番を入れ替えて、メッシュが末端か否かを判断する前に、メッシュリストにメッシュを加えると、条件に合う中間メッシュと末端メッシュの両方を含むメッシュリストが得られる。
【０３５３】
次に、図３８を参照して、図３４のステップ３４０１におけるメッシュリストの作成のルーチンについて、さらに詳しく説明する。すなわち、図３４のステップ３４０１においては、それまでの最短距離（それまでの最近傍図形までの距離）を半径、中心点を中心とする円と矩形に重なる末端メッシュ及び中間メッシュを探し出して、新たな検索対象メッシュリストとする場合を示している。
【０３５４】
なお、この処理は、上述した矩形検索での、矩形にかかるメッシュリストの作成のフローチャート（図２５）とほぼ同じである。違う点は、メッシュリストを作成するステップに至るまでに、１つ条件分岐（ステップ３８０８）が加わっている点である。
【０３５５】
また、このフローでは、末端メッシュと中間メッシュがメッシュリストに加わえられるが、ステップ３８０９とステップ３８１０の順番を入れ替えて、メッシュが末端か否かを判断した後で、メッシュリストにメッシュを加えると、条件に合う末端メッシュだけのメッシュリストが得られる。
【０３５６】
［７−２−２．最近傍図形検索．．．その２］
上述した最近傍図形検索は、中間メッシュにもサブ図形を登録する場合についてのものであったが、以下に述べる最近傍図形検索は、末端メッシュにのみサブ図形を登録する場合についてのものである。
【０３５７】
以下、中間メッシュに図形を登録する場合と登録しない場合の最近傍図形検索の違いについて、図３２（中間メッシュにもサブ図形を登録する場合）と図４０（末端メッシュにのみサブ図形を登録する場合）で比べる。図から明らかなように、図３２では、ステップ３２０９、ステップ３２１０のループがあるが、図４０にはない。その理由は、図３２では、中間メッシュにも図形が存在するので、末端メッシュを調べて図形が存在しなかった場合には、親メッシュへ溯って調べなければ、検索漏れを起こしてしまうからである。
【０３５８】
次に、図３３（中間メッシュにもサブ図形を登録する場合）と図４１（末端メッシュのみにサブ図形を登録する場合）を比べる。この違いは、図３３では、ステップ３３０２の条件分岐でＮＯのとき、図３２のステップ３２１１の検索対象メッシュリストの処理終了判断へ飛ばず、ステップ３２０９に飛んでいる。一方、図４１では、図３３のステップ３３０２に相当するステップ４１０２でＮＯのとき、図３２のステップ３２１１に相当するステップ４００８に飛んでいる。その理由は、中間メッシュにも図形がある図３３においては、親メッシュを調べなければならないので、親メッシュを調べるフローであるステップ３２０９へ飛ばなければならないからである。
【０３５９】
なお、図４０からＢへ進み、Ｃから戻ってくるところに接続するフローチャートは、上述した図３６（中間メッシュに図形がある場合の図）と同一である。また、図４０のＡへ進む先のフローチャートは、ステップ３４０１を除いて、図３４及び図３５と同一である。
【０３６０】
図３４のステップ３４０１に対応する処理が異なるのは、それまでに見つけた最近傍図形までの距離を半径とする円の範囲内のメッシュを見つけるに際し、中間メッシュにも図形がある場合は、円にかかるメッシュを探すとき、末端だけでなく、中間メッシュも探し出さなければならないからである。一方、末端メッシュにしか図形がない場合には、中間メッシュを調べる必要がないので、ステップ３４０１のステップを、末端メッシュのみを探し出すように変更する。すなわち、図３８のステップ３８０９とステップ３８１０を置き換えれば良く、メッシュが末端か否かを判断し、ＹＥＳのときのみ、メッシュをリストに加えるようになっている。
【０３６１】
このように、図３４のステップ３４０１を変え、図３８のステップ３８０９及びステップ３８１０を変えて、図４０のＡから図３４及び図３５のフローを実行すれば、末端メッシュにのみ図形がある場合の最近傍図形検索の処理フローになる。
【０３６２】
［７−３．第５実施形態の効果］
前記の様な構成を有する第５実施例によれば、最近傍図形検索処理において、１回の検索あたりに距離計算するデータが少なくなるので、検索時間が速くなる。さらに、最近傍図形検索処理の速さが、データ密度の疎密に影響されず、いつでも同程度の速さで処理できるようになる。
【０３６３】
［７−４．第５実施形態の変形例］
第５実施形態では、図２９に示すように、メッシュ分割手段１２と分割反対手段１３、およびメッシュ併合手段１４と併合判定手段１５を設けたが、これらの一方の組のみを設けても良いし、両者を省くこともできる。また、範囲検索手段２０を第３実施形態に組み合わせる代わりに、第２実施形態に組み合わせても良い。また、最近傍データ検索手段２１を範囲検索手段２０と組み合わせ両方の検索が可能としたが、範囲検索手段２０がなくても良い。
【０３６４】
［８．他の実施形態］
［８−１．図形のメッシュへの所属条件の拡張］
第２実施形態において図形の所属を親メッシュから子メッシュへ移すべきか否かを判定する条件、及び第３実施形態において図形を現メッシュに所属させる（登録する）べきか否かを判定する条件とは、類似の作用及び効果を有するものである。第３実施形態においては条件判定及びその結果に依存した図形のメッシュへの登録作用が、その時のメッシュ分割（４分木）の状態の如何にかかわらず、必要な場合にはメッシュ分割を行なっても、条件に合致するメッシュに図形を所属させる。これに対して第２実施形態においては、その作用が図形登録時のメッシュ分割の状態によって制限され、図形登録時ではなくて、別の基準に従って作用するメッシュ分割操作の作用時に同時に行なわれる。つまりメッシュ分割時までその作用が延期されるという差があるにすぎない。
【０３６５】
この条件としてどのようなものを採用するかによって、各図形のメッシュへの重複登録の数及び図形とメッシュとの重なり具合が異なってくる。これが所要記憶容量の大小及び矩形検索、最速傍図形検索の効率に影響する。
【０３６６】
従来技術はこの条件として、
（ａ）末端のメッシュで、かつ所属図形数がＰ未満のメッシュか否かを判定し、該当メッシュであれば登録する。（該当していなければメッシュ分割によって該当するメッシュを作り出す。）
（ｂ）図形全体を包含する最小のメッシュか否かを判定し、最小のメッシュに該当していれば登録する。
【０３６７】
（ｃ）図形全体を包含する最小のメッシュを分割した子メッシュの境界によって分断された各部分図形に注目し、それらの部分図形のうち１つを含む最小のメッシュか否かを判定し、該当メッシュであればそこに図形を登録する。
【０３６８】
という条件を設定したのとそれぞれ等価である。これらの条件を用いた場合には、それぞれ［発明が解決しようとする課題］に述べたような問題点によって記憶領域の浪費や検索性能の劣化が生じる場合を排除することができなかった。
【０３６９】
これらの従来技術は判定基準にかかわる図形とメッシュとの関係として、例えば前記（ａ）の場合、登録しようとする図形及び既にメッシュに所属している図形の種類の如何にかかわらず、メッシュに既に所属している図形数のみを用いている。また、（ｂ）の場合はメッシュが図形を包含する最小のメッシュか否か、つまりメッシュを分割した子メッシュのうち複数のものに図形が重なるか否かのみを用いている。（ｃ）は判定の過程を二段階に分けているとはいえ、用いられている図形とメッシュとの関係は（ｂ）と同様に、図形の種類の如何にかかわらず、メッシュが（部分）図形を包含する最小のメッシュか否かのみを用いている。
【０３７０】
ここにいう「図形の種類」とは、登録しようとするｎ次元空間データのｎ次元空間内での空間の占有（ひろがり）の態様に主として起因する分類・区別である。例えば極端な例として点データは大きさ（ひろがり）を持たないので前記（ｂ）（ｃ）のような判定基準では扱えず、他の基準例えば（ａ）のような基準を使用せざるを得ない。線分は長さのみあって面積や体積はないから、メッシュとの重なり具合及びそれが検索の効率に及ぼす影響も面積や体積を持つ図形、就中各次元の最大径の比がメッシュの各次元の長さの比に近いような凸な図形とは異なっている。後者に関しては前記（ｃ）あるいは（ｂ）のような基準はメモリ効率の点でも検索速度の点でも有効である場合が多いが、線分や細長い矩形直方体に関しては必ずしも有効でないことは前述のとおりである。
【０３７１】
さらには、ある目的・性質を（共）有することが予めわかっているデータに関しては、それに応じた適切な条件を設定することで資源の浪費を避け、検索効率を高めることができる。例えば、地図、グラフ等の背景に用いられる罫線や座標線は数はそれ程多くはないが、１つ１つが非常に長いという性質がある。これらのデータを他の非常に短い線分や小さな図形と同様な基準でメッシュに所属させたとすると、所属メッシュが細分化されすぎて非常に多くのメッシュに重複登録され、多量のメモリを浪費したうえ、検索効率をも劣化させるおそれが大きい。逆にあまりにも小数のメッシュにしか所属せず、同一のメッシュに多数の罫線が所属することになって検索効率が著しく低下するという事態もまた生じうる。例えば前記（ｂ）の条件を用いれば、すべての罫線は世界座標範囲と同じ１つの（最大の）メッシュにのみ所属することになり、領域を分割して図形を登録することによって検索の効率を向上させるという効果は全然得られない。
【０３７２】
このような状況を避けるために、罫線については、罫線の間隔と同程度の長さの辺を持つメッシュにのみ登録するように第４実施例（ｂ）の条件を設定することが考えられる。この条件に従って登録を行なえば、１つのメッシュに属する罫線は（１方向）１本だけになり、なおかつ極端な重複登録は避けられる。この場合、選ばれる罫線の数が罫線の総本数に比較して非常に少ない矩形検索には特に有効である。前記の条件は個々の罫線の線分としての属性（例えば長さ）ではなく、罫線同士の間隔から予め決定あるいは計算される長さを規準にして登録すべきメッシュを判定するものである。
【０３７３】
面積や体積を持つ図形に関しても、例えば背景として用いられる非常に広い面積を占める図形を、例えば前記（ａ）のような条件で他の小さな図形と同様に扱えば重複登録の数は膨大になる。このような図形に対しては第３実施形態の（ｄ）のような条件で重複登録の数を限るのが、メモリの浪費を避けるのに効果的である。
【０３７４】
上述のように、図形の形状・大きさのみならず、その目的や他の図形との関係から最適と考えられる基準にもとづいて、メッシュへの図形の登録あるいは子メッシュへの図形の所属移動を制御することによって、図形に依存しない一律な条件では達成できないメモリの効率的使用並びに検索の効率化を図ることができる。
【０３７５】
［８−２．多次元データへの適用］
前記各実施形態は、２次元や３次元空間内の図形データを扱う場合について具体的に述べてきたが、それ以外にも各次元が何らかの量を表すような多次元のデータに関して、本実施例と同様の方法で他の多次元空間、すなわちｎ次元空間を再帰的に２のＮ乗分割したｎ次元直方体をメッシュとしてデータを登録・検索することができる。これらｎ次元データはｎ次元空間内の点として扱われるようなデータばかりではなく、１つの（１組の）データがｎ次元空間内にある広がりを持った超立体として扱われるものも希ではない。例えば、１つの物体に関するｎ種の属性の測定値はそれぞれに誤差を含んでおり、それを各次元の真の値がある確率で存在する範囲として扱う場合、ｎ次元直方体データになる。その形状は測定の状況に依存して種々変化するので、それらのデータを一括して記録し、各次元の真の値がある範囲に存在する物体を選択する等の検索を効率良く実施するためには、本発明のような多次元データ管理・検索手段が必要である。
【０３７６】
このように本発明は、上述した実施形態に限られず、多次元空間中で位置の決まるデータの管理・検索に適用できるが、この場合、Ｎ次元空間のデータに関しては、［２のＮ乗］分木でメッシュの分割が管理される。また、データが多種類ある場合には、種類を限定して検索することもできる。さらに、データの種類や座標データの扱いの違いによって、［２のＮ乗］分木を複数用意することも可能である。
【０３７７】
【発明の効果】
以上述べた様に、本発明によれば、データ領域の削減が可能で、しかも矩形検索及び最近傍図形検索の高速化を可能とした多次元データ管理方法及び装置を提供することができる。
【図面の簡単な説明】
【図１】本発明の第１実施形態の構成を表す機能ブロック図
【図２】本発明にかかるデータ領域の全体構成を示す図
【図３】本発明のメッシュデータの構成を示す図
【図４】メッシュデータと図形データとの対応を示す図
【図５】本発明の第１実施形態において、図形ａを登録する世界全体を示す図
【図６】メッシュ分割をした場合の番号付けを示す図
【図７】メッシュとそのメッシュに登録された図形を示すツリー図
【図８】スタックの動作を示す図
【図９】図形のデータ領域への登録の処理の流れを示すフローチャート
【図１０】図形をメッシュに登録する処理の流れを示すフローチャート
【図１１】図形をデータ領域から削除する処理の流れを示すフローチャート
【図１２】図形をメッシュから削除する処理の流れを示すフローチャート
【図１３】図形の修正の処理の流れを示すフローチャート
【図１４】メッシュの分割の処理の流れを示すフローチャート
【図１５】メッシュの併合の処理の流れを示すフローチャート
【図１６】中間メッシュにも図形を登録する場合のメッシュとそのメッシュに登録された図形を示すツリー図
【図１７】本発明の第２実施形態の構成を表す機能ブロック図
【図１８】第２実施形態の処理の流れを示すフローチャート
【図１９】中間メッシュにも図形を登録する場合の条件を説明するための図
【図２０】中間メッシュにも図形を登録する場合の条件を説明するための図
【図２１】本発明の第３実施形態の構成を表す機能ブロック図
【図２２】第３実施形態の処理の流れを示すフローチャート
【図２３】本発明の第４実施形態の矩形検索を説明するための図
【図２４】本発明の第４実施形態の構成を表す機能ブロック図
【図２５】矩形検索において、検索する矩形にかかっている全てのメッシュを探し出す処理の流れを示すフローチャート
【図２６】矩形検索において、図形が矩形に入っているか否かを検索する処理の流れを示すフローチャート
【図２７】メッシュリストと図形リストの対応を示す図
【図２８】末端メッシュにのみ図形を登録した場合の矩形検索の処理の流れを示すフローチャート
【図２９】本発明の第５実施形態の構成を表す機能ブロック図
【図３０】最近傍図形検索を説明するための図
【図３１】中心点と矩形の関係を示す図
【図３２】最近傍図形検索の処理の流れを示すフローチャート
【図３３】最近傍図形検索の処理の流れを示すフローチャート
【図３４】最近傍図形検索の処理の流れを示すフローチャート
【図３５】最近傍図形検索の処理の流れを示すフローチャート
【図３６】最近傍図形検索の処理の流れを示すフローチャート
【図３７】最近傍図形検索の処理の流れを示すフローチャート
【図３８】最近傍図形検索の処理の流れを示すフローチャート
【図３９】最近傍図形検索の処理の流れを示すフローチャート
【図４０】末端メッシュにのみ図形を登録した場合の最近傍図形検索の処理の流れを示すフローチャート
【図４１】末端メッシュにのみ図形を登録した場合の最近傍図形検索の処理の流れを示すフローチャート
【図４２】ＭＤ木法の従来手法を示す図であって、（Ａ）は領域分割、（Ｂ）はＭＤ木
【図４３】ＭＤ木法の問題点を示す図であって、（Ａ）は領域分割、（Ｂ）はデータ４の投入後、（Ｃ）はデータ７の投入後、（Ｄ）はデータ８の投入後
【図４４】従来の最近傍データ検索の手法を説明する図
【図４５】重複登録の例を示す図
【図４６】ｑｕａｄ−ｔｒｅｅ法の第１の変形例を示す図
【図４７】ｑｕａｄ−ｔｒｅｅ法の第２の変形例を示す図
【符号の説明】
１．．．中央処理装置
２．．．入力装置
３．．．出力装置
４．．．メインメモリ
５．．．ファイル装置
６．．．データ管理プログラム
７．．．メッシュデータ記憶手段
８．．．多次元データ記憶手段
９．．．木構造管理手段
１０．．．多次元データ登録削除手段
１１．．．メッシュ／矩形領域重なり判定手段
１２．．．メッシュ／矩形枠重なり判定手段
１３．．．図形／矩形所属判定手段
１４．．．距離計算手段
１５．．．データ領域初期化手段
１６．．．メッシュ検索手段
１７．．．検索結果出力手段

Claims (6)

1. コンピュータの所定の領域に配置される複数の多次元データを管理する多次元データ管理方法において、
   前記所定の領域の中の第１の領域が、その子領域である第２の領域に階層的に分割されている場合に、前記第２の領域に前記多次元データを割り当てたときの状態と、前記第１の領域に前記多次元データを割り当てたときの状態とに基づいて示される併合許容条件を満たすか否かを判断し、
   前記併合許容条件を満たすと判断した場合には、前記第２の領域を前記第１の領域に併合し、
   前記第１の領域に前記多次元データを割り当てることを特徴とする多次元データ管理方法。
2. コンピュータの所定の領域に配置される複数の多次元データを管理する多次元データ管理方法において、
   前記所定の領域の中の第１の領域を、その子領域である第２の領域に階層的に分割する場合に、前記第１の領域に前記多次元データを割り当てたときの状態と、前記第２の領域に前記多次元データを割り当てたときの状態とに基づいて示される分割許容条件を満たすか否かを判断し、
   前記分割許容条件を満たすと判断した場合には、前記第１の領域を前記第２の領域に階層的に分割し、前記第２の領域に前記多次元データを割り当て、
   また、前記第２の領域に前記多次元データを割り当てたときの状態と、前記第１の領域に前記多次元データを割り当てたときの状態とに基づいて示される併合許容条件を満たすか否かを判断し、
   前記併合許容条件を満たすと判断した場合には、前記第２の領域を前記第１の領域に併合し、前記第１の領域に前記多次元データを割り当てることを特徴とする多次元データ管理方法。
3. コンピュータの所定の領域に配置される複数の多次元データを管理する多次元データ管理装置において、
   前記所定の領域の中の第１の領域が、その子領域である第２の領域に階層的に分割されている場合に、前記第２の領域に前記多次元データを割り当てたときの状態と、前記第１の領域に前記多次元データを割り当てたときの状態とに基づいて示される併合許容条件を満たすか否かを判断する手段と、
   前記併合許容条件を満たすと判断した場合には、前記第２の領域を前記第１の領域に併合する手段と、
   前記第１の領域に前記多次元データを割り当てる手段とを備えたことを特徴とする多次元データ管理装置。
4. コンピュータの所定の領域に配置される複数の多次元データを管理する多次元データ管理装置において、
   前記所定の領域の中の第１の領域を、その子領域である第２の領域に階層的に分割する場合に、前記第１の領域に前記多次元データを割り当てたときの状態と、前記第２の領域に前記多次元データを割り当てたときの状態とに基づいて示される分割許容条件を満たすか否かを判断する手段と、
   前記分割許容条件を満たすと判断した場合には、前記第１の領域を前記第２の領域に階層的に分割する手段と、
   前記第２の領域に前記多次元データを割り当てたときの状態と、前記第１の領域に前記多次元データを割り当てたときの状態とに基づいて示される併合許容条件を満たすか否かを判断する手段と、
   前記併合許容条件を満たすと判断した場合には、前記第２の領域を前記第１の領域に併合する手段と、
   前記判断結果に基づいて、前記第１の領域および第２の領域の少なくとも一方に前記多次元データを割り当てる手段と、
   を備えたことを特徴とする多次元データ管理装置。
5. コンピュータの所定の領域に配置される複数の多次元データを管理する多次元データ管理プログラムを記録した記録媒体であって、
   前記プログラムは、コンピュータに、
   前記所定の領域の中の第１の領域が、その子領域である第２の領域に階層的に分割されている場合に、前記第２の領域に前記多次元データを割り当てたときの状態と、前記第１の領域に前記多次元データを割り当てたときの状態とに基づいて示される併合許容条件を満たすか否かを判断する処理と、
   前記併合許容条件を満たすと判断された場合には、前記第２の領域を前記第１の領域に併合する処理と、
   前記第１の領域に前記多次元データを割り当てる処理と、
   を行わせることを特徴とする多次元データ管理プログラムを記録した記録媒体。
6. コンピュータの所定の領域に配置される複数の多次元データを管理する多次元データ管理プログラムを記録した記録媒体であって、
   前記プログラムは、コンピュータに、
   前記所定の領域の中の第１の領域を、その子領域である第２の領域に階層的に分割する場合に、前記第１の領域に前記多次元データを割り当てたときの状態と、前記第２の領域に前記多次元データを割り当てたときの状態とに基づいて示される分割許容条件を満たすか否かを判断する処理と、
   前記分割許容条件を満たすと判断された場合には、前記第１の領域を前記第２の領域に階層的に分割する処理と、
   前記第２の領域に前記多次元データを割り当てる処理と、
   前記第２の領域に前記多次元データを割り当てたときの状態と、前記第１の領域に前記多次元データを割り当てたときの状態とに基づいて示される併合許容条件を満たすか否かを判断する処理と、
   前記併合許容条件を満たすと判断した場合には、前記第２の領域を前記第１の領域に併合する処理と、
   前記第１の領域に前記多次元データを割り当てる処理と、
   を行わせることを特徴とする多次元データ管理プログラムを記録した記録媒体。

Images