|
Algorithm::QuadTree - A QuadTree Algorithm class in pure Perl. |
Algorithm::QuadTree - A QuadTree Algorithm class in pure Perl.
use Algorithm::QuadTree;
# create a quadtree object
my $qt = Algorithm::QuadTree->new(-xmin => 0,
-xmax => 1000,
-ymin => 0,
-ymax => 1000,
-depth => 6);
# add objects randomly
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;
}
# find the objects enclosed in a given region
my $r_list = $qt->getEnclosedObjects(400, 300,
689, 799);
Algorithm::QuadTree implements a quadtree algorithm (QTA) in pure Perl. Essentially, a QTA is used to access a particular area of a map very quickly. This is especially useful in finding objects enclosed in a given region, or in detecting intersection among objects. In fact, I wrote this module to rapidly search through objects in a the Tk::Canvas manpage widget, but have since used it in other non-Tk programs successfully. It is a classic memory/speed trade-off.
Lots of information about QTAs can be found on the web. But, very briefly, a quadtree is a hierarchical data model that recursively decomposes a map into smaller regions. Each node in the tree has 4 children nodes, each of which represents one quarter of the area that the parent represents. So, the root node represents the complete map. This map is then split into 4 equal quarters, each of which is represented by one child node. Each of these children is now treated as a parent, and its area is recursively split up into 4 equal areas, and so on up to a desired depth.
Here is a somewhat crude diagram (those diagrams might not appear unless you run pod2text):
------------------------------
|AAA|AAB| | |
|___AA__| AB | |
|AAC|AAD| | |
|___|___A_______| B |
| | | |
| | | |
| AC | AD | |
| | | |
-------------ROOT-------------
| | |
| | |
| | |
| C | D |
| | |
| | |
| | |
------------------------------