What's the most efficient way to detect triangle-triangle intersections ?

Question

How can I tell whether two triangles intersect in 2D Euclidean space? (i.e. classic 2D geometry) given the (X,Y) coordinates of each vertex in each triangle.

Answer 1

One way is to check if 2 sides of triangle A intersect with any side of triangle B.

There is the case where a triangle A may be inside triangle B.
In that case see for example: Point in triangle test.

When we test collisions on polygons we also have a surrounding rectangle for our polygons. So we first test for rectangle collisions and if there is a hit we proceed with polygon collision detection.

Answer 2

What you're really looking for is a "Point in Polygon" algorithm. If any of the points of one triangle are in the other, they are intersecting. Here is a good question to check out.

http://stackoverflow.com/questions/217578/point-in-polygon-aka-hit-test

Answer 3

For this type of problem there are many algorithms in Graphics Gems (http://tog.acm.org/resources/GraphicsGems/) and althought they are in C they should recode very easily. In your current case you could use http://tog.acm.org/resources/GraphicsGems/gemsii/xlines.c and iterate over all lines in boith triangles (i.e. 9 possible intersections). I haven't looked but there may even be algorithms that solve your problem directly.

Answer 4

As stated, you'll need to check that a point is inside a triangle. The simplest way to check if a point is inside a closed polygon is to draw a straight line in any direction from the point and count how many times the line crosses a vertex. If the answer is odd then the point is in the polygon, even, then it's outside.

The simplest straight line to check is the one going horizontally to the right of the point (or some other perpendicular direction). This makes the check for vertex crossing nearly trivial. The following checks should suffice:

• Is the point's y-coordinate between the y-coordinates of the two end points of the vertex? No, then doesn't cross.

• Is the point's x-coordinate greater than the furthest right end point of the vertex? Yes, then doesn't cross.

• Is the point's x-coordinate less than the furthest left end point of the vertex? Yes, then does cross.

• If the cases above fail, then you can use the cross product of the vector representing the vertex and a vector formed from the end of the vertex to the point. A negative answer will indicate the point lies on one side of the vertex, a positive answer on the other side of the vertex, and a zero answer on the vertex. This works because a cross product involves taking the sine of two vectors.