Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Detect Overlapping Rectangles

 
Eric Pascarello
author
Rancher
Posts: 15385
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here is a problem I ran into at work with some Web development. I came up with a solution, but I am worndering if you can come up with a slicker method.

Given X1,Y1,W1,H1 and X2,Y2,W2,H2 figure out if two rectangles overlap each other.



Eric
 
Warren Dew
blacksmith
Ranch Hand
Posts: 1332
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If X1+H1 < X2 or X2+H2 < X1 or Y1+W1 < Y2 or Y2+W2 < Y1, they don't overlap (assuming heights and widths are positive). If none of these holds, they overlap. I don't think you can simplify it any further than that.
 
fred rosenberger
lowercase baba
Bartender
Pie
Posts: 12097
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
are we assuming the edges are always parallel/perpendicular to the x and y axis?
 
Eric Pascarello
author
Rancher
Posts: 15385
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes for this we are assuming they are parallel/perpendicular.

This is the basic idea I came up with, The first part forces the data to be in the correct orrientation to each other. This is done in JavaScript since that is what I was working with.





Eric
 
Nick George
Ranch Hand
Posts: 815
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Level two:

Detect overlap:

 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I replaced l and h with a and b respectively, because (1) l is a horrible name for a Java variable, and (2) to me names like l, h, w refer to the total height, length, or width. Since we're using a half-width and half height, I thought it better to remove a possible source of confusion. Anyway:

It might be possible to optimize this a bit more (deferring calculations of y and yMin, until they're really needed) but I think that would lose some clarity.
[ December 31, 2004: Message edited by: Jim Yingst ]
 
Nick George
Ranch Hand
Posts: 815
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
nicely done
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic