perl-Algorithm-RectanglesContainingDot

Find rectangles containing a given dot

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