| Name : perl-Algorithm-QuadTree
| |
| Version : 0.500.0
| Vendor : obs://build_opensuse_org/devel:languages:perl
|
| Release : lp155.1.1
| Date : 2024-07-14 18:52:44
|
| Group : Unspecified
| Source RPM : perl-Algorithm-QuadTree-0.500.0-lp155.1.1.src.rpm
|
| Size : 0.04 MB
| |
| Packager : https://www_suse_com/
| |
| Summary : QuadTree Algorithm class in pure Perl
|
Description :
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.
|
RPM found in directory: /packages/linux-pbone/ftp5.gwdg.de/pub/opensuse/repositories/devel:/languages:/perl/15.5/noarch |
