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)
|