Algorithm::BreakOverlappingRectangles - Break overlapping rectangles into non overlapping ones
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);
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.
The following methods are provided:
Creates a new object.
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.
Returns the set of non-overlapping rectangles. Every entry is an array of the form [$x0, $y0, $x1, $y1, @names]
.
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 (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.