perl-Algorithm-QuadTree

QuadTree Algorithm class in pure Perl

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 Tk::Canvas 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: ------------------------------ |AAA|AAB| | | |___AA__| AB | | |AAC|AAD| | | |___|___A_______| B | | | | | | | | | | AC | AD | | | | | | -------------ROOT------------- | | | | | | | | | | C | D | | | | | | | | | | ------------------------------ Which corresponds to the following quadtree: __ROOT_ / / \ \ / / \ \ _____A_ B C D / / \ \ / / \ \ _____AA AB AC AD / / \ \ / / \ \ AAA AAB AAC AAD In the above diagrams I show only the nodes through the first branch of each level. The same structure exists under each node. This quadtree has a depth of 4. Each object in the map is assigned to the nodes that it intersects. For example, if we have an object that overlaps regions _AAA_ and _AAC_, it will be assigned to the nodes _ROOT_, _A_, _AA_, _AAA_ and _AAC_. Now, suppose we want to find all the objects that intersect a given area. Instead of checking all objects, we check to see which children of the ROOT node intersect the area. For each of those nodes, we recursively check _their_ children nodes, and so on until we reach the leaves of the tree. Finally, we find all the objects that are assigned to those leaf nodes and check them for overlap with the initial area.