GrandFather has asked for the wisdom of the Perl Monks concerning the following question:

I'm writing code to test Windows dialog resources for compliance with various in-house rules for layout etc. Among the rules are constraints on how controls are layed out WRT each other - spacing and such.

My question is, is there a tidy way of quickly checking for rectangle overlap (I can inflate control rectangles to accomodate the margins they need to have). A simplification may be that the rectangles are constrained to an integer grid (dialog units) where the integers are of modest size (less than 800 x 600) limited by maximum dialog sizes.

So are there any modules around that I can leverage for this task. If not, is it something that would be worth writing a CPAN module for?


DWIM is Perl's answer to Gödel
  • Comment on Detecting control placement constraints in dialog resources - rectangle overlap checking

Replies are listed 'Best First'.
Re: Detecting control placement constraints in dialog resources - rectangle overlap checking
by Corion (Patriarch) on Mar 09, 2006 at 20:55 UTC

    I'm not aware on any modules that are readily available for this, but you could either abuse one of the many imaging modules to do it, by actually painting your bounding boxes into an image (using the "add" function) and then scanning that image for a colour value larger than 1.

    Another, not too hard way would be to do the checking of the bounding boxes yourself. I have some bounding box code hidden in Banish the overlap (was:Re: drawmap.pl - Spot The Monk!) somewhere. Basically there are two kinds of overlap:

    1) 2) aaaaaaa aa aaaaaaa aa aaaaabbbb bbbbbbbb aaaaabbbb aa bbbb aa

    ... that is, either one of the corners of one rectangle is contained in the other rectangle, or they intersect otherwise. You can reduce the second case to the first by shrinking the rectangle by moving an outlier corner to line up with one side of the other rectangle.

