3

I need to calculate the overlap (amount or yes/no) that two rectangles make on a special x/y grid. The grid is 500x500 but the sides and corners connect (are continuous). So the next point after 499 becomes 0 again.

In a previous question I asked for a way to calculate the distance between two points in this grid. This turned out to be the Euclidean distance:

sqrt(min(|x1 - x2|, gridwidth - |x1 - x2|)^2 + min(|y1 - y2|, gridheight - |y1-y2|)^2)

What is the good mathematical way of calculating if two rectangles (defined by a point (x,y), width and height) have overlap in this grid?

Rectangle-1 ([x=0,y=0], w=20, h=20) and Rectangle-2 ([x=495,y=0], w=10, h=10) should have overlap. The overlapping rectangle (not really needed but) should be ([x=0,y=0], w=5, h=10)

Ropstah
  • 17,538
  • 24
  • 120
  • 194
  • I can tell you how to do it in 3D space... it will work also in 2D but I don't know if it is acceptable for you. Basically the idea is to look at the 2 planes that the rectangles are on. Find the intersection of those planes and see if the line that makes the planes intersection intersects with both rectangles... Want to hear the math? – Cipi Jan 24 '10 at 15:08
  • I'm very interested in the math. I understand what you're saying, and I can deduct the math, but i cannot produce it... Will a 2d approach be less intensive on CPU power? – Ropstah Jan 24 '10 at 15:11
  • CPU power?! You can calculate that on a Casio Watch CPU. xD It's really simple math... Let me test this that I have in mind. You are producing it in a C-like OO language? – Cipi Jan 24 '10 at 15:15
  • I'm a bit confused when you say "Rectangle-1 ([x=0,y=0], w=20, h=20) and Rectangle-2 ([x=495,y=0], w=10, h=10) should have overlap." If one is at the origin and the other is way out at 495 on the x axis, they would not overlap. – Chris Upchurch Jan 24 '10 at 15:17
  • Actualy, all this is answered here: http://stackoverflow.com/questions/115426/algorithm-to-detect-intersection-of-two-rectangles – Cipi Jan 24 '10 at 15:19
  • @Chris: please read the first 3 lines of my question. – Ropstah Jan 24 '10 at 15:23
  • @Cipi: I'm looking for a very efficient function which does this calculation almost continuously. Isn't that other answer way to broad (rotation etc..). And does it take into account my requirements where the grid should be continuous? – Ropstah Jan 24 '10 at 15:27

1 Answers1

3

First, compute the x and y range for each rectangle (because you have a torus geometry do it mod gridsize).

So, given your Rectangle-1, compute:

x1 = x = 0, x2 = x + w = 20
y1 = y = 0, y2 = y + h = 20

Same for Rectangle-2:

x3 = 495, x4 = 505 mod 500 = 5
y3 = 0,   y4 = 10

Create the x and y "regions" for each rectangle:

Reactangle-1: x-regions: (0, 20)
              y-regions: (0, 20)

Rectangle-2:  x-regions: (495, 500), (0, 5)
              y-regions: (0, 10)

If any (both) x and y regions between the two rectangles have a non-null intersection, then your rectangles overlap. Here the (0, 20) x-region of Rectangle-1 and the (0, 5) x-region of Rectangle-2 have a non-null intersection and so do the (0, 20) and (0, 10) y-regions.

3lectrologos
  • 9,469
  • 4
  • 39
  • 46