Algorithm::RectanglesContainingDot - find rectangles containing a given dot
use Algorithm::RectanglesContainingDot; my $alg = Algorithm::RectanglesContainingDot->new; for my $i (0 .. $num_rects) { $alg->add_rectangle($rname[$i], $rx0[$i], $ry0[$i], $rx1[$i], $ry1[$i]); } for my $j (0 .. $num_points) { my @rects_containing_dot_names = $alg->rectangles_containing_dot($px[$j], $py[$j]); ... }
Given a set of rectangles and a set of dots, the algorithm implemented in this modules finds for every dot, which rectangles contain it.
The algorithm complexity is O(R * log(R) * log(R) + D * log(R)) being R the number of rectangles and D the number of dots.
Its usage is very simple:
$a = Algorithm::RectanglesContainingDot->new;
$a->add_rectangle($name, $x0, $y0, $x1, $y1);
Rectangles are identified by a name that can be any perl scalar (typically an integer or a string).
($x0, $y0) and ($x1, $y1) correspond to the coordinates of the left-botton and right-top vertices respectively.
@rects = $a->rectangles_containing_dot($x, $y)
Returns the names of the rectangles containing the dot ($x, $y).
Algorithm::RectanglesContainingDot_XS implements the same algorithm as this module in C/XS and so it is much faster. When available, this module will automatically load and use it.
Salvador Fandiño, <sfandino@yahoo.com>
Copyright (c) 2007 by Salvador Fandino.
Copyright (c) 2007 by Qindel Formacion y Servicios SL.
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.8.8 or, at your option, any later version of Perl 5 you may have available.
To install Algorithm::RectanglesContainingDot, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Algorithm::RectanglesContainingDot
CPAN shell
perl -MCPAN -e shell install Algorithm::RectanglesContainingDot
For more information on module installation, please visit the detailed CPAN module installation guide.