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

Abstract

(57)【要約】 【課題】メモリが有効利用でき、登録、削除、検索など
の処理の高速化が可能な多次元データ管理方法、装置、
そのプログラムを記録した媒体を提供する。 【解決手段】多次元データ記憶手段に多次元データを登
録・削除する多次元データ登録削除手段１０と、前記多
次元空間を複数のメッシュに階層的に分割し、分割され
た各階層のメッシュを木構造の各ノードに対応させ、各
メッシュと各ノードとの対応関係を記憶する木構造管理
手段９と、分割された各メッシュに前記多次元データに
関する情報を登録するメッシュデータ記憶手段７とを備
え、前記各メッシュデータ記憶手段に登録された情報に
基づいて前記多次元データ記憶手段に蓄積されている多
次元データを管理する。メッシュ分割手段１３により、
前記末端メッシュに登録できる多次元データ数を一定値
以下に設定し、末端メッシュに登録する多次元データ数
が前記設定値を超えた場合にその末端メッシュを分割す
る。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、２次元乃至はそれ
以上の多次元空間中で位置の決まる多次元データの管理
に適した多次元データ管理方法、多次元データ管理装置
および多次元データ管理プログラムを記録した媒体に関
するものである。より具体的には、平面あるいは空間内
における図形データや、複数の属性を有する統計的なデ
ータを個々の属性を各次元に対応させることにより、登
録、削除、修正、検索（例えば、範囲検索、最近傍値検
索）などの処理を、単独であるいは適宜組み合わせて実
施することのできる多次元データ管理装置、方法および
そのプログラムを記録した媒体に関する。

【０００２】

【従来の技術】従来から、複数の属性を有するデータを
コンピュータを用いて管理する手法が数多く提案されて
いる。例えば、画像処理、コンピュータビジョン、図面
管理などの分野においては、ベクトル、点、記号などの
大量の図形要素により表される膨大な図面をコンピュー
タにより管理し、データの登録、削除を行ったり、所望
の図面を検索し、変更する作業が必要とされている。こ
のようなデータ管理として、従来から知られていたもの
に、固定グリッド法がある。この固定グリッド法は、空
間を固定の領域に分割して、各領域単位でデータを管理
するものである。この固定グリッド法は、データが定ま
っている場合には、空間検索が高速に行えてメモり効率
も良い。しかし、例えば設備データのように頻繁に追加
削除されるデータに対しては、領域の分割が固定のため
分割領域ごとのデータ数のばらつきが大きくなる。その
ため、全くデータが存在しない領域についても、他の領
域と同様に検索処理を行ったり、データの蓄積領域を確
保する必要があり、検索速度が上がらず、メモリ効率も
低くなる。

【０００３】このような固定グリッド法の問題点を解消
し、多次元データの効率的管理や高速な検索を目的とし
て、空間分割に基づく階層的なデータ構造が着目され、
種々の提案がなされている。例えば、特開平３−４８９
７４号公報に示された図形データ管理装置は、多次元空
間中の大量の図形の位置情報及び属性を、３分木構造を
有するＭＤ木の理論を適用して分割・構造化することに
より、表示領域の変更に伴うデータ検索速度の向上を図
るものである。また、同様な手法として、２次元データ
に対する２ｎ分割木を使用したｑｕａｄ−ｔｒｅｅ法も
知られている。

【０００４】（１）ＭＤ木による方法 ＭＤ木による方法では、木は、図４２に示すように、末
端の葉Ｌと内部ノードＩの２種類のノードとポインタか
ら構成されている。データを配置する空間は再帰的に分
割され、各ノードは分割された空間に対応付けられる。
すなわち、親ノードは、すべての子ノードの空間を包含
する最小の（ｎ次元）長方形に対応する。また、データ
はすべて末端の葉Ｌに蓄積される。内部ノードは、初期
状態をのぞき、２つ以上３つ以下の子ノードを持つよう
に設定され、子ノード数が３を越える場合には、内部ノ
ードを分割し、この条件を満足するように設定されてい
る。

【０００５】各葉に蓄積できるデータ数をデータ容量Ｐ
と呼び、ある葉にＰ＋１個目のデータが投入されると、
そのノードに対応する空間は分割される。例えば、図４
３に示すように、Ｐ＝３とし、空間内に１から６のデー
タが図４３（Ａ）のように配置されているとすると、こ
の空間は分割軸Ｘ１によって２分割される。このような
分割された空間は、図４３（Ｂ）のような木構造に対応
しており、各空間に対応する各葉にはそれぞれ１，４，
５と２，３，６の３個のデータがそれぞれ蓄積されてい
る。この状態で新たなデータ７が投入されると、各葉に
はそれ以上データを蓄積することはできないので、デー
タ７が投入された側の領域は図４３（Ａ）の第２の分割
軸Ｙ１によって分割される。この領域の分割に対応し
て、木構造においても分割された領域に対応する葉を分
割し、新しい葉を作成すると共に、この葉に対応する子
ノードを追加する。

【０００６】このようにすると葉の数が増加した分、新
たなデータ７の投入が可能となり、さらにデータ８の投
入も可能となる。さらに、データ９の投入すると、デー
タ９を投入領域に対応する葉には、それ以上のデータを
投入する余地がないので、この投入領域を３回目の分割
軸Ｘ２によって分割すると共に、対応する新しい葉を作
成する。ところが、ＭＤ木による分割では、１つの親ノ
ードが３つの子ノードしか持つことができないように設
定されているため、図４３（Ｃ）のノードＣに対応する
葉を分割して新しい葉を作成する場合には、内部ノード
そのものを、図４３（Ｄ）のように分割する必要があ
る。

【０００７】このような木構造を有するＭＤ木では、内
部ノードの分割により、データの分布状態や投入順序に
かかわりなく、木の根（ＲＯＯＴ）からすべての葉まで
の距離が等しいため、木構造としてのバランスが良く、
検索効率がよい利点がある。また、どの葉にも必ず（Ｐ
＋１）／２のデータが蓄積されるため、固定グリッド法
に比較して、メモリの利用効率も向上する。

【０００８】（２）ｑｕａｄ−ｔｒｅｅ法 ｑｕａｄ−ｔｒｅｅ法では、領域を２次元平面の各軸に
平行な面で４等分割する。分割された１つの空間に含ま
れるデータ数がＰ以下になるまで再帰的に分割を繰り返
し、この過程を４分木として記憶する。このｑｕａｄ−
ｔｒｅｅ法は、例えば、ＡＣＭ Ｃｏｍｐｕｔｉｎｇ
Ｓｕｒｖｅｙｓ， Ｖｏｌ，２０，Ｎｏ．４ Ｄｅｃｅ
ｍｂｅｒ １９８８に記載されている。

【０００９】この分割法では、葉の分割時にそれに対応
する子ノードを新設するだけであるため、ＭＤ木法のよ
うに内部ノードの分割時に新規なＲＯＯＴを作成する作
業は不要であり、木構造の管理は容易となる。また、領
域を等分割するため、分割位置は簡単に特定でき、ＭＤ
木法のように個々の分割軸を記憶しておく必要はない。

【００１０】一方、ｑｕａｄ−ｔｒｅｅ法では、データ
の分布を無視した等面積分割が行われるため、データの
分布が一様でない場合に、木のバランス性およびメモリ
の利用効率が極端に低下する。

【００１１】（３）範囲検索、最近傍データ検索 前記のようなＭＤ木法やｑｕａｄ−ｔｒｅｅ法によって
空間を階層的に分割するデータの管理方法においても、
通常のデータ管理方法と同様に、範囲検索や最近傍デー
タ検索が要求される。すなわち、範囲検索は、一定の値
の範囲に属するデータを検索するものである。また、最
近傍データ検索は、例えば、図形の中心点やカーソル、
各データの平均値や中心値などのある特定の値から最も
近い値を持つデータを検索するものである。

【００１２】図４４に最近傍データ検索の一例を挙げ
る。この例は、平面図形データを管理する装置におい
て、登録されたデータである図形要素の指定が容易に行
えるようにカーソルに最も近い図形要素を常に色替え表
示するものである。この例では、図４４（Ａ）に示すよ
うにカーソル位置に対応する点Ｑを含む領域に対応する
葉を求め、その葉の中で点Ｑに最も近いデータ１を求め
る。次に、点Ｑとデータ１の距離Ｄ１に含まれるデータ
を範囲検索を利用して他の葉の中から検索し、点Ｑとの
距離Ｄ２がより近いデータ３を得る。以下、指定範囲を
Ｄ２に変更し検索を続ける。

【００１３】

【発明が解決しようとする課題】

（１）分割手法による問題点 ところで、前記のようなＭＤ木法においては、葉の分割
における空間分割法は、Ｘ−Ｙ−Ｘ−Ｙ・・のように巡
回的に分割軸を選択したり、あるいは長方形の辺の長さ
により分割軸を選択するなどの方法があるが、基本的に
は、データ量によって分割する可変面積（容積）分割を
基本としている。しかしながら、このような可変面積分
割は、分割軸の位置が一定でないため、分割作業時に分
割位置の算定に時間がかかると共に、各分割軸の座標を
記憶しておく必要があり、その分だけ必要な記憶領域が
増大する欠点があった。また、完全平衡木を作成するた
めに、内部ノードの分割時に分割する葉に対応するノー
ドを新設するだけでなく、新設したノードから遡ってＲ
ＯＯＴとなるノードを新設する必要があり、分割する葉
に対応するノードのみを新設すれば良い他の方法に比較
して、木構造の管理が複雑化する欠点があった。

【００１４】（２）末端の葉のみのデータ登録による問
題点 さらに、前記ＭＤ木法やｑｕａｄ−ｔｒｅｅ法などの従
来の技術では、木構造の末端に存在する各葉にだけデー
タを蓄積するものであるため、領域内に投入するデータ
が他の領域にもまたがる場合には、複数の領域に重複登
録されるデータ数が多くなり、それに伴って個々の領域
内に存在すると判定されるデータ数が大きくなるため、
その分領域の分割数も多くなる。すなわち、図４５に示
すように、線分Ｌが領域Ｂ，Ｃ，Ｄにまたがって存在す
る場合、この線分はＬは各領域に対応するすべての葉に
登録される。しかし、各葉に登録できるデータ数はあら
かじめＰに設定されているので、重複分だけ余分にデー
タ数が領域に投入されているのと同じことになり、その
ために領域の分割数が多くなり、分割領域に対応する内
部ノードや葉の数も多くなる。その結果、木構造が複雑
がすると共に、必要とするメモリの増大や、検索効率の
低下を招く欠点があった。特に、工事設計、設備管理、
図面管理などのように、異なった長さ、面積、容積など
を有する多数の図形データを管理する場合には、従来技
術のように末端の葉に各領域に属するデータをすべて登
録し、かつデータ数によって領域を分割していると、ほ
とんどの図形データが重複登録の対象となり、メモリの
利用効率が極端に低下する。

【００１５】さらに、前記の従来技術では、末端の葉を
分割する基準を、その葉に登録するデータ数が予め設定
された値Ｐを越えるか否かによっていた。そのため、重
複登録が多いと、末端の葉を分割しても分割後の葉に登
録されたデータ数が分割前の葉に登録されたデータ数に
比較してほとんど減少せず、その結果、さらに分割を繰
り返す必要性が生じ、記憶領域の限度まで際限なく分割
が行われてしまう欠点もあった。

【００１６】また、ＭＤ木法では、データ数が等しくな
るように領域を分割するため、結果として分割軸による
図形データの分割を避けることもあるが、ｑｕａｄ−ｔ
ｒｅｅ法では、データの分布を無視した等面積分割が行
われるため、図形データの分割を避けるように分割軸を
配置することはできない。そのため、一定のサイズを有
する図形データが分割される機会が多くなり、重複登録
の可能性がより高くなっていた。

【００１７】（３）中間ノードへの登録 これを改善するために、ｑｕａｄ−ｔｒｅｅ法では、次
のような手法が採用されている。まず、前記ＡＣＭ Ｃ
ｏｍｐｕｔｉｎｇ Ｓｕｒｖｅｙｓ， Ｖｏｌ，２０，
Ｎｏ．４ Ｄｅｃｅｍｂｅｒ １９８８の第２９９頁の
Ｆｉｇｕｒｅ１９．に記載の手法は、図４６に記載のよ
うな図形データＡ−Ｇをｑｕａｄ−ｔｒｅｅによって管
理する場合に、２以上の領域にまたがる図形について
は、中間ノードに登録することにより、重複登録を避け
ている。すなわち、図形データＡ，Ｅは全領域（全世
界）を４分割してなる領域の複数にまたがるために、こ
れらの領域を包含する全領域に対応する親ノード１に登
録される。同様に、領域をまたがる図形データＢ，Ｃ，
Ｄはそれらをすべて包含する領域に対応するノード３
に、図形データＧはノード５に対応する。そして、また
がることのない図形データＦは、最も細分化された領域
に対応するノード１５に登録される。

【００１８】確かにこのような従来技術では複数領域に
またがったデータの重複登録は完全に解消される利点は
ある。しかし、このような手法では、図形データＨのよ
うに複数の領域にまたがる部分がごく少ないデータであ
っても、その複数の領域を包含する上位の領域に対応す
るノードに登録することになる。その結果、上位の領域
内に登録するデータが多くなり、データ検索の範囲が広
くなって、検索効率が低下する。すなわち、広大な範囲
を持つ上位の領域全体を検索するよりも、たとえ重複登
録の結果検索対象領域の数は多くなっても範囲の狭い複
数の領域を検索する方が、検索を高速に行えるからであ
る。

【００１９】このような重複登録を完全に避ける手法の
問題点を解決するために、前記の文献第３０１頁のＦｉ
ｇｕｒｅ ２１．には、中間ノードへの登録を行うと同
時に重複登録も可能とした手法も提案されている。この
手法を図４７により説明する。

【００２０】例えば、図形データＧは、それを含む最小
の領域は全領域を４分割した際の右下の領域５＃に属す
るので、この領域をさらに４分割してその境界Ｘ１で図
形Ｇを２つの図形データＧ１，Ｇ２に分割する。そし
て、分割されたそれぞれの図形データＧ１，Ｇ２につい
て、それを包含する最小の領域１０＃，１１＃を求め
る。この場合、図形データＦが属する領域１４＃と同じ
サイズまで領域の分割を行うと、図形データＧの分割さ
れた部分はＧ１，Ｇ２さらに分割されることになるた
め、「図形データを包含する最小の領域を判定した後、
１回だけ図形データの分割を行う」という条件に反す
る。そのため、図形データＧは、領域１０＃，１１＃に
対応するノード１０，１１に登録する。

【００２１】ここで、ノード１１は中間ノードであり、
この中間ノード１１にデータを登録することにより、そ
れよりも中間ノード１１の子ノードである末端のノード
１５，１６にデータを重複して登録するよりも、検索速
度を向上できる。一方、図形データＧが存在する２つの
ノード１０，１１の両方に図形データＧを登録すること
により、検索対象範囲を図形データＧが属する最小の領
域５＃よりもより狭い領域６＃，７＃に対応するノード
６，７に限定することが可能になる。

【００２２】ところが、この従来技術は、図形データの
分割を１回しか行わないことを条件としているために、
１つのデータについての重複登録が１回で済むという利
点はあるものの、パイプライン、送電線、交通路などの
ように長尺の図形データのように、重複数が多くなった
としても分割して登録したいデータを処理するには不適
当であった。

【００２３】（４）最近傍データ検索時の問題点 また、前記の従来技術では、最近傍データ検索を行う場
合に、指定された点Ｑを含む葉を求め、その葉の中で最
も近いデータを求めてから、そのデータと指定された点
Ｑとの距離を利用して範囲検索を行っていた。しかし、
ＭＤ木法のように、各葉の内部に必ずデータが存在する
場合には、このような手法を利用することは可能であ
る。しかし、ｑｕａｄ−ｔｒｅｅ法のように、領域を等
分割するものでは、分割された領域内にデータが存在し
ない場合があり、そのような場合には、前記のような手
法では最近傍データの検索を行うことが不可能であっ
た。

【００２４】（５）発明の目的 本発明は前記のような従来技術の問題点を解決するため
に提案されたもので、その目的は、末端の葉を分割する
か否かの判定を行うことにより、それ以上分割してもデ
ータ管理上のメリットがない場合には、分割を行わない
ことによって、メモリの利用効率の向上と検索処理の高
速化を可能とすることにある。

【００２５】本発明の他の目的は、一定の条件下で、内
部ノードにもデータを登録すると共に重複登録もことに
より、複数の分割領域にまたがるようなデータについて
の検索速度の向上を可能とすることにある。

【００２６】本発明の他の目的は、１個あるいは複数個
の分割された領域を包含する一定の範囲を定め、この範
囲内に属するデータを迅速に検索することにある。本発
明の他の目的は、指定した点の最近傍に位置するデータ
を検索する処理に当たって、指定した点を含む分割され
た領域内に最近傍データが存在しない場合でも、他の領
域内の最近傍データを迅速に検索することにある。本発
明の他の目的は、２のＮ乗分木で領域の分割を管理する
と共に、各領域を等面積（等容積）に分割することによ
り、領域の分割および領域の合併作業を容易に実施でき
ると共に、分割位置を記憶することを不要として利用す
るメモリ領域の低減することにある。

【００２７】本発明の他の目的は、２のＮ乗分木で領域
の分割を管理すると共に、各領域をデータ数に依存する
ことなく、一定の分割規則（制限された範囲内における
ランダムな分割も含む）にしたがって分割することによ
り、領域の分割作業を容易に実施することにある。

【００２８】

【課題を解決するための手段】前記の目的を達成するた
め、請求項１の発明は、コンピュータの記憶装置に管理
対象となる複数の多次元データを多次元空間内に配置
し、各多次元データの値を多次元空間内における座標と
してコンピュータの記憶装置に登録するステップと、前
記多次元空間を複数のメッシュに階層的に分割し、分割
された各階層のメッシュを木構造の各ノードに対応さ
せ、各メッシュと各ノードとの対応関係を記録するステ
ップと、分割された各メッシュに多次元データに関する
情報を登録するステップと、前記各メッシュに登録され
た情報に基づいてコンピュータの記憶領域内に蓄積され
ている多次元データを管理するステップを有する多次元
データ管理方法において、前記各メッシュのうち、少な
くとも前記木構造の末端のノードに対応する末端メッシ
ュに多次元データを登録するステップと、前記末端メッ
シュに登録できる多次元データ数を一定値以下に設定
し、末端メッシュに登録する多次元データ数が前記設定
値を超えた場合に、その末端メッシュの分割を試行する
ステップと、この末端メッシュの分割ステップの試行に
当たり、予め設定された分割許容条件にしたがって分割
の可否を判定するステップを備えていることを特徴とす
る。

【００２９】請求項２の発明は、コンピュータの記憶装
置に管理対象となる複数の多次元データを多次元空間内
に配置し、各多次元データの値を多次元空間内における
座標としてコンピュータの記憶装置に登録するステップ
と、前記多次元空間を複数のメッシュに階層的に分割
し、分割された各階層のメッシュを木構造の各ノードに
対応させ、各メッシュと各ノードとの対応関係を記録す
るステップと、分割された各メッシュに多次元データに
関する情報を登録するステップと、前記各メッシュに登
録された情報に基づいてコンピュータの記憶領域内に蓄
積されている多次元データを管理するステップを有する
多次元データ管理方法において、前記各メッシュのう
ち、少なくとも前記木構造の末端のノードに対応する末
端メッシュに多次元データを登録するステップと、前記
末端メッシュの親メッシュに登録できる多次元データ数
を一定値以下に設定し、前記親メッシュに所属する多次
元データ数が前記設定値未満の場合に、その末端メッシ
ュの併合を試行するステップと、前記末端メッシュをそ
の兄弟メッシュと共に親メッシュに併合するステップの
試行に当たり、予め設定された併合許容条件にしたがっ
て併合の可否を判定するステップを備えていることを特
徴とする。

【００３０】請求項３の発明は、コンピュータの記憶装
置に管理対象となる複数の多次元データを多次元空間内
に配置し、各多次元データの値を多次元空間内における
座標としてコンピュータの記憶装置に登録するステップ
と、前記多次元空間を複数のメッシュに階層的に分割
し、分割された各階層のメッシュを木構造の各ノードに
対応させ、各メッシュと各ノードとの対応関係を記録す
るステップと、分割された各メッシュに多次元データに
関する情報を登録するステップと、前記各メッシュに登
録された情報に基づいてコンピュータの記憶領域内に蓄
積されている多次元データを管理するステップを有する
多次元データ管理方法において、前記各メッシュのう
ち、少なくとも前記木構造の末端のノードに対応する末
端メッシュに多次元データを登録するステップと、前記
末端メッシュに登録できる多次元データ数を一定値以下
に設定し、末端メッシュに登録する多次元データ数が前
記設定値を超えた場合に、その末端メッシュの分割を試
行するステップと、この末端メッシュの分割ステップの
試行に当たり、予め設定された分割許容条件にしたがっ
て分割の可否を判定するステップと、前記末端メッシュ
の親メッシュに登録できる多次元データ数を一定値以下
に設定し、前記親メッシュに所属する多次元データ数が
前記設定値未満の場合に、その末端メッシュの併合を試
行するステップと、前記末端メッシュをその兄弟メッシ
ュと共に親メッシュに併合するステップの試行に当た
り、予め設定された併合許容条件にしたがって併合の可
否を判定するステップを備えていることを特徴とする。

【００３１】請求項４の発明は、請求項１または３記載
の多次元データ管理方法において、前記分割を許容する
か否かの判定ステップが、分割後の子メッシュに所属す
る多次元データ数の和と、分割前の親メッシュに所属す
る多次元データ数とを比較して、分割の可否を判定する
ものである。

【００３２】請求項５の発明は、請求項１または３記載
の多次元データ管理方法において、前記分割を許容する
か否かの判定ステップが、親メッシュに所属する多次元
データ数と、前記親メッシュから分割された子メッシュ
の中の複数の子メッシュに所属する多次元データ数とを
比較して、分割の可否を判定するものである。

【００３３】請求項６の発明は、請求項２または３記載
の多次元データ管理方法において、前記併合を許容する
か否かの判定ステップが、併合前の各子メッシュに所属
する多次元データ数の和と、併合後の親メッシュに所属
する多次元データ数とを比較して、併合の可否を判定す
るものである。

【００３４】請求項７の発明は、請求項２，３または６
記載の多次元データ管理方法において、前記併合を許容
するか否かの判定ステップが、併合後の親メッシュに所
属する多次元データ数と、これら子メッシュの中の複数
の子メッシュに所属する多次元データ数とを比較して、
併合の可否を判定するものである。

【００３５】請求項８の発明は、請求項２，３，６また
は７記載の多次元データ管理方法において、前記併合を
許容するか否かの判定ステップが、前記末端メッシュに
登録できる多次元データ数を一定値以下に設定し、親メ
ッシュを同じくする各末端メッシュに登録された多次元
データ数がいずれも前記設定値未満の場合に、その末端
メッシュの併合を実行するものである。

【００３６】請求項９の発明は、コンピュータの記憶装
置に管理対象となる複数の多次元データを多次元空間内
に配置し、各多次元データの値を多次元空間内における
座標としてコンピュータの記憶装置に登録するステップ
と、前記多次元空間を複数のメッシュに階層的に分割
し、分割された各階層のメッシュを木構造の各ノードに
対応させ、各メッシュと各ノードとの対応関係を記録す
るステップと、分割された各メッシュに多次元データに
関する情報を登録するステップと、前記各メッシュに登
録された情報に基づいてコンピュータの記憶領域内に蓄
積されている多次元データを管理するステップを有する
多次元データ管理方法において、末端メッシュの分割時
において、前記各メッシュのうち、前記木構造の末端の
ノードに対応する分割によって生じた子メッシュと、前
記末端ノードの親ノードに対応する分割によって生じた
親メッシュいずれかに多次元データを登録しなおすステ
ップと、末端メッシュの分割時において、１つの図形あ
たりの複数メッシュへの重複登録を抑制する条件に従っ
て、前記多次元データを分割によって生じた子メッシュ
と分割によって生じた親メッシュのいずれに登録しなお
すかを判定するステップを備えていることを特徴とす
る。

【００３７】請求項１０の発明は、請求項９記載の多次
元データ管理方法において、前記多次元データを親メッ
シュと子メッシュのいずれに登録するかを判定するステ
ップが、前記多次元データがその親メッシュを完全に含
んでいないことを重複登録を抑制する条件としている。

【００３８】請求項１１の発明は、請求項９または１０
記載の多次元データ管理方法において、前記多次元デー
タを親メッシュと子メッシュのいずれに登録するかを判
定するステップが、前記多次元データが重なっている子
メッシュ数が予め設定された数以下であることを重複登
録を抑制する条件としている。

【００３９】請求項１２の発明は、請求項９，１０また
は１１記載の多次元データ管理方法において、前記多次
元データを親メッシュと子メッシュのいずれに登録する
かを判定するステップが、前記多次元データごとに重複
メッシュ数の上限が定められており、子メッシュへの登
録を行っても重複登録数が上限以下であることを重複登
録を抑制する条件としている。

【００４０】請求項１３の発明は、コンピュータの記憶
装置に管理対象となる複数の多次元データを多次元空間
内に配置し、各多次元データの値を多次元空間内におけ
る座標としてコンピュータの記憶装置に登録するステッ
プと、前記多次元空間を複数のメッシュに階層的に分割
し、分割された各階層のメッシュを木構造の各ノードに
対応させ、各メッシュと各ノードとの対応関係を記録す
るステップと、分割された各メッシュに多次元データに
関する情報を登録するステップと、前記各メッシュに登
録された情報に基づいてコンピュータの記憶領域内に蓄
積されている多次元データを管理するステップを有する
多次元データ管理方法において、前記各メッシュのう
ち、前記木構造の末端のノードに対応する末端メッシュ
と、前記末端ノードの親ノードに対応する中間メッシュ
の少なくとも一方に多次元データを登録するステップ
と、多次元データの登録時において、登録する多次元デ
ータの状態に従って、前記多次元データを末端メッシュ
と中間メッシュのどこに登録するかを判定するステップ
を備えていることを特徴とする。

