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.