(57)【要約】【課題】  ４分木データ構造中の図形データの一つを一意のキー値から効率的に検索可能な図形検索システムを提供する。【解決手段】  ４分木データ構造のツリーに図形データを追加する際に、図形データの存在位置による検索エリア番号とエリア内で追加した図形データの連続番号値とから図形データを一意に表す図形キーを生成しつつ図形データを追加する。図形キー決定手段５１は入力装置３から入力された情報に基づき、記憶装置２の図形キー格納部２２等から図形キーを抽出する。図形検索処理手段５２は図形キー決定手段５１で決定された図形キーから図形データの格納されている４分木データ構造のノードを算出し、決定された４分木データ構造のノードから図形データを抽出する。図形データ処理手段５７は図形データ抽出手段５６で抽出された図形データからの情報に任意の処理を行い、出力装置４に出力する。【選択図】      図２                                                  
2005115708.tif 000002
【特許請求の範囲】
【請求項１】
図形データをＮ分木データ構造にて格納する図形検索システムであって、前記図形データの存在位置による検索エリア番号とそのエリア内で一意なシーケンス番号とから生成されかつ前記図形データを一意に表す図形キーを格納する格納手段と、前記格納手段の格納内容を基に前記図形キーから算出された前記検索エリア番号によって表される２次元領域のみについて前記Ｎ分木データ構造の対応するノードを探索する図形検索処理手段とを有することを特徴とする図形検索システム。
【請求項２】
前記図形検索処理手段は、決定された図形キーから前記検索エリア番号を算出するエリア番号抽出手段と、前記エリア番号抽出手段で算出された前記検索エリア番号を基に前記図形データが存在する検索エリアを算出するエリア算出手段と、前記Ｎ分木データ構造のノードに対応したエリアのうちの前記検索エリアが交差するノードを再帰的にルートノードから探索しかつ交差ノードに格納された図形データに付与された図形キーと検索する図形キーとの間で完全一致する図形キーを２分探索手法によって探索するノード探索手段と、前記図形データが探索された時にその図形データを取得する図形データ抽出手段とを含むことを特徴とする請求項１記載の図形検索システム。
【請求項３】
前記ノード探索手段は、前記交差ノードに格納された図形データに付与された図形キーと前記検索する図形キーとの間で完全一致する図形キーを２分探索手法によって探索することを特徴とする請求項２記載の図形検索システム。
【請求項４】
前記図形データを探索する際に前記図形キーを決定する図形キー決定手段を含むことを特徴とする請求項１から請求項３のいずれか記載の図形検索システム。
【請求項５】
前記図形データを前記Ｎ分木データ構造に追加する際に前記図形データの存在位置から全体領域を一定に分割したエリア番号の一つを算出する検索エリア番号算出手段と、前記図形データの存在位置を基に前記図形データを覆うような最少の矩形領域を算出する外包矩形算出手段と、前記Ｎ分木データ構造で構築された記憶装置に図形データを格納するノードを決める追加ノード探索手段と、前記図形データを前記ノードへ格納する際に前記図形キーを生成しかつ前記図形キーを参照して順次ソートしながら前記図形データとともに前記ノードに格納する図形のノード追加手段とを含むことを特徴とする請求項１から請求項４のいずれか記載の図形検索システム。
【請求項６】
前記Ｎ分木データ構造は、２次元の図形データを格納する４分木データ構造であることを特徴とする請求項１から請求項５のいずれか記載の図形検索システム。
【請求項７】
図形データをＮ分木データ構造にて格納する図形検索システムの図形検索方法であって、前記図形データを検索するデータ処理装置側に、前記図形データの存在位置による検索エリア番号とそのエリア内で一意なシーケンス番号とから生成されかつ前記図形データを一意に表す図形キーを格納する格納手段の格納内容を基に前記図形キーから算出された前記検索エリア番号によって表される２次元領域のみについて前記Ｎ分木データ構造の対応するノードを探索するステップを有することを特徴とする図形検索方法。
【請求項８】
前記ノードを探索するステップは、決定された図形キーから前記検索エリア番号を算出するステップと、その算出された前記検索エリア番号を基に前記図形データが存在する検索エリアを算出するステップと、前記Ｎ分木データ構造のノードに対応したエリアのうちの前記検索エリアが交差するノードを再帰的にルートノードから探索しかつ交差ノードに格納された図形データに付与された図形キーと検索する図形キーとの間で完全一致する図形キーを探索するステップと、前記図形データが探索された時にその図形データを取得するステップとを含むことを特徴とする請求項７記載の図形検索方法。
【請求項９】
前記図形キーを探索するステップは、前記交差ノードに格納された図形データに付与された図形キーと前記検索する図形キーとの間で完全一致する図形キーを２分探索手法によって探索することを特徴とする請求項８記載の図形検索方法。
【請求項１０】
前記データ処理装置側に、前記図形データを探索する際に前記図形キーを決定するステップを含むことを特徴とする請求項７から請求項９のいずれか記載の図形検索方法。
【請求項１１】
前記データ処理装置側に、前記図形データを前記Ｎ分木データ構造に追加する際に前記図形データの存在位置から全体領域を一定に分割したエリア番号の一つを算出するステップと、前記図形データの存在位置を基に前記図形データを覆うような最少の矩形領域を算出するステップと、前記Ｎ分木データ構造で構築された記憶装置に図形データを格納するノードを決めるステップと、前記図形データを前記ノードへ格納する際に前記図形キーを生成しかつ前記図形キーを参照して順次ソートしながら前記図形データとともに前記ノードに格納するステップとを含むことを特徴とする請求項７から請求項１０のいずれか記載の図形検索方法。
【請求項１２】
前記Ｎ分木データ構造は、２次元の図形データを格納する４分木データ構造であることを特徴とする請求項７から請求項１１のいずれか記載の図形検索方法。
【請求項１３】
図形データをＮ分木データ構造にて格納する図形検索システムの図形検索方法のプログラムであって、コンピュータに、前記図形データの存在位置による検索エリア番号とそのエリア内で一意なシーケンス番号とから生成されかつ前記図形データを一意に表す図形キーを格納する格納手段の格納内容を基に前記図形キーから算出された前記検索エリア番号によって表される２次元領域のみについて前記Ｎ分木データ構造の対応するノードを探索する処理を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は図形検索システム及びそれに用いる図形検索方法並びにそのプログラムに関し、特にデータベース等に記録された図形データの検索方法に関する。
【背景技術】
【０００２】
従来、この種の図形検索を行う図形検索システムにおいては、４分木データ構造中の図形データを検索する際に、点やエリア等の位置情報をキーにした範囲検索の方法が提案されている（例えば、特許文献１参照）。
【０００３】
上記の図形検索システムでは、図形データの外部装置への出力等に際して、予め図形データを表示しうる範囲を計算し、この範囲に存在する図形を検索する場合、図形データを格納する図形データ格納手段に、矩形領域を最深層に向かって順次分割した階層構造のメッシュ領域に対応した４分木階層インデックスの格納手段を用いることによって、範囲内に存在しうる図形データの検索を高速に行っている。
【０００４】
【特許文献１】特開２００１−１４３３８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上述した従来の図形検索システムでは、単に一意な番号を図形データのキー値として付与した場合、４分木データ構造中のいずれのノードに図形データが格納されているかを判別することができず、検索を高速に行うことができない。
【０００６】
そこで、本発明の目的は上記の問題点を解消し、４分木データ構造中の図形データの一つを一意のキー値から効率的に検索することができる図形検索システム及びそれに用いる図形検索方法並びにそのプログラムを提供することにある。
【課題を解決するための手段】
【０００７】
本発明による図形検索システムは、図形データをＮ分木データ構造にて格納する図形検索システムであって、前記図形データの存在位置による検索エリア番号とそのエリア内で一意なシーケンス番号とから生成されかつ前記図形データを一意に表す図形キーを格納する格納手段と、前記格納手段の格納内容を基に前記図形キーから算出された前記検索エリア番号によって表される２次元領域のみについて前記Ｎ分木データ構造の対応するノードを探索する図形検索処理手段とを備えている。
【０００８】
本発明による図形検索方法は、図形データをＮ分木データ構造にて格納する図形検索システムの図形検索方法であって、前記図形データを検索するデータ処理装置側に、前記図形データの存在位置による検索エリア番号とそのエリア内で一意なシーケンス番号とから生成されかつ前記図形データを一意に表す図形キーを格納する格納手段の格納内容を基に前記図形キーから算出された前記検索エリア番号によって表される２次元領域のみについて前記Ｎ分木データ構造の対応するノードを探索するステップを備えている。
【０００９】
本発明による図形検索方法のプログラムは、図形データをＮ分木データ構造にて格納する図形検索システムの図形検索方法のプログラムであって、コンピュータに、前記図形データの存在位置による検索エリア番号とそのエリア内で一意なシーケンス番号とから生成されかつ前記図形データを一意に表す図形キーを格納する格納手段の格納内容を基に前記図形キーから算出された前記検索エリア番号によって表される２次元領域のみについて前記Ｎ分木データ構造の対応するノードを探索する処理を実行させている。
【００１０】
すなわち、本発明の図形検索システムは、検索エリア番号算出手段と、追加４分木ノード探索手段とを備え、４分木データ構造に図形データを追加する際に、図形データの存在位置による検索エリア番号と当該エリア内の一意の番号とから図形データを一意に表す図形キーを生成し、その図形キーを付与して図形データを追加する。
【００１１】
このように、本発明の図形検索システムでは、追加された図形キーから４分木中の１つの図形データを探索する場合、図形キーから図形データの存在位置を表す検索エリア番号を算出し、検索エリア番号によって表される２次元領域のみについて４分木データ構造の対応するノードを探索する。
【００１２】
これによって、本発明の図形検索システムでは、探索データ範囲を抑えることが可能となり、４分木データ構造中のデータから唯一の図形データを抽出する操作を高速に行うことが可能となる。
【００１３】
よって、本発明の図形検索システムでは、４分木データ構造に格納された図形データに一意なキーを付与し、このキーを用いて４分木データ構造中から一つの図形データを効果的に検索することが可能となる。また、本発明の図形検索システムでは、４分木データ構造に格納された図形データは範囲検索に有効であることのメリットを損なわずに、４分木データ構造中から一つの図形データを検索することが可能となる。
【発明の効果】
【００１４】
本発明は、以下に述べるような構成及び動作とすることで、４分木データ構造中の図形データの一つを一意のキー値から効率的に検索することができるという効果が得られる。
【発明を実施するための最良の形態】
【００１５】
次に、本発明の実施の形態について図面を参照して説明する。図１は本発明の実施の形態による図形追加処理を行うデータ処理装置の構成を示すブロック図である。図１において、データ処理装置１はプログラム制御により動作し、情報を記憶する記憶装置２と、キーボード等の入力装置３と、ディスプレイ装置や印刷装置等の出力装置４とに接続されている。尚、記憶装置２は４分木データ記憶部２１と、図形キー格納部［ＤＢＭＳ（Ｄａｔａｂａｓｅ  Ｍａｎａｇｅｍｅｎｔ  Ｓｙｓｔｅｍ）等］２２とから構成されている。
【００１６】
データ処理装置１は図形追加処理手段１１及び記録媒体１６とを内蔵し、図形追加処理手段１１は検索エリア番号算出手段１２と、外包矩形算出手段１３と、追加４分木ノード探索手段１４と、図形のノード追加手段１５とから構成されている。
【００１７】
検索エリア番号算出手段１２は入力装置３によって入力された図形データが４分木データ構造の表現する全体領域のいずれのエリアに存在するかを算出することで、エリア番号を得るとともに、同時にエリア番号とエリア内の一意の番号（エリア番号内ＩＤ）とから図形データを一意に識別する図形キーを生成する。
【００１８】
外包矩形算出手段１３は追加する図形データを外包する矩形領域を算出する。追加４分木ノード探索手段１４は図形データの外包矩形の位置及びサイズから、追加すべき４分木データ構造のノードの一つを決定する。
【００１９】
図形のノード追加手段１５は追加４分木ノード探索手段１４によって決定されたノードに図形データを追加する。この時、図形データはその図形データを一意に識別する図形キーの順（昇順または降順）にソートしつつ格納する。記録媒体１６はデータ処理装置１が実行するプログラム（コンピュータで実行可能なプログラム）を格納している。
【００２０】
図２は本発明の実施の形態による図形検索処理を行うデータ処理装置の構成を示すブロック図である。図２において、データ処理装置５はプログラム制御により動作し、情報を記憶する記憶装置２と、キーボード等の入力装置３と、ディスプレイ装置や印刷装置等の出力装置４とに接続されている。
【００２１】
データ処理装置５は図形キー決定手段５１と、図形検索処理手段５２と、図形データ処理手段５７と、記録媒体５８とを内蔵し、図形検索処理手段５２はエリア番号抽出手段５３と、エリア算出手段５４と、検索４分木ノード検索手段５５と、図形データ抽出手段５６とから構成されている。
【００２２】
図形キー決定手段５１は入力装置３によって入力された情報に基づき、記憶装置２の図形キー格納部２２等から図形キーを抽出する。図形検索処理手段５２は図形キー決定手段５１によって決定された図形キーから図形データの格納されている４分木データ構造のノードを算出し、決定された４分木データ構造のノードから図形データを抽出する。
【００２３】
図形データ処理手段５７は図形データ抽出手段５６によって抽出された図形データからの情報に任意の処理を行い、出力装置４に出力する。記録媒体５８はデータ処理装置５が実行するプログラム（コンピュータで実行可能なプログラム）を格納している。
【００２４】
図形検索処理手段５２において、エリア番号抽出手段５３は図形キー決定手段５１によって決定された図形キーからエリア番号を抽出する。エリア算出手段５４はエリア番号から、図形データの存在しうる検索エリアを算出する。
【００２５】
検索４分木ノード探索手段５５は４分木データ構造のノードのうち検索エリアに内包または交差するもののみを選択するようにツリーをたどり、これらのノード内に該当図形データが存在しないかどうかを判定する。尚、検索４分木ノード探索手段５５では探索されたノードから図形キーに一致する図形データを探索し、ソートされたデータを探索するのに有効な２分探索等のアルゴリズムを用いている。図形データが探索された場合には、図形データ抽出手段５６によって４分木データ構造から図形データを抽出する。
【００２６】
これによって、本発明の実施の形態では、図形データの存在エリアを図形キーに格納し、図形データを検索する際により少ない４分木ノードの探索に抑えることができるので、４分木データ構造中の図形データの一つを一意のキー値から効率的に検索することができる。
【実施例１】
【００２７】
次に、本発明の一実施例について図面を参照して説明する。本発明の一実施例による図形追加処理及び図形検索処理を行うデータ処理装置は、図１及び図２に示す本発明の実施の形態によるデータ処理装置１，５と同様の構成となっているので、その構成及び動作について説明は省略する。
【００２８】
図３は本発明の一実施例によるエリア番号を示す図である。図３において、本発明の一実施例によるエリア番号は、４分木データ構造のルートに対応した全体領域を４分木データ構造を最大分割した矩形領域のサイズＳｘ，Ｓｙで均等に分割し、原点Ｏ右上を（０，０）としてＸ軸の正方向及び負方向とＹ軸の正方向及び負方向とにそれぞれ番号付けしたものである［例えば、エリア番号（３，６）］。
【００２９】
図４は本発明の一実施例による追加処理動作の流れを示すフローチャートであり、図５及び図６は本発明の一実施例による図形追加時の４分木ノード探索動作の流れを示すフローチャートである。
【００３０】
図７は本発明の一実施例によるエリア番号算出処理を示す図であり、図８は本発明の一実施例による図形追加処理の結果を示す図であり、図９は本発明の一実施例による図形キー算出処理の結果を示す図である。これら図１と図４〜図９とを参照して図形を４分木に追加する場合の本発明の一実施例の動作について説明する。尚、図４〜図６に示す処理はデータ処理装置１が記録媒体１６のプログラムを実行することで実現される。
【００３１】
データ処理装置１の図形追加処理手段１１は図形データの４分木データ構造に対して図形データの追加処理が起動されると（図４ステップＳ１）、最初に、検索エリア番号算出手段１２にて追加する図形データについて、図形データの存在するエリア番号を算出する（図４ステップＳ２）。この時、図７に示すように、図形Ｚが存在する場合には、その図形データの１頂点の存在するエリア番号を算出する。
【００３２】
次に、図形追加処理手段１１は外包矩形算出手段１３にて、図８に示すように、追加する図形データについて外包矩形Ｐを算出し（図４ステップＳ３）、外包矩形Ｐを内包する最も末端の４分木データ構造のノードＮを算出する（図４ステップＳ４）。
【００３３】
続いて、図形追加処理手段１１は追加４分木ノード探索手段１４にて、図９に示すように、エリア番号とエリア番号内ＩＤとから図形キーを算出し（図４ステップＳ５）、見つかったノードＮに図形を複数追加する（図４ステップＳ６）。図８に示す場合には子ノードの一つに追加される。この時、ノード内に存在する図形データは、図形キーの順（昇順または降順）にソートされていることとする。
【００３４】
図形データが追加されると、図形追加処理手段１１は図形のノード追加手段１５にて図形キーを図形キー格納部（ＤＢＭＳ等）２２に登録し（図４ステップＳ７）、図形データの追加処理を終了する。
【００３５】
上述したステップＳ４で行う処理は、４分木データ構造を再帰的に探索する関数（ＩＮＰＵＴ；ルートノードの矩形，Ｐ，０、ＯＵＴＰＵＴ；ノードＮ  ｏｒ  ＮＵＬＬ）よりなり、その処理の流れを図５及び図６に示す。
【００３６】
図形追加処理手段１１は矩形領域Ｐを内包する最も末端のノードを探索する関数として、初期の入力値にルートノードの矩形ｎｐ、矩形領域Ｐ、探索階層ｎＤｅｐｔｈを入力する（図５ステップＳ１１）。探索階層は初期状態で「０」とする。
【００３７】
最初に、図形追加処理手段１１はルートノードの矩形ｎｐの内部に矩形領域Ｐが存在するかどうかを決定する（図５ステップＳ１２）。この時、図形追加処理手段１１は矩形領域Ｐがルートノードの矩形ｎｐの外部であれば、末端ノードなしとして戻り値ｎｕｌｌを返す（図５ステップＳ１３）。
【００３８】
また、図形追加処理手段１１は矩形領域Ｐがルートノードの矩形ｎｐの内部であれば、探索階層ｎＤｅｐｔｈが予め決定された最大階層数より小さいかどうかを決定し（図５ステップＳ１４）、最大階層よりも大きい場合、ルートノードの矩形ｎｐを戻り値とし（図５ステップＳ１５）、末端ノードとする。
【００３９】
図形追加処理手段１１は最大階層よりも小さい場合、ルートノードの矩形ｎｐを４等分割し、４つの子ノードｎｐ１〜ｎｐ４を生成し（図５ステップＳ１６）、矩形領域Ｐが子ノードｎｐ１〜ｎｐ４のいずれに含まれるかを順次判定する（図５ステップＳ１７，Ｓ２０、図６ステップＳ２３，Ｓ２６）。
【００４０】
図形追加処理手段１１は左上ノードの子ノードｎｐ１に矩形領域Ｐが内包される場合（図５ステップＳ１７）、引数（ＩＮＰＵＴ）をｎｐ１，Ｐ，ｎＤｅｐｔｈ＋１として自関数の再帰呼び出しを行い（図５ステップＳ１８）、再帰呼び出し時の関数の戻り値を戻り値ｎ１にし（図５ステップＳ１９）、関数を終了する。
【００４１】
図形追加処理手段１１は右上ノードの子ノードｎｐ２に矩形領域Ｐが内包される場合（図５ステップＳ２０）、引数（ＩＮＰＵＴ）をｎｐ２，Ｐ，ｎＤｅｐｔｈ＋１として自関数の再帰呼び出しを行い（図５ステップＳ２１）、再帰呼び出し時の関数の戻り値を戻り値ｎ２にし（図５ステップＳ２２）、関数を終了する。
【００４２】
図形追加処理手段１１は左下ノードの子ノードｎｐ３に矩形領域Ｐが内包される場合（図６ステップＳ２３）、引数（ＩＮＰＵＴ）をｎｐ３，Ｐ，ｎＤｅｐｔｈ＋１として自関数の再帰呼び出しを行い（図６ステップＳ２４）、再帰呼び出し時の関数の戻り値を戻り値ｎ３にし（図６ステップＳ２５）、関数を終了する。
【００４３】
図形追加処理手段１１は右下ノードの子ノードｎｐ４に矩形領域Ｐが内包される場合（図６ステップＳ２６）、引数（ＩＮＰＵＴ）をｎｐ４，Ｐ，ｎＤｅｐｔｈ＋１として自関数の再帰呼び出しを行い（図６ステップＳ２８）、再帰呼び出し時の関数の戻り値を戻り値ｎ４にし（図６ステップＳ２９）、関数を終了する。図形追加処理手段１１は右下ノードの子ノードｎｐ４に矩形領域Ｐが内包されない場合（図６ステップＳ２６）、戻り値ｎｐを返し（図６ステップＳ２７）、関数を終了する。
【００４４】
図１０は本発明の一実施例による検索処理動作の流れを示すフローチャートであり、図１１及び図１２は本発明の一実施例による図形検索時の４分木ノード探索動作の流れを示すフローチャートである。図１３は本発明の一実施例によるエリア番号からの検索エリア算出動作を示す図であり、図１４は本発明の一実施例による図形検索動作を示す図である。これら図２と図１０〜図１４とを参照して本発明の一実施例による図形キーを用いて４分木データ構造から一意の図形データを検索する方法について説明する。
【００４５】
データ処理装置５は図形キー格納部（ＤＢＭＳ等）２２から図形キーを抽出し、図形キーから図形データを抽出する図形検索が起動されると（図１０ステップＳ３１）、データベース（ＤＢ）［図形キー格納部（ＤＢＭＳ等）２２］から図形キーを抽出し（図１０ステップＳ３２）、検索する図形キーが決定されると、この図形キーのエリア番号を用いて、エリアＡを算出する（図１０ステップＳ３３）。
【００４６】
図１３に示す場合には、最大分割矩形のサイズ（Ｓｘ，Ｓｙ）と検索エリア番号（６，４）とから、それに該当する検索エリアＡを算出する。検索エリアＡの左下点の座標値は（Ｓｘ×６，Ｓｙ×４）で算出され、右上点の座標値は（Ｓｘ×６＋Ｓｘ，Ｓｙ×４＋Ｓｙ）で算出される。検索エリアＡはこれらの座標値によって構成される矩形エリアに決定される。
【００４７】
データ処理装置５は検索エリアＡを算出すると、この検索エリアＡと交差する４分木ノードを順に探索し、図形キーを探索する（図１０ステップＳ３４）。データ処理装置５は図形キーから図形データへのポインタを算出すると、図形データから図形位置や形状等を算出する（図１０ステップＳ３５）。地図を表示する場合には、地図表示をスクロールさせる等の操作を行い（図１０ステップＳ３６）、処理を終了する。図１４に示す場合には図形Ｚが探索される。
【００４８】
上述したステップＳ３４で行う処理は、４分木データ構造を再帰的に探索する関数［ＩＮＰＵＴ；ルート矩形，エリア（Ａ），０，図形キー、ＯＵＴＰＵＴ；図形へのポインタ）よりなり、その処理の流れを図１１及び図１２に示す。
【００４９】
図形検索処理手段５１は図形キーによって図形データを探索する関数として、初期入力値にルートノードの矩形ｎｐ、探索エリアＡ、探索階層ｎＤｅｐｔｈ，図形キーｚｋを入力する（図１１ステップＳ４１）。探索階層は初期状態で「０」とする。
【００５０】
最初に、図形検索処理手段５１はルートノードの矩形ｎｐの内部に探索エリアＡが存在するかどうかを決定する（図１１ステップＳ４２）。この時、図形検索処理手段５１は探索エリアＡがルートノードの矩形ｎｐの外部であれば、このノードにはデータが存在しないとして、戻り値ｎｕｌｌを返す（図１２ステップＳ６１）。
【００５１】
図形検索処理手段５１は探索エリアＡがルートノードの矩形ｎｐの内部であれば、ノードに存在する図形データから図形キーｚｋに該当する図形データを予めソートされたデータから２分探索等のアルゴリズムを用いて探索する（図１１ステップＳ４３）。この時、図形検索処理手段５１は図形キーに該当する図形データｚｄが存在すれば（図１１ステップＳ４４）、その図形データへのポインタを戻り値ｚｄとして（図１１ステップＳ４５）、関数を終了する。
【００５２】
図形検索処理手段５１は図形キーに該当する図形データｚｄが存在しなければ（図１１ステップＳ４４）、探索階層ｎＤｅｐｔｈが予め決定された最大階層よりも小さいかどうかを判別し（図１１ステップＳ４６）、探索階層ｎＤｅｐｔｈが最大階層より大きい場合、関数を終了する。
【００５３】
図形検索処理手段５１は探索階層ｎＤｅｐｔｈが最大階層より小さい場合、さらに子ノードを探索するため、子ノードを形成する４つの矩形領域ｎｐ１〜ｎｐ４を生成し（図１１ステップＳ４７）、順に探索エリアＡが内包または交差する子ノードを図形データが見つかるまで探索する（図１１ステップＳ４８、図１２ステップＳ５２，Ｓ５６，Ｓ６０）。
【００５４】
図形検索処理手段５１は、例えば左上の子ノードｎｐ１に探索エリアＡが内包されれば（図１１ステップＳ４８）、さらに引数（ＩＮＰＵＴ）をｎｐ１，Ａ，ｎＤｅｐｔｈ，ｚｋとして自関数の再帰呼び出しを行い（図１１ステップＳ４９）、戻り値がｎｕｌｌでないかを判定する（図１１ステップＳ５０）。図形検索処理手段５１は戻り値がｎｕｌｌでない場合、図形データが探索されたとして、戻り値にその値ｚｄ１を設定し（図１１ステップＳ５１）、関数を終了する。
【００５５】
図形検索処理手段５１は戻り値がｎｕｌｌであり、図形データが探索されなかった場合、次の右上の子ノードｎｐ２に探索エリアＡが内包されれば（図１２ステップＳ５２）、さらに引数（ＩＮＰＵＴ）をｎｐ２，Ａ，ｎＤｅｐｔｈ，ｚｋとして自関数の再帰呼び出しを行い（図１２ステップＳ５３）、戻り値がｎｕｌｌでないかを判定する（図１２ステップＳ５４）。図形検索処理手段５１は戻り値がｎｕｌｌでない場合、図形データが探索されたとして、戻り値にその値ｚｄ２を設定し（図１２ステップＳ５１）、関数を終了する。
【００５６】
図形検索処理手段５１は戻り値がｎｕｌｌであり、図形データが探索されなかった場合、次の左下の子ノードｎｐ３に探索エリアＡが内包されれば（図１２ステップＳ５６）、さらに引数（ＩＮＰＵＴ）をｎｐ３，Ａ，ｎＤｅｐｔｈ，ｚｋとして自関数の再帰呼び出しを行い（図１２ステップＳ５７）、戻り値がｎｕｌｌでないかを判定する（図１２ステップＳ５８）。図形検索処理手段５１は戻り値がｎｕｌｌでない場合、図形データが探索されたとして、戻り値にその値ｚｄ３を設定し（図１２ステップＳ５９）、関数を終了する。
【００５７】
図形検索処理手段５１は戻り値がｎｕｌｌであり、図形データが探索されなかった場合、次の右下の子ノードｎｐ４に探索エリアＡが内包されれば（図１２ステップＳ６０）、さらに引数（ＩＮＰＵＴ）をｎｐ４，Ａ，ｎＤｅｐｔｈ，ｚｋとして自関数の再帰呼び出しを行い（図１２ステップＳ６２）、戻り値がｎｕｌｌでないかを判定する（図１２ステップＳ６３）。図形検索処理手段５１は戻り値がｎｕｌｌでない場合、図形データが探索されたとして、戻り値にその値ｚｄ４を設定し（図１２ステップＳ６４）、関数を終了する。
【００５８】
図形検索処理手段５１は全ての子ノードｎｐ１〜ｎｐ４に内包及び交差しなかった場合、戻値にｎｕｌｌを設定し（図１２ステップＳ６１）、関数を終了する。
【００５９】
このように、本実施例では、図形データの存在エリアを図形キーに格納し、図形データを検索する際により少ない４分木データ構造のノードの探索に抑えられるので、４分木データ構造中の図形データの一つを一意のキー値から効率的に検索することができる。
【実施例２】
【００６０】
図１５は本発明の他の実施例による図形追加処理を行うデータ処理装置の構成を示すブロック図である。図１５において、データ処理装置６はプログラム制御により動作し、情報を記憶する記憶装置７と、キーボード等の入力装置３と、ディスプレイ装置や印刷装置等の出力装置４とに接続されている。尚、記憶装置７はＮ分木データ記憶部７１と、図形キー格納部（ＤＢＭＳ等）２２とから構成されている。
【００６１】
データ処理装置６は図形追加処理手段６１及び記録媒体１６とを内蔵し、図形追加処理手段６１は検索エリア番号算出手段１２と、外包矩形算出手段１３と、追加Ｎ分木ノード探索手段６２と、図形のノード追加手段１５とから構成されている。
【００６２】
検索エリア番号算出手段１２は入力装置３によって入力された図形データがＮ分木データ構造の表現する全体領域のいずれのエリアに存在するかを算出することで、エリア番号を得るとともに、同時にエリア番号とエリア内の一意の番号（エリア番号内ＩＤ）とから図形データを一意に識別する図形キーを生成する。
【００６３】
外包矩形算出手段１３は追加する図形データを外包する矩形領域を算出する。追加Ｎ分木ノード探索手段６２は図形データの外包矩形の位置及びサイズから、追加すべきＮ分木データ構造のノードの一つを決定する。
【００６４】
図形のノード追加手段１５は追加Ｎ分木ノード探索手段６２によって決定されたノードに図形データを追加する。この時、図形データは、その図形データを一意に識別する図形キーの順（昇順または降順）にソートしつつ格納する。記録媒体１６はデータ処理装置６が実行するプログラム（コンピュータで実行可能なプログラム）を格納している。
【００６５】
図１６は本発明の他の実施例による図形検索処理を行うデータ処理装置の構成を示すブロック図である。図１６において、データ処理装置８はプログラム制御により動作し、情報を記憶する記憶装置７と、キーボード等の入力装置３と、ディスプレイ装置や印刷装置等の出力装置４とに接続されている。
【００６６】
データ処理装置８は図形キー決定手段５１と、図形検索処理手段８１と、図形データ処理手段５７と、記録媒体５８とを内蔵し、図形検索処理手段８１はエリア番号抽出手段５３と、エリア算出手段５４と、検索Ｎ分木ノード検索手段８２と、図形データ抽出手段５６とから構成されている。
【００６７】
図形キー決定手段５１は入力装置３によって入力された情報に基づき、記憶装置７の図形キー格納部２２等から図形キーを抽出する。図形検索処理手段８１は図形キー決定手段５１によって決定された図形キーから図形データの格納されているＮ分木データ構造のノードを算出し、図形キーの一致する図形データを抽出する。図形データ処理手段５７は決定された図形データに任意の処理を行い、結果を出力装置４に出力する。記録媒体５８はデータ処理装置５が実行するプログラム（コンピュータで実行可能なプログラム）を格納している。
【００６８】
図形検索処理手段８１において、検索エリア番号抽出手段５３は図形キー決定手段５１によって決定された図形キーからエリア番号を抽出する。エリア算出手段５４はエリア番号から、図形データの存在しうる検索エリアを算出する。
【００６９】
検索Ｎ分木ノード探索手段８２はＮ分木データ構造のノードのうち検索エリアに内包または交差するもののみを選択するようにツリーをたどり、これらのノード内に該当図形データが存在しないかどうかを判定する。図形キーの一致する図形データが見つかった場合には、図形データ抽出手段５６によってＮ分木データ構造から図形データを抽出する。
【００７０】
本発明の他の実施例では、上述した本発明の一実施例とは異なり、図形データを保持するデータをＮ分木データ構造に拡張して構成しているため、２次元平面上の図形データに限らずに処理することができる。
【００７１】
次に、具体的な例を用いて本実施例の動作について説明する。例えば、図形データを保持するデータ構造を８分木データ構造とした場合には、図１７に示すように、保持することができる図形データを３次元に拡張することが可能となり、３次元の図形データを８分木で保持し、図形キーに検索エリアを考慮したキーを付与することによって、高速に図形データの一つを検索することができる。
【００７２】
この場合、処理手順は、上述した本発明の一実施例と同様の処理となるが、検索エリアは立方体（直方体）となり、８分木データ構造を探索する場合には、８つの子ノードについて探索する。
【図面の簡単な説明】
【００７３】
【図１】本発明の実施の形態による図形追加処理を行うデータ処理装置の構成を示すブロック図である。
【図２】本発明の実施の形態による図形検索処理を行うデータ処理装置の構成を示すブロック図である。
【図３】本発明の一実施例によるエリア番号を示す図である。
【図４】本発明の一実施例による追加処理動作の流れを示すフローチャートである。
【図５】本発明の一実施例による図形追加時の４分木ノード探索動作の流れを示すフローチャートである。
【図６】本発明の一実施例による図形追加時の４分木ノード探索動作の流れを示すフローチャートである。
【図７】本発明の一実施例によるエリア番号算出処理を示す図である。
【図８】本発明の一実施例による図形追加処理の結果を示す図である。
【図９】本発明の一実施例による図形キー算出処理の結果を示す図である。
【図１０】本発明の一実施例による検索処理動作の流れを示すフローチャートである。
【図１１】本発明の一実施例による図形検索時の４分木ノード探索動作の流れを示すフローチャートである。
【図１２】本発明の一実施例による図形検索時の４分木ノード探索動作の流れを示すフローチャートである。
【図１３】本発明の一実施例によるエリア番号からの検索エリア算出動作を示す図である。
【図１４】本発明の一実施例による図形検索動作を示す図である。
【図１５】本発明の他の実施例による図形追加処理を行うデータ処理装置の構成を示すブロック図である。
【図１６】本発明の他の実施例による図形検索処理を行うデータ処理装置の構成を示すブロック図である。
【図１７】本発明の他の実施例によるデータ保持構造を示す図である。
【符号の説明】
【００７４】
１，５，６，８  データ処理装置
２，７  記憶装置
３  入力装置
４  出力装置
１１，６１  図形追加処理手段
１２  検索エリア番号算出手段
１３  外包矩形算出手段
１４  追加４分木ノード探索手段
１５  図形のノード追加手段
１６  記録媒体
２１  ４分木データ記憶部
２２  図形キー格納部
５１  図形キー決定手段
５２，８１  図形検索処理手段
５３  エリア番号抽出手段
５４  エリア算出手段
５５  検索４分木ノード検索手段
５６  図形データ抽出手段
５７  図形データ処理手段
５８  記録媒体
６２  追加Ｎ分木ノード探索手段
７１  Ｎ分木データ記憶部
８２  検索Ｎ分木ノード検索手段
【図１】
2005115708.tif 000003
【図２】
2005115708.tif 000004
【図３】
2005115708.tif 000005
【図４】
2005115708.tif 000006
【図５】
2005115708.tif 000007
【図６】
2005115708.tif 000008
【図７】
2005115708.tif 000009
【図８】
2005115708.tif 000010
【図９】
2005115708.tif 000011
【図１０】
2005115708.tif 000012
【図１１】
2005115708.tif 000013
【図１２】
2005115708.tif 000014
【図１３】
2005115708.tif 000015
【図１４】
2005115708.tif 000016
【図１５】
2005115708.tif 000017
【図１６】
2005115708.tif 000018
【図１７】
2005115708.tif 000019