I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Overlapping Rectangles

04.25.2013
| 3733 views |
  • submit to reddit

Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Do you have code puzzlers that you'd like to share with the DZone community?  If so, please submit here. 

Determine if Two Rectangles are Overlapping

Write a function that takes two rectangles and determines if they overlap. The rectangle data structure is x, y, width, height.


Catch up on all our previous puzzlers here.

 

Comments

Frank Dietrich replied on Thu, 2013/04/25 - 2:54pm

Java

@Test
public void overlapTests() {
    Rectangle r1;
    Rectangle r2;

    r1 = new Rectangle(10, 10, 20, 20);
    r2 = new Rectangle(0, 0, 20, 20);
    Assert.assertTrue("r1 overlap r2", r1.intersects(r2));

    r1 = new Rectangle(10, 10, 5, 5);
    r2 = new Rectangle(0, 0, 20, 20);
    Assert.assertTrue("r1 overlap r2", r1.intersects(r2));

    r1 = new Rectangle(10, 10, 5, 5);
    r2 = new Rectangle(20, 20, 20, 20);
    Assert.assertFalse("r1 do not overlap r2", r1.intersects(r2));
}

Peter Huber replied on Fri, 2013/04/26 - 2:50am

@Frank Dietrich: +1 for knowing the API!

---

You can use a much-simplified Version of SAT (Seperating Axis Theorem) which works for any convex object composed of line segements.

Basically the simplified check is: Check if their projections on X-Axis overlap AND if their projections on Y-Axis overlap.

Assuming the rectangles have not been rotated the projections to the axis are very simple...

Let's say R1 is left of R2, then I have to check if their x-Axis-Segments overlap (I assume there's no negative width/heigth extents) - CX12: R1.x + R1.width > R2.x

Then let's say R1 is below R2 - again check if their y axis overlap - CY12: R1.y + R1.height > R2.y

To complete the check I have to add both checks with changed roles and "and" the both axis-related checks (CX12||CX21) && (CY12||CY21)


koen handekyn replied on Wed, 2013/05/01 - 2:29pm

in ruby
class Range # extend Range class
  def overlaps(other) !(self.max<other.begin or other.max<self.begin) end
end

Rectangle = Struct.new(:x, :y, :width, :height)
class Rectangle # a Rectangle is a struct with extras
  def xr() (x)..(x+width) end
  def yr() (y)..(y+height) end	
  def overlap(other) xr.overlaps(other.xr) && yr.overlaps(other.yr) end
end

# basic test

r1 = Rectangle.new(0,0,20,20)
r2 = Rectangle.new(10,5,20,20)
r3 = Rectangle.new(25,5,20,20)
r4 = Rectangle.new(25,25,20,20)

puts r1.overlap(r2) == true
puts r1.overlap(r3) == false
puts r1.overlap(r4) == false

Wissem Belguidoum replied on Wed, 2013/05/01 - 5:46pm

Java : 

public class OverlappingRectangles {
	
	public static void main(String[] args) {
		Rectangle r1 = new Rectangle(15, 15, 15, 15); 
		Rectangle r2 = new Rectangle(10, 10, 20, 20);
		System.out.println(areOverlapping(r1, r2)); 
	}
	
	private static boolean areOverlapping(Rectangle r1, Rectangle r2)  {
		List<Rectangle> recs = Arrays.asList(r1,r2); 
		Collections.sort(recs, new ByXComparator());
		boolean condition1 = (recs.get(0).getX() + recs.get(0).getWidth()) > recs.get(1).getX();   
		Collections.sort(recs, new ByYComparator());
		boolean condition2 = (recs.get(0).getY() + recs.get(0).getHeight()) > recs.get(1).getY();   
		return condition1 && condition2; 
	}

	static class ByXComparator implements Comparator<Rectangle> {
		@Override
		public int compare(Rectangle o1, Rectangle o2) {
			Double x1 = o1.getX(); 
			Double x2 = o2.getX();
			return x1.compareTo(x2);
		}
	}
	
	static class ByYComparator implements Comparator<Rectangle> {
		@Override
		public int compare(Rectangle o1, Rectangle o2) {
			Double y1 = o1.getY(); 
			Double y2 = o2.getY();
			return y1.compareTo(y2);
		}
	}
}

Knut W. Hansson replied on Wed, 2013/05/01 - 4:04pm in response to: Peter Huber

Well explained, Peter, but I think you might have to rethink your final check. In the example below, I beleive both CX12 and CY12 are true and therefore the final check should return true, but obviously the two rectangels don't overlap. What do you say?

Bob Beechey replied on Wed, 2013/05/01 - 9:40pm

Just the obvious in Python, using my own rect part class:

 

class rect:
    def __init__(self, xin=0,yin=0,length=10,height=10):
        self.x=xin
        self.y=yin
        self.length = length
        self.height = height
        
    def is_overlap(self, other):
        xdiff = abs(self.x-other.x)
        ydiff = abs(self.y-other.y)
        if self.x < other.x:
            xlap = xdiff < self.length
        else:
            xlap = xdiff < other.length
        if self.y < other.y:
            ylap = ydiff < self.height
        else:
            ylap = ydiff < other.height
        return xlap and ylap

r1 = rect(5,6,20,10)
r2=rect(6,15,20,10)
print(r1.is_overlap(r2))
r2=rect(7,18,20,10)
print(r1.is_overlap(r2))
print(r2.is_overlap(r1))


 

Andre Rieck replied on Thu, 2013/05/02 - 3:46am

#!/usr/bin/python

import unittest

def rectanglesOverlap(r1,r2) :
  """ Tests whether two Rectangles represented by two tuples (x,y,width,height) overlap."""
  X=0; Y=1; W=2; H=3;
  return r1[X] <= r2[X]+r2[W] and r1[X]+r1[W] >= r2[X] and \
            r1[Y] <= r2[Y]+r2[H] and r1[Y]+r1[H] >= r2[Y]

class TestOverlappingRectangles(unittest.TestCase) :

  def test_overlapping(self) :
    self.assertTrue(rectanglesOverlap((10,10,20,20),(0,0,20,20)))
    self.assertTrue(rectanglesOverlap((10,10,5,5),(0,0,20,20)))
    self.assertTrue(rectanglesOverlap((0,0,20,20),(10,5,20,20)))

  def test_non_overlapping(self) :
    self.assertFalse(rectanglesOverlap((10,10,5,5),(20,20,20,20)))
    self.assertFalse(rectanglesOverlap((0,0,20,20),(25,5,20,20)))
    self.assertFalse(rectanglesOverlap((0,0,20,20),(25,25,20,20)))

if (__name__=='__main__') :
  unittest.main()

Clinton Lee replied on Mon, 2013/05/06 - 8:43am

In F#

let within (x1, y1, width1, height1) (x2, y2, width2, height2) =
    let pointWithin start length point = (point >= start) && (point < (start + length))
    let lineWithin p1 l1 p2 l2 = (pointWithin p1 l1 p2) || (pointWithin p2 l2 p1)
    (lineWithin x1 width1 x2 width2) && (lineWithin y1 height1 y2 height2);;

Philippe Lhoste replied on Mon, 2013/05/27 - 6:34am in response to: Knut W. Hansson

Knut, I think you missed the last sentence, about changing roles and doing a AND.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.