【００４１】請求項１４の発明は、請求項１３記載の多
次元データ管理方法において、前記多次元データを末端
メッシュと中間メッシュのどこに登録するかを判定する
ステップが、前記多次元データが重なり合っている子メ
ッシュ数に応じて登録するメッシュを選択するものであ
る。

【００４２】請求項１５の発明は、請求項１３または１
４記載の多次元データ管理方法において、前記多次元デ
ータを末端メッシュと中間メッシュのどこに登録するか
を判定するステップが、前記多次元データによって登録
すべきメッシュの大きさの限度が決まっており、このメ
ッシュの大きさの限度に従って前記多次元データを登録
するメッシュを選択するものである。

【００４３】請求項１６の発明は、請求項１３，１４ま
たは１５記載の多次元データ管理方法において、前記多
次元データを末端メッシュと中間メッシュのどこに登録
するかを判定するステップが、前記多次元データごとに
重複登録メッシュ数の限度が定められており、この限度
に従って前記多次元データを登録するメッシュを選択す
るものである。

【００４４】請求項１７の発明は、請求項１３，１４，
１５または１６記載の多次元データ管理方法において、
前記多次元データを末端メッシュと中間メッシュのどこ
に登録するかを判定するステップが、前記多次元空間内
における前記多次元データの大きさと、前記多次元空間
内における所定のメッシュの大きさとの比較から、前記
多次元データを登録するメッシュを選択するものであ
る。

【００４５】請求項１８の発明は、請求項１，２，３，
９または１３記載の多次元データ管理方法において、前
記コンピュータの記憶領域内に蓄積されている多次元デ
ータを管理するステップが、前記多次元空間内における
指定された範囲を対象とし、この指定された範囲内に属
する多次元データを検索する範囲検索ステップを含むこ
とを特徴とする。

【００４６】請求項１９の発明は、請求項１，２，３，
９または１３記載の多次元データ管理方法において、前
記コンピュータの記憶領域内に蓄積されている多次元デ
ータを管理するステップが、前記多次元空間内における
指定された点に最も近い多次元データを検索する最近傍
データの検索ステップを含むことを特徴とする。

【００４７】請求項２０の発明は、請求項１９記載の多
次元データ管理方法において、前記最近傍データの検索
ステップが、前記指定された点を含む最小のメッシュに
多次元データが登録されていない場合に、前記最小のメ
ッシュの親メッシュ、最小のメッシュに隣接するメッシ
ュ、親メッシュの親メッシュ、隣接するメッシュの親メ
ッシュ、隣接するメッシュに隣接する他のメッシュのご
とく、再帰的に最近傍データの候補が１つ決定されるま
で検索範囲を拡大するステップを含むことを特徴とす
る。

【００４８】請求項２１の発明は、請求項１，２，３，
９または１３記載の多次元データ管理方法において、前
記多次元空間を複数のメッシュに階層的に分割し、分割
された各階層のメッシュを木構造の各ノードに対応さ
せ、各メッシュと各ノードとの対応関係を記録するステ
ップが、２のＮ乗分木による木構造に対応して前記多次
元空間を階層的に２のＮ乗個に等分割するものである。

【００４９】請求項２２の発明は、請求項１，２，３，
９または１３記載の多次元データ管理方法において、管
理対象となる多次元データが、２次元の平面もしくは３
次元の空間内に配置された図形データである。

【００５０】請求項２３の発明は、コンピュータの記憶
装置に管理対象となる複数の多次元データを多次元空間
内に配置し、各多次元データの値を多次元空間内におけ
る座標としてコンピュータの記憶装置に登録するステッ
プと、前記多次元空間を複数のメッシュに階層的に分割
し、分割された各階層のメッシュを木構造の各ノードに
対応させ、各メッシュと各ノードとの対応関係を記録す
るステップと、分割された各メッシュに多次元データに
関する情報を登録するステップと、前記各メッシュに登
録された情報に基づいてコンピュータの記憶領域内に蓄
積されている多次元データを管理するステップを有する
多次元データ管理方法を実行させるためのプログラムを
記録した媒体であって、前記プログラムは、前記各メッ
シュのうち、少なくとも前記木構造の末端のノードに対
応する末端メッシュに多次元データを登録するステップ
と、前記末端メッシュに登録できる多次元データ数を一
定値以下に設定し、末端メッシュに登録する多次元デー
タ数が前記設定値を超えた場合に、その末端メッシュの
分割を試行するステップと、この末端メッシュの分割ス
テップの試行に当たり、予め設定された分割許容条件に
したがって分割の可否を判定するステップを備えている
ことを特徴とする。

【００５１】請求項２４の発明は、コンピュータの記憶
装置に管理対象となる複数の多次元データを多次元空間
内に配置し、各多次元データの値を多次元空間内におけ
る座標としてコンピュータの記憶装置に登録するステッ
プと、前記多次元空間を複数のメッシュに階層的に分割
し、分割された各階層のメッシュを木構造の各ノードに
対応させ、各メッシュと各ノードとの対応関係を記録す
るステップと、分割された各メッシュに多次元データに
関する情報を登録するステップと、前記各メッシュに登
録された情報に基づいてコンピュータの記憶領域内に蓄
積されている多次元データを管理するステップを有する
多次元データ管理方法を実行させるためのプログラムを
記録した媒体であって、前記プログラムは、前記各メッ
シュのうち、少なくとも前記木構造の末端のノードに対
応する末端メッシュに多次元データを登録するステップ
と、前記末端メッシュの親メッシュに登録できる多次元
データ数を一定値以下に設定し、前記親メッシュに所属
する多次元データ数が前記設定値未満の場合に、その末
端メッシュの併合を試行するステップと、前記末端メッ
シュをその兄弟メッシュと共に親メッシュに併合するス
テップの試行に当たり、予め設定された併合許容条件に
したがって併合の可否を判定するステップを備えている
ことを特徴とする。

【００５２】請求項２５の発明は、コンピュータの記憶
装置に管理対象となる複数の多次元データを多次元空間
内に配置し、各多次元データの値を多次元空間内におけ
る座標としてコンピュータの記憶装置に登録するステッ
プと、前記多次元空間を複数のメッシュに階層的に分割
し、分割された各階層のメッシュを木構造の各ノードに
対応させ、各メッシュと各ノードとの対応関係を記録す
るステップと、分割された各メッシュに多次元データに
関する情報を登録するステップと、前記各メッシュに登
録された情報に基づいてコンピュータの記憶領域内に蓄
積されている多次元データを管理するステップを有する
多次元データ管理方法を実行させるためのプログラムを
記録した媒体であって、前記プログラムは、前記各メッ
シュのうち、少なくとも前記木構造の末端のノードに対
応する末端メッシュに多次元データを登録するステップ
と、前記末端メッシュに登録できる多次元データ数を一
定値以下に設定し、末端メッシュに登録する多次元デー
タ数が前記設定値を超えた場合に、その末端メッシュの
分割を試行するステップと、この末端メッシュの分割ス
テップの試行に当たり、予め設定された分割許容条件に
したがって分割の可否を判定するステップと、前記末端
メッシュの親メッシュに登録できる多次元データ数を一
定値以下に設定し、前記親メッシュに所属する多次元デ
ータ数が前記設定値未満の場合に、その末端メッシュの
併合を試行するステップと、前記末端メッシュをその兄
弟メッシュと共に親メッシュに併合するステップの試行
に当たり、予め設定された併合許容条件にしたがって併
合の可否を判定するステップを備えていることを特徴と
する。

【００５３】請求項２６の発明は、コンピュータの記憶
装置に管理対象となる複数の多次元データを多次元空間
内に配置し、各多次元データの値を多次元空間内におけ
る座標としてコンピュータの記憶装置に登録するステッ
プと、前記多次元空間を複数のメッシュに階層的に分割
し、分割された各階層のメッシュを木構造の各ノードに
対応させ、各メッシュと各ノードとの対応関係を記録す
るステップと、分割された各メッシュに多次元データに
関する情報を登録するステップと、前記各メッシュに登
録された情報に基づいてコンピュータの記憶領域内に蓄
積されている多次元データを管理するステップを有する
多次元データ管理方法を実行させるためのプログラムを
記録した媒体であって、前記プログラムは、末端メッシ
ュの分割時において、前記各メッシュのうち、前記木構
造の末端のノードに対応する分割によって生じた子メッ
シュと、前記末端ノードの親ノードに対応する分割によ
って生じた親メッシュいずれかに多次元データを登録し
なおすステップと、末端メッシュの分割時において、１
つの図形あたりの複数メッシュへの重複登録を抑制する
条件に従って、前記多次元データを分割によって生じた
子メッシュと分割によって生じた親メッシュのいずれに
登録しなおすかを判定するステップを備えていることを
特徴とする。

【００５４】請求項２７の発明は、コンピュータの記憶
装置に管理対象となる複数の多次元データを多次元空間
内に配置し、各多次元データの値を多次元空間内におけ
る座標としてコンピュータの記憶装置に登録するステッ
プと、前記多次元空間を複数のメッシュに階層的に分割
し、分割された各階層のメッシュを木構造の各ノードに
対応させ、各メッシュと各ノードとの対応関係を記録す
るステップと、分割された各メッシュに多次元データに
関する情報を登録するステップと、前記各メッシュに登
録された情報に基づいてコンピュータの記憶領域内に蓄
積されている多次元データを管理するステップを有する
多次元データ管理方法を実行させるためのプログラムを
記録した媒体であって、前記プログラムは、前記各メッ
シュのうち、前記木構造の末端のノードに対応する末端
メッシュと、前記末端ノードの親ノードに対応する中間
メッシュの少なくとも一方に多次元データを登録するス
テップと、多次元データの登録時において、登録する多
次元データの状態に従って、前記多次元データを末端メ
ッシュと中間メッシュのどこに登録するかを判定するス
テップを備えていることを特徴とする。

【００５５】請求項２８の発明は、管理対象となる複数
の多次元データを多次元空間内に配置し、各多次元デー
タの値を多次元空間内における座標として登録する多次
元データ記憶手段と、前記多次元データ記憶手段に多次
元データを登録・削除する多次元データ登録削除手段
と、前記多次元空間を複数のメッシュに階層的に分割
し、分割された各階層のメッシュを木構造の各ノードに
対応させ、各メッシュと各ノードとの対応関係を記憶す
る木構造管理手段と、分割された各メッシュに前記多次
元データに関する情報を登録するメッシュデータ記憶手
段と、前記各メッシュのうち、少なくとも前記木構造の
末端のノードに対応する末端メッシュに、その末端メッ
シュに対応する前記多次元データに関する情報を登録ま
たは削除するメッシュデータ登録削除手段とを備え、前
記各メッシュデータ記憶手段に登録された情報に基づい
て前記多次元データ記憶手段に蓄積されている多次元デ
ータを管理する多次元データ管理装置において、前記末
端メッシュに登録できる多次元データ数を一定値以下に
設定し、末端メッシュに登録する多次元データ数が前記
設定値を超えた場合にその末端メッシュを分割するメッ
シュ分割手段と、このメッシュ分割手段による末端メッ
シュの分割処理に当たり、予め設定された分割許容条件
にしたがって分割の可否を判定する分割判定手段を備え
ていることを特徴とする。

【００５６】請求項２９の発明は、管理対象となる複数
の多次元データを多次元空間内に配置し、各多次元デー
タの値を多次元空間内における座標として登録する多次
元データ記憶手段と、前記多次元データ記憶手段に多次
元データを登録・削除する多次元データ登録削除手段
と、前記多次元空間を複数のメッシュに階層的に分割
し、分割された各階層のメッシュを木構造の各ノードに
対応させ、各メッシュと各ノードとの対応関係を記憶す
る木構造管理手段と、分割された各メッシュに前記多次
元データに関する情報を登録するメッシュデータ記憶手
段と、前記各メッシュのうち、少なくとも前記木構造の
末端のノードに対応する末端メッシュに、その末端メッ
シュに重なる前記多次元データに関する情報を登録また
は削除するメッシュデータ登録削除手段とを備え、前記
各メッシュデータ記憶手段に登録された情報に基づいて
前記多次元データ記憶手段に蓄積されている多次元デー
タを管理する多次元データ管理装置において、前記末端
メッシュの親メッシュに登録できる多次元データ数を一
定値以下に設定し、前記親メッシュに所属する多次元デ
ータ数が前記設定値未満の場合に、その末端メッシュの
併合を試行するメッシュ併合手段と、前記末端メッシュ
をその兄弟メッシュと共に親メッシュに併合するステッ
プの試行に当たり、予め設定された併合許容条件にした
がって併合の可否を判定する併合判定手段を備えている
ことを特徴とする。

【００５７】請求項３０の発明は、管理対象となる複数
の多次元データを多次元空間内に配置し、各多次元デー
タの値を多次元空間内における座標として登録する多次
元データ記憶手段と、前記多次元データ記憶手段に多次
元データを登録・削除する多次元データ登録削除手段
と、前記多次元空間を複数のメッシュに階層的に分割
し、分割された各階層のメッシュを木構造の各ノードに
対応させ、各メッシュと各ノードとの対応関係を記憶す
る木構造管理手段と、分割された各メッシュに前記多次
元データに関する情報を登録するメッシュデータ記憶手
段と、前記各メッシュのうち、少なくとも前記木構造の
末端のノードに対応する末端メッシュに、その末端メッ
シュに重なる前記多次元データに関する情報を登録また
は削除するメッシュデータ登録削除手段とを備え、前記
各メッシュデータ記憶手段に登録された情報に基づいて
前記多次元データ記憶手段に蓄積されている多次元デー
タを管理する多次元データ管理装置において、前記末端
メッシュに登録できる多次元データ数を一定値以下に設
定し、末端メッシュに登録する多次元データ数が前記設
定値を超えた場合にその末端メッシュを分割するメッシ
ュ分割手段と、このメッシュ分割手段による末端メッシ
ュの分割処理に当たり、予め設定された分割許容条件に
したがって分割の可否を判定する分割判定手段と、前記
末端メッシュの親メッシュに登録できる多次元データ数
を一定値以下に設定し、前記親メッシュに所属する多次
元データ数が前記設定値未満の場合に、その末端メッシ
ュの併合を試行するメッシュ併合手段と、前記末端メッ
シュをその兄弟メッシュと共に親メッシュに併合するス
テップの試行に当たり、予め設定された併合許容条件に
したがって併合の可否を判定する併合判定手段を備えて
いることを特徴とする。

【００５８】請求項３１の発明は、請求項２８または３
０記載の多次元データ管理装置において、前記分割判定
手段が、分割後の子メッシュに所属する多次元データ数
の和と、分割前の親メッシュに所属する多次元データ数
とを比較して、分割の可否を判定するものである。

【００５９】請求項３２の発明は、請求項２８または３
０記載の多次元データ管理装置において、前記分割判定
手段が、親メッシュに所属する多次元データ数と、前記
親メッシュから分割された子メッシュの中の複数の子メ
ッシュに所属する多次元データ数とを比較して、分割の
可否を判定するものである。

【００６０】請求項３３の発明は、請求項２９または３
０記載の多次元データ管理装置において、前記併合判定
手段が、併合前の各子メッシュに所属する多次元データ
数の和と、併合後の親メッシュに所属する多次元データ
数とを比較して、併合の可否を判定するものである。

【００６１】請求項３４の発明は、請求項２９，３０ま
たは３３記載の多次元データ管理装置において、前記併
合判定手段が、併合後の親メッシュに所属する多次元デ
ータ数と、これら子メッシュの中の複数の子メッシュに
所属する多次元データ数とを比較して、併合の可否を判
定するものである。

【００６２】請求項３５の発明は、請求項２９，３０ま
たは３３記載の多次元データ管理装置において、前記併
合判定手段が、前記末端メッシュに登録できる多次元デ
ータ数を一定値以下に設定し、親メッシュを同じくする
各末端メッシュに登録された多次元データ数がいずれも
前記設定値未満の場合に、その末端メッシュの併合を実
行するものである。

【００６３】請求項３６の発明は、管理対象となる複数
の多次元データを多次元空間内に配置し、各多次元デー
タの値を多次元空間内における座標として登録する多次
元データ記憶手段と、前記多次元データ記憶手段に多次
元データを登録・削除する多次元データ登録削除手段
と、前記多次元空間を複数のメッシュに階層的に分割
し、分割された各階層のメッシュを木構造の各ノードに
対応させ、各メッシュと各ノードとの対応関係を記憶す
る木構造管理手段と、分割された各メッシュに前記多次
元データに関する情報を登録するメッシュデータ記憶手
段と、前記各メッシュのうち、少なくとも前記木構造の
末端のノードに対応する末端メッシュに、その末端メッ
シュに重なる前記多次元データに関する情報を登録また
は削除するメッシュデータ登録削除手段とを備え、前記
各メッシュデータ記憶手段に登録された情報に基づいて
前記多次元データ記憶手段に蓄積されている多次元デー
タを管理する多次元データ管理装置において、前記メッ
シュデータ登録削除手段およびメッシュ分割手段に関連
して、末端メッシュの分割時において、前記各メッシュ
のうち、前記木構造の末端のノードに対応する分割によ
って生じた子メッシュと、前記末端ノードの親ノードに
対応する分割によって生じた親メッシュいずれかに多次
元データを登録しなおすメッシュデータ再登録手段と、
末端メッシュの分割時において、１つの図形あたりの複
数メッシュへの重複登録を抑制する条件に従って、前記
多次元データを分割によって生じた子メッシュと分割に
よって生じた親メッシュのいずれに登録しなおすかを判
定する再登録メッシュ判定手段が設けられいることを特
徴とする。

【００６４】請求項３７の発明は、請求項３６記載の多
次元データ管理装置において、前記再登録メッシュ判定
手段が、前記多次元データがその親メッシュを完全に含
んでいないことを重複登録を抑制する条件としている。

【００６５】請求項３８の発明は、請求項３６または３
７記載の多次元データ管理装置において、前記再登録メ
ッシュ判定手段が、前記多次元データが重なっている子
メッシュ数が予め設定された数以下であることを重複登
録を抑制する条件としている。

【００６６】請求項３９の発明は、請求項３６，３７ま
たは３８記載の多次元データ管理装置において、前記再
登録メッシュ判定手段が、前記多次元データごとに重複
メッシュ数の上限が定められており、子メッシュへの登
録を行っても重複登録数が上限以下であることを重複登
録を抑制する条件としている。

【００６７】請求項４０の発明は、管理対象となる複数
の多次元データを多次元空間内に配置し、各多次元デー
タの値を多次元空間内における座標として登録する多次
元データ記憶手段と、前記多次元データ記憶手段に多次
元データを登録・削除する多次元データ登録削除手段
と、前記多次元空間を複数のメッシュに階層的に分割
し、分割された各階層のメッシュを木構造の各ノードに
対応させ、各メッシュと各ノードとの対応関係を記憶す
る木構造管理手段と、分割された各メッシュに前記多次
元データに関する情報を登録するメッシュデータ記憶手
段と、前記各メッシュのうち、少なくとも前記木構造の
末端のノードに対応する末端メッシュに、その末端メッ
シュに重なる前記多次元データに関する情報を登録また
は削除するメッシュデータ登録削除手段とを備え、前記
各メッシュデータ記憶手段に登録された情報に基づいて
前記多次元データ記憶手段に蓄積されている多次元デー
タを管理する多次元データ管理装置において、前記メッ
シュデータ登録削除手段およびメッシュ分割手段に関連
して、前記各メッシュのうち、前記木構造の末端のノー
ドに対応する末端メッシュと、前記末端ノードの親ノー
ドに対応する中間メッシュの少なくとも一方に多次元デ
ータを登録するデータ登録手段と、多次元データの登録
時において、登録する多次元データの状態に従って、前
記多次元データを末端メッシュと中間メッシュのどこに
登録するかを判定する登録位置判定手段が設けられてい
ることを特徴とする。

【００６８】請求項４１の発明は、請求項４０記載の多
次元データ管理装置において、登録位置判定手段が、前
記多次元データが重なり合っている子メッシュ数に応じ
て登録するメッシュを選択するものである。

【００６９】請求項４２の発明は、請求項４０または４
１記載の多次元データ管理装置において、前記登録位置
判定手段が、前記多次元データによって登録すべきメッ
シュの大きさの限度が決まっており、このメッシュの大
きさの限度に従って前記多次元データを登録するメッシ
ュを選択するものである。

【００７０】請求項４３の発明は、請求項４０，４１ま
たは４２記載の多次元データ管理装置において、前記登
録位置判定手段が、前記多次元データごとに重複登録メ
ッシュ数の限度が定められており、この限度に従って前
記多次元データを登録するメッシュを選択するものであ
る。

【００７１】請求項４４の発明は、請求項４０，４１，
４２または４３記載の多次元データ管理装置において、
前記登録位置判定手段が、前記多次元空間内における前
記多次元データの大きさと、前記多次元空間内における
所定のメッシュの大きさとの比較から、前記多次元デー
タを登録するメッシュを選択するものである。

【００７２】請求項４５の発明は、請求項２８，２９，
３０，３６または４０記載の多次元データ管理装置にお
いて、前記コンピュータの記憶領域内に蓄積されている
多次元データを管理する装置が、前記多次元空間内にお
ける指定された範囲を対象とし、この指定された範囲内
に属する多次元データを検索する範囲検索手段を含むこ
とを特徴とする。

【００７３】請求項４６の発明は、請求項２８，２９，
３０，３６，４０または４５記載の多次元データ管理装
置において、前記コンピュータの記憶領域内に蓄積され
ている多次元データを管理する装置が、前記多次元空間
内における指定された点に最も近い多次元データを検索
する最近傍データの検索手段を含むことを特徴とする。

【００７４】請求項４７の発明は、請求項４６記載の多
次元データ管理装置において、前記最近傍データの検索
手段が、前記指定された点を含む最小のメッシュに多次
元データが登録されていない場合に、前記最小のメッシ
ュの親メッシュ、最小のメッシュに隣接するメッシュ、
親メッシュの親メッシュ、隣接するメッシュの親メッシ
ュ、隣接するメッシュに隣接する他のメッシュのごと
く、再帰的に最近傍データの候補が１つ決定されるまで
検索範囲を拡大することを特徴とする。

【００７５】請求項４８の発明は、請求項２８，２９，
３０，３６または４０記載の多次元データ管理装置にお
いて、前記木構造管理手段が、２のＮ乗分木による木構
造に対応して前記多次元空間を階層的に２のＮ乗個に等
分割するものである。

【００７６】請求項４９の発明は、請求項２８，２９，
３０，３６または４０記載の多次元データ管理装置にお
いて、管理対象となる多次元データが、２次元の平面も
しくは３次元の空間内に配置された図形データである。

【００７７】

【発明の実施の形態】以下、本発明の実施形態につい
て、図面を参照して具体的に説明する。なお、以下の実
施形態は、電力系統の配電線図のような２次元データの
管理・検索についてのものである。

【００７８】［１．用語の説明］各実施形態について説
明する前に、本明細書中で用いられる種々の用語につい
て説明する。

【００７９】（ａ）データの管理 データの登録・削除、メッシュの分割・併合、データの
検索（例えば、矩形検索、最近傍データ検索）などのデ
ータを処理する１つあるいは複数の手続きを包含する。

【００８０】（ｂ）世界座標範囲または世界範囲 データを管理する空間の範囲のことをいう。通常、デー
タ格納領域の初期時に与えられた範囲である。

【００８１】（ｃ）図形 多次元空間内で座標によって表示される多次元データの
１つであって、本実施の形態では、２次元空間内に配置
された点、線、面などの図形要素の単独あるいは組み合
わせからなるデータを指す。図形は、その図形が世界座
標範囲でどのような位置／領域を占めているかを表わす
数値データを持っている。この図形データは与えられた
ままデータ領域にコピーされる。なお、３次元空間内に
おいては、立体図形を指すことは言うまでもない。図形
には、図形要素の組み合わせからなる比較的小さな図形
（本実施の形態ではサブ図形と呼ぶ）と、このサブ図形
をさらに組み合わせてなるより大きな図形（本実施の形
態ではスーパー図形と呼ぶ）がある。本実施の形態にお
いて、登録、削除、検索などの管理対象となる図形に
は、図形要素、サブ図形、スーパー図形のいずれもが含
まれる。図形をどのような態様で管理するかは、管理の
目的、コンピュータの記憶領域の大小、検索速度、分割
するメッシュの階層レベルなどによって適宜選択するこ
とができる。

【００８２】（ｄ）メッシュ 世界座標範囲が２のＮ乗分割されてできる空間を言う。
従来技術の説明で使用したデータが属する領域と同じ。
本発明の第１実施形態ないし第３実施形態では図形とい
う２次元データを管理するため、世界座標範囲を４分割
（繰り返し４分割された場合も含む）された結果できる
四角形をいう。世界座標範囲全体自体もメッシュと呼
ぶ。ある程度の数の図形データがデータ格納領域に登録
された状態では、世界座標範囲はいくつかのメッシュに
分割されている。通常、図形の詰まったところは細かく
小さいメッシュに分割され、図形の少ないところは大き
なメッシュに分割される。

【００８３】Ｎ次元空間における分割では、各次元につ
いて２分割するので、メッシュは２のＮ乗分割される。
世界範囲から始まって細かく分割されるメッシュを２の
Ｎ乗分木を用いて管理する。２のＮ乗分木のデータ構造
もデータ領域上に載せる。２のＮ乗分木の各ノードから
対応するメッシュに関する情報が容易に得られる。

