Algorithm to detect intersection of two rectangles?

by

The standard method would be to do the separating axis test (do a google search on that).

In short:

  • Two objects don’t intersect if you can find a line that separates the two objects. e.g. the objects / all points of an object are on different sides of the line.

The fun thing is, that it’s sufficient to just check all edges of the two rectangles. If the rectangles don’t overlap one of the edges will be the separating axis.

In 2D you can do this without using slopes. An edge is simply defined as the difference between two vertices, e.g.

  edge = v(n) - v(n-1)

You can get a perpendicular to this by rotating it by 90°. In 2D this is easy as:

  rotated.x = -unrotated.y
  rotated.y =  unrotated.x

So no trigonometry or slopes involved. Normalizing the vector to unit-length is not required either.

If you want to test if a point is on one or another side of the line you can just use the dot-product. the sign will tell you which side you’re on:

  // rotated: your rotated edge
  // v(n-1) any point from the edge.
  // testpoint: the point you want to find out which side it's on.

  side = sign (rotated.x * (testpoint.x - v(n-1).x) + 
               rotated.y * (testpoint.y - v(n-1).y);

Now test all points of rectangle A against the edges of rectangle B and vice versa. If you find a separating edge the objects don’t intersect (providing all other points in B are on the other side of the edge being tested for – see drawing below). If you find no separating edge either the rectangles are intersecting or one rectangle is contained in the other.

The test works with any convex polygons btw..

Amendment: To identify a separating edge, it is not enough to test all points of one rectangle against each edge of the other. The candidate-edge E (below) would as such be identified as a separating edge, as all points in A are in the same half-plane of E. However, it isn’t a separating edge because the vertices Vb1 and Vb2 of B are also in that half-plane. It would only have been a separating edge if that had not been the case
http://www.iassess.com/collision.png

More Related Contents:

  1. How do you find a point at a given perpendicular distance from a line?
  2. How to determine if a point is in a 2D triangle? [closed]
  3. Circle line-segment collision detection algorithm?
  4. How to calculate an angle from three points? [closed]
  5. Sort points in clockwise order?
  6. How do you calculate the average of a set of circular data? [closed]
  7. Precise subpixel line drawing algorithm (rasterization algorithm)
  8. Puzzle: Find largest rectangle (maximal rectangle problem)
  9. Calculate largest inscribed rectangle in a rotated rectangle
  10. Circle-circle intersection points
  11. Sort Four Points in Clockwise Order
  12. Determining if two line segments intersect? [duplicate]
  13. Calculating the position of points in a circle
  14. Find if a point is inside a convex hull for a set of points without computing the hull itself
  15. determine if a point sits inside an arbitrary shape?
  16. How can I perform Collision Detection on rotated rectangles? [closed]
  17. Location of highest density on a sphere
  18. Equation for testing if a point is inside a circle
  19. Mapping two integers to one, in a unique and deterministic way
  20. Select k random elements from a list whose elements have weights
  21. What is the fastest algorithm to calculate the minimum distance between two sets of points?
  22. Is there an efficient algorithm to generate a 2D concave hull?
  23. Modulus power of big numbers
  24. How to find two most distant points?
  25. Fastest algorithm for circle shift N sized array for M position
  26. Mesh generation from points with x, y and z coordinates
  27. How to find distance from the latitude and longitude of two locations?
  28. How do I determine whether my calculation of pi is accurate?
  29. JavaScript: Calculate the nth root of a number
  30. Optimized low-accuracy approximation to `rootn(x, n)`

Leave a Comment