Triangle - Square intersection test in 2d

Question

How can I test if a triangle and a square is intersecting each other?

Is there any way of optimizing this, when we know it's a square instead of rectangle? Also, the square is axis aligned, so that should give some more boost to performance?

Or should I just break the square into triangles, and make triangle-triangle intersection check twice?

Edit: To clarify: I'm trying to check if those two shapes overlap each other in any way. So the triangle can be inside square, and square can be inside triangle, and it should return true for that too.

Answer 1

Compare your rectangle (or square) against each edge of the triangle, by taking the triangle's vertices and building the equation of a line for each edge, with a consistent ordering (clockwise or anti-clockwise around the triangle).

If the rectangle is entirely outside of the triangle on any edge, it does not intersect.

Test again with the rectangle's edges against the triangle.

There is potentially a boost to performance by knowing the rectangle is axis-aligned, as you can work out which corner is most likely to be inside the triangle, and test only that one, rather than testing all four corners.

Whether or not that is a win depends on implementation. Sometimes it can be faster to blindly check four coordinates rather than actually calculating the best one.

Checking the triangle against the rectangle should be easier as the line equations are simple tests against x or y when the rectangle is axis aligned.

This is a generalised form of separating axis test - finding a line or plane which separates the two objects, thus proving that they can't intersect. If you want more performance, you can find the nearest features of the two objects to work out the most appropriate line/plane to use, rather than trying all of them.

Answer 2

This is a classic collision detection problem. The shapes intersect if any of the following conditions are true:

• At least one vertex in the triangle is contained in the rectangle.
• At least one vertex of the rectangle is contained within the triangle.
• Any edge of the triangle intersects any edge of the rectangle.

The first two conditions cover the possibilities that one of the shapes is entirely contained with the other (in which case the edges will not intersect).

Some optimizations are possible.

• Compute the circumscribing circles of the shapes. Collisions can be ruled out if the distance between the centerpoints of the two shapes is greater than the sum of the radii of the circumscribing circles. Note that the centerpoint of the circle that circumscribes the rectangle is the midpoint of its diagonal. The centerpoint of a circumscribing circle for the triangle can be obtained by finding the intersection of the perpendicular bisectors of any two edges. Two ways to find a pessimistic estimates circles that will fully contain a triangle are (1) use the longest edge as the circle's diameter, and (2) create a bounding rectangle with corners at (mintx, minty), (mintx, maxty), (maxtx, maxty) and (maxtx, minty) where maxtx is the maximum X coordinate of any triangle corner, mintx is the minimum X coordinate of any triangle corner, etc.

• The shapes can be translated and rotated so that one of the vertices of the rectangle is located at the origin and the rectangle's base is along the positive X axis. This makes finding whether a vertex in the triangle is contained within the rectangle simple.

Translation, rotation, and line intersection are very well understood problems and you should have no problems finding suitable code here on stackoverflow, here on stackoverflow, or elsewhere on the web.

Hints:

• Translation is easy -- add or subtract the same value from every X or Y coordinate.

• Conceptually, rotation is easy -- for each point, convert to polar coordinates, add or subtract the rotation angle, then convert back to Cartesian coordinates. Since converting to/from polar coordinates is computationally expensive, you can do the rotation using the formulae:

  Xrot = X * cos(theta) - Y * sin(theta)
  Yrot = X * sin(theta) + Y * cos(theta)

• You can find the angle theta by taking a side of the rectangle, and noticing that

  theta = atan2(deltaX, deltaY)