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