【００８４】（ｅ）木構造 メッシュ分割された世界座標範囲は４分木で管理され、
世界座標範囲内の各メッシュは４分木の１つのノードに
対応する。逆に、４分木のどのノードも、メッシュ分割
された世界座標範囲のいずれか１つのメッシュに対応す
る。例えば、与えられたデータ格納領域の初期時には、
前記世界座標範囲には図形は一つもなく、世界座標範囲
全体を指すたった1 個のノード（根ノード）からなる４
分木だけを構成する。ノードとメッシュは１体１に対応
し、メッシュの分割・併合に伴ってノードの追加・削除
を行うことによってこの対応が維持される。各ノードは
対応するメッシュが存在する時は、そのメッシュデータ
を指していて、存在しないときはどこも指さない。メッ
シュ分割の時は、与えられた飯データ領域を指し、合併
しメッシュがなくなったときはどこも指さないようにノ
ードは変わる。おな、ノードの追加・削除を動的に行わ
ず、あらかじめ定められた４分木乗でメッシュと対応付
けられているノードの範囲のみを管理することもできる
が、その場合はこの限りでない。具体的には、世界座標
範囲全体を示す四角形のメッシュは「根ノード」に対応
し、根ノードの４つの子ノードは世界座標範囲の四角形
を４分割した４つのメッシュに対応する。例えば、メッ
シュＭがメッシュｍ０〜ｍ３に４分割されているとき、
メッシュＭに対応するノードＮはメッシュｍ０〜ｍ３に
対応するノードｎ０〜ｎ３をすぐ下の子ノードとして持
つ。以下の実施形態では、メッシュの親子関係が分かる
ように、子メッシュの番号を親メッシュの番号の４倍プ
ラス０，１，２，３とし、４分割したメッシュの左下、
左上、右下、右上の順にその番号を付する。すなわち、
ｍ０＝４Ｍ，ｍ１＝４Ｍ＋１，ｍ２＝４Ｍ＋２，ｍ３＝
４Ｍ＋３である。

【００８５】逆に、メッシュに対応するノードを決定す
る方法としては、例えば４分木の根ノードから出発し
て、与えられたメッシュを含むメッシュに対応する子ノ
ードに順次降りて行き、与えられたメッシュに一致する
メッシュに対応するノードに至る方法がある。いずれに
せよ、ノードとメッシュは１対１に対応するから、その
対応を実現する方法には種々の形態があり、いずれの方
法を採用してもメッシュ及びノードが一意に決定され
る。なお、管理するデータの種類によっては、４分木は
１本とは限らず、表示倍率別あるいは図形種類別に用意
することもある。

【００８６】（ｆ）末端ノードと内ノード 葉ノードに対応するメッシュは分割されておらず、この
メッシュを「末端メッシュ」と呼ぶ。これに対し、内ノ
ードに対応するメッシュは必ず分割済みである。また、
図形は末端メッシュに所属するものとし、末端メッシュ
に対応する葉ノードは、そのメッシュに所属する全図形
リストを持つ。さらに、図形が占める領域とメッシュの
領域の重なりがあるとき、「図形はメッシュに所属す
る」という。なお、内ノードは「中間ノード」とも呼ば
れ、これに対応するめしは「中間メッシュ」「被分割メ
ッシュ」呼ばれる。

【００８７】（ｇ）メッシュの状態データ １つノードを指定すると、そのノードに対応するメッシ
ュがどれであるかを検索する手段（後述するメッシュ検
索手段）があるが、この手段としては、例えば、メッシ
ュの座標を計算で割り出したり、メッシュのデータを直
接ノードが持つことにより実現される。

【００８８】例えば、各ノードが直接対応するメッシュ
に関するデータを持つ方法がある。このデータを「メッ
シュの状態データ」と呼ぶ。このデータはデータ領域上
に置かれ、対応するメッシュが存在するノードにはその
データ格納領域を指すポインタを格納すればよい。一
方、対応するメッシュがないノードは何も指さない（ヌ
ルを指すポインタを格納する）。このメッシュの状態デ
ータ図３に示すような構造をしており、は、図形のリス
トを状態データとして持つ。この図形リストから具体的
な図形データ（座標、色、幅、種類など）にアクセスす
ることが容易となる。その他、状態データとして、メッ
シュと重なりのある図形数や、種類毎の所属する図形数
などを持つ場合もある。なお、以下の実施形態では、所
属図形数を状態データとして持っている。

【００８９】ここで、図形がメッシュに登録されている
とは、図形データがメッシュの所属図形リストに入って
いることを言い、図形がメッシュに所属するとは、単に
図形がメッシュには言っているだけでなく、メッシュの
下層の子メッシュにも登録されていることを言う。ま
た、所属図形数とは、メッシュそれ自体に登録されてい
る図形と、そのメッシュより下層の子メッシュに登録さ
れている図形を重複なく数えることを言う。所属図形リ
ストとは、メッシュに登録されている図形（図形要素や
サブ図形）のリストを意味する。

【００９０】また、メッシュデータとして、葉ノードと
内ノードが持つ情報の種類が異なることもある。これ
は、内ノードには所属する図形リストを保持させる必要
がないことによるが、データ領域に余裕があれば、内ノ
ードにも所属する図形リストを保持させることもでき
る。なお、ノードが持つメッシュの状態データは、与え
られたデータ領域上に格納される。

【００９１】（ｈ）メッシュの分割 葉ノードＮに対応する末端メッシュＭは、一定の条件
（例えば、そのメッシュに所属する図形数が一定数を超
えたとき）を満たすと４分割される。そして、４分割に
よって生じる４つのメッシュ（ｍ０〜ｍ３）に対応する
ノードが４つ（ｎ０〜ｎ３）作られ、それらはノードＮ
の子ノードになる。つまり、ノードＮは内ノードにな
り、４つのノード（ｎ０〜ｎ３）が葉ノードになる。メ
ッシュＭに所属している図形のうち、分割後のメッシュ
（ｍ０〜ｍ３）に所属すべき図形は分割後のメッシュに
所属させる。メッシュＭの所属のままでよい図形はその
ままで良い。メッシュＭ，ｍ０，ｍ１，ｍ２，ｍ３の状
態データを各対応ノードで更新する。一方、内ノードＮ
に対応するメッシュＭは必ず分割されている。メッシュ
Ｍが一定の条件（例えば、そのメッシュに所属する図形
数が一定数を下回ったとき）を満たしたとき、メッシュ
Ｍに対応するノードの子ノード、孫ノードを抹消する。
その結果、メッシュＭは未分割のメッシュになり、対応
ノードは葉ノードになる。そして、メッシュＭ以下の末
端メッシュに所属していた図形をメッシュＭに所属させ
る。これにより、ノードＮが持つメッシュＭの状態デー
タは、所属図形リストを持つことになる。

【００９２】［２．各実施形態とコンピュータ］本発明
の各実施形態はコンピュータ上に実現され、実施形態の
各機能は、所定の手順（プログラム）がこのコンピュー
タを制御することで実現される。本明細書における各
「手段」は、実施形態の各機能に対応する概念的なもの
で、必ずしも特定のハードウェアやソフトウェア・ルー
チンに１対１には対応しない。同一のハードウェア要素
が、場合によって異なった手段を構成する。例えば、コ
ンピュータは、ある命令を実行するときにある手段とな
り、別の命令を実行するときは別の手段となりうる。ま
た、一つの手段が、わずか１命令によって実現される場
合もあれば、多数の命令によって実現される場合もあ
る。したがって、本明細書では、以下、実施形態の各機
能を有する仮想的回路ブロック（手段）を想定して実施
形態を説明する。また、本実施形態における各手順の各
ステップは、その性質に反しない限り、実行順序を変更
し、複数同時に実行し、また、実行ごとに異なった順序
で実行してもよい。このような順序の変更は、例えば、
ユーザが実行可能な処理を選択するなどメニュー形式の
インターフェース手法によって実現することができる。

【００９３】［３．第１実施形態］第１実施形態は、前
記第１の目的を達成するための発明に関するものであ
り、請求項１〜請求項８に記載の多次元データ管理方
法、請求項２３〜２５に記載のプログラムを記録した媒
体及び請求項２８〜３５に記載の多次元データ管理装置
に対応するものである。

【００９４】第１実施形態は、末端メッシュのみに図形
を登録すると共に、末端メッシュの分割を所定の条件下
で行うことにより、データ管理の観点から見て非効率的
なメッシュの分割を抑制することで、メモリの使用効率
の向上を可能としたものである。

【００９５】すなわち、末端メッシュの分割を許容する
所定の条件としては、例えば、次のようなものがある。 （ａ）所属図形が一定数以上である。 （ｂ）分割した場合、子メッシュの所属図形数の和が、
分割前の親メッシュの所属図形数のｍ倍未満である。 （ｃ）分割した場合、３つ以上の子メッシュに所属する
図形の数が、所属図形数のｎ％未満である。 なお、ｍの典型的な値は、２倍（４分割だから、４以上
は無意味である）、ｎの典型的な値は例えば３０％に設
定することができる。

【００９６】木構造を利用したデータ管理方法におい
て、前記（ａ）の条件のみを用いるのは公知である。第
１実施形態では、この（ａ）の条件に（ｂ）ないし
（ｃ）の条件を併用することによって、図形の複数メッ
シュへの重複登録を抑制し、分割に伴う所要記憶領域の
増加を抑制している。使用すべき条件としては、（ｂ）
（ｃ）のような形のものだけではなく、（ａ）のみの条
件を用いて分割を行った場合に比較して、個々の図形に
ついてあるいは全図形に関して平均的に１つの図形あた
りの所属（登録）メッシュ数を減少させるような効果を
持つものならば、どのような条件を用いても良い。例え
ば、（ｂ）のｍの値を所属図形の種類別の数の比率に基
づいて決定したり、非常に長い線分のようにもともとあ
る程度の数のメッシュへの重複登録が避けられないタイ
プの図形を除外して（ｂ）あるいは（ｃ）の条件をチェ
ックするなど、種々考えられる。

【００９７】（ａ）の条件に基づいて分割を行うことの
効果は、より小さなメッシュにより少ない図形を登録す
ることにより、第２実施形態において、矩形検索で矩形
に重なると判定されたメッシュから図形を取り出して矩
形への所属をチェックする際に、矩形に所属しないと判
定される図形を減少させることによって、処理の高速化
を図るものである。また、最近傍検索においても、１つ
のメッシュ所属する図形数が少なければ、最近傍図形を
決定するまでに検索調査される図形数が減少することに
よって高速化が図られる。

【００９８】しかしながら、前記（ｂ）（ｃ）の条件を
併用しないで（ａ）の条件によって資源の許す限り無制
限に分割を進めれば、多数重なり合って存在するある程
度の大きさを有する図形を登録した場合には、１つの図
形の所属メッシュは非常に多数になり、近接するメッシ
ュに所属している図形には共通のものが多いという状況
が生じる。このような状況では、分割による個々のメッ
シュの所属図形の現象が十分はかられないばかりか、検
索に際して既にチェックした図形を再度チェックする、
あるいは既にチェックしたものと判定して捨象するとい
う無駄な作業の割合が増加し、所要記憶領域の増加のみ
ならず処理速度の低下をも招く。

【００９９】これに対して、（ｂ）（ｃ）の条件を併用
すれば、１つの図形あたりの所属メッシュ数を著しく増
加させるような分割を抑制することができ、所要記憶領
域の増加を抑制し、かつ検索処理の速度を向上させる
（低下させない）という効果がある。さらには、分割／
併合の頻度が減少することによって、登録／削除の処理
も高速化される。

【０１００】末端メッシュの分割に対応して、併合の場
合の所定の条件としては、次のようなものを用いること
ができる。 （ｄ）親メッシュの所属図形が一定数未満である。 （ｅ）併合した場合、子メッシュの所属図形数の和が、
親メッシュの所属図形数のｍ｀倍以上である。 （ｆ）併合した場合、３つ以上の子メッシュに所属する
図形の数が、所属図形数のｎ％以上である。 （ｄ）は分割の（ａ）に対応する条件で、（ｄ）のみを
用いるのは公知である。（ｅ）を併用する場合、登録に
おいて（ｂ）を併用したとすれば、ｍ｀をｍに対してど
の程度に設定するかで併合の発生を抑制し得る。ｍ｀が
ｍに対して大きければ併合が生じにくく、小さければ併
合が生じやすい。同様に、（ｆ）と（ｃ）を用いる場
合、ｎ｀がｎに対して大きければ併合が生じにくく、小
さければ併合が生じ易い。

【０１０１】なお、併合を判定する前記の条件は、併用
せず単独で用いても良い。すなわち、（ｅ）のみを用い
て併合の可否を判定しても良い。（ｄ）の条件を用いな
いとすれば、登録の結果として併合すべきメッシュが生
じることもあるので、登録処理時において、末端メッシ
ュの所属図形リストに図形を加えた後に、メッシュの分
割処理を試みるだけでなく、メッシュの併合処理も合わ
せて試みることが効果的である。

【０１０２】また、（ｅ）の条件判定を行う場合、第１
実施形態においては各メッシュの所属図形数は得られる
ようになっているので、メッシュ状態データはそのまま
でよい。（ｂ）に関しては、末端メッシュの状態データ
の一部として子メッシュの所属図形数の和を保持するカ
ウンタを設け、登録処理時において末端メッシュを分割
して作成する子メッシュについて図形の所属をチェック
し、所属すればそのカウンタを増すなどの手段を講じ
て、判定が迅速に行えるようにすれば効果的である。

【０１０３】［３−１．第１実施形態の構成］図１は、
第１実施形態の構成を示す機能ブロック図である。

【０１０４】すなわち、本実施形態の多次元データ管理
装置は、中央処理装置１に接続されたキーボードマウス
その他の入力装置２、ディスプレイやプリンタ、外部フ
ァイルなどの出力装置３、本発明のデータ管理プログラ
ム６や管理データを保存する記憶装置５、データ管理プ
ログラム６の実行・記憶領域であるメインメモリ５を備
えている。

【０１０５】メッシュデータ記憶手段７は、多次元空間
を複数のメッシュに階層的に分割し、分割された各階層
のメッシュを木構造の各ノードに対応させ、各メッシュ
と各ノードとの対応関係を記憶する。すなわち、分割さ
れた各メッシュに前記多次元データに関する情報を登録
する。前記多次元データ記憶手段８は、管理対象となる
複数の多次元データを多次元空間内に配置し、各多次元
データの値を多次元空間内における座標として登録す
る。

【０１０６】これら各記憶手段によってファイル装置あ
るいはメインメモリのデータ格納領域に記録される各デ
ータの一例を図２乃至図４に示す。なお、データ格納領
域は、アクセスが早いものが望ましく、コンピュータの
メインメモリ上に確保することが非常に好ましい。ま
た、前記「４分木管理領域」には、４分木のノードに対
応するメッシュ番号が付されており、そのノードが末端
メッシュの場合には、メッシュデータを格納している領
域を指すポインタが記されている。

【０１０７】このデータ格納領域は、一例として図２に
示すように、パラメータ格納領域、図形キー管理、４分
木管理構造、メッシュデータおよび図形データの格納領
域などから構成されている。前記パラメータ格納領域に
格納されるパラメータとしては、世界座標範囲、各メッ
シュに登録する最大の図形数、４分木を分割する際の最
大分割レベル数、メッシュの分割・合併の条件を定める
各種の値（メッシュ分割する図形数、メッシュ合併する
図形数など）、図形に種類がある時その内容、４分木が
複数ある場合その判別、データサイズ、空き領域の先頭
などが格納されている。

【０１０８】メッシュデータは、一例として図３に示す
ように、所属図形数、最大図形数（所属図形数がこの数
より大きくなったら、そのメッシュは４分割される）、
所属図形リストを備えており、この所属図形リストに、
所属する図形のデータの前記データ格納領域上における
格納領域を示すポインタを登録する。なお、本実施形態
においては、末端メッシュでないメッシュは、前記所属
図形リストは持たないものとする。

【０１０９】さらに、サブ図形の組合わせで構成される
図形データの場合には、図４に示したように、サブ図形
単位でメッシュに所属させることにより、サブ図形を分
けて別個の図形データとして格納するよりもデータ領域
を節約できる。また、一つにまとまった図形はまとめた
方が人間の感覚に合致するし、画面への表示は大きくま
とまっている方が速いというメリットもある。

【０１１０】データ管理プログラム６は、木構造管理手
段９、多次元データ登録削除手段１０、メッシュデータ
登録削除手段１１、メッシュ分割手段１２、分割判定手
段１３、メッシュ併合手段１４および併合判定手段１５
を備えている。

【０１１１】木構造管理手段９は、前記多次元空間を複
数のメッシュに階層的に分割し、分割された各階層のメ
ッシュを木構造の各ノードに対応させ、各メッシュと各
ノードとの対応関係を管理する。この木構造管理手段９
においては、世界座標範囲の中のメッシュを４分木のノ
ードと対応させ、そのノードから対応するメッシュに関
するデータが格納されているデータ領域を指す。第１実
施形態では、４分木ノードとメッシュの対応付けは、メ
ッシュの番号と４分木のノードの番号を同一にすること
により実現している。例えば、あるメッシュの４分割後
の４つのメッシュの番号を、分割前のメッシュの番号の
４倍プラス０，１，２，３，とし、左下、左上、右下、
右上の順に番号を付けることとする。これにより、メッ
シュの親子関係が簡単に分かり、また、メッシュの番号
から計算によりメッシュの座標が求まり、分割レベルも
求まる。

【０１１２】また、木構造管理手段９は、４分木から検
索対象メッシュが末端メッシュ（４分木の葉ノード）で
あるか否かを判定し、検索対象メッシュがカバーする範
囲（左下と右上の座標）を指示し、検索対象メッシュの
分割レベルを示す。この場合、全図形データに「図形キ
ー」と呼ばれるユニークな図形ＩＤ番号を付し、その図
形キーに基づいて全図形を管理し、図形キーが与えられ
ると該当図形のデータ格納場所を検索することができ
る。また、図形データを格納するデータ領域を、図形デ
ータの大きさに合わせて確保する。さらに、図形データ
の座標とメッシュの座標を使って、検索対象図形が検索
対象メッシュに入っているか否かを判定する。

【０１１３】多次元データ登録削除手段１０は、前記多
次元データ記憶手段８に多次元データを登録・削除す
る。メッシュデータ登録削除手段１１は、メッシュデー
タ記憶手段７に作用して、前記各メッシュのうち、少な
くとも前記木構造の末端のノードに対応する末端メッシ
ュに、その末端メッシュに対応する前記多次元データに
関する情報を登録または削除する。

【０１１４】これらの各手段により、本発明では、前記
各メッシュデータ記憶手段に登録された情報に基づいて
前記多次元データ記憶手段に蓄積されている多次元デー
タを管理する。

【０１１５】本発明においては、前記のような構成を有
する多次元データ管理装置において、次の構成を備えた
ことを特徴とする。まず、メッシュ分割手段１２は、前
記末端メッシュに登録できる多次元データ数を一定値以
下に設定し、末端メッシュに登録する多次元データ数が
前記設定値を超えた場合にその末端メッシュを分割す
る。分割判定手段１３は、このメッシュ分割手段による
末端メッシュの分割処理に当たり、予め設定された分割
許容条件にしたがって分割の可否を判定する。メッシュ
併合手段１４は、前記末端メッシュの親メッシュに登録
できる多次元データ数を一定値以下に設定し、前記親メ
ッシュに所属する多次元データ数が前記設定値未満の場
合に、その末端メッシュの併合を試行する。併合判定手
段１５は、前記末端メッシュをその兄弟メッシュと共に
親メッシュに併合するステップの試行に当たり、予め設
定された併合許容条件にしたがって併合の可否を判定す
る。

【０１１６】具体的には、前記分割判定手段１３として
は、（ａ）分割後の子メッシュに所属する多次元データ
数の和と、分割前の親メッシュに所属する多次元データ
数とを比較して、分割の可否を判定するもの、（ｂ）親
メッシュに所属する多次元データ数と、前記親メッシュ
から分割された子メッシュの中の複数の子メッシュに所
属する多次元データ数とを比較して、分割の可否を判定
するもの、が使用できる。

【０１１７】前記併合判定手段１５としては、（ａ）併
合前の各子メッシュに所属する多次元データ数の和と、
併合後の親メッシュに所属する多次元データ数とを比較
して、併合の可否を判定するもの、（ｂ）併合後の親メ
ッシュに所属する多次元データ数と、これら子メッシュ
の中の複数の子メッシュに所属する多次元データ数とを
比較して、併合の可否を判定するもの、（ｃ）前記末端
メッシュに登録できる多次元データ数を一定値以下に設
定し、親メッシュを同じくする各末端メッシュに登録さ
れた多次元データ数がいずれも前記設定値未満の場合
に、その末端メッシュの併合を実行するもの、が使用で
きる。

【０１１８】［３−２．第１実施形態の作用］以下前記
のような構成を有する第１実施形態の多次元データ管理
装置の作用並びに、これに対応する多次元データ管理方
法について、図５乃至図７の木構造とメッシュとの関
係、図８のスタックの機能、図９乃至図１５のフローチ
ャートに従って説明する。

【０１１９】［３−２−１．データ領域への図形の登録
処理］データ領域に新たな図形を登録する処理は、図９
に示したフローチャートにしたがって実行される。以
下、各ステップごとに説明する。

【０１２０】（ステップ９０１）登録する図形データに
合ったデータ領域を確保する。

【０１２１】（ステップ９０２）データ領域が確保でき
たか否かが判断され、データ領域が確保できた場合に
は、次のステップに進み、データ領域が確保できない場
合には、データ領域への図形の登録はできず、この処理
は終了する。

【０１２２】（ステップ９０３）ステップ９０２でデー
タ領域が確保できた場合には、図形データを確保したデ
ータ領域にコピーする。

【０１２３】（ステップ９０４）図形キー管理エリアに
その図形を加える。

【０１２４】（ステップ９０５）図形キー管理エリアに
図形を加えることができたか否かが判断され、加えるこ
とができた場合には、次のステップ９０６に進み、一
方、加えることができない場合には、ステップ９０９に
進む。

【０１２５】（ステップ９０６）図形キー管理エリアに
図形を加えることができた場合には、その図形をメッシ
ュに登録する。

【０１２６】（ステップ９０７）図形をメッシュに登録
できたが否かが判断され、登録できた場合には、データ
領域への図形の登録は完了する。一方、登録できなかっ
た場合には、次のステップに進む。

【０１２７】（ステップ９０８）登録処理の過程で変化
したメッシュを元に戻して、図形データを削除し、この
処理を終了する。

【０１２８】（ステップ９０９）ステップ９０５で図形
キー管理エリアに図形を加えることができなかった場合
には、ステップ９０３においてデータ領域にコピーした
図形データを消し、データ領域への図形の登録処理を終
了する。

【０１２９】ここで、「登録処理の過程で変化したメッ
シュ」とは、例えば、そのメッシュに所属する図形の数
が増えた結果、４分割されたメッシュ等をいう。したが
って、本処理によって、結果的に図形の登録ができなか
った場合には、すべてのデータは元の状態に戻される。

【０１３０】なお、図９に示したフローチャートの内、
ステップ９０６の「図形をメッシュに登録する処理」、
及びステップ９０８の「図形をデータ領域から削除する
処理」については、後述する。

【０１３１】［３−１−２．メッシュデータへの図形の
登録処理］全世界を再帰的に分割したメッシュに新たな
図形を登録する処理は、図１０に示したフローチャート
にしたがって実行される。本実施例では図形を末端メッ
シュにのみ登録する。以下、各ステップごとに説明す
る。

【０１３２】（ステップ１００１）メッシュスタックを
空にする。

【０１３３】（ステップ１００２）メッシュスタックに
世界全体（全世界１）をメッシュとして入れる。

【０１３４】（ステップ１００３）メッシュスタックが
空か否かを判断し、空の場合には本処理を終了する。一
方、空でない場合には次のステップに進む。なお、ここ
では、前ステップにおいて、全世界１が入っているので
次のステップに進む。

【０１３５】（ステップ１００４）メッシュスタックか
らメッシュを一つ取り出し、現メッシュとする。すなわ
ち、ここでは全世界１が取り出される。

【０１３６】（ステップ１００５）現メッシュと図形が
重なっているか否かを判断し、重なっていない場合には
ステップ１００３に戻る。一方、重なっている場合には
次のステップに進む。ここでは、全世界１は登録すべき
図形ａと重なっているので、次のステップに進む。

【０１３７】（ステップ１００６）現メッシュの所属図
形数を増やす。ここでは、全世界１のメッシュデータの
所属図形数を、図形ａの分として１つ増やす。

【０１３８】（ステップ１００７）現メッシュが末端の
メッシュであるか否かが判断され、末端メッシュである
場合には、ステップ１００９に進む。一方、末端メッシ
ュでない場合には、ステップ１００８に進む。ここで、
全世界１がすでに４〜７のメッシュに分割されており、
４〜７が末端メッシュであるとすると、現メッシュであ
る全世界１は末端メッシュではないので、ステップ１０
０８へ進む。

【０１３９】（ステップ１００８）現メッシュを４分割
した４つのメッシュをメッシュスタックに入れ、ステッ
プ１００４へ戻る。すなわち、ここでは、全世界１を４
分割した４〜７のメッシュをメッシュスタックに入れ、
ステップ１００４へ戻る。そして、ステップ１００４に
おいて、メッシュスタックからメッシュを順に一つずつ
取り出して現メッシュとし、上記ステップ１００５〜ス
テップ１００７の処理を各メッシュについて行う。この
例では、メッシュスタックからメッシュ７を取り出し、
現メッシュとしてステップ１００５へ進む。このメッシ
ュ７は、図５に示したように、登録する図形ａと重なっ
ているので、ステップ１００６及びステップ１００７に
進み、ステップ１００７でメッシュ７は末端メッシュで
あると判断され、ステップ１００９に進む。

