### Finding overlapping rectangles

This is a classic quick programming puzzle: write a function that, given two rectangles, will determine if the triangles overlap. I found this puzzle over on http://leetcode.com/2011/05/determine-if-two-rectangles-overlap.html, and thought it was worth talking about *because the solution is wrong*, and it was interesting to me because it shows how thinking about a domain can influence your implementation of behaviour.

The mistake made by the original author is with one of the assumptions / interpretations made during their reasoning process. They said “when two rectangles overlap, one rectangle’s corner point(s) must [be contained within] the other rectangle”. This appears reasonable, given the example below:

But this is actually not the case. Here are two overlapping rectangles where no corners are contained in any other rectangle:

To me, this problem was caused by the author’s defining a rectangle as two points (that imply the existence of two other points). When I started to think about the problem I preferred to think of a rectangle as a combination of a centre point, a width, and a height. In F# such a domain might look like this:

type Point = { x : float; y : float } type Rectangle = { centre : Point; width : float; height : float }

Once I had visualised my types it became obvious that you could deduce overlapping shapes from knowledge of their geometry and the distance between their centre points. In the case of rectangles, given distances dx and dy (the absolute difference between the x and y coordinates of the two shapes, respectively), dx must be less than (or equal to?) the average width of the two rectangles (half of rectangle1’s width and half of rectangle2’s width), and dy must be less than the average height. This gives us the function:

let overlapping r1 r2 = let deltaX = r1.centre.x - r2.centre.x |> Math.Abs let deltaY = r1.centre.y - r2.centre.y |> Math.Abs let averageWidth = (r1.width + r2.width) / 2. let averageHeight = (r1.height + r2.height) / 2. deltaX <= averageWidth && deltaY <= averageHeight

I find this easier to reason with that the solution given to the original puzzle, and it has the added benefit of being correct even for rectangles who wholly overlap one another. One of the benefits of the centre-and-dimensions method of representing a rectangle is that it’s easy to carry over to other shapes. Here’s the same idea expanded to a circle:

type Circle = { centre : Point; radius : float } with static member overlapping c1 c2 = let deltaX, deltaY = Point.xyDeltas c1.centre c2.centre let distance = sqrt ((deltaX ** 2.) + (deltaY ** 2.)) distance < (c1.radius + c2.radius)

Here, instead of examining the x and y deltas individually we use Pythagoras to calculate the distance between the centre of the two circles. If the distance is less that the sum of the two radii then the circles overlap.

2015-05-20 at 04:59

Simply desire to say your article is as surprising. The clarity in your post is

just great and i could assume you are an expert on this subject.

Fine with your permission let me to grab your RSS feed to keep updated with forthcoming post.

Thanks a million and please continue the enjoyable work.