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.