【０１４０】（ステップ１００９）現メッシュの所属図
形リストに登録する図形を加える。

【０１４１】（ステップ１０１０）現メッシュについ
て、後述する「メッシュの分割処理」がなされ、ステッ
プ１００３へ戻る。この例では、他のメッシュ６、５、
４は、いずれも図形ａと重ならないので、ステップ１０
０３〜ステップ１００５を順次繰り返し、すべての末端
メッシュのチェックが終了すると、ステップ１００３で
メッシュスタックが空になるので、本処理を終了する。
結局、末端メッシュ７に図形ａが登録される。

【０１４２】なお、後述する「メッシュの分割処理」に
おいて、現メッシュが４分割されると、現メッシュは親
メッシュになるので、前記ステップ１００９でメッシュ
７の所属図形リストに加えた図形ａは、メッシュ７の所
属図形リストから削除される。

【０１４３】［３−１−３．データ領域からの図形の削
除処理］データ領域から所定の図形を削除する処理は、
図１１に示したフローチャートにしたがって実行され
る。以下、各ステップごとに説明する。

【０１４４】（ステップ１１０１）後述する「図形をメ
ッシュから削除する処理」がなされる。

【０１４５】（ステップ１１０２）図形キー管理エリア
から該当図形を除く。

【０１４６】（ステップ１１０３）図形データ格納場所
にあるデータを消去して、本処理を終了する。

【０１４７】［３−１−４．メッシュからの図形の削除
処理］メッシュから所定の図形を削除する処理は、図１
２に示したフローチャートにしたがって実行される。以
下、各ステップごとに説明する。

【０１４８】（ステップ１２０１）メッシュスタックを
空にする。

【０１４９】（ステップ１２０１）メッシュスタックに
世界全体（全世界１）をメッシュとして入れる。

【０１５０】（ステップ１２０３）メッシュスタックが
空か否かを判断し、空の場合には本処理を終了する。一
方、空でない場合には次のステップに進む。なお、ここ
では、前ステップにおいて、全世界１が入っているので
次のステップに進む。

【０１５１】（ステップ１２０４）メッシュスタックか
らメッシュを一つ取り出し、現メッシュとする。すなわ
ち、ここでは全世界１が取り出される。

【０１５２】（ステップ１２０５）現メッシュと図形が
重なっているか否かを判断し、重なっていない場合には
ステップ１２０３に戻る。一方、重なっている場合には
次のステップに進む。ここでは、全世界１は登録すべき
図形ａと重なっているので、次のステップに進む。

【０１５３】（ステップ１２０６）現メッシュの所属図
形数を減らす。ここでは、全世界１のメッシュデータの
所属図形数を、図形ａの分として１つ減らす。

【０１５４】（ステップ１２０７）現メッシュが末端の
メッシュであるか否かが判断され、末端メッシュである
場合には、ステップ１２０９に進む。一方、末端メッシ
ュでない場合には、ステップ１２０８に進む。ここで、
全世界１がすでに４〜７のメッシュに分割されており、
４〜７が末端メッシュであるとすると、現メッシュであ
る全世界１は末端メッシュではないので、ステップ１２
０８へ進む。

【０１５５】（ステップ１２０８）現メッシュを４分割
した４つのメッシュをメッシュスタックに入れ、ステッ
プ１２０４へ戻る。すなわち、ここでは、全世界１を４
分割した４〜７のメッシュをメッシュスタックに入れ、
ステップ１２０４へ戻る。そして、ステップ１２０４に
おいて、メッシュスタックからメッシュを順に一つずつ
取り出して現メッシュとし、上記ステップ１２０５〜ス
テップ１２０７の処理を各メッシュについて行う。この
例では、メッシュスタックからメッシュ７を取り出し、
現メッシュとしてステップ１２０５へ進む。このメッシ
ュ７は、図５に示したように、削除する図形ａと重なっ
ているので、ステップ１２０６及びステップ１２０７に
進み、ステップ１２０７でメッシュ７は末端メッシュで
あると判断され、ステップ１２０９に進む。

【０１５６】（ステップ１２０９）現メッシュの所属図
形リストから図形を削除する。

【０１５７】（ステップ１２１０）現メッシュについ
て、後述する「メッシュの併合処理」がなされ、ステッ
プ１２０３へ戻る。この例では、他のメッシュ６、５、
４は、いずれも図形ａと重ならないので、ステップ１２
０３〜ステップ１２０５を順次繰り返し、すべての末端
メッシュのチェックが終了すると、ステップ１２０３で
メッシュスタックが空になるので、本処理を終了する。
結局、末端メッシュ７から図形ａが削除される。

【０１５８】なお、後述する「メッシュの併合処理」に
おいて、現メッシュが併合されると、親メッシュ（全世
界１）が現メッシュになるので、前記ステップ１２０９
でメッシュ７の所属図形リストから削除された図形ａ
は、親メッシュ１からも削除され、親メッシュの所属図
形数が一つ減少する。

【０１５９】［３−１−５．データ領域における図形デ
ータの修正処理］データ領域に記憶された図形データを
修正する処理は、図１３に示したフローチャートにした
がって実行される。なお、修正の前後で、図形を同定す
る図形キーは不変である。以下、各ステップごとに説明
する。

【０１６０】（ステップ１３０１）旧図形データを図形
キーから検索する。

【０１６１】（ステップ１３０２）修正後の新図形デー
タのためのデータ領域を確保する。

【０１６２】（ステップ１３０３）データ領域が確保で
きたか否かが判断され、データ領域が確保できた場合に
は、次のステップに進む。一方、データ領域が確保でき
ない場合には、データ領域への新図形の登録はできず、
この処理は終了する。

【０１６３】（ステップ１３０４）新図形データを確保
したデータ領域にコピーする。

【０１６４】（ステップ１３０５）図形キー管理エリア
に登録されている旧図形データへのポインタと新図形デ
ータへのポインタを置き換える。

【０１６５】（ステップ１３０６）新図形をメッシュに
登録する。

【０１６６】（ステップ１３０７）新図形をメッシュに
登録できたか否かが判断され、登録できた場合にはステ
ップ１３０８へ進み、登録できなかった場合には、ステ
ップ１３１０へ進む。

【０１６７】（ステップ１３０８）旧図形をメッシュか
ら削除する。

【０１６８】（ステップ１３０９）図形データ格納場所
にある旧図形データを消去して、本処理を終了する。

【０１６９】（ステップ１３１０）前記ステップ１３０
７において、新図形をメッシュに登録できなかった場合
には、登録処理の過程で変化したメッシュを元に戻し
て、新図形データを削除する。

【０１７０】（ステップ１３１１）図形キー管理エリア
において置き換えた新図形データへのポインタを旧図形
データへのポインタに戻し、本処理を終了する。すなわ
ち、本処理によって、結果的に修正後の新図形の登録が
できなかった場合には、すべてのデータは元の状態に戻
される。

【０１７１】［３−１−６．メッシュの分割処理］末端
のメッシュに登録された図形数が一定数を越えた場合に
行われるメッシュの分割処理は、図１４に示したフロー
チャートにしたがって実行される。以下、各ステップご
とに説明する。

【０１７２】（ステップ１４０１）分割メッシュスタッ
クを空にする。

【０１７３】（ステップ１４０２）分割メッシュスタッ
クに現メッシュを入れる。

【０１７４】（ステップ１４０３）分割メッシュスタッ
クからメッシュを一つ取り出し、親メッシュとする。

【０１７５】（ステップ１４０４）別途説明した所定の
分割条件に照らして、親メッシュを分割して良いか否か
が判断され、分割して良い場合には次のステップ１４０
５に進む。一方、分割すべきでない場合には、ステップ
１４１７に進み、分割メッシュスタックが空か否かが判
断され、空の場合には本処理は終了し、空でない場合に
はステップ１４０３へ戻る。

【０１７６】（ステップ１４０５）前記ステップ１４０
４において、親メッシュを分割して良いと判断された場
合には、そのメッシュを４分割する。

【０１７７】（ステップ１４０６）４分割された各子メ
ッシュについてメッシュデータ領域を確保する。

【０１７８】（ステップ１４０７）すべての子メッシュ
について、メッシュデータ領域が確保されたか否かが判
断され、確保された場合には次のステップに進み、一
方、４つのメッシュの内、いずれか一つでもメッシュデ
ータ領域が確保されない場合には、ステップ１４０９に
進む。

【０１７９】（ステップ１４０８）４分割されたすべて
のメッシュについてメッシュデータ領域が確保された場
合には、親メッシュに登録されている図形の内から一つ
の図形を選択する。

【０１８０】（ステップ１４０９）ステップ１４０７に
おいて、４つのメッシュの内、いずれか一つでもメッシ
ュデータ領域が確保されない場合には、メッシュの４分
割処理はできないので、確保されたメッシュデータ領域
を元に戻し、本処理を終了する。

【０１８１】（ステップ１４１０）４分割されたメッシ
ュから一つの子メッシュを選択する。

【０１８２】（ステップ１４１１）ステップ１４０８に
おいて選択された図形が、その子メッシュに重なるか否
かが判断され、重なる場合にはステップ１４１２に進
み、重ならない場合にはステップ１４１３に進む。

【０１８３】（ステップ１４１２）ステップ１４１１に
おいて図形がその子メッシュに重なると判断された場合
には、その図形をその子メッシュに登録する。具体的に
は、子メッシュの所属図形数を増やし、所属図形リスト
に図形を加える。

【０１８４】（ステップ１４１３）ステップ１４１１に
おいて図形がその子メッシュに重ならないと判断された
場合には、上記ステップ１４０７及びステップ１４１２
の処理がすべての子メッシュについてなされたか否かが
判断され、まだなされていない場合にはステップ１４１
０に戻り、一方、すべての子メッシュについて終了して
いる場合には、次のステップに進む。

【０１８５】（ステップ１４１４）親メッシュに登録さ
れていたすべての図形について、ステップ１４１０〜ス
テップ１４１３の処理がなされたか否かが判断され、ま
だなされていない場合にはステップ１４０８に戻り、一
方、すべての図形について終了している場合には、次の
ステップに進む。

【０１８６】（ステップ１４１５）上記のようにして、
親メッシュに登録されていたすべての図形について処理
が終了した後、親メッシュの所属図形リストのデータ領
域を消去する。

【０１８７】（ステップ１４１６）４つの子メッシュを
分割メッシュスタックに入れ、ステップ１４０３に戻
る。

【０１８８】［３−１−７．メッシュの併合処理］末端
のメッシュに登録された図形数が一定数以下になった場
合に行われるメッシュの併合処理は、図１５に示したフ
ローチャートにしたがって実行される。以下、各ステッ
プごとに説明する。

【０１８９】（ステップ１５０１）現メッシュの親のメ
ッシュを「親メッシュ」、現メッシュを含む親メッシュ
の４つの子メッシュを「子メッシュ」（４個）とする。

【０１９０】（ステップ１５０２）別途説明した所定の
併合条件に照らして、４つの子メッシュを親メッシュに
併合して良いか否かが判断され、併合して良い場合には
次のステップ１５０３に進む。一方、併合すべきでない
場合には本処理は終了する。

【０１９１】（ステップ１５０３）前記ステップ１５０
２で親メッシュに併合して良いと判断された場合には、
親メッシュにメッシュデータ領域を割り当てる。

【０１９２】（ステップ１５０４）子メッシュの一つを
選択する。

【０１９３】（ステップ１５０５）子メッシュの所属図
形リストから図形を一つ選ぶ。

【０１９４】（ステップ１５０６）親メッシュの所属図
形リストに、その図形がすでに含まれているか否かが判
断され、含まれていない場合には次のステップに進み、
一方、すでに含まれている場合には、ステップ１５０８
に進む。

【０１９５】（ステップ１５０７）親メッシュの所属図
形リストに図形を加える。

【０１９６】（ステップ１５０８）子メッシュに所属す
るすべての図形を処理したか否かが判断され、未処理の
図形がある場合にはステップ１５０５へ戻り、すべての
図形について処理が終了している場合には、次のステッ
プに進む。

【０１９７】（ステップ１５０９）４つの子メッシュの
すべてを処理したか否かが判断され、未処理の子メッシ
ュがある場合にはステップ１５０４へ戻り、すべての子
メッシュについて処理が終了している場合には、次のス
テップに進む。

【０１９８】（ステップ１５１０）親メッシュを現メッ
シュとし、ステップ１５０１へ戻る。

【０１９９】［３−３．第１実施形態の効果］前記の様
な構成を有する第１実施形態は、次のような効果を有す
る。すなわち、固定メッシュからデータ密度によってメ
ッシュを分割し、その大きさを変えるので、無駄なデー
タ領域が減り、主記憶装置上でデータを扱うことができ
る。また、４分木で分割を管理するので、メッシュへの
アクセスがスムーズに実行でき、階層を下る検索によ
り、無駄な条件判断を減らすことができる。さらに、デ
ータの股がりによって、末端メッシュだけでなく内メッ
シュにもデータを入れることができるので、メッシュ１
つ当りのデータ数が減り、無駄なデータ領域を減らすこ
とができる。

【０２００】また、メッシュの分割を無制限に進めると
指数オーダーでデータ領域を消費するので、分割レベル
の限界を設けることにより、有限なデータ領域を節約す
ることができる。また、１メッシュ当りのデータ数が少
ないときは、メッシュの分割を解消してメッシュを合併
するので、データ密度に応じた分割レベルを保つことが
できる。さらに、メッシュの分割を解消した結果、使わ
なくなったデータ領域を再利用することができる。ま
た、サブ図形の組合わせで構成される図形データの場合
に、サブ図形単位でメッシュに所属させることとしたた
め、データ領域をさらに節約することができる。

【０２０１】このように本実施形態の多次元データ管理
装置によれば、データ領域を大幅に節約することができ
るので、計算機の主記憶上でデータを扱うことができ、
高速なデータアクセスが可能となる。

【０２０２】［３−４．第１実施形態の変形例］第１実
施形態では図１に示すように、メッシュ分割手段１２と
分割反対手段１３、およびメッシュ併合手段１４と併合
判定手段１５の両方を設けたが、いずれか一方の組み合
わせのみを設けても良い。

【０２０３】［４．第２実施形態］第２実施形態は、前
記第１実施形態と同様に４分木ノード、メッシュ状態デ
ータ、図形検索キーデータ、図形データを記憶領域上に
配置し、利用する。第１実施形態と異なるのは、末端メ
ッシュでない被分割メッシュの状態データにも所属図形
リストを含める点である。すなわち、４分木構造におい
て被分割メッシュに対応する中間ノードについても図形
データを登録することにより、末端メッシュに登録され
た図形だけでなく、被分割メッシュに登録された図形を
も検索対象とするものである。また、被分割メッシュに
も図形を登録する手法としては、末端メッシュを分割す
る際に子メッシュに登録するのが適切でない図形を親メ
ッシュに残すようにしたものである。

【０２０４】このような第２実施形態においては、前記
第１実施形態における図形のメッシュへの登録、メッシ
ュの４分割、図形のメッシュからの削除、およびメッシ
ュの併合の手法が次のように変更される。

【０２０５】第２実施形態では、被分割メッシュの状態
データにも所属図形リストを含めるが、そのリストに実
際に図形が登録されている状態は、次のようなメッシュ
分割フローの処理によって作り出される。前記第１実施
形態とは異なるこの分割処理の特徴は、図形の所属を親
メッシュから子メッシュに移す際に、親メッシュに所属
するすべての図形を無条件に移すのではなく、所定の条
件に照らして子メッシュに移すのが適切と判断された図
形のみを移し、適切でないと判断された図形については
親メッシュに所属させたままにしておく点である（図１
６、図５及び図６を参照）。

【０２０６】ここで、「所定の条件（図形の登録先変更
条件）に照らして図形を子メッシュに移して良いか？」
という判定に係る所定の条件とは、無条件に子メッシュ
に移した場合に比較して１つの図形あたりの複数メッシ
ュへの重複登録を抑制するような条件であり、例えば次
のようなものである。なお、これらの条件は単独で用い
ても良いし、複数を併用しても良い。

【０２０７】（ａ）図形がその親メッシュを完全に含ん
でいない。

【０２０８】（ｂ）図形が重なっている子メッシュが２
つ以下である。

【０２０９】（ｃ）図形ごとに重複登録メッシュ数の上
限が定められており、子メッシュへの登録（移動）を行
っても重複登録数が上限以下である。

【０２１０】（ｄ）図形の種類・大きさなどの属性によ
って登録して良い最小のメッシュの大きさが定められて
おり、子メッシュの大きさがその最小メッシュの大きさ
以上である。

【０２１１】これらの条件によって、メッシュ分割にお
ける図形の登録メッシュの増加が抑制されると共に、子
メッシュに登録を変更する図形の数が減少するため、分
割処理自体も高速化される。例えば、図形の面積（大き
さ）・形状に応じて予め登録すべき最小のメッシュを決
めておき、条件（ｄ）を採用して判定を行いつつ図形の
登録を進めれば、メッシュの分割が進んでも１つの図形
はその図形の面積（大きさ）に比例する数以下の、その
図形に予め定められた最小のメッシュ以上に大きさのメ
ッシュにのみ登録される。これによって、過剰な重複登
録を抑制して記憶領域を節約すると共に、検索処理の速
度の低下を防止することができる。

【０２１２】例えば、矩形の形状の図形に関しては、メ
ッシュの短辺がその図形の短辺より長い最も小さなメッ
シュを、その図形を登録して良い最小のメッシュとして
設定するという方法がある。この方法に従えば、細長い
矩形は長手方向に小さな多数のメッシュに所属するの
で、検索時にそのメッシュが選択された場合に最終的な
検索結果として選ばれる割合が高まって検索効率が向上
する。いたずらに上位の大きなメッシュに属させておけ
ば、メッシュが選ばれる割合が大きい反面その図形が最
終的な検索結果として選ばれる割合が減少し、検索効率
の悪化を招く。この方法では、予測可能な範囲である程
度多数のメッシュに重複登録されるが、無制限に著しく
記憶領域を浪費することはなく、検索効率が劣化するこ
とはない。縦横の長さが極端に違わない矩形に関して
は、最も重複が多くなっても数個のメッシュに所属する
だけで済む。この方法を採用した場合の長所は、検索に
おいて所属メッシュが選択された場合に、最終的な検索
結果としてその図形が採用される割合を細長い矩形とそ
うでない矩形で極端に違わないようにする効果が得られ
ることである。

【０２１３】細長い図形の場合と類似の効果は、線分を
扱う場合にも得られる。例えば、メッシュの短辺が線分
の長さのｎ分の１以上である最小のメッシュをその線分
を登録して良い最小のメッシュとする方法が考えられ
る。その線分は、多くとも４ｎ個よりは少ない数のメッ
シュに重複登録されるに過ぎない。

【０２１４】（ｃ）を採用した場合、１つの図形につい
て重複登録メッシュ数が制限されるので、記憶領域の節
約には非常に有効である。しかも、所属メッシュの大き
さにはばらつきがあっても良いから、重複登録数の上限
以下であれば、図形の密度に応じて分割されていくの
で、さらに細かなメッシュへの登録を進めることがで
き、検索効率の向上を図ることができる。

【０２１５】［４−１．第２実施形態の構成］図１７
は、本発明の第２実施形態の構成を示す機能ブロック図
である。すなわち、本実施形態の多次元データ検索装置
は、第１実施形態に示した多次元データ管理装置の構成
要素に加えて、前記メッシュデータ登録削除手段１１お
よびメッシュ分割手段１２に関連して、メッシュデータ
再登録手段１６と再登録メッシュ判定手段１７が設けら
れていることを特徴とする。このメッシュデータ再登録
手段１６は、末端メッシュの分割時において、前記各メ
ッシュのうち、前記木構造の末端のノードに対応する分
割によって生じた子メッシュと、前記末端ノードの親ノ
ードに対応する分割によって生じた親メッシュいずれか
に多次元データを登録しなおすものである。また、再登
録メッシュ判定手段１７は、末端メッシュの分割時にお
いて、１つの図形あたりの複数メッシュへの重複登録を
抑制する条件に従って、前記多次元データを分割によっ
て生じた子メッシュと分割によって生じた親メッシュの
いずれに登録しなおすかを判定する。

【０２１６】前記再登録メッシュ判定手段１７として
は、（ａ）前記多次元データがその親メッシュを完全に
含んでいないことを重複登録を抑制する条件とするも
の、（ｂ）前記多次元データが重なっている子メッシュ
数が予め設定された数以下であることを重複登録を抑制
する条件とするもの、（ｃ）前記多次元データごとに重
複メッシュ数の上限が定められており、子メッシュへの
登録を行っても重複登録数が上限以下であることを重複
登録を抑制する条件とするものが使用される。

【０２１７】［４−２．第２実施形態の作用］以下前記
のような構成を有する第２実施形態の多次元データ管理
装置の作用並びに、これに対応する多次元データ管理方
法について、図１６〜１７の木構造とメッシュとの関係
を示す図、および図１８のフローチャートにしたがっ
て、中間ノードに図形データを登録する第１の方法につ
いて説明する。なお、この中間ノードに図形データを登
録する第１の方法は、第１実施形態において説明した
「末端メッシュの分割処理」において、子メッシュに登
録するのが適切でない図形を、中間ノードに相当する親
メッシュに残すようにするものである。また、図１８に
示したフローチャートは、図１４に示した［メッシュの
分割処理］フローに一部の処理（ステップ１８１８）を
追加したものなので、この変更部分について説明する。

【０２１８】（ステップ１８１８）図１８に示したよう
に、ステップ１８０８において、親メッシュに登録され
ている図形の内から選択された一つの図形について、別
途説明した図形の登録先変更条件に照らして、図形を子
メッシュに移して良いか否かが判断され、子メッシュに
移して良い場合には、ステップ１８１０に進む。その結
果、ステップ１８１０〜ステップ１８１２の処理によっ
て、図形が子メッシュに登録される。一方、ステップ１
８１８において、図形を子メッシュに移すことは適切で
ないと判断された場合には、ステップ１８１４に進む。
その結果、その図形は子メッシュには登録されず、親メ
ッシュに登録されたままの状態に保持される。そして、
ステップ１８１４において、親メッシュに所属するすべ
ての図形について、ステップ１８１８、ステップ１８１
０〜ステップ１８１３の処理がなされたか否かが判断さ
れる。

【０２１９】［４−３．第２実施形態の変形例］第２実
施形態では、図１７に示すように、メッシュ分割手段１
２と分割反対手段１３、およびメッシュ併合手段１４と
併合判定手段１５を設けたが、これらの一方の組のみを
設けても良いし、両者を省くこともできる。

【０２２０】［５．第３実施形態］第３実施形態は、前
記第２実施形態と同様に被分割メッシュにも図形を登録
するものであるが、末端メッシュの分割時ではなく、図
形の登録時に適切なメッシュを選んで登録するものであ
る。すなわち、第３実施形態では、被分割メッシュの状
態データにも所属図形リストを含めるが、第２実施形態
とは異なって、その状態は図形の登録処理の過程によっ
て直接に作成され、分割という付随処理の結果生じるも
のではない。

【０２２１】なお、この第３実施形態においては、メッ
シュ分割処理は再帰的でなくても良く、親メッシュから
の登録図形の移動を伴わない形で、単に４つの子メッシ
ュを作成し、子メッシュの所属図形リストは空のままに
しておくという形でも実施できる。もちろん、第２実施
形態のように所定の条件を吟味した上で分割し、さらに
所定の条件を満たす図形を子メッシュに移しても良い。

【０２２２】ところで、この第３実施形態において、
「所定の条件（図形の登録先変更条件）に照らして現メ
ッシュに図形を登録して良いか？」という判定に係る
「所定の条件」とは、例えば次のようなものである（図
１９及び図２０参照）。 （ａ）図形が重なり合っている現メッシュの子メッシュ
が３個以上である。 （ｂ）図形の種類、大きさなどの属性によって登録して
良い最小のメッシュの大きさが決まっており、現メッシ
ュの子メッシュの大きさがその最小のメッシュ未満であ
る。 （ｃ）図形の種類、大きさなどの属性によって登録して
良い最大のメッシュの大きさが決まっており、現メッシ
ュの親メッシュの大きさがその最大のメッシュを越えて
いる。 （ｄ）図形ごとに重複登録メッシュ数の上限が定められ
ており、子メッシュへの登録を行うと重複登録数の上限
を越えてしまう。 （ｅ）図形の面積が現メッシュのα％を占める。面積の
ない線分などの場合には、現メッシュの中心からの距離
がメッシュの短辺の１／２の長さのβ％以内である。

【０２２３】これらの条件は単独で用いても良いし、複
数を併用してそのすべてが成立したら条件を満足したも
のと判定しても良い。また、複数を併用していずれか１
つが成立したら条件を満足したものとしても良い。

【０２２４】例えば、（ａ）と（ｅ）を併用して両方が
成立したら条件を満足するとして使用した際に、αが例
えば１０％というような値に設定されているとすれば、
図１９に示したように、すべての子メッシュ２−４に重
なっているが、現メッシュ１に比較して大きさが非常に
小さい図形Ｆ１は（ｅ）の条件を満たさないために現メ
ッシュよりもさらに小さなメッシュに所属するように促
される。一方、図２０に示したように、メッシュに比較
してある程度大きい面積の図形Ｆ２、すなわち図形の面
積は現メッシュの１０％以上あるが、現メッシュの周辺
に存在する図形Ｆ２は（ａ）の条件を満たさないために
さらに小さなメッシュに所属するように促される。

【０２２５】このようにして、メッシュの中心を含みか
つメッシュ中のある程度の面積を占めるような状況での
み図形がメッシュに登録されるので、後述する最近傍図
形検索手続きにおいて、図形を探索する範囲が狭められ
て検索が効率化されるという効果が得られる。

