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)
[download]

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.