NAME

Algorithm::BreakOverlappingRectangles - Break overlapping rectangles into non overlapping ones

SYNOPSIS

use Algorithm::BreakOverlappingRectangles;

my $bor = Algorithm::BreakOverlappingRectangles->new;

                   # id => X0, Y0, X1, Y1
$bor->add_rectangle( A =>  0,  4,  7, 10);
$bor->add_rectangle( B =>  3,  2,  9,  6);
$bor->add_rectangle( C =>  5,  0, 11,  8);

# that's:
#
#   Y
#   ^
#   |
#  11
#  10 +------+
#   9 |      |
#   8 |  A +-+---+
#   7 |    |     |
#   6 |  +-+---+ |
#   5 |  |     | |
#   4 +--+  B  | |
#   3    |     | |
#   2    +-+---+ |
#   1      |  C  |
#   0      +-----+
#   |
#   +-01234567891111--> X
#               0123
#

$bor->dump;

# prints:
#
# [0 4 3 10 | A]
# [3 4 5 6 | A B]
# [3 6 5 8 | A]
# [7 2 9 4 | B C]
# [3 2 5 4 | B]
# [5 4 7 6 | A B C]
# [3 8 7 10 | A]
# [5 6 7 8 | A C]
# [7 4 9 6 | B C]
# [5 2 7 4 | B C]
# [9 0 11 4 | C]
# [9 4 11 6 | C]
# [7 6 11 8 | C]
# [5 0 9 2 | C]
#
# that's:
#
#   Y
#   ^
#   |
#  11
#  10 +----+-+
#   9 |    | |
#   8 |    +-+---+
#   7 |    | |   |
#   6 +--+-+-+-+-+
#   5 |  | | | | |
#   4 +--+-+-+ | |
#   3    | | | | |
#   2    +-+-+-+-+
#   1      |     |
#   0      +-----+
#   |
#   +-01234567891111--> X
#               0123
#

# or alternatively:
my $rect = $bor->get_rectangles_as_array_ref;
print "[@$_]\n" for (@$rect);

DESCRIPTION

Given a set of rectangles that can overlap, break them in a set of non overlapping ones.

This module is highly optimized and can handle big sets efficiently.

API

The following methods are provided:

Algorithm::BreakOverlappingRectangles->new()

Creates a new object.

$bor->add_rectangle($x0, $y0, $x1, $y1, @names)

Adds a new rectangle to the set.

$x0, $y0, $x1, $y1 are the coordinates of the extremes. @names can be anything you like and will be attached to the output rectangles contained inside this one.

$bor->get_rectangles()

Returns the set of non-overlapping rectangles. Every entry is an array of the form [$x0, $y0, $x1, $y1, @names].

$bor->get_rectangles_as_array_ref()

Returns an array ref (actually a tied one) containing the broken rectangles.

Rectangles are stored inside Algorithm::BreakOverlappingRectangles objects as packed data to reduce memory comsumption, but calling the get_rectangles method expands them and so can eat lots of memory when the number of rectangles is high. This alternative method returns a reference to a tied array that unpacks the rectangles on the fly.

For instance:

my $r = $abor->get_rectangles_as_array_ref;
for (@$r) {
  print "@$_\n";
}

COPYRIGHT AND LICENSE

Copyright (C) 2008 by Salvador Fandiño (sfandino@yahoo.com)

Copyright (C) 2008 by Qindel Formacion y Servicios S.L.

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.