【０２２６】また、（ｂ）の条件を図形ごとに適切に設
定することにより、図形がその大きさに比較してあまり
に大きなメッシュに所属して検索効率を低下させること
を防ぐことができる。さらには、（ｃ）の条件を図形ご
とに適切に設定することにより、図形がその大きさに比
較してあまりに小さな多数のメッシュに重複登録される
ことを避け、検索の効率化および記憶領域の節約を図る
ことができる。

【０２２７】なお、（ｂ）および（ｅ）の条件は、図形
の属性によって一方的に決まる場合ばかりでなく、現メ
ッシュの所属図形数などのメッシュ側の状況を吟味して
判定するなど、より柔軟かつ多様な変形例が種々考えら
れる。

【０２２８】上述のように、第３実施形態は、前記登録
に係る所定の条件として図形の属性に応じた条件を設定
することによって、図形のメッシュへの重複登録を制限
あるいは抑制する効果を得ると共に、検索手続きの効率
化を図ることを可能にするものである。

【０２２９】１つの木構造に対応させたデータ管理方法
及び装置において、木構造を構成する各ノード部分に種
々の図形を登録する際に、同一の手続きによって図形ご
とやその種類ごとに異なる条件を採用することを特徴と
するものであり、これによって、従来技術のｑｕａｄ−
ｔｒｅｅ法やその変形例のように、中間ノードに図形を
登録させる場合にどの図形であっても画一的な分割手法
を使用していたものに比較して、より優れた記憶領域の
有効利用と検索処理の高速化が可能になる。

【０２３０】［５−１．第３実施形態の構成］図２１
は、本発明の第３実施形態の構成を示す機能ブロック図
である。すなわち、本実施形態の多次元データ検索装置
は、第１実施形態に示した多次元データ管理装置の構成
要素に加えて、前記メッシュデータ登録削除手段１１お
よびメッシュ分割手段１２に関連して、末端あるいは中
間メッシュへのデータ登録手段１８と登録位置判定手段
１９を備えていることを特徴とする。データ登録手段１
８は、前記各メッシュのうち、前記木構造の末端のノー
ドに対応する末端メッシュと、前記末端ノードの親ノー
ドに対応する中間メッシュの少なくとも一方に多次元デ
ータを登録する。登録位置判定手段１９は、多次元デー
タの登録時において、登録する多次元データの状態に従
って、前記多次元データを末端メッシュと中間メッシュ
のどこに登録するかを判定する。

【０２３１】前記登録位置判定手段１９としては、
（ａ）前記多次元データが重なり合っている子メッシュ
数に応じて登録するメッシュを選択するもの、（ｂ）前
記多次元データによって登録すべきメッシュの大きさの
限度が決まっており、このメッシュの大きさの限度に従
って前記多次元データを登録するメッシュを選択するも
の、（ｃ）前記多次元データごとに重複登録メッシュ数
の限度が定められており、この限度に従って前記多次元
データを登録するメッシュを選択するもの、（ｄ）前記
多次元空間内における前記多次元データの大きさと、前
記多次元空間内における所定のメッシュの大きさとの比
較から、前記多次元データを登録するメッシュを選択す
るもの、が使用できる。

【０２３２】［５−２．第３実施形態の作用］以下前記
のような構成を有する第３実施形態の多次元データ管理
装置の作用並びに、これに対応する多次元データ管理方
法について、図１９，２０によって、その条件を説明す
ると共に、図２２に示したフローチャートにしたがっ
て、中間ノードに図形データを登録する第２の方法につ
いて説明する。なお、この中間ノードに図形データを登
録する第２の方法は、第２実施形態と異なり、図形の登
録時に適切なメッシュを選んで登録するものである。以
下、各ステップごとに説明する。

【０２３３】（ステップ２２０１）メッシュスタックを
空にする。

【０２３４】（ステップ２２０２）メッシュスタックに
世界全体（全世界１）をメッシュとして入れる。

【０２３５】（ステップ２２０３）メッシュスタックか
らメッシュを一つ取り出し、現メッシュとする。

【０２３６】（ステップ２２０４）現メッシュと図形が
重なっているか否かを判断し、重なっていない場合には
ステップ２２０３に戻る。一方、重なっている場合には
次のステップに進む。

【０２３７】（ステップ２２０５）現メッシュの所属図
形数を増やす。

【０２３８】（ステップ２２０６）後述する図形の登録
先変更条件に照らして、現メッシュに図形を登録して良
いか否かが判断され、登録して良い場合には、次のステ
ップ２２０７に進む。一方、現メッシュに図形を登録す
ることが適切でないと判断された場合には、ステップ２
２０９に進む。

【０２３９】（ステップ２２０７）現メッシュの所属図
形リストに図形を加える。

【０２４０】（ステップ２２０８）メッシュスタックが
空か否かを判断し、空の場合には本処理を終了する。一
方、空でない場合にはステップ２２０３に戻る。

【０２４１】（ステップ２２０９）ステップ２２０６に
おいて、現メッシュに図形を登録することが適切でない
と判断された場合には、現メッシュが末端のメッシュで
あるか否かが判断され、末端メッシュである場合には、
ステップ２２１０に進む。一方、末端メッシュでない場
合には、ステップ２２１２に進む。

【０２４２】（ステップ２２１０）ステップ２２０９に
おいて現メッシュが末端のメッシュである場合には、メ
ッシュ分割処理によって、現メッシュの４分割を試み
る。

【０２４３】（ステップ２２１１）現メッシュが４分割
できたか否かが判断され、分割できた場合にはステップ
２２１３に進み、分割できない場合にはステップ２２０
７に戻る。

【０２４４】（ステップ２２１２）ステップ２２０９に
おいて現メッシュが末端のメッシュでない場合には、現
メッシュを４分割する。

【０２４５】（ステップ２２１３）ステップ２２１１及
びステップ２２１２において現メッシュを４分割した場
合には、４分割したメッシュをメッシュスタックに入
れ、ステップ２２０３へ戻る。

【０２４６】［５−３．第３実施形態の変形例］第３実
施形態では、図２１に示すように、メッシュ分割手段１
２と分割反対手段１３、およびメッシュ併合手段１４と
併合判定手段１５を設けたが、これらの一方の組のみを
設けても良いし、両者を省くこともできる。

【０２４７】［６．第４実施形態］矩形検索とは、与え
られた矩形の枠内にある図形を全て探し出すことをい
う。具体的には、まず、世界座標範囲内の矩形とメッシ
ュを与えたとき、矩形とメッシュの重なりの有無が判定
され、矩形と重なりを有するメッシュが検索される。次
に、そのメッシュに含まれる図形と矩形の領域の重なり
の有無が判定され、与えられた矩形の枠内にある図形が
全て検索される。

【０２４８】［６−１．第４実施形態の構成］図２９
は、本発明の第４実施形態の構成を示す機能ブロック図
である。すなわち、本実施形態の多次元データ検索装置
は、前記各実施形態に示した多次元データ管理装置の構
成要素に加えて、前記コンピュータの記憶領域内に蓄積
されている多次元データを管理する装置が、前記多次元
空間内における指定された範囲を対象とし、この指定さ
れた範囲内に属する多次元データを検索する範囲検索手
段２０を含むことを特徴とする。

【０２４９】この範囲検索手段２０は、入力装置２から
入力されたメッシュの座標と矩形の座標を使って、メッ
シュと矩形の領域が重なっているか否かを判定するメッ
シュ／矩形領域重なり判定手段２０１と、図形データの
座標と矩形の座標を使って、図形が矩形に入っているか
否かを判定する図形／矩形所属判定手段２０２と、デー
タ領域上に、固定パラメータを格納したり、初期４分木
（根ノードしかない４分木）を作成したり、図形キー管
理領域を構成する際にデータ領域を初期化するデータ領
域初期化手段２０３と、与えられた一点を含む末端メッ
シュを検索するメッシュ検索手段２０４とを備えてい
る。

【０２５０】この範囲検索手段２０による検索結果は、
前記出力装置３に出力される。すなわち、本実施形態に
おいては、前記検索結果は、入力装置２および出力装置
３において、検索を使用する側が用意したデータ領域に
検索結果を書き込むことにより実現される。例えば、矩
形検索の場合、矩形内にある図形のデータ格納領域の場
所を指すポインタのリストを返し、また、最近傍図形検
索の場合は、図形のデータ領域を指すポインタと距離と
最近傍点を返すように構成されている。なお、前記メッ
シュ／矩形枠重なり判定手段１２においては、矩形にす
っぽり含まれるメッシュや矩形をすっぽり含むメッシュ
は、「重なっている」と言わないこととする。さらに、
メッシュ検索手段１６においては、与えられた一点がメ
ッシュの境界上に乗っているときは、存在するならば右
上のメッシュ、上のメッシュ、右のメッシュ、下のメッ
シュ、左のメッシュに含まれるとする。メッシュ／矩形
領域重なり判定手段１１とメッシュ／矩形枠重なり判定
手段１２とによって、世界座標範囲内の矩形とメッシュ
を与えたとき、矩形とメッシュの重なりを、次の4つの
場合について判定することができる。

【０２５１】すなわち、（ａ）メッシュが矩形を含む、
（ｂ）メッシュが矩形に含まれる、（ｃ）メッシュと矩
形の重なりがある、（ｄ）メッシュと矩形の重なりがな
いの４つの場合について判定がなされる。したがって、
この手段を繰り返し使うことによって、矩形と重なりの
あるメッシュを全て探し出すことができる。また、前記
（ａ）が判定できると、他のメッシュを判定する必要が
なくなり、４分木で言えば、横方向に検索を広げなくて
済む。さらに（ｂ）が判定できると、そのメッシュが分
割されていたとき、分割された４つのメッシュを判定す
る必要がなくなる。４分木で言えば、縦方向に検索を進
めなくて済むというメリットがある。

【０２５２】［６−２．第４実施形態の作用］以下前記
のような構成を有する第４実施形態の多次元データ管理
装置の作用並びにこれに対応する多次元データ管理方法
について、図２３によってそ木構造を説明すると共に、
図２４〜２８のフローチャートに従って説明する。

【０２５３】［６−２−１．中間メッシュにも末端メッ
シュにも図形を登録する場合の矩形検索］上記第２実施
形態及び第３実施形態において説明した中間メッシュに
も図形を登録する場合の矩形検索は、図２５及び図２６
に示したフローチャートにしたがって実行される。以
下、各ステップごとに説明する。

【０２５４】まず、図２５に示したフローチャートは、
検索する矩形にかかっているすべてのメッシュを探し出
す処理の流れを示したものである。

【０２５５】（ステップ２５０１）検索する矩形及び検
索結果格納図形リストをセットする。すなわち、検索す
る矩形のセットは、矩形の左下と右上の座標をセットす
ることによりなされ、また、検索結果格納図形リストの
セットは、記憶領域のポインタをセットすることにより
なされる。なお、この検索する矩形と検索結果格納図形
リストは、矩形検索を行なう側から与えられる。

【０２５６】（ステップ２５０２）探し出したメッシュ
リストを入れておく空のメッシュリストを用意する。

【０２５７】（ステップ２５０３、ステップ２５０４）
処理すべきメッシュの順番を覚えておくためのメッシュ
スタックを空にして用意し、まず世界全体のメッシュ１
をこのスタックに入れる。

【０２５８】（ステップ２５０５）スタックが空か否か
が判断され、スタックが空であれば、図２６に示す図形
が矩形に入っているか否かの検索処理へ進む。このと
き、矩形と重なりのある中間メッシュと末端メッシュの
リストができている。一方、スタックが空でなければ、
次のステップ２５０６に進む。この例では、検索を始め
た直後であり世界全体のメッシュ１がスタックにあるの
で、ステップ２５０６に進む。

【０２５９】（ステップ２５０６）スタックから１つメ
ッシュを取り出す。この例では、世界全体のメッシュ１
が取り出され、スタックは空の状態になる。

【０２６０】（ステップ２５０７）取り出したメッシュ
が矩形と重なっているか否かを判断し、重なっていない
ならば、スタックが空か否かの判断ステップ２５０５へ
戻る。一方、重なっているならば、次のステップ２５０
８へ進む。ここでは、世界全体のメッシュ１と矩形の重
なりを判断し、重なっているのでステップ２５０８へ進
む。なお、本実施形態においては、メッシュの座標を４
分木で管理し、また、メッシュ番号を規則的に付けてい
ることから、メッシュの座標を容易に計算できるため、
メッシュの座標と矩形の座標からメッシュが矩形と重な
っているか否かの判断は容易である。

【０２６１】（ステップ２５０８）メッシュをメッシュ
リストに加える。ここでは、世界全体のメッシュ１だけ
のメッシュリストができる。

【０２６２】（ステップ２５０９）メッシュが末端メッ
シュか否かを判断し、末端メッシュならばステップ２５
０５へ戻る。一方、末端メッシュでなければ４分割され
た子メッシュがあるので、それらについても調べる必要
があるため、次のステップ２５１０へ進む。本例では、
世界全体メッシュ１は末端メッシュでないので、ステッ
プ２５１０に進む。なお、メッシュが末端メッシュか否
かの判断は、４分木から容易に分かる。

【０２６３】（ステップ２５１０）メッシュを４分割し
た４つの子メッシュをスタックに入れ、ステップ２５０
５に戻る。本例では、世界全体の子メッシュ７、６、
５、４をスタックに入れる。スタック内は、上から７、
６、５、４と並ぶ。本例では、ステップ２５０５での判
断は、スタックは空ではないので、ＮＯとなり、ステッ
プ２５０６へ進む。

【０２６４】以下、図２３に示した例に基づいて、本処
理をさらに詳しく説明する。

【０２６５】ステップ２５０６においてスタックから１
つ取り出す場合、末尾のメッシュ４が取り出され、スタ
ックは７、６、５になる。ここで、図２３に示したよう
に、メッシュ４と矩形は重なっているので（ステップ２
５０７）、メッシュリストにメッシュ４を加える（ステ
ップ２５０８）。その結果、メッシュリストは１、４に
なる。続いて、ステップ２５０９において、メッシュ４
は末端メッシュなのでステップ２５０５へ戻る。

【０２６６】ステップ２５０５において、まだスタック
は空でないので、ステップ２５０６でスタックから次の
メッシュを１つ取り出す。ここではメッシュ５が取り出
され、スタックは、７、６になる。ここで、図２３に示
したように、メッシュ５と矩形は重ならないので（ステ
ップ２５０７）、ステップ２５０５に戻る。

【０２６７】ステップ２５０５に戻ってもまだスタック
は空でないので、スタックから次のメッシュを１つ取り
出す。ここではメッシュ６が取り出され、スタックは７
のみになる。ここで、図２３に示したように、メッシュ
６と矩形は重なっているので、メッシュリストにメッシ
ュ６を加える（ステップ２５０８）。その結果、メッシ
ュリストは、１、４、６になる。続いて、ステップ２５
０９において、メッシュ６は末端メッシュでないので、
ステップ２５１０でメッシュの６の４つの子メッシュ２
７、２６、２５、２４をスタックに入れた後、ステップ
２５０５に戻る。その結果、スタックは７、２７、２
６、２５、２４になる。

【０２６８】ステップ２５０６において、次にスタック
から取り出されるのは２４であるが、これは矩形と重な
りがない（ステップ２５０７）ので、再びステップ２５
０５に戻る。次にメッシュ２５が取り出されるが、図２
３に示したように、このメッシュ２５は矩形と重なりが
ある（ステップ２５０７）ため、メッシュ２５はメッシ
ュリストに加えられる（ステップ２５０８）。その結
果、メッシュリストは１、４、６、２５になる。また、
このメッシュ２５は末端メッシュなので（ステップ２５
０９）、このままステップ２５０５に戻る。この時点
で、スタックは７、２７、２６になっている。

【０２６９】さらに、ステップ２５０６において、スタ
ックからメッシュ２６が取り出されるが、図２３に示し
たように、このメッシュ２６は矩形と重ならない（ステ
ップ２５０７）。続いて、ステップ２５０６において、
スタックからメッシュ２７が取り出されるが、このメッ
シュ２７も矩形と重ならない（ステップ２５０７）。こ
の時点で、スタックは７になる。

【０２７０】次に、ステップ２５０６において、スタッ
クからメッシュ７を取り出すと、スタックは空になる。
また、図２３に示したように、このメッシュ７も矩形と
重ならない（ステップ２５０７）。ここでステップ２５
０５へ戻るとスタックが空なので、ＹＥＳの方へ進む
（すなわち、図２６に示す図形が矩形に入っているか否
かの検索処理へ進む）。なお、この時、メッシュリスト
には１、４、６、２５が入っており、これが矩形にかか
っている全メッシュのリストである。

【０２７１】図２６に示したフローチャートは、図２５
で挙げられたメッシュリストのメッシュを１つずつ調べ
て、図形が矩形に入っているか否かを検索する処理の流
れを示したものである。

【０２７２】（ステップ２６０１）メッシュリスト内の
すべてのメッシュに対して、矩形内に含まれる図形を集
める処理を行ない、すべてのメッシュに対してこの処理
が終わっている場合には、矩形検索は終了する。一方、
未処理のメッシュが残っている場合には、次のステップ
２６０２へ進む。

【０２７３】（ステップ２６０２）まだ図形を探してい
ない未処理のメッシュをメッシュリストから１つ選ぶ。
本例では、メッシュリストに１、４、６、２５が入って
いるので、まずメッシュ１から始める。

【０２７４】（ステップ２６０３）メッシュに登録され
ているすべての図形に対して、後述するステップ２６０
４〜ステップ２６０７の処理が終了しているならば、ス
テップ２６０１に戻る。一方、未処理の図形があれば、
次のステップ２６０４に進む。本例では、メッシュ１に
は図形が１つもないので、処理済みとみなされ、ステッ
プ２６０１に戻る。次に、ステップ２６０２においてメ
ッシュ４が選ばれる。

【０２７５】（ステップ２６０４）メッシュに登録され
ている図形の中から未処理の図形を１つ選ぶ。ここで
は、図２３に示したように、メッシュ４の図形ｃを選
ぶ。

【０２７６】（ステップ２６０５）ステップ２６０４に
おいて選んだ図形がすでに検索結果格納図形リストに入
っているか否かが判断され、入っているならば何もせず
にステップ２６０３に戻る。一方、検索結果格納図形リ
ストに入っていなければ、次のステップ２６０６に進
む。本例では、検索結果格納図形リストは初期時は空で
あり、図形ｃは入っていない。したがって、ステップ２
６０６に進む。なお、この処理は、図形データに調査済
マークを付けることによっても実現できる。

【０２７７】（ステップ２６０６）ステップ２６０４に
おいて選んだ図形が矩形に入っているか否かが判断さ
れ、入っていれば、次のステップ２６０７に進む。一
方、入ってなければステップ２６０３へ戻る。本例の図
形ｃは矩形に入っているので、ステップ２６０７に進
む。なお、この条件判断は行わなくてもよいこともあ
る。つまり、矩形に入っているか否かに関係なく図形リ
ストに加える場合もある。図形表示を行なう場合、ディ
スプレイの外の図形を表示してもまったく見えないの
で、表示について影響ないからである。グラフィック表
示が大変高速ならばこの判断を省くことは有効である。

【０２７８】（ステップ２６０７）検索結果格納図形リ
ストに図形データポインタを加え、その後ステップ２６
０３に戻る。その結果、図形ｃが検索結果格納図形リス
トに加わる。ここでは図形ｃだけの図形リストができ
る。

【０２７９】以下、図２３に示した例に基づいて、本処
理をさらに詳しく説明する。

【０２８０】すなわち、図形ｃが検索結果格納図形リス
トに加えられた後、ステップ２６０３に戻る。図２３に
示したように、メッシュ４にはさらに図形ｄがあるの
で、ステップ２６０４に進み、この図形ｄが選ばれる
（ステップ２６０４）。次に、ステップ２６０５におい
て、図形ｄは検索結果格納図形リストにないと判断さ
れ、ステップ２６０６に進む。ここで、図形ｄは矩形に
入っているので、検索結果格納図形リストに加えられる
（ステップ２６０７）。その結果、検索結果格納図形リ
ストは、ｃ、ｄになる。次に、ステップ２６０３に戻
り、メッシュ４に登録されているすべての図形について
の処理が終了したと判断され、さらにステップ２６０１
に戻る。ステップ２６０１において、まだメッシュ６と
２５について処理が済んでいないので、ステップ２６０
２に進み、本例ではメッシュ６を選ぶ。図１６及び図２
３に示したように、このメッシュ６には図形ｈだけが登
録されている。ステップ２６０４において、この図形ｈ
が選ばれる。

【０２８１】次に、ステップ２６０５において、図形ｈ
は検索結果格納図形リストにないと判断され、ステップ
２６０６に進む。ここで、図形ｈは矩形に入っているの
で、検索結果格納図形リストに加えられる（ステップ２
６０７）。その結果、検索結果格納図形リストは、ｃ、
ｄ、ｈになる。次に、ステップ２６０３に戻り、メッシ
ュ６に登録されているすべての図形についての処理が終
了したと判断され、ステップ２６０１に戻る。ステップ
２６０１において、まだメッシュ２５について処理が済
んでいないので、ステップ２６０２に進み、メッシュ２
５が選ばれる。図１６及び図２３に示したように、この
メッシュ２５には未処理の図形ｄ、ｉがあるので（ステ
ップ２６０３）、ステップ２６０４に進む。なお、図形
ｈは、図１６に示したように、中間メッシュであるメッ
シュ６に登録されており、メッシュ２５には登録されて
いないので、ここでは検索の対象とはならない。

【０２８２】ステップ２６０４において図形ｄが選ばれ
るが、この図形ｄはすでに検索結果格納図形リストにあ
るので、ステップ２６０３に戻る。一方、図形ｉは検索
結果格納図形リストにないので（ステップ２６０５）、
ステップ２６０６に進む。このステップ２６０６におい
て、図形ｉは矩形に入っていないので、ステップ２６０
３に戻る。このようにして、メッシュ２５内のすべての
図形の処理が終わったので、ステップ２６０１に戻る。

【０２８３】そして、メッシュリスト内のすべてのメッ
シュに対して処理が終わったので、本処理を終了する。
この時点で、検索結果格納図形リストは、図形ｃ、ｄ、
ｈとなる。

【０２８４】［６−２−２．サブ図形を扱うとき］表示
側の都合上、図形が複数の構成要素からなることがあ
る。一般に、図形は数種類の複数の単純な図形（サブ図
形）から構成される。例えば、配電線は、複数の線分の
集まりである。この場合、表示側は、配電線を１つ１つ
の線分に分けて管理しない。１つの図形として扱う方が
人間の感覚に合っているからである。表示の上でも、線
分を線分の数だけ描画することを繰り返すよりも、線分
の集まりとして一度に表示する方が効率が良い。このよ
うなサブ図形で構成される図形を「スーパー図形」と呼
ぶ。

【０２８５】１つの図形データが複数のサブ図形から構
成されている場合、図形キー（ＩＤ）はスーパー図形に
対してのみ１つだけ発番される。また、４分木のメッシ
ュデータの所属図形リストは、図形データではなくサブ
図形のデータ領域を指す。ただし、サブ図形のデータ領
域を指してはいるが、元のスーパー図形がどれか分かる
ようにサブ図形を指すポインタをつくる。例えば、サブ
図形を指すのに、元のスーパー図形のデータ領域の場所
と、そこからのサブ図形のデータ領域へのオフセットを
対にして、サブ図形へのポインタとする。このようにポ
インタを作ると、サブ図形も元のスーパー図形も分か
る。このポインタを使ってメッシュへの登録はサブ図形
単位に行なうことができる。

【０２８６】このようにサブ図形単位に登録すること
は、後述する最近傍検索で利益がある。その理由は、複
数の単純な図形（サブ図形）からなる図形は、通常大き
な図形になることが多く、複数のメッシュにまたがる場
合が多い傾向があるからである。例えば、２つのサブ図
形Ａ，Ｂ（２本の線分）からなるスーパー図形Ａを例に
考える。なお、線分Ａ，Ｂはそれぞれたった１つのメッ
シュｍ、ｎにしか登録されていないとする。しかし、ス
ーパー図形Ａから見ると、この図形は２つのメッシュ
ｍ、ｎにまたがっていることになる。

【０２８７】ここで、矩形にはちょうどスーパー図形Ａ
しか存在せず、最近傍検索を行なう中心点がメッシュｍ
にあるとする。サブ図形に分けないでスーパー図形単位
で登録している場合には、スーパー図形Ａがメッシュｍ
に登録されているということしか情報はなく、線分Ａ，
Ｂがどのように位置しているかは分からないため、中心
点からの距離計算を行うには、線分Ａ，Ｂ両方に対して
行なうことになる。すなわち、スーパー図形Ａが最近傍
図形であることを得るのに、２回線分に対する距離計算
を行なわねばならない。

【０２８８】一方、サブ図形に分けて登録すると、メッ
シュｍには線分Ａのみが登録されていて、線分Ｂは登録
されていないので、距離計算は線分Ａに対してだけ行わ
れる。この距離を半径とする円に他のメッシュが入って
なければ、線分に対する距離計算を１回するだけで最近
傍図形であることを得る。最近傍図形を返すときは、サ
ブ図形Ａの元のスーパー図形Ａを返す。なぜなら、もと
もと表示側はスーパー図形単位でデータを与えているか
らである。

