Geo::SpaceManager

I have written a module I am calling Geo::SpaceManager. It allows a
Perl program to place rectangles into a two-dimensional rectangular
space without overlap. I am preparing this module for submission to
CPAN, which I have searched without finding anything similar.

A typical application of this module would be to add non-overlapping
labels to a map, which is the application for which I wrote it. Another
application might be to manage non-overlapping windows in a graphical
user interface.

The name SpaceManager was taken from a research paper on the topic.
This sort of module would seem to fit into the Geo namespace. If
anybody has a better name or location, I would consider changing them.

The POD is included below (sorry for its length).

-----------------------------------------------------------

NAME
Geo::SpaceManager - Place rectangles without overlap

VERSION
Version 0.9, released April, 2006.

SYNOPSIS
use Geo::SpaceManager;

$sm = Geo::SpaceManager->new([0,0,100,100]);
$r1 = [10,10,40,30];
$r2 = [20,20,60,40];
$r3 = [50,10,70,40];
$r4 = [70,40,100,60];
$sm->add($r1);
$p2 = $sm->nearest($r2); # returns [20,30,60,50];
$sm->add($p2);
$p3 = $sm->nearest($r3); # returns [60,10,80,50];
$sm->add($p3);
$p4 = $sm->nearest($r4); # returns undef

DESCRIPTION
Geo::SpaceManager keeps track of the free space available in a
two-dimensional space as upright (non-rotated) rectangles are
added. The module can find the nearest available location where
a rectangle may be placed or indicate that the rectangle cannot
be placed in any of the remaining free space.

Rectangles are specified by references to four-element arrays
giving the boundaries of the rectangle:

[ left, bottom, right, top ]

Reflected boundary values may be used by swapping left <-> right
and top <-> bottom when specifying rectangles, but the return
value of nearest() will return a value as shown above.

CONSTRUCTOR
new
The new() constructor should be called with the rectangle
representing the entire free space to be managed. A second,
optional argument turns debugging on if it has a true value.

my $sm = Geo::SpaceManager->new( [0, 0, 100, 100] );
my $sm_debug = Geo::SpaceManager->new( [0, 0, 100, 100], 1 );

METHODS
set_minimum_size
Set the minimum size for rectangles to be added.

The following all set the minimum size of rectangles to (10,20):

$sm->set_minimum_size([10,20]);
$sm->set_minimum_size([0,0,10,20]);
$sm->set_minimum_size([10,30,20,50]);
$sm->set_minimum_size([20,50,10,30]);

Setting a minimum size means that SpaceManager can be more
efficient in space and time by discarding free-space areas if
they are too small to contain any more rectangles of the minimum
size.

You should set the minimum size before adding any rectangles and
not change it afterwards with another call to set_minimum_size.

add
Add a rectangle to the current free space.

$sm->add( [10,20,50,40] );

The free space will be reduced by the rectangle. The method
returns 1 if successful and undef on failure. The only failures
will be if the rectangle argument is missing or if it lies
entirely outside of the space.

nearest
Find the nearest location in which to place the specified
rectangle.

$r = $sm->nearest([10,30,30,50]);

The method will return a reference to an array of four scalars
specifying a rectangle of the same size as the supplied one that
fits wholly into an available free space if space can be found.
The rectangle will be a copy of the provided one if it fits as
is. The method will return undef if there is no free space that
can contain the supplied rectangle.

distance
Return the distance between two (x,y) points or two rectangles.

$dist = $sm->distance( $rect1, $rect2 );
$dist = $sm->distance( [0,0], [3,4] ); # returns 5

Calculate the distance between the two arguments, which should
be references to arrays with at least two elements. Only the
first two elements will be used, so you may pass refereces to
two arrays with four elements that represent rectangles. This
method may be used to find how far away the nearest available
location is from a desired rectangle placement location.

$s = $sm->nearest($r);
$d = $sm->distance($r,$s);
print "nearest available location is $d units away\n";

dump
$sm->dump()

Print out the current set of free-space rectangles to standard
output. The area of each rectangle is also printed.

--
Jim Gibson