32
\$\begingroup\$

I received the following question in a technical interview today (for a devops/SRE position):

Write a function which returns true if the two rectangles passed to it as arguments would overlap if drawn on a Cartesian plane. The rectangles are guaranteed to be aligned with the axes, not arbitrarily rotated.

I pretty much blew the whole thought process for how to approach the question I wasn't thinking of cases where, for example, one rectangle might be enclosed entirely within the other or of cases where a short wide rectangle might cross wholly through a taller, narrower one forming some sort of cross --- so I was off on a non-productive tangent thinking about whether any corner of either rectangle was within the bounding box of the other.

Naturally as soon as I got home, having let the problem settle more in my mind, I was able to write something which seems reasonably elegant and seems to work (for the test cases I've tried so far).

Rectangle Overlap Test Cases

This graphic (which took far longer to create than the code, and I don't even know how to make Inkscape show the gridlines in the saved image as it's showing in my working canvas) shows the simplest obvious cases: red/aqua overlapping by a corner, blue completely enclosing fuschia and green/yellow overlapping but without any corner enclosed within the other. My test code uses red/blue, blue/green and similar combinations as the non-overlapping test cases, including those which would overlap only in horizontal or vertical dimensions but are clear in the other dimension.

My thought process, when I got home and sat down with a keyboard was as follows:

We only care about edges, ultimately. So my Rect() class store just the X scalar of the left and right edges, and the Y scalar of top and bottom edges.

For rectangles to overlap there must be some overlap in both the horizontal and vertical directions. So it should be sufficient to just test if either the left or right edge of the first rectangle argument is to the right or left (respectively) of the other rectangle's opposite edge ... and likewise for top and bottom.

Here's the code for creating Points and Rectangles. Rectangles are only instantiated using corner points; points are actually trivial and could be named tuples if I were inclined.

#/usr/bin/env python
class Point(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Rect(object):
    def __init__(self, p1, p2):
        '''Store the top, bottom, left and right values for points 
               p1 and p2 are the (corners) in either order
        '''
        self.left   = min(p1.x, p2.x)
        self.right  = max(p1.x, p2.x)
        self.bottom = min(p1.y, p2.y)
        self.top    = max(p1.y, p2.y)

Note that I'm setting left to the minimum of the two x co-ordinates, right to the max, and so on. I'm not doing any error checking here for zero area rectangles here, they would be perfect valid for the class and probably, arguably, be valid the the same collision "overlap" function. Points and lines would simply be infinitesimal "rectangles" for my code. (However, no such degenerate cases are in my test suite).

Here's the overlap function:

#/usr/bin/env python 

def overlap(r1,r2):
    '''Overlapping rectangles overlap both horizontally & vertically
    '''
    hoverlaps = True
    voverlaps = True
    if (r1.left > r2.right) or (r1.right < r2.left):
        hoverlaps = False
    if (r1.top < r2.bottom) or (r1.bottom > r2.top):
        voverlaps = False
    return hoverlaps and voverlaps

This seems to work (for all my test cases) but it also looks wrong to me. My initial attempt was to start with hoverlaps and voverlaps as False, and selectively set them to True using conditions similar to these shown (but with the inequality operators reversed).

So, what's a better way to render this code?

Oh, yeah: here's the test suite at the end of that file:

#!/usr/bin/env python
# if __name__ == '__main__':

p1 = Point(1,1)
p2 = Point(3,3)
r1 = Rect(p1,p2)
p3 = Point(2,2)
p4 = Point(4,4)
r2 = Rect(p3,p4)

print "r1 (red),r2 (aqua): Overlap in either direction:"
print overlap(r1,r2)
print overlap(r2,r1)

p5 = Point(3,6)     # overlaps horizontally but not vertically
p6 = Point(12,11)
r3 = Rect(p5,p6)

print "r1 (red),r3 (blue): Should not overlap, either way:"
print overlap(r1,r3)
print overlap(r3,r1)

print "r2 (aqua),r3 (blue: Same as that"
print overlap(r2,r3)
print overlap(r3,r2)

p7 = Point(7,7)
p8 = Point(11,10)
r4 = Rect(p7,p8)    # completely inside r3

print "r4 (fuschia) is totally enclosed in r3 (blue)"
print overlap(r3,r4)
print overlap(r4,r3)

print "r4 (fuschia) is nowhere near r1 (red) nor r2 (aqua)"
print overlap(r1,r4)

p09 = Point(13,11)
p10 = Point(19,13)
r5  = Rect(p09,p10)

p11 = Point(13,9)
p12 = Point(15,14)
r6  = Rect(p11,p12)

print "r5 (green) and r6 (yellow) cross without corner overlap"
print overlap(r5,r6)
print overlap(r6,r5)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ By the way, please excuse the horribly amateurish graphic. I'm NOT a graphics guy and had to go fetch Inkscape to even manage this pathetic thing here. \$\endgroup\$
    – Jim Dennis
    Sep 16, 2013 at 8:47
  • \$\begingroup\$ The problem was posed with the explicit constraint that the rectangles would be aligned along the axes. \$\endgroup\$
    – Jim Dennis
    Sep 16, 2013 at 14:43
  • \$\begingroup\$ Incidentally if it were not the case that the rectangles were constrained to be aligned to the axes then I suspect the most obvious approach would be a series of tests, solving for each vertex of each (polygon) to find it its enclosed by the other (a series and then of each line segment against the others (any intersection means overlap). The first test is for the case where one completely encloses the other and the tests are all solutions to linear/algebraic equations. If I'm right that approach generalizes to all planar polygons. \$\endgroup\$
    – Jim Dennis
    Sep 17, 2013 at 7:25

3 Answers 3

18
+50
\$\begingroup\$

You have common code, which moreover has applications beyond this one, so should you not pull it out into a function? Then you can reduce overlap to

def overlap(r1, r2):
    '''Overlapping rectangles overlap both horizontally & vertically
    '''
    return range_overlap(r1.left, r1.right, r2.left, r2.right) and range_overlap(r1.bottom, r1.top, r2.bottom, r2.top)

Now, the key condition encapsulated by range_overlap is that neither range is completely greater than the other. A direct refactor of the way you've expressed this is

def range_overlap(a_min, a_max, b_min, b_max):
    '''Neither range is completely greater than the other
    '''
    overlapping = True
    if (a_min > b_max) or (a_max < b_min):
        overlapping = False
    return overlapping

For such a simple condition I would prefer to use not rather than if-else assignment. I would also reorder the second condition to exhibit the symmetry more clearly:

def range_overlap(a_min, a_max, b_min, b_max):
    '''Neither range is completely greater than the other
    '''
    return not ((a_min > b_max) or (b_min > a_max))

Of course, de Morgan's laws allow rewriting as

def range_overlap(a_min, a_max, b_min, b_max):
    '''Neither range is completely greater than the other
    '''
    return (a_min <= b_max) and (b_min <= a_max)

I think that the last of these is the most transparent, but that's an issue of aesthetics and you may disagree.

Note that I've assumed throughout, as you do, that the rectangles are closed (i.e. that they contain their edges). To make them open, change > to >= and <= to <.

\$\endgroup\$
4
  • \$\begingroup\$ Practical use of de Morgan's Laws was the deciding factor in getting this bounty. (Though a link and proper spelling would have been nice, too). I really should remember to consider those when I'm trying to untangle more complicated boolean expressions in my code. \$\endgroup\$
    – Jim Dennis
    Sep 26, 2013 at 10:32
  • \$\begingroup\$ @JimDennis, I'm not sure what complaint you have against my spelling. Fair point on the link, though: I shouldn't assume that everyone has studied formal logic. \$\endgroup\$ Sep 26, 2013 at 11:12
  • \$\begingroup\$ It was more of a teasing nitpick than a real complaint. I could have sworn that you left out the "de" in "de Morgan." \$\endgroup\$
    – Jim Dennis
    Sep 26, 2013 at 11:21
  • \$\begingroup\$ Nice answer, however one problem with this solution is that it is easy to mix up the arguments to range_overlap (is it amin, amax, bmin, bmax, or amin, bmin, amax, bmax, or ...?) \$\endgroup\$
    – mkrieger1
    Feb 1, 2018 at 11:32
10
\$\begingroup\$

I would simply apply a logic transformation. Here's your original, verbatim:

def overlap(r1,r2):
    '''Overlapping rectangles overlap both horizontally & vertically
    '''
    hoverlaps = True
    voverlaps = True
    if (r1.left > r2.right) or (r1.right < r2.left):
        hoverlaps = False
    if (r1.top < r2.bottom) or (r1.bottom > r2.top):
        voverlaps = False
    return hoverlaps and voverlaps

Each of the variables is True unless you set it to False, so you could just negate each condition.

def overlap(r1,r2):
    hoverlaps = not((r1.left > r2.right) or (r1.right < r2.left))
    voverlaps = not((r1.top < r2.bottom) or (r1.bottom > r2.top))
    return hoverlaps and voverlaps

Applying De Morgan's Laws

def overlap(r1,r2):
    hoverlaps = not(r1.left > r2.right) and not(r1.right < r2.left)
    voverlaps = not(r1.top < r2.bottom) and not(r1.bottom > r2.top)
    return hoverlaps and voverlaps

You can eliminate the "not"s by reversing the inequalities.

def overlap(r1,r2):
    hoverlaps = (r1.left <= r2.right) and (r1.right >= r2.left)
    voverlaps = (r1.top >= r2.bottom) and (r1.bottom <= r2.top)
    return hoverlaps and voverlaps

Personally, I would prefer to rearrange my inequalities for parallelism. Also, I would move the function into the Rect class. Final answer:

class Rect(object):
    def __init__(p1, p2):
        ...

    @staticmethod
    def overlap(r1, r2):
        '''Overlapping rectangles overlap both horizontally & vertically
        '''
        h_overlaps = (r1.left <= r2.right) and (r1.right >= r2.left)
        v_overlaps = (r1.bottom <= r2.top) and (r1.top >= r2.bottom)
        return h_overlaps and v_overlaps

I'd resist the urge to do anything more than that, because I think you would be running into diminishing returns.

\$\endgroup\$
0
0
\$\begingroup\$

I just had a bit of a play with this. The solution is at the bottom, but I'll show the steps I took.

Using a visual determination of whether two rectangles overlap.

For rectangles that do overlap:

#1st rectangle
#  (x1,y1)
#  (x2,y2)
#x1,y1 < x2,y2

#2nd rectangle
#  (x3,y3)
#  (x4,y4)
#x3,y3 <x4y4

def rectangleOverlap():
  x1=2
  y1=3
  x2=111
  y2=99
  x3=41
  y3=1
  x4=90
  y4=121
#find largest x (X) and largest y (Y)
  if y4>y2:
    Y=y4
  else:
    Y=y2
  if x4>x2:
    X=x4
  else:
    X=x2
  pic = makeEmptyPicture (X,Y)
  for y in range (0,Y-1):
    for x in range (0,X-1):
      px = getPixel(pic, x,y)

      if (y>y1 and y<y2) and (x>x1 and x<x2):
        setColor(px,makeColor(255,255,0))
      if (y>y3 and y<y4) and (x>x3 and x<x4):
        setColor(px,makeColor(0,255,255))  
      if (y>y1 and y<y2) and (x>x1 and x<x2)  and (y>y3 and y<y4) and (x>x3 and x<x4):
        setColor(px,makeColor(255,0,0))

  show(pic)

rectanlges

Clearly the overlap can be seen here in red.


For rectangles that do not overlap:

def rectangleOverlap():
  x1=2
  y1=3
  x2=11
  y2=9
  x3=41
  y3=11
  x4=90
  y4=121
#find largest x (X) and largest y (Y)
  if y4>y2:
    Y=y4
  else:
    Y=y2
  if x4>x2:
    X=x4
  else:
    X=x2
  pic = makeEmptyPicture (X,Y)
  for y in range (0,Y-1):
    for x in range (0,X-1):
      px = getPixel(pic, x,y)
      if (y>y1 and y<y2) and (x>x1 and x<x2):
        setColor(px,makeColor(255,255,0))
      if (y>y3 and y<y4) and (x>x3 and x<x4):
        setColor(px,makeColor(0,255,255))  
      if (y>y1 and y<y2) and (x>x1 and x<x2)  and (y>y3 and y<y4) and (x>x3 and x<x4):
        setColor(px,makeColor(255,0,0))

   show(pic)

enter image description here


So if we focus on the part that overlaps:

if (y>y1 and y<y2) and (x>x1 and x<x2)  and (y>y3 and y<y4) and (x>x3 and x<x4):

Trim down our ranges, to optimise code.

def rectangleOverlap():

  for y in range (y1,y2):
    for x in range (x1,x2):

      if (y>y3 and y<y4) and (x>x3 and x<x4):
        print "overlap"
        return true

I'm no expert, I enjoy this aspect of python.. hope it helps

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Aaaargh! JPEGs! \$\endgroup\$ Dec 9, 2013 at 17:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.