NAME

Algorithm::RectanglesContainingDot - find rectangles containing a given dot

SYNOPSIS

            

              
              
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]);
  ...
}
            
          

DESCRIPTION

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:

1) create and algorithm object:

            

              
              
$a = Algorithm::RectanglesContainingDot->new;
            
          

2) add the rectangles:

            

              
              
$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.

3) call the search method for every dot:

            

              
              
@rects = $a->rectangles_containing_dot($x, $y)
            
          

Returns the names of the rectangles containing the dot ($x, $y).

SEE ALSO

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.

AUTHOR

Salvador Fandiño, <sfandino@yahoo.com>

COPYRIGHT AND LICENSE

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.