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]