Algorithm-QuadTree

 view release on metacpan or  search on metacpan

lib/Algorithm/QuadTree.pm  view on Meta::CPAN

    # find the objects enclosed in a given region
    my $r_list = $qt->getEnclosedObjects(400, 300,
                                         689, 799);

=head1 DESCRIPTION

Algorithm::QuadTree implements a quadtree algorithm (QTA) in pure Perl.
Essentially, a I<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 L<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,

lib/Algorithm/QuadTree.pm  view on Meta::CPAN

              /  /   \  \
        _____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 I<AAA> and I<AAC>, it will be
assigned to the nodes I<ROOT>, I<A>, I<AA>, I<AAA> and I<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 I<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.

=head1 CLASS METHODS

The following methods are public:

=over 4

lib/Algorithm/QuadTree/PP.pm  view on Meta::CPAN

		} else {
			# segment is a leaf and overlaps the obj
			push @nodes, $current;
		}
	}

	return \@nodes;
}

# choose the right function based on argument count
# first argument is always $self, second is $finding, the rest are coords
sub _loopOnNodes
{
	goto \&_loopOnNodesInCircle if @_ == 5;
	goto \&_loopOnNodesInRectangle;
}

sub _clearHasObjects
{
	my $node = shift;

t/05-window.t  view on Meta::CPAN

	is $qt->{SCALE}, 4, 'scale ok';
	is $qt->{ORIGIN}[0], 0.75, 'origin x ok';
	is $qt->{ORIGIN}[1], 0.75, 'origin y ok';
};

subtest 'should be able to add and get objects when window is set' => sub {
	# should only be in most top left zone
	$qt->add('test1', 8, 8, 8.8, 8.8);

	# should only be in second most top left zone (one to the right to the prev one)
	$qt->add('test2', 9.1, 8, 9.3, 8.8);

	check_array $qt->getEnclosedObjects(1, 1, 7.9), ['test1'], ' (circular, first zone)';
	check_array $qt->getEnclosedObjects(2, 1.5, 7), ['test1', 'test2'], ' (circular, both zones)';

	check_array $qt->getEnclosedObjects(3, 8, 8, 8.5), ['test1'], ' (rectangular, first zone)';
	check_array $qt->getEnclosedObjects(5, 8.4, 9, 9.5), ['test1', 'test2'], ' (rectangular, both zones)';
};

subtest 'should be able to reset window' => sub {