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
And that outputs:#!/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);
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 ] ];
In reply to Re^5: Implementation of a QuadTree and worries of a lone programmer (Flood Fill)
by eric256
in thread RFC: Implementation of a QuadTree and worries of a lone programmer
by Xenofur
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |