Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

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


    Geo::SpaceManager - Place rectangles without overlap

    Version 0.9, released April, 2006.

     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];
     $p2 = $sm->nearest($r2);  # returns [20,30,60,50];
     $p3 = $sm->nearest($r3);  # returns [60,10,80,50];
     $p4 = $sm->nearest($r4);  # returns undef

    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.

    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 );
    Set the minimum size for rectangles to be added.

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


    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

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

    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.

    Find the nearest location in which to place the specified

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

    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";

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

Jim Gibson

Site Timeline