Title : Algorithm::QuadTree
|
Location : Home > Languages > Perl > Package Title : Algorithm::QuadTree |
|
Algorithm::QuadTree - ４分木を用いた処理
use Algorithm::QuadTree;
# quadtree オブジェクトの生成
my $qt = Algorithm::QuadTree->new(-xmin => 0,
-xmax => 1000,
-ymin => 0,
-ymax => 1000,
-depth => 6);
# オブジェクトをランダムに追加
my $x = my $tag = 1;
while ($x < 1000) {
my $y = 1;
while ($y < 1000) {
$qt->add($tag++, $x, $y, $x, $y);
$y += int rand 200;
}
$x += int rand 100;
}
# 所与の領域に囲まれたブジェクトを探索
my $r_list = $qt->getEnclosedObjects(400, 300, 689, 799);
Algorithm::QuadTree は Perl 上で４分木アルゴリズム（QTA; quadtree algorithm）を実装する。
本質的にh QTA はマップの特定の領域に非常に迅速にアクセスするために用いられる。
これは特に、所与の領域に囲まれたブジェクトを探索する際やオブジェクト間の共通部分を探索する際に有用である。実際、Tk::Canvas ウィジェットでオブジェクトを通じて迅速に探索するために本モジュールを書いたが、Tk でないプログラムでの利用のほうがうまく行っている。やはりメモリと速度はトレードオフの関係にある。
QTA に関する多くの情報がウェブで見つけることができるだろう。が、端的に言えば、四分木（quadtree）とは、マップをより小さい領域に再帰的に分解する階層的モデルと言える。ツリーの各ノードは４つの子ツリーを持ち、それぞれが親の表現の４分の１の表現となる。だからルートノードは完全なマップの表現となる。このマップは４等分され、各子ノードにより表現される。今度はそれぞれの子ノードが親として扱われ、再帰的に４等分される。これを目的の深度まで繰り返す。
ここにいくぶん粗い図を用意した。（この図は pod2text を走らせないとうまく表示できないかも知れない）
------------------------------ |AAA|AAB| | | |___AA__| AB | | |AAC|AAD| | | |___|___A_______| B | | | | | | | | | | AC | AD | | | | | | -------------ROOT------------- | | | | | | | | | | C | D | | | | | | | | | | ------------------------------
これは以下の４分木に対応している。
__ROOT_
/ / \ \
/ / \ \
_____A_ B C D
/ / \ \
/ / \ \
_____AA AB AC AD
/ / \ \
/ / \ \
AAA AAB AAC AAD
上の図では各レベルで最初の枝しか示していないが、同じ構造が各ノードについて存在している。この４分木の深度は４である。
マップの各オブジェクトにはそれが交差するノードが割り当てられる。例えば AAA 及び AAC をオーバーラップする長方形を考えたとすると、これにはノード ROOT・A・AA・AAA・AAC が割り当てられる。さて、この領域に対し共有部分を持つあらゆるオブジェクトを探索してみよう。全オブジェクトを探索する代わりに、領域と共通部分を持つ ROOT の子ノードを探索する。これらの各ノードでは再帰的にそれらの子ノードを探索し、ツリーの最深部まで行う。最終的に最初の領域とオーバーラップするあらゆる葉ノードを割り当てられたオブジェクトを全て見つけることができる。
以下のメソッドが公開されている。
Algorithm::QuadTree->new( options )
これはコンストラクタである。以下のオプションが指定され（ただし全部必須）Algorithm::QuadTree オブジェクトを返す。
-xmin
４分木に関係付けられた領域の左下の X 座標。
-ymin
４分木に関係付けられた領域の左下の Y 座標。
-xmax
４分木に関係付けられた領域の右上の X 座標。
-ymax
４分木に関係付けられた領域の右上の Y 座標。
-depth
４分木の深度。
$qt->add(ID, x0, y0, x1, y1)
本メソッドはツリーにオブジェクトを追加する際に用いられる。正しいツリーノードに割り当てられるようマップの各オブジェクトによって呼び出される。最初の引数はオブジェクトのユニークな ID である。残りの４つの引数はオブジェクトの外形を定義する。本メソッドはツリーを再帰的に走査し、これをオーバーラップするノードを追加する。
NOTE: 本メソッドは ID がユニークかどうかを確認しない。それは利用者が行う。
$qt->delete(ID)
本メソッドは所与の ID によって指定されたオブジェクトを削除し、それ以前に割り当てられたノードから切り離す。
$qt->getEnclosedObjects(x0, y0, x1, y1)
本メソッドは所与の領域をオーバーラップするノードに割り当てられた全てのオブジェクトの匿名リスト（anonymous list）を返す。
$qt->setWindow(x0, y0, scale)
本メソッドはマップのある部分を拡大表示する際に有用である。add または getEnclosedObjects が適切な座標を持つように所与の領域にウィンドウを設定する。最初の２つの座標は新しいウィンドウのひだ視したの座標を特定する。３つめの座標は新しい拡大スケールを特定する。
NOTE: もちろん自分自身の座標に変換することも自由である。
$qt->resetWindow( )
本メソッドはウィンドウを全マップにリセットする。
今までに気づいたものはない。見つかれば教えてほしい。
Either the usual:
perl Makefile.PL make make install
または Perl が見つけられるように @INC と書いておくこと。ピュアな Perl での方法である。
Ala Qumsieh, aqumsieh@cpan.org
本モジュールは Perl と同等の条件で配布される。
|
|
Updated : 2007/03/20 |