Hp 50g Math question: Intersection of 2 triangulars

[Han]

For the 3D case, you have a lot of the right calculations already. I will use \( \vec{x}_i \) to mean both a vector as well as a point.

To test whether or not the second triangle is on the same plane as the first triangle, we only only need to do a very straightforward set of computations. If \(H: \vec{n} \cdot (\vec{x}-\vec{x}_1) = 0 \) is the equation of the plane \(H\) containing triangle one (where \( \vec{x}_1 \) is a vertex of triangle one), then we simply need to check whether
\[ \vec{n} \cdot (\vec{x}_i -\vec{x}_1) =0 \]
for \(i = 4, 5, 6 \). Within this check we can also deduce whether the second triangle even intersects the first. If the dot product is 0 for \(i = 4, 5, 6 \) then the second triangle is coplanar with the first, so we need only check for the position of \(\vec{x}_i\) relative to triangle one for \(i=4,5,6\). More on this later. If the dot product is non-zero in all three cases, and all of the same sign, then we know the two triangles do not intersect (as triangle two lies completely inside one of the half-spaces separated by \(H\)). That only leaves the case that two vertices of triangle two are one side of \(H\) while the third vertex is on the opposite side of \(H\). Without loss of generality, suppose the points \( \vec{x}_4 \) and \( \vec{x}_5 \) are on opposite sides of \( H \), and \( \vec{x}_6 \) is on the same side as \( \vec{x}_5 \). We can find a point of intersection between \( H \) and the line \( L \) through \( \vec{x}_4 \) and \( \vec{x}_5 \). This line \( L \) has the form
\[ L : t \cdot (\vec{x}_5 - \vec{x}_4) + \vec{x}_4, \quad \text{ where } \quad t\in [0,1]\subseteq \mathbb{R} \]
Substitute this into the equation for \( H \) to obtain an equation of only one variable: \( t \). Solve for \(t \) and we have the desired intersection point. If necessary, find the other intersection point using \( \vec{x}_4 \) and \( \vec{x}_6 \).

At this stage, we have basically reduced all cases down to \( H \) containing triangle one, and points that also lie on \( H\) -- either intersection points or actual vertices of triangle two. The most difficult step is to determine the position of a point the the plane \( H \) relative to triangle one.

To determine their positions relative to triangle one, you can use a linear system. Since we already have the three vertices from triangle one being coplanar, any other point in \( H \) must be a linear combination of the vertices of triangle one. The solution can even be normalized. That is, if \( \mathbf{A} \) is the matrix whose entries are the coordinates of the vertices (in column form) of triangle one, and \( \vec{b} \) is a point on \( H \), then the solution \(\vec{x} = \vec{\lambda} \) to \( \mathbf{A}\cdot \vec{x} = \vec{b} \) can also be made to satisfy
\[ \sum_{j=1}^3 \lambda_j = 1 \]
where \( \lambda_j \) is the \(j\)-th component of \( \vec{\lambda} \). In a sense, \( \lambda_j \) is a weight on the \(j\)-th vertex of triangle one and is a measure of how close \( \vec{b} \) is to that vertex. Moreover, the sign of \( \lambda_j \) determines the relative position of \( \vec{b} \) to vertex \( j \). (Look up Radon partitions; there are also lots of theorems regarding \(d+2\) points in a \(d\)-dimensional space.) That is, if \(\lambda_j\) is positive, then \( \vec{b} \) and vertex \( j \) are on the same side of the line passing through the remaining two vertices of triangle one. Thus, if \(\lambda_j \) are all positive, then \( \vec{b} \) lies in the relative interior of triangle one. If \( \lambda_j = 0 \) for a specific value of \( j \) then \( \vec{b} \) actually lies one an edge of triangle one.

This should give you more than enough to figure out the rest. As a friendly reminder, area of a triangle in \( \mathbb{R}^3 \) is merely half the magnitude of the cross product of the two vectors representing two sides of that triangle. So once you know the position of \( \vec{x}_4\), \(\vec{x}_5\), and \( \vec{x}_6 \) relative to triangle one, just partition into triangles and compute the area accordingly.

Edit: The worst case is of course when all six points are coplanar. In this case, you will actually have to repeat the last bit of linear algebra and switch the roles of triangle one and triangle two to reduce the complexity. It very well could be that triangle one is inside triangle two! However, the steps above would detect that by simply swapping triangle one out for triangle two.