Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
"Now, if this line lies in both of the triangular regions, then these two triangles intersect, otherwise not." Not really... If the line lies in both triangular regions, then each triangle meets the line in a line segment, and only if those two line segments have points in common do the triangles intersect. –  Rahul Aug 18 '11 at 22:24
    
I was going to say the two triangles could be parametrized as closed curves and then invoke the linking coefficient, but I don't think the formula applies when the curves are only piecewise differentiable. –  anon Aug 19 '11 at 0:02

4 Answers 4

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.

share|improve this answer

I haven't had time to check the other answers in detail, so this may be equivalent... but the standard method of doing this is by the "separating axis theorem", which basically says that two convex objects are separated if there exists an axis so that the projections of the objects onto the axis do not overlap.

In the case of two triangles this amounts to just a couple of cross products, dot products and interval checks, which can be done very efficiently. A quick Google search turned up this:

http://www.geometrictools.com/Documentation/MethodOfSeparatingAxes.pdf

share|improve this answer
    
This is a very clean method, and Dave Eberly (in the document to which you link) explains it clearly. Thanks! –  Joseph O'Rourke Aug 19 '11 at 15:01

One asks that the linear system of five equations with six unknowns $$ a_1+a_2+a_3=1,\quad u_1+u_2+u_3=1,\quad a_1x_1+a_2x_2+a_3x_3=u_1p_1+u_2p_2+u_3p_3, $$ and $$ a_1y_1+a_2y_2+a_3y_3=u_1q_1+u_2q_2+u_3q_3,\quad a_1z_1+a_2z_2+a_3z_3=u_1r_1+u_2r_2+u_3r_3, $$ has some solutions such that every $a_i$ and every $u_j$ is nonnegative.

share|improve this answer

Here is a geometrically flavored solution.

First test to see whether or not the triangles are parallel. If they are, then find the minimum distance $d$ between the two planes they occupy; if $d\ne0$ then the triangles do not intersect, if $d=0$ then our problem reduces to the planar case which we'll analyze shortly. For any $x\in\pi_1,y\in\pi_2$, two parallel planes $\pi_1$ and $\pi_2$ with shared normal vector $n$ have zero distance from each other if and only if $(x-y)\perp n$. The easiest selection would be to make $x,y$ vertices from distinct triangles.

In the planar case, two triangles intersect if and only if there is a pair of edges, one from each triangle, which intersect. Therefore the problem reduces to testing whether or not two line segments intersect (for nine possible pairs of segments, though only a maximum of seven need be tested for). This can be achieved with a basic least-squares method.

If the triangles are not parallel, then they intersect if and only if at least one edge of one of the triangles intersects the other triangle, and this intersection point (for a given edge) will be unique. Thus we will say the second triangle is affixed to the plane $\pi$, and because of symmetry only test whether a single edge from the first triangle intersects $\pi$, this edge having endpoints $a$ and $b$ (in reality, this test may need to be applied up to three times, once for each edge). Further, use an affine transformation on the entire setup so the second triangle has the origin $O$ as a vertex for convenience.

$\hskip 1in $ triangle edge intersection

Every point on the green line will be of the form $r\mathbf{a}+(1-r)\mathbf{b}, r\in[0,1]$. All points inside of the black triangle will be of the form $s\mathbf{u}+t\mathbf{v}, s,t\in[0,1]$. Equating the two expressions will have a unique solution as the point of intersection between the green line and the plane the black triangle lies on. Let $X$ denote the $3\times3$ matrix with columns $\mathbf{b}-\mathbf{a}$, $\mathbf{u}$, and $\mathbf{v}$. Then the point of intersection lies within the triangle if and only if $X^{-1} \mathbf{b} \in [0,1]^3$.

share|improve this answer
    
I believe our two prescriptions are fundamentally the same, although I think it is not so much the parallelness of the triangles that matters, but rather whether all three vertices of one are to the same side of the plane determined by the other. –  Joseph O'Rourke Aug 19 '11 at 0:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.