Finding overlapping rectangles

Posted on Updated on

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:

Two overlapping rectangles

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

Two overlapping rectangles

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.

One thought on “Finding overlapping rectangles

    poniard said:
    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s