Re: Detecting control placement constraints in dialog resources - rectangle overlap checking
by bart (Canon) on Mar 09, 2006 at 21:54 UTC
    A sub to detect overlap of two rectangles is not that hard, especially if you go the other way: eliminate all the possibilities on how not to overlap. The rectangles will not overlap if one is completely to the left of the other, or vice vera, nor if it's completely below the other, or vice versa. In any other circumstances, they must overlap. This code will do that. I do allow the rectangles to touch.
    use List::Util qw(min max); sub rect_overlap { my($r1, $r2) = @_; # two rectangles, like [x1, y1, x2, y2] # r1 is on the left of r2 return 0 if max(@$r1[0, 2]) <= min(@$r2[0, 2]); # r2 is on the left of r1 return 0 if max(@$r2[0, 2]) <= min(@$r1[0, 2]); # r1 is below r2 return 0 if max(@$r1[1, 3]) <= min(@$r2[1, 3]); # r2 is below r1 return 0 if max(@$r2[1, 3]) <= min(@$r1[1, 3]); # they must overlap: return 1; } # some tests: use Test::Simple 'no_plan'; ok rect_overlap [10, 10, 30, 30], [20, 20, 40, 60]; # do ok !rect_overlap [10, 10, 30, 30], [20, 40, 40, 60]; # don't ok rect_overlap [10, 10, 30, 30], [15, 15, 20, 20]; # inside
Re: Detecting control placement constraints in dialog resources - rectangle overlap checking
by idsfa (Vicar) on Mar 09, 2006 at 20:59 UTC
Re: Detecting control placement constraints in dialog resources - rectangle overlap checking
by shotgunefx (Parson) on Mar 09, 2006 at 21:31 UTC
    You want to double check my work here (though some use of rand() and Tk could make quick work of testing visually). I'm assuming X1 < X2 , Y1 < Y2
    my @box = ( { name => "Box 1", x1 => 0, y1 => 0, x2 => 320, y2 => 100 }, { name => "Box 2", x1 => 100, y1 => 10, x2 => 510, y2 => 500 }, { name => "Box 3", x1 => 20, y1 => 300, x2 => 120, y2 => 600 }, { name => "Box 4", x1 => 300, y1 => 301, x2 => 310, y2 => 600 }, ); sub bounding_box { my @box = sort { $a->{x1} <=> $b->{x1} } @_; # Sort on X axis for ( my $i = 0 ; $i < $#box ; $i++ ) { for ( my $j = $i + 1 ; $j < @box ; $j++ ) { warn "Checking $box[$i]->{name} against $box[$j]->{name}\n +"; if ( $box[$i]->{x2} > $box[$j]->{x1} ) { if ( $box[$i]->{y2} > $box[$j]->{y1} && $box[$i]->{y1} < $box[$j]->{y2} ) { warn " $box[$i]->{name} overlaps $box[$j]->{name}\ +n"; # Do something here } else { warn " $box[$i]->{name} doesn't overlap $box[$j]->{na +me}\n"; } } else { last; } } } }
    update My spaceship <=> was half missing. Whoops.

    -Lee
    "To be civilized is to deny one's nature."
Re: Detecting control placement constraints in dialog resources - rectangle overlap checking
by jdalbec (Deacon) on Mar 10, 2006 at 04:59 UTC
    My approach was in some sense the reverse of bart's. Two rectangles overlap if their defining inequalities have a common solution. The inequalities in x and y can be considered separately. If we have $r1[x1] <= $x <= $r1[x2] and $r2[x1] <= $x <= $r2[x2] (assuming topologically closed rectangles), a common solution is possible only if the larger x1 value is less than or equal to the smaller x2 value. This (rect_overlap_1) assumes of course that the x1 value is smaller than the x2 value in each rectangle. All of bart's test cases (plagiarized below) have this property. I've added a test case where the property is violated and rect_overlap_1 gets it wrong.

    However, we can remove that assumption by replacing x1 by min(x1,x2) and x2 by max(x1,x2) (rect_overlap_2). This gets the fourth test case correct.

    We can simplify further by using map to apply the min resp. max operation to the appropriate coordinates of the two rectangles (rect_overlap_3).

    At this point, the variables $r1 and $r2 become unnecessary and we can replace ($r1,$r2) throughout by @_. At this point, rect_overlap should be able to calculate correctly whether any number of rectangles have at least one point that is common to all of them.

    use List::Util qw(min max); sub x1{0} sub y1{1} sub x2{2} sub y2{3} sub rect_overlap_1 { my($r1,$r2) = @_; return max($$r1[x1],$$r2[x1]) <= min($$r1[x2],$$r2[x2]) && max($$r1[y1],$$r2[y1]) <= min($$r1[y2],$$r2[y2]); } # some tests: use Test::Simple 'no_plan'; ok rect_overlap_1 [10, 10, 30, 30], [20, 20, 40, 60]; # do ok !rect_overlap_1 [10, 10, 30, 30], [20, 40, 40, 60]; # don't ok rect_overlap_1 [10, 10, 30, 30], [15, 15, 20, 20]; # inside ok rect_overlap_1 [10, 10, 30, 30], [40, 20, 20, 60]; # do sub rect_overlap_2 { my($r1,$r2) = @_; return max(min(@$r1[x1,x2]),min(@$r2[x1,x2])) <= min(max(@$r1[x1,x2]),max(@$r2[x1,x2])) && max(min(@$r1[y1,y2]),min(@$r2[y1,y2])) <= min(max(@$r1[y1,y2]),max(@$r2[y1,y2])); } ok rect_overlap_2 [10, 10, 30, 30], [20, 20, 40, 60]; # do ok !rect_overlap_2 [10, 10, 30, 30], [20, 40, 40, 60]; # don't ok rect_overlap_2 [10, 10, 30, 30], [15, 15, 20, 20]; # inside ok rect_overlap_2 [10, 10, 30, 30], [40, 20, 20, 60]; # do sub rect_overlap_3 { my($r1,$r2) = @_; return max(map{min(@$_[x1,x2])}($r1,$r2)) <= min(map{max(@$_[x1,x2])}($r1,$r2)) && max(map{min(@$_[y1,y2])}($r1,$r2)) <= min(map{max(@$_[y1,y2])}($r1,$r2)); } ok rect_overlap_3 [10, 10, 30, 30], [20, 20, 40, 60]; # do ok !rect_overlap_3 [10, 10, 30, 30], [20, 40, 40, 60]; # don't ok rect_overlap_3 [10, 10, 30, 30], [15, 15, 20, 20]; # inside ok rect_overlap_3 [10, 10, 30, 30], [40, 20, 20, 60]; # do sub rect_overlap { return max(map{min(@$_[x1,x2])}@_) <= min(map{max(@$_[x1,x2])}@_) && max(map{min(@$_[y1,y2])}@_) <= min(map{max(@$_[y1,y2])}@_); } ok rect_overlap [10, 10, 30, 30], [20, 20, 40, 60]; # do ok !rect_overlap [10, 10, 30, 30], [20, 40, 40, 60]; # don't ok rect_overlap [10, 10, 30, 30], [15, 15, 20, 20]; # inside ok rect_overlap [10, 10, 30, 30], [40, 20, 20, 60]; # do ok rect_overlap [10, 10, 30, 30], [15, 15, 20, 20], [20, 20, 40, 60]; + # (20,20)