【０２８９】このようなサブ図形を扱う場合に、上記矩
形検索処理で変わるところを述べる。すなわち、図２６
において、ステップ２６０３、ステップ２６０４、ステ
ップ２６０６の「図形」という言葉は「サブ図形」と変
わる。また、図２５のステップ２５０１，図２６のステ
ップ２６０５の「検索結果格納図形リスト」は、スーパ
ー図形のリストである。さらに、ステップ２６０５の条
件は「そのサブ図形が検索結果格納スーパー図形リスト
内のスーパー図形のサブ図形であるか」と書き直し、ま
た、ステップ２６０７の図形データポインタは、スーパ
ー図形のポインタと書き直す。

【０２９０】［６−２−３．末端メッシュにのみ図形を
登録する場合の矩形検索］図２５及び図２６に示した
「中間メッシュにも末端メッシュにも図形を登録する場
合の矩形検索」に対して、「末端メッシュに図形を登録
する場合の矩形検索」は、図２８に示したフローチャー
トにしたがって実行される。なお、この処理の流れは図
２５に類似しているので（図２８のステップ２８０１〜
ステップ２８０７は、図２５のステップ２５０１〜ステ
ップ２５０７と同じ）、以下、相違点について説明す
る。

【０２９１】（ステップ２８０７）取り出したメッシュ
が矩形と重なっているか否かを判断し、重なっていない
ならば、スタックが空か否かの判断ステップ２８０５へ
戻る。一方、重なっているならば、次のステップ２８０
８へ進む。

【０２９２】（ステップ２８０８）メッシュが末端メッ
シュか否かを判断し、末端メッシュならばステップ２８
０９へ進み、一方、末端メッシュでなければ４分割され
た子メッシュがあるので、それらについても調べる必要
があるため、次のステップ２８１０へ進む。

【０２９３】（ステップ２８０９）メッシュをメッシュ
リストに加え、ステップ２８０５に戻る。

【０２９４】（ステップ２８１０）メッシュを４分割し
た４つの子メッシュをスタックに入れ、ステップ２８０
５に戻る。

【０２９５】すなわち、矩形検索のスピードは検索にか
かるデータ数にほぼ比例するため、データ密度が小さい
にもかかわらず多くの検索時間がかかることがなくな
り、データ密度に見合った矩形検索速度を得ることがで
きる。また、４分木の階層を下る検索により、無駄な条
件判断が減るので、矩形検索速度が高速化される。

【０２９６】［６−３．第４実施形態の変形例］第４実
施形態では、図２４に示すように、メッシュ分割手段１
２と分割反対手段１３、およびメッシュ併合手段１４と
併合判定手段１５を設けたが、これらの一方の組のみを
設けても良いし、両者を省くこともできる。また、範囲
検索手段２０を第３実施形態に組み合わせる代わりに、
第２実施形態に組み合わせても良い。

【０２９７】［７．第５実施形態］最近傍図形検索と
は、一点と矩形を指定し、その点に最も近い矩形内の図
形を１つ検索し、最近傍図形のデータ格納ポイント、距
離、その距離を図った図形上の座標を出力することをい
う。なお、この一点を「中心点」、矩形を「検索範囲」
と呼ぶ。

【０２９８】＊最近傍（スーパー）図形検索の概要＊ 最近傍（スーパー）図形検索とは、矩形と一点（中心点
と呼ぶ）が与えられたとき、矩形内のスーパー図形のう
ち中心点に最も近いスーパー図形（最近傍図形と呼ぶ）
を探し出す操作をいう。また、この最近傍図形検索は、
例えば、画面に表示される設備図のうち、マウスカーソ
ルに最も近い設備を見つけて、その色を目立たせるよう
な状況で使われる。この場合、画面の範囲が矩形にな
り、マウスカーソルの位置が中心点になる。

【０２９９】通常、中心点は矩形内に入っているもので
あるが、この最近傍図形検索においては、中心点が矩形
に入っていない場合でも、中心点に最も近い矩形内のス
ーパー図形を探し出すことができる。

【０３００】（１）検索対象地点（図３１に示したよう
に、矩形内に中心点があれば中心点、中心点が矩形外に
ある場合には、中心点に最も近い矩形上の一点）の周辺
で、１つ以上のサブ図形を見つけて、最近傍サブ図形を
一時的に設定する。

【０３０１】検索対象地点の周辺から１つ以上のサブ図
形を見つける手続きは、次のように行われる。まず、検
索対象地点を含む末端メッシュから調べる。この末端メ
ッシュにサブ図形がなければ、サブ図形が存在するまで
４分木を親メッシュへ遡る。４分木の根ノードまで（世
界全体メッシュ）まで遡ってもサブ図形が見つからなけ
れば、はじめの末端メッシュの周辺のメッシュへ検索範
囲を広げる。この検索範囲を検索枠と呼ぶ。

【０３０２】これら周辺の末端メッシュにもサブ図形が
なければ、末端メッシュから親メッシュへ遡って調べ
る。サブ図形を１つ以上調べるまで、検索枠を周囲へ広
げて末端メッシュから探し、親メッシュへ遡ることを繰
り返す。検索枠を周囲へ広げ続けて、矩形をすっぽり囲
むほど大きくなっても、その検査枠内にサブ図形がなけ
れば、最近傍サブ図形が見つけられずに終了する。

【０３０３】以下に示すフローチャートにおいては、末
端メッシュに図形がなかったときには、まず親メッシュ
へ遡り、それでも図形がなかったときに、末端メッシュ
の周辺に検索範囲を広げるようにしているが、逆に、ま
ず末端メッシュの周辺に検索範囲を広げてから、次に親
メッシュを探すように処理の順序を変えてもよい。

【０３０４】また、中心点から遠い図形を検索対象とし
たくないので、図形がなかったときの検索するメッシュ
を選ぶ順序を次のようにする。すなわち、メッシュの選
ぶ順序は、短形と重なるメッシュそれぞれにおいて中心
点から最も離れた地点（最遠点）を見つけて、中心点と
の最遠点の距離が近いメッシュ順とする。しかし、実際
には、図形がない場合は、もともと図形の密度が小さい
ところで最近傍図形検索を行なうことになる。そのため
多少遠いところを一時的な最近傍図形と設定しても、検
索する図形数が少ないので実行時間に問題はない。

【０３０５】（２）一時的な最近傍図形への距離を半径
とし、中心点を中心とする円を作り、その円の中の図形
からより近い図形を探す。この場合、何らかの最近傍サ
ブ図形が見つかる。このサブ図形から元のスーパー図形
が分かり、スーパー図形を返す。

【０３０６】［７−１．第５実施形態の構成］図２９
は、本発明の第５実施形態の構成を示す機能ブロック図
である。すなわち、本実施形態の多次元データ検索装置
は、前記各実施形態に示した多次元データ管理装置の構
成要素に加えて、前記コンピュータの記憶領域内に蓄積
されている多次元データを管理するステップが、前記多
次元空間内における指定された点に最も近い多次元デー
タを検索する最近傍データの検索手段２１を含むことを
特徴とする。第５実施形態において、前記最近傍データ
の検索手段２１としては、前記指定された点を含む最小
のメッシュに多次元データが登録されていない場合に、
前記最小のメッシュの親メッシュ、最小のメッシュに隣
接するメッシュ、親メッシュの親メッシュ、隣接するメ
ッシュの親メッシュ、隣接するメッシュに隣接する他の
メッシュのごとく、再帰的に最近傍データの候補が１つ
決定されるまで検索範囲を拡大するものを使用する。

【０３０７】また、この最近傍データ検索手段２１は、
前記範囲検索手段２０と同様に、入力装置２から入力さ
れたメッシュの座標と矩形の座標を使って、メッシュと
矩形の領域が重なっているか否かを判定するメッシュ／
矩形領域重なり判定手段２１１と、図形データの座標と
矩形の座標を使って、図形が矩形に入っているか否かを
判定する図形／矩形所属判定手段２１２と、図形の座標
データを使って、与えられた一点（中心座標）との距離
を計算し、その中心座標に最も近い図形上の座標を求め
る距離計算手段２１３と、データ領域上に、固定パラメ
ータを格納したり、初期４分木（根ノードしかない４分
木）を作成したり、図形キー管理領域を構成する際にデ
ータ領域を初期化するデータ領域初期化手段２１４と、
与えられた一点を含む末端メッシュを検索するメッシュ
検索手段２１５とを備えている。

【０３０８】［７−２．第５実施形態の作用］以下前記
のような構成を有する第５実施形態の多次元データ管理
装置の作用並びに、これに対応する多次元データ管理方
法について、図３０，３１の最近傍データの説明図と、
図３２〜４１のフローチャートに従って説明する。

【０３０９】［７−２−１．最近傍図形検索…その１］
図３２〜図３８は、中間メッシュにもサブ図形を登録す
るときの最近傍図形検索の処理の流れを示すフローチャ
ートである。

【０３１０】以下、最近傍（スーパー）図形検索の処理
の流れを、図３０及び図３２〜図３８を参照して、各ス
テップごとに説明する。

【０３１１】（ステップ３２０１）…図３２参照 中心点と矩形をセットする。例えば、図３０に示したよ
うに中心点と矩形をセットする。

【０３１２】（ステップ３２０２）検索過程で見つける
最近傍サブ図形について記憶するところを初期化する。 最近傍サブ図形＝無し◎ 最近傍点＝無し◎ 最短距離＝無限大（または、世界全体で引ける最も長い
線分の長さより長い長さ） ここで、「最近傍サブ図形」は、検索過程で見つけた最
も近いサブ図形であり、「最近傍点」は、そのサブ図形
上で中心点に最も近い点である。また、「最短距離」
は、そのサブ図形への中心点からの距離である。すなわ
ち、「最短距離」は最近傍点と中心点の距離である。

【０３１３】（ステップ３２０３）中心点から最も近い
矩形内の点（検索対象地点）を見つける。すなわち、矩
形内に中心点があるときは検索対象地点は中心点であ
る。一方、中心点が矩形外にあるときは、中心点と矩形
の間の距離計算を行なえば得られる。図３０に示したよ
うに、本例では、中心点そのものが検索対象地点にな
る。

【０３１４】（ステップ３２０４）検索対象地点のある
末端メッシュを見つける。これが検索を始めるメッシュ
となる。なお、この末端メッシュを見つける方法は、検
索対象地点の座標から４分木を使って得られる。本例で
は、メッシュ５が見つかる。

【０３１５】（ステップ３２０５）見つけた末端メッシ
ュを、これまでに調べた範囲を示す矩形（検索枠と呼
ぶ）とする。例では、全世界を４分割した左上４分の１
の四角形（メッシュ５）が検索枠となる。

【０３１６】（ステップ３２０６）検索のループのため
に、今見つけた末端メッシュだけからなる検索対象メッ
シュリストを作る。例では、検索対象メッシュリストは
５となる。

【０３１７】（ステップ３２０７）検索対象メッシュリ
ストから順にメッシュを１つ取り出し、現メッシュとす
る。例では、メッシュ５が選ばれる。そして、このメッ
シュ５に登録されているサブ図形から調べる。

【０３１８】（ステップ３２０８）まず、図形を調べる
前に、現メッシュが検索済みか否かを判断する。この処
理は、検索済メッシュリストに現メッシュが入っている
かどうかを調べることで分かる。そして、検索済みなら
ば次のステップ３２０９へ進み、未検索ならば、図３３
に示したステップ３３０１へ進む。例では、検索を始め
たところなので、メッシュ５は未検索であるため、ステ
ップ３３０１へ進む。

【０３１９】ここからは、メッシュに登録されているサ
ブ図形を調べる処理についての説明である。

【０３２０】（ステップ３３０１）…図３３参照 検索済メッシュリストに現メッシュを加える。例では、
検索済メッシュリストは、５だけからなる。

【０３２１】（ステップ３３０２）現メッシュにサブ図
形が登録されているか否かを判断し、現メッシュにサブ
図形が登録されていなければ、図３４に示した根ノード
へ遡るフローへ進む。一方、現メッシュにサブ図形があ
る場合には、次のステップ３３０３に進む。例では、図
３０に示したように、現メッシュ５は図形ｂを１つ持っ
ているので、ステップ３３０３に進む。

【０３２２】（ステップ３３０３）現メッシュに登録さ
れているサブ図形を順に調べる。ここでは、サブ図形を
１つずつ取ってきて現図形とする。例では、メッシュ５
の図形ｂを現図形とする。

【０３２３】（ステップ３３０４）すでに調べたサブ図
形のリスト（調査済サブ図形リスト）に現図形があるか
否かを調べ、あるならば、この現図形への処理をスキッ
プし、ステップ３３１１へ進む。一方、調査済サブ図形
リストに現図形がないならば、現図形への処理へ移り、
ステップ３３０５へ進む。なお、メッシュまたがりのあ
るサブ図形のとき、このステップで（ＹＥＳ）に進むこ
とがある。例では、図形ｂは検索済サブ図形リストにな
いので、ステップ３３０５へ進む。

【０３２４】（ステップ３３０５）現図形を２度調べな
いように、調査済サブ図形リストに現図形を加える。例
では、調査済サブ図形リストは、図形ｂだけからなる。

【０３２５】（ステップ３３０６）現図形が矩形に入っ
ているか否かを調べ、矩形に入っていなければ、処理を
行なうことは無駄なので、ステップ３３１１へスキップ
する。一方、矩形に入っていれば、距離計算のステップ
３３０７へ進む。例では、図形ｂは矩形内に入っている
ので、距離計算のステップ３３０７へ進む。

【０３２６】（ステップ３３０７）中心点から現図形へ
の距離を計算し、図形上の最も近い点（近傍点）を計算
する。この処理に対しては、座標からの計算手段が用意
されている。例では、図３０に示したように、図形ｂに
対して距離計算手段で計算すると、距離はＬで、近傍点
は点Ｖと分かる。距離、遠近の定義は多次元データの種
類に依存する。例では、ユークリッド距離である。

【０３２７】（ステップ３３０８）計算した距離とこれ
までの最短距離を比較し、計算した距離がこれまでの最
短距離より小さければ、最近傍サブ図形、最近傍点、最
短距離を更新するステップ３３０９へ進む。一方、計算
した距離がこれまでの最短距離と等しいか大きければ、
何もせずにステップ３３１１に進む。本例では、今のと
ころ最短距離は無限大なので、図形ｂの方が距離が小さ
いので、ステップ３３０９へ進む。

【０３２８】（ステップ３３０９）最近傍サブ図形、最
近傍点、最短距離を更新する。例の場合、最近傍サブ図
形＝図形ｂ、最近傍点＝点Ｖ、最短距離＝距離Ｌに更新
される。

【０３２９】（ステップ３３１０）最短距離が０かどう
か調べ、もし０ならば、もうこれより小さい距離はあり
えないので、ここで検索を打ち切り、ステップ３３１２
へ進む。一方、０でないならば、ステップ３３１１へ進
む。例では、図形ｂは距離が０でないので、ステップ３
３１１へ進む。

【０３３０】（ステップ３３１１）現メッシュ内の登録
サブ図形全てについてのループの終了条件の判断であ
る。全てのサブ図形について処理が終わってなければ、
ステップ３３０３へ戻る。一方、全てのサブ図形につい
て処理が終わっている場合には、図３２のステップ３２
１１へ進み、検索対象メッシュリストの全てについて、
処理したか否かを判断する。例の場合、メッシュ５の全
図形について処理が終わったので、次のメッシュについ
て調べるか否かを判断するステップ３２１１へ進む。

【０３３１】（ステップ３３１２）ここでは検索結果を
返す。最近傍の図形としてサブ図形が得られている。検
索結果としては、スーパー図形を返す必要があるので、
サブ図形の元のスーパー図形のデータへのポインタに直
す。それと合わせて最短距離と最近傍点を返す。

【０３３２】ここからは、ステップ３３０２で調べるメ
ッシュに図形が１つもなかったり、ステップ３２０８で
メッシュが検索済の場合の処理についての説明である。

【０３３３】（ステップ３２０９）ステップ３３０２で
調べるメッシュに図形が１つもなかったり、ステップ３
２０８でメッシュが検索済ならば、図３２のステップ３
２０９へ進む。ステップ３２０９からステップ３２１０
へのループでは、メッシュに調べるべき図形があるま
で、親メッシュへ遡る。このステップ３２０９は、遡っ
て行って根ノード（世界全体）まで来たらループを中断
するための判断である。すなわち、メッシュが世界全体
でなければ、親メッシュへ遡るステップ３２１０へ進
み、世界全体ならば、次の末端メッシュを調べるための
フローへ進む。

【０３３４】（ステップ３２１０）親メッシュを調べる
ため、現メッシュを親メッシュに置き換える。そしてス
テップ３２０８へ進む。

【０３３５】（ステップ３２１１）世界全体まで遡った
場合、ステップ３２０９からステップ３２１１へ進んで
いる。ここで、検索対象メッシュリストのメッシュ全て
に対して処理が終わっているか否かが判断され、処理が
終わってなければステップ３２０７へ戻る。一方、終わ
っていれば次のステップ３２１２へ進む。例の場合、検
索対象メッシュリストにはメッシュ５だけしかなく、メ
ッシュ５の処理が終わっているので、ステップ３２１２
へ進む。

【０３３６】（ステップ３２１２）ここで、１つ以上の
サブ図形について距離計算を行なったか否かを判断し、
分岐する。すなわち、最近傍図形＝無しのままでなけれ
ば、サブ図形１つ以上に対して距離計算をしたことを意
味する。一方、最近傍図形＝無しならば、まだ１つもサ
ブ図形に対して距離計算をしていないことになる。サブ
図形１つ以上に対して距離計算をしていれば、これまで
の最短距離、最近傍点、最近傍サブ図形があることにな
る。そして、このステップの次は、この最短距離を半径
とする円内のサブ図形を調べるフローステップ３４０１
へ進む。

【０３３７】上述したように、図３２のステップ３２１
２において、サブ図形に対して一度も距離計算をしてい
なければ、検索対象メッシュリスト内のメッシュすべて
と、それぞれのメッシュから親メッシュへ遡ってもサブ
図形が１つも見つからなかったことを意味する。そのた
め、この先のフロー（図３６に示したステップ３６０３
から）では、検索枠を広げて検索し直すための準備を行
なう。簡単に言うと、これまで調べた末端メッシュの範
囲を少し広げて、新たな末端メッシュのリストを作って
検索対象メッシュリストとする。ただし、範囲を広げた
結果、検索枠が矩形より大きくなったときには、最近傍
検索は終了する。この点について、図３９を参照してよ
り具体的に説明する。すなわち、はじめ、検索枠はメッ
シュＺの四角に設定される。そして、メッシュＺを検索
して、親メッシュをさかのぼっても図形がないときは、
回りを探す。この検索枠と接するか、重なる末端メッシ
ュで、検索済みではなく、矩形と重なるのはメッシュＡ
〜Ｈである。メッシュＡ〜Ｈの中で最小のメッシュＢの
縦幅、横幅分だけ検索枠を広げる。すると、図３９に示
したように、旧検索枠（太実線）から新検索枠（一点鎖
線）に広がる。さらに、メッシュＡ〜Ｈとその親メッシ
ュに図形がないならば、新検索枠を使ってメッシュリス
トを作る。メッシュリストは、メッシュＩ〜Ｍになり、
新たな検索枠（新々検索枠）は点線で囲んだ部分とな
る。

【０３３８】以下、この処理を各ステップごとに説明す
る。

【０３３９】（ステップ３６０１）このステップへは、
図３２に示したステップ３２１２から来る。なお、この
ステップにおけるメッシュリストの作成の詳細なルーチ
ンについては、図３７に示し、後述する。はじめにこの
ステップに到達したときは、検索枠は検索対象地点のあ
る末端メッシュである。この末端メッシュの回りの末端
メッシュを検索対象にしたいので、検索枠に接するか重
なる末端メッシュを探す。そして、これらの中の矩形に
重ならないメッシュと検索済のメッシュを除いて検索対
象メッシュリストとする。

【０３４０】もし、検索対象メッシュリストにメッシュ
が１つもなければ、検索枠が十分に広がって、矩形より
大きくなっていることを意味する。本例の矩形の場合、
メッシュ５に図形がなければ、メッシュ５の回りの末端
メッシュ２８、２９が検索対象メッシュリストになる。
なお、メッシュ４、メッシュ２５もメッシュ５の回りの
末端メッシュであるが、矩形に重なっていないので対象
外である。

【０３４１】（ステップ３６０２）検索対象メッシュリ
ストにメッシュあるか否かが判断され、メッシュが１つ
もなければ、検索すべきメッシュがもうないことを意味
し、検索結果として返るのは、最近傍図形がないという
ことである。一方、検索対象メッシュリストにメッシュ
があれば、ステップ３６０３に進む。

【０３４２】（ステップ３６０３）ここでは、新たな検
索対象メッシュリスト内のメッシュの中で最小のメッシ
ュの縦幅、横幅分だけ検索枠を縦にも横にも正負両方向
に広げる。このように広げると、次に再び図形が１つも
なくて検索対象メッシュリストを作るとき、近いところ
にあるメッシュから順に検索対象メッシュリストに加わ
ることになる。検索対象メッシュリストができているの
で、図３２のステップ３２０７へ戻ってメッシュに対す
る処理を行なう。

【０３４３】このように、図３２、図３３及び図３６に
示したフローチャートにしたがって最近傍図形検索を行
なうと、１つの最近傍サブ図形候補が見つかるか、最近
傍図形がないという結果が返るかどちらかになる。そし
て、最近傍図形候補が１つ見つかっていると、図３２の
ステップ３２１２から（ＮＯ）の分岐へ進み、図３４の
ステップ３４０１へ到達する。

【０３４４】（ステップ３４０１）このステップに到達
した場合には、最近傍サブ図形が１つ見つかっている
が、これより近いものがないかどうかを調べなければな
らない。このために中心点を中心として、最短距離を半
径とする円を作り、それにかかるメッシュを調べる。こ
のステップでは、その円と重なりかつ矩形と重なるメッ
シュ（末端も中間も）を検索し、検索対象メッシュリス
トとする。このメッシュ検索のルーチンについては、図
３８に詳細に表わし、後述する。本例では、メッシュ
１，５，７，２８，２９が検索対象メッシュリストに含
まれる。

【０３４５】（ステップ３４０２）検索対象メッシュリ
スト内のメッシュを１つずつ調べるため、メッシュを１
つ取って現メッシュとする。

【０３４６】（ステップ３４０３）現メッシュが検索済
か否かを調べる。すなわち、検索済メッシュリスト内に
現メッシュがあるか否かを調べれば良い。そして、現メ
ッシュが検索済ならば、メッシュに対する処理をスキッ
プして、図３５のステップ３５０６へ進む。一方、検索
済でなければ次のステップ３４０４に進む。例の場合、
メッシュ５が検索済リストにあるので、メッシュ５の処
理の時に、図３５のステップ３５０６へスキップする。

【０３４７】（ステップ３４０４）現メッシュを検索済
メッシュリストに加える（なお、検索したメッシュリス
トが必要なければこのステップはなくてもよい）。

【０３４８】（ステップ３４０５）現メッシュに登録サ
ブ図形があるか否かを判断し、あれば、図形の処理へ進
み、なければ、図３５のステップ３５０６へスキップす
る。例では、メッシュ１，７がステップ３５０６へスキ
ップすることになる。

【０３４９】（ステップ３４０６）現メッシュに登録さ
れているサブ図形１つ１つへの処理を始める。すなわ
ち、現メッシュに登録されているサブ図形を１つ選ん
で、現図形とする。例では、メッシュ２８の処理の場
合、図形ｉが選ばれ、メッシュ２９の処理の場合、図形
ａが選ばれる。

【０３５０】（ステップ３４０７）現図形が調査済か否
かを調べる。これは、調査済サブ図形リストを調べれば
分かる。そして、調査済ならば、図３５のステップ３５
０５へスキップし、調査済でなければ、次のステップ３
４０８へ進み、現図形への処理を行う。例では、図形ｉ
は調査済ではないので、ステップ３４０８へ進む。ま
た、図形ａも調査済ではないので、同様にステップ３４
０８へ進む。

【０３５１】（ステップ３４０８）メッシュまたがりが
ある場合に２度計算しないように、調査済サブ図形リス
トに現図形を加える。

【０３５２】（ステップ３４０９）距離計算をする前
に、現図形が矩形に入っているか否かを調べ、矩形に入
っていれば距離計算へ進み、矩形に入ってなければ、図
３５のステップ３５０５へスキップする。本例では、図
形ｉの場合、矩形に入っていないので、距離計算をせず
にステップ３５０５へスキップする。一方、図形ａの場
合、矩形に入っているので、ステップ３４１０で距離計
算を行なう。

【０３５３】（ステップ３４１０）中心点からの距離、
近傍点を距離計算手段によって計算する。図形ａの距離
はＫ、近傍点は点Ｕと計算される。

【０３５４】（ステップ３５０１）…図３５参照 距離計算した結果を、これまでの最短距離と比べる。こ
れまでの最短距離と等しいか大きければ、何もせずにス
テップ３５０５に進む。一方、これまでの最短距離より
小さければ、最近傍サブ図形更新のフローへ進む。本例
では、図形ａの場合、これまでの最短距離より距離が短
いので、ステップ３５０２へ進み更新する。

【０３５５】（ステップ３５０２）最近傍サブ図形、最
近傍点、最短距離を更新する。例の場合、最近傍サブ図
形＝図形ａ、最近傍点＝点Ｕ、最短距離＝距離Ｋとな
る。

【０３５６】（ステップ３５０３）最短距離が０かどう
か調べる。もし０ならば、もうこれより小さい距離はあ
りえないので、ここで検索を打ち切り、ステップ３５０
４へ進む。０でないならば、ステップ３５０５へ進む。
例の図形ａの場合、距離が０でないので、ステップ３５
０５へ進む。

【０３５７】（ステップ３５０４）ここでは検索結果を
返す。最近傍の図形としてサブ図形が得られているた
め、検索結果としては、スーパー図形を返す必要がある
ので、サブ図形の元のスーパー図形のデータへのポイン
タに直す。それと合わせて最短距離と最近傍点を返す。

