多次元パターン管理構造の図形管理への応用
宮崎敬 大沢裕 坂内正夫
MULTIDIMENSIONAL PATTERN DATA MANAGEMENT STRUCTURE FOR SPATIAL RETRIEVAL
Takashi MIYAZAKI Yutaka OHSAWA and Masao SAKAUHI
I ti sof t e nne c e s s ar yt or et r i evei nf or ma t i ono nt heba s i sofr angei nn‑ di me ns i ona l c oor di nat es pa c e .A numberofda t as t r uc t ur eha vebe e npr opo s e df ort hi spr obl e m.
Amongt he m,t hek･ dt r e ea ndt hebi na r yt r e es e em t obeef fe ct i ve f r o m t he po i nt ofvi e wofgeo me t r i c a ld a t aba s ema na ge me nt .The s eda t as t r uct ur e s ,ho wever ,ar enot f ul l y s at i s f a c t or y,e s pe c i a l l y i n dynami c s i t ua t i o n ori n ma l di s t r i but i o n s i t uat i on.
Thi spaper pr opo s e san appl i c at i o n oft he da t as t r uc t ur e .name dt heBD･ t r e e,t o ge ome t i c a lda t a ba s e ma nage me nt . We wi l lde s c r i be t he s t r uct ur eoft heBD･ t r ee
,pa r t i t i oni ng me t hod,i t sdi r e c t or y t r e eo r ga ni z a t i on a ndt hema n age me nt of pl a i n 丘gur eda t a .
1 . ま え が き
近年, グラフィック閑適機器のメモ リ増大や表示解像度の向上に伴い
,C AD
やCAM
シ ステムに よる図面入力,作成および編集が盛んに行われている. これ らの処理は,対話的に 逐次進め られるため,対話性のよい グラフィックシステムの必要性が高まっている. この対 話型 グラフィックシステムで重要な要素は,ある範囲を指定 して,その範囲内に含 まれ る図 形要素を拡大表示 した り,処理対象図形の実体を直接ではな く,近傍を指示す るだけで所望 の対象図形を検索 した り,図形要素間のある意味を持つ重畳関係を満たすパターソを検索す る機能である. これ らの空間的位置関係に基づ く検索においては,対象空間上の図形要素 と 指示 された範囲や点の位置関係が重要 となる. このため対話性の良い グラフィックシステム では,図形要素の位置 と領域情報を基礎 としたデータ管理構造が必要 と考えられ る.従来か ら,空間的位置関係に基づ くデータ管理構造 としては,次のような方式が用い られ ている.対象平面を縦 ･横で等間隔にn等分を行ない,近 くに位置す る要素をブロック化 し,
2
次記憶上に蓄積 して管理す る方式(1)(2),また,対象平面を縦 ･横 とい う順に2
等分割を行な い,分割に より得 られ る小田域内に存在す るデ‑タ数を等 しくす る2等分割法,2n分割法(3),* 昭和
60
年10
月 昭和60
年度電子通信学会情報 システム部門全国大会にて発表** 電気工学科 助手
*** 東京大学生産技術研究所 助手
**** 東京大学生産技術研究所 助教授 原稿受付 昭和
62
年9
月30
日8 4
宮崎 敬 ･大沢 裕 ･坂内正夫対象平面内に存在す るデ‑タ数がある値になるよ うに矩形分割を行なって管理する
k‑ d
木 がある(4X5).しか し,それぞれ‑,次のような欠点を持っているため十分 とはいえない.ブロック化による方法, 2分割法および 2n分割法では,図形要素の分布に偏 りがある場合に,密 な部分において検索効率の劣化がおこる. また
, k‑ d
木では,データの動的状況に対す る 特性が十分ではない(6). 以上における欠点を改良し, この偏 りがある分布や動的状況下にお いても良好な特性を持つBD
木構造が提案 されている( 6 ) ( 7 ) . BD
木 とは,縦 ･坊 とい う順に2 等分割を繰 り返 し,分割前域を ｢領域式｣ と呼ぶ領域表現に より管理す るデータ構造であ り, 多次元情報管理のために開発 された ものである.本文では, この構造を
2
次元平面における図形管理へ拡張 したので,その作成方法 と管理 方法を報告す る.2 .
図形情報の表現 と管理一般のグラフィックシステムで扱 う図形情報 としては,点,線および様 々な図形の種煩や, それ らが持つ大 きさや色などの属性があげ られ る.本論では, これ らの うち本提案方式の管 理構造の構成に必要 となる大 きさ展性 と種析属性を持つ図形要素を扱 っている. これ らの図 形要素の空間に占める領域については,外接矩形で管理を行なっている. また, これ らの図 形要素の空間的位置関係については,対象空間を縦 ･横 と順次
2
等分割を繰 り返 していき, 各分割領域内に存在す る図形要素が1
つになるまで行な う. この分割過程において,分割領 域内に1
つになった段階の額域か ら,木構造の葉 ノー ドとして位置関係を管理す る.本管理方式は,図形要素の分布に依存す ることな く,一定の/‑ ド数を持つ木構造である ため, グラフィック等の対象空間における図形要素の空間管理方式 として, メモ リ効率が良 い とい う特散を持 っている.
しか し,図形要素の種煩が増加 し,様 々な図形要素を頻繁に検索す る必要のあるグラフィ ックシステムや,図形要素の数が少な くても,検索範囲をある種煩の図形要素に限定 した う えで,様々な検索を行な うようなグラフィックシステムでは,検索に関係 しない種類の図形 要素が検索効率を悪 くして しま う可能性がある.
以上のよ うなことか ら,全図形要素をまとめて
BD
木構造で管理す る方法 と,図形要素の 種類別に管理す る方法が考えられ る.前者を一括型BD
木構造,後者を レイヤ‑型BD
木構 造 と呼ぶことにす る.3 . BI
)木構造による図形情報管理方法BD
木構造は,対象 とす るデータ空間内における各々のデータの存在位置を表わす ｢領域 式｣ とい うものを作成 し, これに基づいた2
分木構造で全てのデータを管理する方法である｡また, この木構造の各 ノ‑ ドには,領域を管理するための外接矩形情報 とい うものが持たさ れている. ここでは
,8 0 0 0×8 0 0 0
の2
次元空間をデータ空間 とし,データとしては,1 0 ‑4 0
の大 きさを持つ4
種類の図形を用いている.但 し,多角形については,底辺が水平軸 と平行 になるように存在す るものとしている. このモデルに対す る本データ構造の構成について, 以下に述べ る.3 ‑1
図形要素の重心による空間分割各図形の存在位置 としては重心座 標を用い, この重心座標に基づいて 領域分割を行な う.複雑な図形要素 を対象 とす る場合には,単純な図形 要素になるまで分割 し,その重心座 標を用いるか, または,各辺の中心 座標を用いるような工夫が必要 とな る.対象空間を, y軸
,
Ⅹ軸に平行 な分割軸で交互に2
等分割を繰 り返 し,各分割領域内に存在す る図形要 素がただ1
つになるまで行なっていく.
図‑ 1の場合について,具体的に その分割法を示す.図‑ 1のデータ 番号順にデータが発生 した とす る･
まず,空間
K
を y軸 に平行な軸Xl
で 2等分割する.データ 3が発生す ると,領域
K
lに は複数のデータが存在す る ので,
Ⅹ軸に平行な軸yl
で2
等分割を行な う.次に, データ4
が発生す ると,軸Ⅹ如こよりデータ
3
の含まれ る田城 と分割を行な う.チ ータ5
については,まず軸Ⅹ3
に より分割を行 うが,チ‑タ
1
と分離で きないので, 更に軸y2
に よる分割を行ラ.以上の分割に より,令
‑分割領域内のデータの個数 が
1
つになるので,以後の 分割を中止す る. この2
等 分割法に より得 られたのが 図‑ 2
である. この構造を みると,図形要素を持たな い空の菓 ノー ドが存在す る ことがわかる. これは,分 割軸yl , Ⅹ3
に より生成 さ れた無効領域である. この■′
( 80
00. 8 0(
> I( ､ ∋ I ⊂ ]Y牟
･a,
/＼
I
図 1 2分割法による領域分割
･d,.
読 .
↓
･b,
, A.
I
･C,. P
l 図2 2分割法による図形データの 管理構造の作成過程宮崎 敬 ･大沢 裕 ･坂内正夫
( 800 0. 8000)
･‑･甲‑IIII
① 俗
' 〇 ･ o'
x'2J.
‑x
図3 BD木法による銃域分割
ため,木構造の管理データ量が増加 し, グラフィ ックシステム等 の編集作業におけるデータ検索の 効率や メモ り効率の劣化を生 じる. この無効分割 を防 ぐために考 え られたのが
,
｢領域式｣による 領域分割方法である. この琉域式を利用 した領域 分割管理について,図‑ 3
によ り説明する.まず, 2分割法を行なってい く段階で
, y
軸お よび Ⅹ軸に平行な軸で2
等分割 されてできる領域 の左側および下側琉域を｢0
｣ とし,右側および 上側鏡域を ｢1｣ とす る.例えは, y軸に平行に2
等分割 し,更にⅩ軸に平行な軸で2
等分 して得 られ る領域の うち,左上4
分の1
の街域K3
は,｢ 0 1
｣ と表わされ る. この記号 の最後に分割の終(d)
図4 BD木法による図形データの 管理構造 の作成過程
了符 として ｢*｣を付けると約束する. この領域式表現に よる分割過程を述べる.初めに, 軸
Ⅹ
1によって生成 され る左右 の領域Kl
とK2
は,｢
0*｣ と ｢1*｣ と表わされ る.各領域内 にそれぞれ1
つのデータしか存在 しないので,対象空間K
を板 とし,領域Kl
とK2
をその 左右の子ノー ドとす る.次に,領域Kl
にデータ2および 3が存在 しているので, この領域Kl
を軸yl
によ り分割 し,領域K3
とK4
に分割す る.得 られた街域K
書は｢ 0
0*｣と表わされ, 領域K3
は｢ O l *
｣ と表わ され る. この2
つの領域が元の額域Kl
の左右 の子 ノー ドとされ る.続いてデータ4がデータ 3の領域
K4
に存在す るために,更に分割が軸Ⅹ2
により行われる.データ
1
とデータ5
について,｢2
等分割によりで きる領域にデータが1
つずつ存在す る｣とい う条件に合 うには,軸
yl ,
Ⅹ3 ,y
之とい う順に3
回分割 される必要がある. これを領域式 表現を用いて,木構造を表わす と,図‑4
のようになる. しか し, この3
回の分割の うち, 軸yl
と Ⅹ8による分割では,データの分割が行なわれない.そこで,軸yl
と Ⅹ8に よる分割でできる田城については, 木構造 の 子ノ‑ ドにはしないで, 領域式の 作成 のみに とどめ る.次に,軸
y
･.に よる分割を行な うと,データ1
およびデ‑タ5
が分離 され る･ この両領 域の領域式は｢ 1 1 1 0
*｣と｢ 1 1
11*｣ となる.従って,領域K7
が左子 ノ‑ ドとな り,領域K8
が右子ノー ドとなる木構造が生成 される. このときの親 ノー ドには,左子 ノ‑ ドの拐域式で ある｢ 1 1 1 0
*｣が残 されている.以上に より
, 2
等分割法を用いた場合の無効分割が事実上行なわれず, ノ‑ ド数の増加を 防 ぐことができる. この構造に よってできる全ノー ド数は,データの分布 に依存せずに一定とい う性質を持っている.
3 ‑2
外接矩形による図形の大きさ管理図形要素の管理 としては,上記の対象空間における位置情報の管理 とともに,大 きな情報 の管理 も重要である.大 きさの管理方法 としては,様 々な方法が考えられ る. ここでは, 4 節で述べる検索方法を考慮 し,図形要素に外接す る矩形額域を用いている. この矩形情報は 図
‑ 5
に示す ように,座標軸に平行な辺を持ち,図形要素に外接する矩形の左下頂点 (Xb, yb)および右上頂点 (Xt, yt)の座標値に より管理 されている･図
‑5
において, この情報の管理 の方法を述べ る. まず,木構造中の全英 ノー ドには,令 図形要素の外接矩形街域を持たせ る.図形要素1, 2, 3, 4, 5
の外接矩形鎖域をG,D
,F,E,H
とす ると,図‑ 5
の木構造の各葉 ノー ドに対応す る図形要素の情報を持たせ る･次に,薬 ノー ド以外のノ‑ ドには,各ノー ドの左右 の子 ノー ドが持つ外接矩形領域に外接す るような新 しい矩形領域を作成 し, その左下頂点お よび右上頂点の座標を持たせ ることにす る. この作成は,木構造の下位 レベルのノ‑ ドか ら順次行な う.データ3とデータ4の外接 矩形領域
E
とF
の外接矩形領域 として預域C
が作成 され る.次に, この田城C
とデータ2
の 外接矩形田城D
の外接矩形領域A
が作成 される. また,データ1
とデータ5
の外接矩形領域G
とH
より,その外接矩形領域 として領域B
が作成 され る.最後に,田城A
と領域B
の外接(βoor).8000)
(a)
4
3
>
‑‑‑‑X
図5 外接長方形の作成と管理
2 1 5
(b)
88 宮崎 故 ･大沢 裕 ･坂内正夫
錦
城T
が作成 され る.以上で,全ての図形要素の大 きさ情報が管理 され る.即 ち,中間ノー ドに置かれ る外接矩形は,そのノー ドを板 とす る部分木 中に含 まれ る全図形情報 となってい る.木 の板 ノー ドの外接矩形は,対象空間に存在す る全図形要素の外接矩形領域 となってい る. また,各 ノー ドには, この他に左右 の子 ノー ドへのポインタと領域式が置かれる.以上をまとめ ると,図形情報 の空間管理構造は,以下 に示す要素をノー ドに含む
2
分木構 造 に よ り構成 されている.[空間管理構造のノー ド構成]
左右子 ノー ド‑のポイソタ :left,righ t 領域式 .･reg 外接矩形の左下お よび右上頂点座標 :Ⅹも
, y
b, X
t, yt
図形要素の実体‑のポイソタ :point
4 .
あ と が き一般に
,CAD
等 の2
次元図形データを扱 うシステムにおいて,処理対象 となる図形デー タを効率良 く検索す るためには,図形データをデータ構造上で管理す る必要があ る.今まで に このためのデータ構造 として開発 された方法があるが,いずれ も,図形デ‑タの偏在下や 動的環境下において検索効率が非常に悪 くな る欠点があ る.今回,本論文では2
つの状況下 で も良好な検索効率を確保で きるデータ構造 として,BD
木構造を拡張 したので, その作成 方法 と管理方法を報告 した.現在,本データ構造 の検索効率を調べてい るところであ る.参 考 文 献
(1)笠原,他 :｢地理情報システムとその応用｣
,
｢グラフィックスとCAD｣シソポジウム予稿集,pp.59‑66,1983.12.
(2)大金 正 :｢公益事業における地理情報データベース｣,電気学会情報工学研究会資料,IPl8114, pp.33‑42,1981.
(3) Finkle,R.A.andBentley,∫.L.:…Quadtrees:adatastructureforretrievaloncom‑
positekeyH,Actalnformatica,4,pp.ト9(1974).
(4) Bentley,J.L.:''MultidimensionalBinarySearchTreesUsedforAs sociativeSearch‑
ing",CACM,18,9(1975).
(5)松山,他 :借地学会コンビュ‑クビジaン研究会資料.
(6)大沢,坂内 :｢良好な動特性を持つ多次元点データ管理構造の‑提案｣,信学論,J66･D,No.10, 1983.10.
(7)大沢,坂内 :｢2段階の木構造による餌域情報管理方式｣,信学論,J67･D,No.4,1984.10.
