I don't understand your notation there "0:3:2:3|2:3:0:1|0:1:1:1|1:1:0:0|", but can't you draw the area with 1's as two objects one large tall one and one small tall one? (1,0)-(3,3) and (0,1)-(0,3) or of course you could split it the other way (0,1)->(3,3) and (1,0)->(3,0).

The notation comes from this:
$rectangles .= "$child->{XMIN}:$child->{XMAX}:$child->{YMIN}:$child->{YMAX}|";

As for it being condensable into two rectangles: Yes, i am aware of that. Just haven't gotten around to implementing that last bit of optimization. :)

Reason for that being that i was only made aware of a decently fast way to do it an hour ago.

I was looking at the QuadTree stuff and I wonder if you wouldn't be better off just using some soft of fill technique instead. I've thrown together and example, its fast and it automaticaly builds the biggest rectangles it can. I think it might be better for your needs. It is not optomized in any way and could definitly have some parts combined together, but it works nice

#!/bin/perl

use strict;
use warnings;
use Data::Dumper;

my $grid = [[0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0],
            [1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0],
            [1,1,1,1,0,0,0,0,0,0,0,0,1,0,0,0],
            [1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0],
            [0,0,1,1,1,1,0,0,0,0,0,0,1,1,1,0],
            [0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
            [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
           ];


sub get_area {
   my $sel_area = 0;
   my ($grid, $x1, $y1, $x2, $y2) = @_;
   for my $x ($x1..$x2) {
      for my $y ($y1..$y2) {
         $sel_area++ if $grid->[$x][$y] eq "1";
     }
   }
   return $sel_area;
}

sub sel_area {
   my $sel_area = 0;
   my ($grid, $label,$x1, $y1, $x2, $y2) = @_;
   die unless defined $x1 and defined $y1 and defined $x2 and defined 
+$y2;
   for my $x ($x1..$x2) {
      for my $y ($y1..$y2) {
         $grid->[$x][$y] = $label;
     }
   }
   return $sel_area;
}



my ($min_x , $min_y,$max_x, $max_y) = (0,0,15,15);

my $area = get_area($grid, $min_x, $min_y,$max_x, $max_y);
my $sel_area = 0;

sub print_grid {
   my $grid = shift;
   for my $row (@$grid) {
      for my $item (@$row) {
         print( $item eq '0' ? '.' : $item );
      }
      print "\n";
   }
}

print "Selected area: $area\n";
print_grid($grid);
print "\n", "X" x 16, "\n\n";

my ($s_x, $s_y) = ($min_x, $min_y);
my $boxes;
my $l = 'a';
while ($sel_area < $area) {
   if ($grid->[$s_x][$s_y] eq "1") {
      my ($t_x,$t_y) = ($s_x, $s_y);
      while (1) {
         last if ($grid->[$t_x+1][$s_y] ne '1');
         $t_x++;
      }
      while (1) {
         $t_y++; 
         my ($trial_area, $real_area) = (
            get_area($grid, $s_x, $s_y, $t_x, $t_y),
            ( ($t_x - $s_x + 1) * ($t_y - $s_y + 1) )   
            );
         if ($trial_area < $real_area) {
            $t_y--;
            last;
         };
      }
      $sel_area += get_area($grid, $s_x, $s_y, $t_x, $t_y);
      sel_area($grid, $l, $s_x, $s_y, $t_x, $t_y);
      push @$boxes, [ $s_x, $s_y, $t_x, $t_y ];
      $l ++;
   }
   last if $sel_area == $area;
   $s_x++;
   if ($s_x > $max_x) {
      $s_x = $min_x;
      $s_y++;
      if ($s_y > $max_y) {
         die "Failed"
      }
   }
}


print_grid($grid);
print "\n";
print Dumper($boxes);
[download]

And that outputs:

Selected area: 38
.111............
1111............
1111........1...
1111............
................
................
................
.........1111...
...........11...
...........11...
............111.
..1111......111.
..1111..........
................
................
................

XXXXXXXXXXXXXXXX

.bbb............
aaaa............
aaaa........f...
aaaa............
................
................
................
.........dddd...
...........ee...
...........ee...
............ggg.
..cccc......ggg.
..cccc..........
................
................
................

$VAR1 = [
          [ 1, 0, 3, 3 ],
          [ 0, 1, 0, 3 ],
          [11, 2,12, 5 ],
          [ 7, 9, 7,12 ],
          [ 8,11, 9,12 ],
          [ 2,12, 2,12 ],
          [10,12,11,14 ]
        ];
[download]


___________
Eric Hodges