0

I would like to check if two square are intersecting with each other. My idea is this

for (i = 0; i < 4; i++)
   for (j = 0; j < 4; j++) {
       bool x = check line(i) of first square intersect with 
       line (j) of the second square
       if (x) return;
   }

any idea to optimize this code?

Xeo
  • 129,499
  • 52
  • 291
  • 397
user2081740
  • 81
  • 1
  • 3
  • 9

1 Answers1

5

You don't have to loop through all coordinates to check if two squares intersect.

Here's a simple solution which will work as long as the squares are not rotated.

Say that you represent a square by its top left corner coordinate and its side length. Let aX and aY represent the coordinates and aLen the side length of square A, and vice versa for square B.

Then to check if square B intersects with square A evaluate this:

(aX < (bX + bLen) && (aX + aLen) > bX)
&& (aY < (bY - bLen) && (aY - aLen) > bY)

In other words, there are four possible scenarios and you check if either of square B's corners are within the X-range of square A and that either of square B's corners are within the Y-range of square A.

(Y)
 ^
 |             1:                        2:
 |       +--------+                   +--------+
 |       |        |                   |        |
 |       |   A +--|-----+       +-----+--+ A   |
 |       |     |  |     |       |     |  |     |
 |       +-----+--+ B   |       |   B +--+-----+
 |             |        |       |        |
 |             +--------+       +--------+
 |
 |             3:                        4:
 |       +--------+                   +--------+
 |       |        |                   |        |
 |       |   B +--|-----+       +-----+--+ B   |
 |       |     |  |     |       |     |  |     |
 |       +-----+--+ A   |       |   A +--+-----+
 |             |        |       |        |
 |             +--------+       +--------+
 |
 +-------------------------------------------------> (X)

For more info see this answer of a similar question: Determine if two rectangles overlap each other?

Community
  • 1
  • 1
Felix Glas
  • 15,065
  • 7
  • 53
  • 82
  • 3
    The proposed formula seems too complicated, a much simpler exists: http://silentmatt.com/rectangle-intersection/ . See also the linked possible duplicate question. – Ali Aug 11 '13 at 15:19
  • @Ali, this is the same thing, just expressed in terms of corners and sizes – Johan Lundberg Aug 11 '13 at 15:24
  • 1
    @JohanLundberg Please check the history: the answer has been edited in the meantime. The original formula was too complicated which is no longer visible. – Ali Aug 11 '13 at 15:31