Triangle - square intersection test in 2d

Question

How can I check if a triangle and a square intersect with each other?

Is there a way to optimize this when we know this is a square instead of a rectangle? Also, the square is axially aligned, so what should this improve performance?

Or should I just split the square into triangles and cross the triangle-triangle twice?

Edit:. To clarify: I'm trying to check if these two figures overlap with each other. Thus, a triangle can be inside a square, and a square can be inside a triangle, and it should also return true.

Answer 1

Compare your rectangle (or square) with each edge of the triangle, taking triangular vertices and constructing a line equation for each edge, with sequential ordering (clockwise or counterclockwise around the triangle).

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

Repeat the test with the edges of the rectangle relative to the triangle.

There is a potential opportunity to increase productivity, knowing that the rectangle is aligned along the axis, since you can determine which angle is most likely to be inside the triangle, and check only this one, and not test all four corners.

Regardless of whether it wins, it depends on the implementation. Sometimes it can be faster to blindly check the four coordinates, rather than actually calculate the best.

Testing a triangle for a rectangle should be simpler, because linear equations are simple tests against x or y when the rectangle is aligned on the axis.

This is a generalized form of analysis of the dividing axis - the search for a line or plane that separates two objects, which proves that they cannot intersect. If you need better performance, you can find the nearest functions of two objects to develop the most suitable line / plane for use, and not for everyone.

Answer 2

This is a classic collision detection problem. Forms intersect if one of the following conditions is true:

• A rectangle contains at least one vertex in a triangle.
• At least one vertex of the rectangle is contained in the triangle.
• Any edge of a triangle intersects any edge of a rectangle.

The first two conditions cover the possibility that one of the figures is completely contained in the other (in this case, the edges will not intersect).

Some optimizations are possible.

• Calculate circles describing the shapes. Collisions can be eliminated if the distance between the center points of the two shapes is greater than the sum of the radii of the circles of the environment. Notice that the center point of the circle that borders the rectangle is the middle of its diagonal. The center point of a circle for a triangle can be obtained by finding the intersection of the perpendicular bisectors of any two edges. There are two ways to find pessimistic circles of estimates that will completely contain a triangle: (1) use the longest edge as the diameter of the circle and (2) create a bounding box with corners in (mintx, minty), (mintx, maxty), (maxtx, maxty ) and (maxtx, minty), where maxtx is the maximum X coordinate of any corner of the triangle, mintx is the minimum X coordinate of any corner of the triangle, etc.

• Shapes can be translated and rotated so that one of the vertices of the rectangle is at the origin and the base of the rectangle is along the positive X axis. This allows you to determine whether the triangle contains a vertex.

Translating, rotating, and crossing lines are very well-understood problems, and you won’t need to find https://stackoverflow.com/a/2129609/212829 , ... or another place on the Internet.

Tips:

• The translation is simple - add or subtract the same value from each X or Y coordinate.

• Rotation is conceptually easy - for each point it is converted to polar coordinates, adds or subtracts the rotation angle, and then it is converted back to Cartesian coordinates. Since converting to / from polar coordinates is computationally expensive, you can do the rotation using the formulas:

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

• You can find the angle of theta by taking the side of the rectangle and noting that

  theta = atan2 (deltaX, deltaY)

Answer 3

As a refinement to Jay Elston’s answer, you can divide the Square / Quadrangle into two triangles, and then use the Möller-Trumbore intersection algorithm to compare the inclusion of vertices. If you read the published paper , there is an implementation of the C algorithm at the end.

This will allow you to verify the inclusion of vertices. Then use one of the Jay links for intersections.