【０３５８】（ステップ３５０５）現メッシュに登録さ
れている登録サブ図形全てについてのループの終了条件
の判断である。すべてのサブ図形について処理が終わっ
ていなければ、図３４のステップ３４０６へ戻り、次の
図形を調べる。一方、すべてのサブ図形について終わっ
ていれば、次のステップ３５０６に進む。

【０３５９】（ステップ３５０６）検索対象メッシュリ
ストのメッシュ全てに対して処理を終えたか否かが判断
され、すべてのメッシュについて処理を終えたら、次の
ステップ３５０７へ進む。一方、終えていければ、図３
４のステップ３４０２に戻り、次のメッシュへの処理を
行なう。

【０３６０】（ステップ３５０７）ここでは検索結果を
返す。最近傍の図形としてサブ図形が得られているた
め、検索結果としては、スーパー図形を返す必要がある
ので、サブ図形の元のスーパー図形のデータへのポイン
タに直す。それと合わせて最短距離と最近傍点を返す。
本例の場合は、最後には、「図形ａが最近傍図形であ
る」との結果を得る。

【０３６１】ここで、図３７を参照して、図３６のステ
ップ３６０１におけるメッシュリストの作成のルーチン
について、さらに詳しく説明する。すなわち、図３６の
ステップ３６０１においては、その時点で設定されてい
る検索枠と接するか、重なる末端メッシュのうち、検索
済メッシュリストになく、且つ、矩形と重なるものを探
し出して、新たな検索対象メッシュリストとする場合を
示している。

【０３６２】なお、この処理は、上述した矩形検索で
の、矩形に重なるメッシュリストの作成のフローチャー
ト（図２５）とほぼ同じである。違う点は、メッシュリ
ストを作成するステップに至るまでに、２つ条件分岐
（ステップ３７０７、ステップ３７０９）が加わってい
る点である。

【０３６３】また、このフローでは、末端メッシュだけ
がメッシュリストに加わえられるが、ステップ３７１０
とステップ３７１１の順番を入れ替えて、メッシュが末
端か否かを判断する前に、メッシュリストにメッシュを
加えると、条件に合う中間メッシュと末端メッシュの両
方を含むメッシュリストが得られる。

【０３６４】次に、図３８を参照して、図３４のステッ
プ３４０１におけるメッシュリストの作成のルーチンに
ついて、さらに詳しく説明する。すなわち、図３４のス
テップ３４０１においては、それまでの最短距離（それ
までの最近傍図形までの距離）を半径、中心点を中心と
する円と矩形に重なる末端メッシュ及び中間メッシュを
探し出して、新たな検索対象メッシュリストとする場合
を示している。

【０３６５】なお、この処理は、上述した矩形検索で
の、矩形にかかるメッシュリストの作成のフローチャー
ト（図２５）とほぼ同じである。違う点は、メッシュリ
ストを作成するステップに至るまでに、１つ条件分岐
（ステップ３８０８）が加わっている点である。

【０３６６】また、このフローでは、末端メッシュと中
間メッシュがメッシュリストに加わえられるが、ステッ
プ３８０９とステップ３８１０の順番を入れ替えて、メ
ッシュが末端か否かを判断した後で、メッシュリストに
メッシュを加えると、条件に合う末端メッシュだけのメ
ッシュリストが得られる。

【０３６７】［７−２−２．最近傍図形検索…その２］
上述した最近傍図形検索は、中間メッシュにもサブ図形
を登録する場合についてのものであったが、以下に述べ
る最近傍図形検索は、末端メッシュにのみサブ図形を登
録する場合についてのものである。

【０３６８】以下、中間メッシュに図形を登録する場合
と登録しない場合の最近傍図形検索の違いについて、図
３２（中間メッシュにもサブ図形を登録する場合）と図
４０（末端メッシュにのみサブ図形を登録する場合）で
比べる。図から明らかなように、図３２では、ステップ
３２０９、ステップ３２１０のループがあるが、図４０
にはない。その理由は、図３２では、中間メッシュにも
図形が存在するので、末端メッシュを調べて図形が存在
しなかった場合には、親メッシュへ溯って調べなけれ
ば、検索漏れを起こしてしまうからである。

【０３６９】次に、図３３（中間メッシュにもサブ図形
を登録する場合）と図４１（末端メッシュのみにサブ図
形を登録する場合）を比べる。この違いは、図３３で
は、ステップ３３０２の条件分岐でＮＯのとき、図３２
のステップ３２１１の検索対象メッシュリストの処理終
了判断へ飛ばず、ステップ３２０９に飛んでいる。一
方、図４１では、図３３のステップ３３０２に相当する
ステップ４１０２でＮＯのとき、図３２のステップ３２
１１に相当するステップ４００８に飛んでいる。その理
由は、中間メッシュにも図形がある図３３においては、
親メッシュを調べなければならないので、親メッシュを
調べるフローであるステップ３２０９へ飛ばなければな
らないからである。

【０３７０】なお、図４０からＢへ進み、Ｃから戻って
くるところに接続するフローチャートは、上述した図３
６（中間メッシュに図形がある場合の図）と同一であ
る。また、図４０のＡへ進む先のフローチャートは、ス
テップ３４０１を除いて、図３４及び図３５と同一であ
る。

【０３７１】図３４のステップ３４０１に対応する処理
が異なるのは、それまでに見つけた最近傍図形までの距
離を半径とする円の範囲内のメッシュを見つけるに際
し、中間メッシュにも図形がある場合は、円にかかるメ
ッシュを探すとき、末端だけでなく、中間メッシュも探
し出さなければならないからである。一方、末端メッシ
ュにしか図形がない場合には、中間メッシュを調べる必
要がないので、ステップ３４０１のステップを、末端メ
ッシュのみを探し出すように変更する。すなわち、図３
８のステップ３８０９とステップ３８１０を置き換えれ
ば良く、メッシュが末端か否かを判断し、ＹＥＳのとき
のみ、メッシュをリストに加えるようになっている。

【０３７２】このように、図３４のステップ３４０１を
変え、図３８のステップ３８０９及びステップ３８１０
を変えて、図４０のＡから図３４及び図３５のフローを
実行すれば、末端メッシュにのみ図形がある場合の最近
傍図形検索の処理フローになる。

【０３７３】［７−３．第５実施形態の効果］前記の様
な構成を有する第５実施例によれば、最近傍図形検索処
理において、１回の検索あたりに距離計算するデータが
少なくなるので、検索時間が速くなる。さらに、最近傍
図形検索処理の速さが、データ密度の疎密に影響され
ず、いつでも同程度の速さで処理できるようになる。

【０３７４】［７−４．第５実施形態の変形例］第５実
施形態では、図２９に示すように、メッシュ分割手段１
２と分割反対手段１３、およびメッシュ併合手段１４と
併合判定手段１５を設けたが、これらの一方の組のみを
設けても良いし、両者を省くこともできる。また、範囲
検索手段２０を第３実施形態に組み合わせる代わりに、
第２実施形態に組み合わせても良い。また、最近傍デー
タ検索手段２１を範囲検索手段２０と組み合わせ両方の
検索が可能としたが、範囲検索手段２０がなくても良
い。

【０３７５】［８．他の実施形態］ ［８−１．図形のメッシュへの所属条件の拡張］第２実
施形態において図形の所属を親メッシュから子メッシュ
へ移すべきか否かを判定する条件、及び第３実施形態に
おいて図形を現メッシュに所属させる（登録する）べき
か否かを判定する条件とは、類似の作用及び効果を有す
るものである。第３実施形態においては条件判定及びそ
の結果に依存した図形のメッシュへの登録作用が、その
時のメッシュ分割（４分木）の状態の如何にかかわら
ず、必要な場合にはメッシュ分割を行なっても、条件に
合致するメッシュに図形を所属させる。これに対して第
２実施形態においては、その作用が図形登録時のメッシ
ュ分割の状態によって制限され、図形登録時ではなく
て、別の基準に従って作用するメッシュ分割操作の作用
時に同時に行なわれる。つまりメッシュ分割時までその
作用が延期されるという差があるにすぎない。

【０３７６】この条件としてどのようなものを採用する
かによって、各図形のメッシュへの重複登録の数及び図
形とメッシュとの重なり具合が異なってくる。これが所
要記憶容量の大小及び矩形検索、最速傍図形検索の効率
に影響する。

【０３７７】従来技術はこの条件として （ａ）末端のメッシュで、かつ所属図形数がＰ未満のメ
ッシュか否かを判定し、該当メッシュであれば登録す
る。（該当していなければメッシュ分割によって該当す
るメッシュを作り出す。） （ｂ）図形全体を包含する最小のメッシュか否かを判定
し、最小のメッシュに該当していれば登録する。

【０３７８】（ｃ）図形全体を包含する最小のメッシュ
を分割した子メッシュの境界によって分断された各部分
図形に注目し、それらの部分図形のうち１つを含む最小
のメッシュか否かを判定し、該当メッシュであればそこ
に図形を登録する。

【０３７９】という条件を設定したのとそれぞれ等価で
ある。これらの条件を用いた場合には、それぞれ［発明
の解決しようとする課題］に述べたような問題点によっ
て記憶領域の浪費や検索性能の劣化が生じる場合を排除
することができなかった。

【０３８０】これらの従来技術は判定基準にかかわる図
形とメッシュとの関係として、例えば前記（ａ）の場
合、登録しようとする図形及び既にメッシュに所属して
いる図形の種類の如何にかかわらず、メッシュに既に所
属している図形数のみを用いている。また、（ｂ）の場
合はメッシュが図形を包含する最小のメッシュか否か、
つまりメッシュを分割した子メッシュのうち複数のもの
に図形が重なるか否かのみを用いている。（ｃ）は判定
の過程を二段階に分けているとはいえ、用いられている
図形とメッシュとの関係は（ｂ）と同様に、図形の種類
の如何にかかわらず、メッシュが（部分）図形を包含す
る最小のメッシュか否かのみを用いている。

【０３８１】ここにいう「図形の種類」とは、登録しよ
うとするｎ次元空間データのｎ次元空間内での空間の占
有（ひろがり）の態様に主として起因する分類・区別で
ある。例えば極端な例として点データは大きさ（ひろが
り）を持たないので前記（ｂ）（ｃ）のような判定基準
では扱えず、他の基準例えば（ａ）のような基準を使用
せざるを得ない。線分は長さのみあって面積や体積はな
いから、メッシュとの重なり具合及びそれが検索の効率
に及ぼす影響も面積や体積を持つ図形、就中各次元の最
大径の比がメッシュの各次元の長さの比に近いような凸
な図形とは異なっている。後者に関しては前記（ｃ）あ
るいは（ｂ）のような基準はメモリ効率の点でも検索速
度の点でも有効である場合が多いが、線分や細長い矩形
直方体に関しては必ずしも有効でないことは前述のとお
りである。

【０３８２】さらには、ある目的・性質を（共）有する
ことが予めわかっているデータに関しては、それに応じ
た適切な条件を設定することで資源の浪費を避け、検索
効率を高めることができる。例えば、地図、グラフ等の
背景に用いられる罫線や座標線は数はそれ程多くはない
が、１つ１つが非常に長いという性質がある。これらの
データを他の非常に短い線分や小さな図形と同様な基準
でメッシュに所属させたとすると、所属メッシュが細分
化されすぎて非常に多くのメッシュに重複登録され、多
量のメモリを浪費したうえ、検索効率をも劣化させるお
それが大きい。逆にあまりにも小数のメッシュにしか所
属せず、同一のメッシュに多数の罫線が所属することに
なって検索効率が著しく低下するという事態もまた生じ
うる。例えば前記（ｂ）の条件を用いれば、すべての罫
線は世界座標範囲と同じ１つの（最大の）メッシュにの
み所属することになり、領域を分割して図形を登録する
ことによって検索の効率を向上させるという効果は全然
得られない。

【０３８３】このような状況を避けるために、罫線につ
いては、罫線の間隔と同程度の長さの辺を持つメッシュ
にのみ登録するように第４実施例（ｂ）の条件を設定す
ることが考えられる。この条件に従って登録を行なえ
ば、１つのメッシュに属する罫線は（１方向）１本だけ
になり、なおかつ極端な重複登録は避けられる。この場
合、選ばれる罫線の数が罫線の総本数に比較して非常に
少ない矩形検索には特に有効である。前記の条件は個々
の罫線の線分としての属性（例えば長さ）ではなく、罫
線同士の間隔から予め決定あるいは計算される長さを規
準にして登録すべきメッシュを判定するものである。

【０３８４】面積や体積を持つ図形に関しても、例えば
背景として用いられる非常に広い面積を占める図形を、
例えば前記（ａ）のような条件で他の小さな図形と同様
に扱えば重複登録の数は膨大になる。このような図形に
対しては第３実施形態の（ｄ）のような条件で重複登録
の数を限るのが、メモリの浪費を避けるのに効果的であ
る。

【０３８５】上述のように、図形の形状・大きさのみな
らず、その目的や他の図形との関係から最適と考えられ
る基準にもとづいて、メッシュへの図形の登録あるいは
子メッシュへの図形の所属移動を制御することによっ
て、図形に依存しない一律な条件では達成できないメモ
リの効率的使用並びに検索の効率化を図ることができ
る。

【０３８６】［８−２．多次元データへの適用］前記各
実施形態は、２次元や３次元空間内の図形データを扱う
場合について具体的に述べてきたが、それ以外にも各次
元が何らかの量を表すような多次元のデータに関して、
本実施例と同様の方法で他の多次元空間、すなわちｎ次
元空間を再帰的に２のＮ乗分割したｎ次元直方体をメッ
シュとしてデータを登録・検索することができる。これ
らｎ次元データはｎ次元空間内の点として扱われるよう
なデータばかりではなく、１つの（１組の）データがｎ
次元空間内にある広がりを持った超立体として扱われる
ものも希ではない。例えば、１つの物体に関するｎ種の
属性の測定値はそれぞれに誤差を含んでおり、それを各
次元の真の値がある確率で存在する範囲として扱う場
合、ｎ次元直方体データになる。その形状は測定の状況
に依存して種々変化するので、それらのデータを一括し
て記録し、各次元の真の値がある範囲に存在する物体を
選択する等の検索を効率良く実施するためには、本発明
のような多次元データ管理・検索手段が必要である。

【０３８７】このように本発明は、上述した実施形態に
限られず、多次元空間中で位置の決まるデータの管理・
検索に適用できるが、この場合、Ｎ次元空間のデータに
関しては、［２のＮ乗］分木でメッシュの分割が管理さ
れる。また、データが多種類ある場合には、種類を限定
して検索することもできる。さらに、データの種類や座
標データの扱いの違いによって、［２のＮ乗］分木を複
数用意することも可能である。

【０３８８】

【発明の効果】以上述べた様に、本発明によれば、デー
タ領域の削減が可能で、しかも矩形検索及び最近傍図形
検索の高速化を可能とした多次元データ管理方法及び装
置を提供することができる。

【図面の簡単な説明】

【図１】本発明の第１実施形態の構成を表す機能ブロッ
ク図

【図２】本発明にかかるデータ領域の全体構成を示す図

【図３】本発明のメッシュデータの構成を示す図

【図４】メッシュデータと図形データとの対応を示す図

【図５】本発明の第１実施形態において、図形ａを登録
する世界全体を示す図

【図６】メッシュ分割をした場合の番号付けを示す図

【図７】メッシュとそのメッシュに登録された図形を示
すツリー図

【図８】スタックの動作を示す図

【図９】図形のデータ領域への登録の処理の流れを示す
フローチャート

【図１０】図形をメッシュに登録する処理の流れを示す
フローチャート

【図１１】図形をデータ領域から削除する処理の流れを
示すフローチャート

【図１２】図形をメッシュから削除する処理の流れを示
すフローチャート

【図１３】図形の修正の処理の流れを示すフローチャー
ト

【図１４】メッシュの分割の処理の流れを示すフローチ
ャート

【図１５】メッシュの併合の処理の流れを示すフローチ
ャート

【図１６】中間メッシュにも図形を登録する場合のメッ
シュとそのメッシュに登録された図形を示すツリー図

【図１７】本発明の第２実施形態の構成を表す機能ブロ
ック図

【図１８】第２実施形態の処理の流れを示すフローチャ
ート

【図１９】中間メッシュにも図形を登録する場合の条件
を説明するための図

【図２０】中間メッシュにも図形を登録する場合の条件
を説明するための図

【図２１】本発明の第３実施形態の構成を表す機能ブロ
ック図

【図２２】第３実施形態の処理の流れを示すフローチャ
ート

【図２３】本発明の第４実施形態の矩形検索を説明する
ための図

【図２４】本発明の第４実施形態の構成を表す機能ブロ
ック図

【図２５】矩形検索において、検索する矩形にかかって
いる全てのメッシュを探し出す処理の流れを示すフロー
チャート

【図２６】矩形検索において、図形が矩形に入っている
か否かを検索する処理の流れを示すフローチャート

【図２７】メッシュリストと図形リストの対応を示す図

【図２８】末端メッシュにのみ図形を登録した場合の矩
形検索の処理の流れを示すフローチャート

【図２９】本発明の第５実施形態の構成を表す機能ブロ
ック図

【図３０】最近傍図形検索を説明するための図

【図３１】中心点と矩形の関係を示す図

【図３２】最近傍図形検索の処理の流れを示すフローチ
ャート

【図３３】最近傍図形検索の処理の流れを示すフローチ
ャート

【図３４】最近傍図形検索の処理の流れを示すフローチ
ャート

【図３５】最近傍図形検索の処理の流れを示すフローチ
ャート

【図３６】最近傍図形検索の処理の流れを示すフローチ
ャート

【図３７】最近傍図形検索の処理の流れを示すフローチ
ャート

【図３８】最近傍図形検索の処理の流れを示すフローチ
ャート

【図３９】最近傍図形検索の処理の流れを示すフローチ
ャート

【図４０】末端メッシュにのみ図形を登録した場合の最
近傍図形検索の処理の流れを示すフローチャート

【図４１】末端メッシュにのみ図形を登録した場合の最
近傍図形検索の処理の流れを示すフローチャート

【図４２】ＭＤ木法の従来手法を示す図であって、
（Ａ）は領域分割、（Ｂ）はＭＤ木

【図４３】ＭＤ木法の問題点を示す図であって、（Ａ）
は領域分割、（Ｂ）はデータ４の投入後、（Ｃ）はデー
タ７の投入後、（Ｄ）はデータ８の投入後

【図４４】従来の最近傍データ検索の手法を説明する図

【図４５】重複登録の例を示す図

【図４６】ｑｕａｄ−ｔｒｅｅ法の第１の変形例を示す
図

【図４７】ｑｕａｄ−ｔｒｅｅ法の第２の変形例を示す
図

【符号の説明】 １…中央処理装置 ２…入力装置 ３…出力装置 ４…メインメモリ ５…ファイル装置 ６…データ管理プログラム ７…メッシュデータ記憶手段 ８…多次元データ記憶手段 ９…木構造管理手段 １０…多次元データ登録削除手段 １１…メッシュ／矩形領域重なり判定手段 １２…メッシュ／矩形枠重なり判定手段 １３…図形／矩形所属判定手段 １４…距離計算手段 １５…データ領域初期化手段 １６…メッシュ検索手段 １７…検索結果出力手段

───────────────────────────────────────────────────── フロントページの続き (72)発明者 和田 潔 東京都府中市東芝町１番地 株式会社東芝 府中工場内

Claims (49)

【特許請求の範囲】
1. 【請求項１】コンピュータの記憶装置に管理対象となる
   複数の多次元データを多次元空間内に配置し、各多次元
   データの値を多次元空間内における座標としてコンピュ
   ータの記憶装置に登録するステップと、 前記多次元空間を複数のメッシュに階層的に分割し、分
   割された各階層のメッシュを木構造の各ノードに対応さ
   せ、各メッシュと各ノードとの対応関係を記録するステ
   ップと、 分割された各メッシュに多次元データに関する情報を登
   録するステップと、 前記各メッシュに登録された情報に基づいてコンピュー
   タの記憶領域内に蓄積されている多次元データを管理す
   るステップを有する多次元データ管理方法において、 前記各メッシュのうち、少なくとも前記木構造の末端の
   ノードに対応する末端メッシュに多次元データを登録す
   るステップと、 前記末端メッシュに登録できる多次元データ数を一定値
   以下に設定し、末端メッシュに登録する多次元データ数
   が前記設定値を超えた場合に、その末端メッシュの分割
   を試行するステップと、 この末端メッシュの分割ステップの試行に当たり、予め
   設定された分割許容条件にしたがって分割の可否を判定
   するステップを備えていることを特徴とする多次元デー
   タ管理方法。
2. 【請求項２】コンピュータの記憶装置に管理対象となる
   複数の多次元データを多次元空間内に配置し、各多次元
   データの値を多次元空間内における座標としてコンピュ
   ータの記憶装置に登録するステップと、 前記多次元空間を複数のメッシュに階層的に分割し、分
   割された各階層のメッシュを木構造の各ノードに対応さ
   せ、各メッシュと各ノードとの対応関係を記録するステ
   ップと、 分割された各メッシュに多次元データに関する情報を登
   録するステップと、 前記各メッシュに登録された情報に基づいてコンピュー
   タの記憶領域内に蓄積されている多次元データを管理す
   るステップを有する多次元データ管理方法において、 前記各メッシュのうち、少なくとも前記木構造の末端の
   ノードに対応する末端メッシュに多次元データを登録す
   るステップと、 前記末端メッシュの親メッシュに登録できる多次元デー
   タ数を一定値以下に設定し、前記親メッシュに所属する
   多次元データ数が前記設定値未満の場合に、その末端メ
   ッシュの併合を試行するステップと、 前記末端メッシュをその兄弟メッシュと共に親メッシュ
   に併合するステップの試行に当たり、予め設定された併
   合許容条件にしたがって併合の可否を判定するステップ
   を備えていることを特徴とする多次元データ管理方法。
3. 【請求項３】コンピュータの記憶装置に管理対象となる
   複数の多次元データを多次元空間内に配置し、各多次元
   データの値を多次元空間内における座標としてコンピュ
   ータの記憶装置に登録するステップと、 前記多次元空間を複数のメッシュに階層的に分割し、分
   割された各階層のメッシュを木構造の各ノードに対応さ
   せ、各メッシュと各ノードとの対応関係を記録するステ
   ップと、 分割された各メッシュに多次元データに関する情報を登
   録するステップと、 前記各メッシュに登録された情報に基づいてコンピュー
   タの記憶領域内に蓄積されている多次元データを管理す
   るステップを有する多次元データ管理方法において、 前記各メッシュのうち、少なくとも前記木構造の末端の
   ノードに対応する末端メッシュに多次元データを登録す
   るステップと、 前記末端メッシュに登録できる多次元データ数を一定値
   以下に設定し、末端メッシュに登録する多次元データ数
   が前記設定値を超えた場合に、その末端メッシュの分割
   を試行するステップと、 この末端メッシュの分割ステップの試行に当たり、予め
   設定された分割許容条件にしたがって分割の可否を判定
   するステップと、 前記末端メッシュの親メッシュに登録できる多次元デー
   タ数を一定値以下に設定し、前記親メッシュに所属する
   多次元データ数が前記設定値未満の場合に、その末端メ
   ッシュの併合を試行するステップと、 前記末端メッシュをその兄弟メッシュと共に親メッシュ
   に併合するステップの試行に当たり、予め設定された併
   合許容条件にしたがって併合の可否を判定するステップ
   を備えていることを特徴とする多次元データ管理方法。
4. 【請求項４】前記分割を許容するか否かの判定ステップ
   が、分割後の子メッシュに所属する多次元データ数の和
   と、分割前の親メッシュに所属する多次元データ数とを
   比較して、分割の可否を判定するものである請求項１ま
   たは３記載の多次元データ管理方法。
5. 【請求項５】前記分割を許容するか否かの判定ステップ
   が、親メッシュに所属する多次元データ数と、前記親メ
   ッシュから分割された子メッシュの中の複数の子メッシ
   ュに所属する多次元データ数とを比較して、分割の可否
   を判定するものである請求項１または３記載の多次元デ
   ータ管理方法。
6. 【請求項６】前記併合を許容するか否かの判定ステップ
   が、併合前の各子メッシュに所属する多次元データ数の
   和と、併合後の親メッシュに所属する多次元データ数と
   を比較して、併合の可否を判定するものである請求項２
   または３記載の多次元データ管理方法。
7. 【請求項７】前記併合を許容するか否かの判定ステップ
   が、併合後の親メッシュに所属する多次元データ数と、
   これら子メッシュの中の複数の子メッシュに所属する多
   次元データ数とを比較して、併合の可否を判定するもの
   である請求項２，３または６記載の多次元データ管理方
   法。
8. 【請求項８】前記併合を許容するか否かの判定ステップ
   が、前記末端メッシュに登録できる多次元データ数を一
   定値以下に設定し、親メッシュを同じくする各末端メッ
   シュに登録された多次元データ数がいずれも前記設定値
   未満の場合に、その末端メッシュの併合を実行するもの
   である請求項２，３，６または７記載の多次元データ管
   理方法。
9. 【請求項９】コンピュータの記憶装置に管理対象となる
   複数の多次元データを多次元空間内に配置し、各多次元
   データの値を多次元空間内における座標としてコンピュ
   ータの記憶装置に登録するステップと、 前記多次元空間を複数のメッシュに階層的に分割し、分
   割された各階層のメッシュを木構造の各ノードに対応さ
   せ、各メッシュと各ノードとの対応関係を記録するステ
   ップと、 分割された各メッシュに多次元データに関する情報を登
   録するステップと、 前記各メッシュに登録された情報に基づいてコンピュー
   タの記憶領域内に蓄積されている多次元データを管理す
   るステップを有する多次元データ管理方法において、 末端メッシュの分割時において、前記各メッシュのう
   ち、前記木構造の末端のノードに対応する分割によって
   生じた子メッシュと、前記末端ノードの親ノードに対応
   する分割によって生じた親メッシュいずれかに多次元デ
   ータを登録しなおすステップと、 末端メッシュの分割時において、１つの図形あたりの複
   数メッシュへの重複登録を抑制する条件に従って、前記
   多次元データを分割によって生じた子メッシュと分割に
   よって生じた親メッシュのいずれに登録しなおすかを判
   定するステップを備えていることを特徴とする多次元デ
   ータ管理方法。
