Given 2 set of points
((x1,y1,z1),(x2,y2,z2),(x3,y3,z3)) and
((p1,q1,r1),(p2,q2,r2),(p3,q3,r3)) each forming a triangle in 3D space.
How will you find out whether these triangles intersect or not?
One obvious solution to this problem is to find the equation of the plane formed by each triangle. If the planes are parallel, then they don't intersect.
Else, find out the equation of line formed by the intersection of these planes using the normal vectors of these planes.
Now, if this line lies in both of the triangular regions, then these two triangles intersect, otherwise not.
Is there any other solution?
Best Answer
I've written code for exactly this problem, but at the moment I cannot find it :-/. [Used in a paper: "On reconstruction of polyhedra from slices," Int. J. Comput. Geom. & Appl., 6(1) 1996: 103-112.] However, it is easy enough to describe.
First, you need robust code to decide if a point is above, below, or on the plane determined by one triangle. See, e.g., the code described in Computational Geometry in C, for this low-level task (which amounts to computing the signed volume of a tetrahedron), and others following; or in many other equivalent sources. If all three points of one triangle are to one side of the other, the intersection is empty.
Let vertex $a$ of triangle $\triangle abc$ be above triangle $t'=\triangle a'b'c'$ and $b$ and $c$ below. (I'll ignore the "on" cases for simplicity, but of course you must deal with them carefully.) If $t$ and $t'$ intersect, then it must be that an edge of one intersects the other; this is the key observation (also made by anon in another answer). So either $ab \cap t'$ or $ac \cap t'$ is nonempty, or the analogous conditions with the role of the triangles reversed.
Checking these conditions requires (again robust) code to determine if a segment intersects a triangle. This can be computed by solving simultaneously a parametric equation for the segment and the plane containing $\triangle t'$, obtaining the point $p$ of intersection, and determining if $p$ falls within $\triangle t'$. The latter is a separate and easy task.
So the whole can be accomplished by a number of confined, controlled, elementary computations.