10. 【請求項１０】前記多次元データを親メッシュと子メッ
    シュのいずれに登録するかを判定するステップが、前記
    多次元データがその親メッシュを完全に含んでいないこ
    とを重複登録を抑制する条件としている請求項９記載の
    多次元データ管理方法。
11. 【請求項１１】前記多次元データを親メッシュと子メッ
    シュのいずれに登録するかを判定するステップが、前記
    多次元データが重なっている子メッシュ数が予め設定さ
    れた数以下であることを重複登録を抑制する条件として
    いる請求項９または１０記載の多次元データ管理方法。
12. 【請求項１２】前記多次元データを親メッシュと子メッ
    シュのいずれに登録するかを判定するステップが、前記
    多次元データごとに重複メッシュ数の上限が定められて
    おり、子メッシュへの登録を行っても重複登録数が上限
    以下であることを重複登録を抑制する条件としている請
    求項９，１０または１１記載の多次元データ管理方法。
13. 【請求項１３】コンピュータの記憶装置に管理対象とな
    る複数の多次元データを多次元空間内に配置し、各多次
    元データの値を多次元空間内における座標としてコンピ
    ュータの記憶装置に登録するステップと、 前記多次元空間を複数のメッシュに階層的に分割し、分
    割された各階層のメッシュを木構造の各ノードに対応さ
    せ、各メッシュと各ノードとの対応関係を記録するステ
    ップと、 分割された各メッシュに多次元データに関する情報を登
    録するステップと、 前記各メッシュに登録された情報に基づいてコンピュー
    タの記憶領域内に蓄積されている多次元データを管理す
    るステップを有する多次元データ管理方法において、 前記各メッシュのうち、前記木構造の末端のノードに対
    応する末端メッシュと、前記末端ノードの親ノードに対
    応する中間メッシュの少なくとも一方に多次元データを
    登録するステップと、 多次元データの登録時において、登録する多次元データ
    の状態に従って、前記多次元データを末端メッシュと中
    間メッシュのどこに登録するかを判定するステップを備
    えていることを特徴とする多次元データ管理方法。
14. 【請求項１４】前記多次元データを末端メッシュと中間
    メッシュのどこに登録するかを判定するステップが、前
    記多次元データが重なり合っている子メッシュ数に応じ
    て登録するメッシュを選択するものである請求項１３記
    載の多次元データ管理方法。
15. 【請求項１５】前記多次元データを末端メッシュと中間
    メッシュのどこに登録するかを判定するステップが、前
    記多次元データによって登録すべきメッシュの大きさの
    限度が決まっており、このメッシュの大きさの限度に従
    って前記多次元データを登録するメッシュを選択するも
    のである請求項１３または１４記載の多次元データ管理
    方法。
16. 【請求項１６】前記多次元データを末端メッシュと中間
    メッシュのどこに登録するかを判定するステップが、前
    記多次元データごとに重複登録メッシュ数の限度が定め
    られており、この限度に従って前記多次元データを登録
    するメッシュを選択するものである請求項１３，１４ま
    たは１５記載の多次元データ管理方法。
17. 【請求項１７】前記多次元データを末端メッシュと中間
    メッシュのどこに登録するかを判定するステップが、前
    記多次元空間内における前記多次元データの大きさと、
    前記多次元空間内における所定のメッシュの大きさとの
    比較から、前記多次元データを登録するメッシュを選択
    するものである請求項１３，１４，１５または１６記載
    の多次元データ管理方法。
18. 【請求項１８】前記コンピュータの記憶領域内に蓄積さ
    れている多次元データを管理するステップが、前記多次
    元空間内における指定された範囲を対象とし、この指定
    された範囲内に属する多次元データを検索する範囲検索
    ステップを含むことを特徴とする請求項１，２，３，９
    または１３記載の多次元データ管理方法。
19. 【請求項１９】前記コンピュータの記憶領域内に蓄積さ
    れている多次元データを管理するステップが、前記多次
    元空間内における指定された点に最も近い多次元データ
    を検索する最近傍データの検索ステップを含むことを特
    徴とする請求項１，２，３，９または１３記載の多次元
    データ管理方法。
20. 【請求項２０】前記最近傍データの検索ステップが、前
    記指定された点を含む最小のメッシュに多次元データが
    登録されていない場合に、前記最小のメッシュの親メッ
    シュ、最小のメッシュに隣接するメッシュ、親メッシュ
    の親メッシュ、隣接するメッシュの親メッシュ、隣接す
    るメッシュに隣接する他のメッシュのごとく、再帰的に
    最近傍データの候補が１つ決定されるまで検索範囲を拡
    大するステップを含むことを特徴とする請求項１９記載
    の多次元データ管理方法。
21. 【請求項２１】前記多次元空間を複数のメッシュに階層
    的に分割し、分割された各階層のメッシュを木構造の各
    ノードに対応させ、各メッシュと各ノードとの対応関係
    を記録するステップが、２のＮ乗分木による木構造に対
    応して前記多次元空間を階層的に２のＮ乗個に等分割す
    るものである請求項１，２，３，９または１３記載の多
    次元データ管理方法。
22. 【請求項２２】管理対象となる多次元データが、２次元
    の平面もしくは３次元の空間内に配置された図形データ
    である請求項１，２，３，９または１３記載の多次元デ
    ータ管理方法。
23. 【請求項２３】コンピュータの記憶装置に管理対象とな
    る複数の多次元データを多次元空間内に配置し、各多次
    元データの値を多次元空間内における座標としてコンピ
    ュータの記憶装置に登録するステップと、 前記多次元空間を複数のメッシュに階層的に分割し、分
    割された各階層のメッシュを木構造の各ノードに対応さ
    せ、各メッシュと各ノードとの対応関係を記録するステ
    ップと、 分割された各メッシュに多次元データに関する情報を登
    録するステップと、 前記各メッシュに登録された情報に基づいてコンピュー
    タの記憶領域内に蓄積されている多次元データを管理す
    るステップを有する多次元データ管理方法を実行させる
    ためのプログラムを記録した媒体であって、 前記プログラムは、 前記各メッシュのうち、少なくとも前記木構造の末端の
    ノードに対応する末端メッシュに多次元データを登録す
    るステップと、 前記末端メッシュに登録できる多次元データ数を一定値
    以下に設定し、末端メッシュに登録する多次元データ数
    が前記設定値を超えた場合に、その末端メッシュの分割
    を試行するステップと、 この末端メッシュの分割ステップの試行に当たり、予め
    設定された分割許容条件にしたがって分割の可否を判定
    するステップを備えていることを特徴とする多次元デー
    タ管理プログラムを記録した媒体。
24. 【請求項２４】コンピュータの記憶装置に管理対象とな
    る複数の多次元データを多次元空間内に配置し、各多次
    元データの値を多次元空間内における座標としてコンピ
    ュータの記憶装置に登録するステップと、 前記多次元空間を複数のメッシュに階層的に分割し、分
    割された各階層のメッシュを木構造の各ノードに対応さ
    せ、各メッシュと各ノードとの対応関係を記録するステ
    ップと、 分割された各メッシュに多次元データに関する情報を登
    録するステップと、 前記各メッシュに登録された情報に基づいてコンピュー
    タの記憶領域内に蓄積されている多次元データを管理す
    るステップを有する多次元データ管理方法を実行させる
    ためのプログラムを記録した媒体であって、 前記プログラムは、 前記各メッシュのうち、少なくとも前記木構造の末端の
    ノードに対応する末端メッシュに多次元データを登録す
    るステップと、 前記末端メッシュの親メッシュに登録できる多次元デー
    タ数を一定値以下に設定し、前記親メッシュに所属する
    多次元データ数が前記設定値未満の場合に、その末端メ
    ッシュの併合を試行するステップと、 前記末端メッシュをその兄弟メッシュと共に親メッシュ
    に併合するステップの試行に当たり、予め設定された併
    合許容条件にしたがって併合の可否を判定するステップ
    を備えていることを特徴とする多次元データ管理プログ
    ラムを記録した媒体。
25. 【請求項２５】コンピュータの記憶装置に管理対象とな
    る複数の多次元データを多次元空間内に配置し、各多次
    元データの値を多次元空間内における座標としてコンピ
    ュータの記憶装置に登録するステップと、 前記多次元空間を複数のメッシュに階層的に分割し、分
    割された各階層のメッシュを木構造の各ノードに対応さ
    せ、各メッシュと各ノードとの対応関係を記録するステ
    ップと、 分割された各メッシュに多次元データに関する情報を登
    録するステップと、 前記各メッシュに登録された情報に基づいてコンピュー
    タの記憶領域内に蓄積されている多次元データを管理す
    るステップを有する多次元データ管理方法を実行させる
    ためのプログラムを記録した媒体であって、 前記プログラムは、 前記各メッシュのうち、少なくとも前記木構造の末端の
    ノードに対応する末端メッシュに多次元データを登録す
    るステップと、 前記末端メッシュに登録できる多次元データ数を一定値
    以下に設定し、末端メッシュに登録する多次元データ数
    が前記設定値を超えた場合に、その末端メッシュの分割
    を試行するステップと、 この末端メッシュの分割ステップの試行に当たり、予め
    設定された分割許容条件にしたがって分割の可否を判定
    するステップと、 前記末端メッシュの親メッシュに登録できる多次元デー
    タ数を一定値以下に設定し、前記親メッシュに所属する
    多次元データ数が前記設定値未満の場合に、その末端メ
    ッシュの併合を試行するステップと、 前記末端メッシュをその兄弟メッシュと共に親メッシュ
    に併合するステップの試行に当たり、予め設定された併
    合許容条件にしたがって併合の可否を判定するステップ
    を備えていることを特徴とする多次元データ管理プログ
    ラムを記録した媒体。
26. 【請求項２６】コンピュータの記憶装置に管理対象とな
    る複数の多次元データを多次元空間内に配置し、各多次
    元データの値を多次元空間内における座標としてコンピ
    ュータの記憶装置に登録するステップと、 前記多次元空間を複数のメッシュに階層的に分割し、分
    割された各階層のメッシュを木構造の各ノードに対応さ
    せ、各メッシュと各ノードとの対応関係を記録するステ
    ップと、 分割された各メッシュに多次元データに関する情報を登
    録するステップと、 前記各メッシュに登録された情報に基づいてコンピュー
    タの記憶領域内に蓄積されている多次元データを管理す
    るステップを有する多次元データ管理方法を実行させる
    ためのプログラムを記録した媒体であって、 前記プログラムは、 末端メッシュの分割時において、前記各メッシュのう
    ち、前記木構造の末端のノードに対応する分割によって
    生じた子メッシュと、前記末端ノードの親ノードに対応
    する分割によって生じた親メッシュいずれかに多次元デ
    ータを登録しなおすステップと、 末端メッシュの分割時において、１つの図形あたりの複
    数メッシュへの重複登録を抑制する条件に従って、前記
    多次元データを分割によって生じた子メッシュと分割に
    よって生じた親メッシュのいずれに登録しなおすかを判
    定するステップを備えていることを特徴とする多次元デ
    ータ管理プログラムを記録した媒体。
27. 【請求項２７】コンピュータの記憶装置に管理対象とな
    る複数の多次元データを多次元空間内に配置し、各多次
    元データの値を多次元空間内における座標としてコンピ
    ュータの記憶装置に登録するステップと、 前記多次元空間を複数のメッシュに階層的に分割し、分
    割された各階層のメッシュを木構造の各ノードに対応さ
    せ、各メッシュと各ノードとの対応関係を記録するステ
    ップと、 分割された各メッシュに多次元データに関する情報を登
    録するステップと、 前記各メッシュに登録された情報に基づいてコンピュー
    タの記憶領域内に蓄積されている多次元データを管理す
    るステップを有する多次元データ管理方法を実行させる
    ためのプログラムを記録した媒体であって、 前記プログラムは、 前記各メッシュのうち、前記木構造の末端のノードに対
    応する末端メッシュと、前記末端ノードの親ノードに対
    応する中間メッシュの少なくとも一方に多次元データを
    登録するステップと、 多次元データの登録時において、登録する多次元データ
    の状態に従って、前記多次元データを末端メッシュと中
    間メッシュのどこに登録するかを判定するステップを備
    えていることを特徴とする多次元データ管理プログラム
    を記録した媒体。
28. 【請求項２８】管理対象となる複数の多次元データを多
    次元空間内に配置し、各多次元データの値を多次元空間
    内における座標として登録する多次元データ記憶手段
    と、 前記多次元データ記憶手段に多次元データを登録・削除
    する多次元データ登録削除手段と、 前記多次元空間を複数のメッシュに階層的に分割し、分
    割された各階層のメッシュを木構造の各ノードに対応さ
    せ、各メッシュと各ノードとの対応関係を記憶する木構
    造管理手段と、 分割された各メッシュに前記多次元データに関する情報
    を登録するメッシュデータ記憶手段と、 前記各メッシュのうち、少なくとも前記木構造の末端の
    ノードに対応する末端メッシュに、その末端メッシュに
    対応する前記多次元データに関する情報を登録または削
    除するメッシュデータ登録削除手段とを備え、 前記各メッシュデータ記憶手段に登録された情報に基づ
    いて前記多次元データ記憶手段に蓄積されている多次元
    データを管理する多次元データ管理装置において、 前記末端メッシュに登録できる多次元データ数を一定値
    以下に設定し、末端メッシュに登録する多次元データ数
    が前記設定値を超えた場合にその末端メッシュを分割す
    るメッシュ分割手段と、 このメッシュ分割手段による末端メッシュの分割処理に
    当たり、予め設定された分割許容条件にしたがって分割
    の可否を判定する分割判定手段を備えていることを特徴
    とする多次元データ管理装置。
29. 【請求項２９】管理対象となる複数の多次元データを多
    次元空間内に配置し、各多次元データの値を多次元空間
    内における座標として登録する多次元データ記憶手段
    と、 前記多次元データ記憶手段に多次元データを登録・削除
    する多次元データ登録削除手段と、 前記多次元空間を複数のメッシュに階層的に分割し、分
    割された各階層のメッシュを木構造の各ノードに対応さ
    せ、各メッシュと各ノードとの対応関係を記憶する木構
    造管理手段と、 分割された各メッシュに前記多次元データに関する情報
    を登録するメッシュデータ記憶手段と、 前記各メッシュのうち、少なくとも前記木構造の末端の
    ノードに対応する末端メッシュに、その末端メッシュに
    重なる前記多次元データに関する情報を登録または削除
    するメッシュデータ登録削除手段とを備え、 前記各メッシュデータ記憶手段に登録された情報に基づ
    いて前記多次元データ記憶手段に蓄積されている多次元
    データを管理する多次元データ管理装置において、 前記末端メッシュの親メッシュに登録できる多次元デー
    タ数を一定値以下に設定し、前記親メッシュに所属する
    多次元データ数が前記設定値未満の場合に、その末端メ
    ッシュの併合を試行するメッシュ併合手段と、 前記末端メッシュをその兄弟メッシュと共に親メッシュ
    に併合するステップの試行に当たり、予め設定された併
    合許容条件にしたがって併合の可否を判定する併合判定
    手段を備えていることを特徴とする多次元データ管理装
    置。
30. 【請求項３０】管理対象となる複数の多次元データを多
    次元空間内に配置し、各多次元データの値を多次元空間
    内における座標として登録する多次元データ記憶手段
    と、 前記多次元データ記憶手段に多次元データを登録・削除
    する多次元データ登録削除手段と、 前記多次元空間を複数のメッシュに階層的に分割し、分
    割された各階層のメッシュを木構造の各ノードに対応さ
    せ、各メッシュと各ノードとの対応関係を記憶する木構
    造管理手段と、 分割された各メッシュに前記多次元データに関する情報
    を登録するメッシュデータ記憶手段と、 前記各メッシュのうち、少なくとも前記木構造の末端の
    ノードに対応する末端メッシュに、その末端メッシュに
    重なる前記多次元データに関する情報を登録または削除
    するメッシュデータ登録削除手段とを備え、 前記各メッシュデータ記憶手段に登録された情報に基づ
    いて前記多次元データ記憶手段に蓄積されている多次元
    データを管理する多次元データ管理装置において、 前記末端メッシュに登録できる多次元データ数を一定値
    以下に設定し、末端メッシュに登録する多次元データ数
    が前記設定値を超えた場合にその末端メッシュを分割す
    るメッシュ分割手段と、 このメッシュ分割手段による末端メッシュの分割処理に
    当たり、予め設定された分割許容条件にしたがって分割
    の可否を判定する分割判定手段と、 前記末端メッシュの親メッシュに登録できる多次元デー
    タ数を一定値以下に設定し、前記親メッシュに所属する
    多次元データ数が前記設定値未満の場合に、その末端メ
    ッシュの併合を試行するメッシュ併合手段と、 前記末端メッシュをその兄弟メッシュと共に親メッシュ
    に併合するステップの試行に当たり、予め設定された併
    合許容条件にしたがって併合の可否を判定する併合判定
    手段を備えていることを特徴とする多次元データ管理装
    置。
31. 【請求項３１】前記分割判定手段が、分割後の子メッシ
    ュに所属する多次元データ数の和と、分割前の親メッシ
    ュに所属する多次元データ数とを比較して、分割の可否
    を判定するものである請求項２８または３０記載の多次
    元データ管理装置。
32. 【請求項３２】前記分割判定手段が、親メッシュに所属
    する多次元データ数と、前記親メッシュから分割された
    子メッシュの中の複数の子メッシュに所属する多次元デ
    ータ数とを比較して、分割の可否を判定するものである
    請求項２８または３０記載の多次元データ管理装置。
33. 【請求項３３】前記併合判定手段が、併合前の各子メッ
    シュに所属する多次元データ数の和と、併合後の親メッ
    シュに所属する多次元データ数とを比較して、併合の可
    否を判定するものである請求項２９または３０記載の多
    次元データ管理装置。
34. 【請求項３４】前記併合判定手段が、併合後の親メッシ
    ュに所属する多次元データ数と、これら子メッシュの中
    の複数の子メッシュに所属する多次元データ数とを比較
    して、併合の可否を判定するものである請求項２９，３
    ０または３３記載の多次元データ管理装置。
35. 【請求項３５】前記併合判定手段が、前記末端メッシュ
    に登録できる多次元データ数を一定値以下に設定し、親
    メッシュを同じくする各末端メッシュに登録された多次
    元データ数がいずれも前記設定値未満の場合に、その末
    端メッシュの併合を実行するものである請求項２９，３
    ０または３３記載の多次元データ管理装置。
36. 【請求項３６】管理対象となる複数の多次元データを多
    次元空間内に配置し、各多次元データの値を多次元空間
    内における座標として登録する多次元データ記憶手段
    と、 前記多次元データ記憶手段に多次元データを登録・削除
    する多次元データ登録削除手段と、 前記多次元空間を複数のメッシュに階層的に分割し、分
    割された各階層のメッシュを木構造の各ノードに対応さ
    せ、各メッシュと各ノードとの対応関係を記憶する木構
    造管理手段と、 分割された各メッシュに前記多次元データに関する情報
    を登録するメッシュデータ記憶手段と、 前記各メッシュのうち、少なくとも前記木構造の末端の
    ノードに対応する末端メッシュに、その末端メッシュに
    重なる前記多次元データに関する情報を登録または削除
    するメッシュデータ登録削除手段とを備え、 前記各メッシュデータ記憶手段に登録された情報に基づ
    いて前記多次元データ記憶手段に蓄積されている多次元
    データを管理する多次元データ管理装置において、 前記メッシュデータ登録削除手段およびメッシュ分割手
    段に関連して、 末端メッシュの分割時において、前記各メッシュのう
    ち、前記木構造の末端のノードに対応する分割によって
    生じた子メッシュと、前記末端ノードの親ノードに対応
    する分割によって生じた親メッシュいずれかに多次元デ
    ータを登録しなおすメッシュデータ再登録手段と、 末端メッシュの分割時において、１つの図形あたりの複
    数メッシュへの重複登録を抑制する条件に従って、前記
    多次元データを分割によって生じた子メッシュと分割に
    よって生じた親メッシュのいずれに登録しなおすかを判
    定する再登録メッシュ判定手段が設けられいることを特
    徴とする多次元データ管理装置。
37. 【請求項３７】前記再登録メッシュ判定手段が、前記多
    次元データがその親メッシュを完全に含んでいないこと
    を重複登録を抑制する条件としている請求項３６記載の
    多次元データ管理装置。
38. 【請求項３８】前記再登録メッシュ判定手段が、前記多
    次元データが重なっている子メッシュ数が予め設定され
    た数以下であることを重複登録を抑制する条件としてい
    る請求項３６または３７記載の多次元データ管理装置。
39. 【請求項３９】前記再登録メッシュ判定手段が、前記多
    次元データごとに重複メッシュ数の上限が定められてお
    り、子メッシュへの登録を行っても重複登録数が上限以
    下であることを重複登録を抑制する条件としている請求
    項３６，３７または３８記載の多次元データ管理装置。
40. 【請求項４０】管理対象となる複数の多次元データを多
    次元空間内に配置し、各多次元データの値を多次元空間
    内における座標として登録する多次元データ記憶手段
    と、 前記多次元データ記憶手段に多次元データを登録・削除
    する多次元データ登録削除手段と、 前記多次元空間を複数のメッシュに階層的に分割し、分
    割された各階層のメッシュを木構造の各ノードに対応さ
    せ、各メッシュと各ノードとの対応関係を記憶する木構
    造管理手段と、 分割された各メッシュに前記多次元データに関する情報
    を登録するメッシュデータ記憶手段と、 前記各メッシュのうち、少なくとも前記木構造の末端の
    ノードに対応する末端メッシュに、その末端メッシュに
    重なる前記多次元データに関する情報を登録または削除
    するメッシュデータ登録削除手段とを備え、 前記各メッシュデータ記憶手段に登録された情報に基づ
    いて前記多次元データ記憶手段に蓄積されている多次元
    データを管理する多次元データ管理装置において、 前記メッシュデータ登録削除手段およびメッシュ分割手
    段に関連して、 前記各メッシュのうち、前記木構造の末端のノードに対
    応する末端メッシュと、前記末端ノードの親ノードに対
    応する中間メッシュの少なくとも一方に多次元データを
    登録するデータ登録手段と、 多次元データの登録時において、登録する多次元データ
    の状態に従って、前記多次元データを末端メッシュと中
    間メッシュのどこに登録するかを判定する登録位置判定
    手段が設けられていることを特徴とする多次元データ管
    理装置。
41. 【請求項４１】登録位置判定手段が、前記多次元データ
    が重なり合っている子メッシュ数に応じて登録するメッ
    シュを選択するものである請求項４０記載の多次元デー
    タ管理装置。
42. 【請求項４２】前記登録位置判定手段が、前記多次元デ
    ータによって登録すべきメッシュの大きさの限度が決ま
    っており、このメッシュの大きさの限度に従って前記多
    次元データを登録するメッシュを選択するものである請
    求項４０または４１記載の多次元データ管理装置。
43. 【請求項４３】前記登録位置判定手段が、前記多次元デ
    ータごとに重複登録メッシュ数の限度が定められてお
    り、この限度に従って前記多次元データを登録するメッ
    シュを選択するものである請求項４０，４１または４２
    記載の多次元データ管理装置。
44. 【請求項４４】前記登録位置判定手段が、前記多次元空
    間内における前記多次元データの大きさと、前記多次元
    空間内における所定のメッシュの大きさとの比較から、
    前記多次元データを登録するメッシュを選択するもので
    ある請求項４０，４１，４２または４３記載の多次元デ
    ータ管理装置。
45. 【請求項４５】前記コンピュータの記憶領域内に蓄積さ
    れている多次元データを管理する装置が、前記多次元空
    間内における指定された範囲を対象とし、この指定され
    た範囲内に属する多次元データを検索する範囲検索手段
    を含むことを特徴とする請求項２８，２９，３０，３６
    または４０記載の多次元データ管理装置。
46. 【請求項４６】前記コンピュータの記憶領域内に蓄積さ
    れている多次元データを管理する装置が、前記多次元空
    間内における指定された点に最も近い多次元データを検
    索する最近傍データの検索手段を含むことを特徴とする
    請求項２８，２９，３０，３６，４０または４５記載の
    多次元データ管理装置。
47. 【請求項４７】前記最近傍データの検索手段が、前記指
    定された点を含む最小のメッシュに多次元データが登録
    されていない場合に、前記最小のメッシュの親メッシ
    ュ、最小のメッシュに隣接するメッシュ、親メッシュの
    親メッシュ、隣接するメッシュの親メッシュ、隣接する
    メッシュに隣接する他のメッシュのごとく、再帰的に最
    近傍データの候補が１つ決定されるまで検索範囲を拡大
    することを特徴とする請求項４６記載の多次元データ管
    理装置。
48. 【請求項４８】前記木構造管理手段が、２のＮ乗分木に
    よる木構造に対応して前記多次元空間を階層的に２のＮ
    乗個に等分割するものである請求項２８，２９，３０，
    ３６または４０記載の多次元データ管理装置。
49. 【請求項４９】管理対象となる多次元データが、２次元
    の平面もしくは３次元の空間内に配置された図形データ
    である請求項２８，２９，３０，３６または４０記載の
    多次元データ管理装置。