Hp 50g Math question: Intersection of 2 triangulars

[Han]

The equation of a line is:
\[ a \cdot (x-x_0) + b\cdot (y-y_0) = 0 \]
and of a plane is:
\[ a \cdot (x-x_0) + b\cdot (y-y_0) + c\cdot (z-z_0) = 0 \]
and generalizes in the natural way to higher dimension. What is both interesting and useful is that it is basically the dot product of a normal (i.e. perpendicular) vector \( \langle a,b \rangle \) with the vector \( \langle x-x_0, y-y_0 \rangle \), and the dot product is 0 since the vectors are perpendicular. The vector \( \langle a,b \rangle \) can be easily obtained from a simple slope calculation through 2 points. In 3D, you would need to create 2 vectors from a set of 3 points, and take a cross product to come up with a vector normal to the plane containing the three points. Here's the 2D version:

Since we now have a dot-product interpretation for a linear equation, it's quite simple to determine if two triangles intersect, and even how they intersect. Let the six points be
\[ P_1:=(x_1, y_1), \quad P_2:=(x_2, y_2), \quad \dotsm,
\quad P_6:=(x_6, y_6) \]
and let \(L_{i,j}\) be the line through points \( (x_i,y_i)\) and \((x_j,y_j)\) with \(i<j\). Define an associated function:
\[ L_{i,j}(X,Y) := -(y_j-y_i) \cdot (X-x_i) + (x_j-x_i) \cdot (Y-y_i) \]
Without loss of generality, let the first triangle be the one created by the lines \( L_{1,2}, L_{2,3}, L_{1,3} \). Then for each line, we can define the "in" side of that line to be the sign of \(L_{i,j}\) evaluated at the remaining point. For example, \( L_{1,2}(P_3) \) will either be negative or positive, or zero. If zero, then \(P_3\) lies on \(L_{1,2} \) -- not possible if we have a valid triangle. If negative, then \(P_3\) is on the opposite side of the normal vector, and positive if on the same side. Apply this to all three lines and it's easy to determine the "in"-side of a that triangle (based purely on the signs of the valuations of each line). So, to continue, if \( L_{i,j}(P_4) \) has the same corresponding signs as for \(P_1\), \(P_2\), and \(P_3\), then \(P_4\) lies on the "in"-side of that triangle. If \( L_{i,j}(P_4) = 0 \) then \(P_4\) lies on the edge defined by \(L_{i,j}\)... and hopefully you get the idea.

If all three points \(P_4, P_5, P_6\) all do not lie on the "outside" then either their vertices are in the interior or possibly boundary of the first triangle. The area would be a simple determinant calculation. The only remaining cases are one or two points are on the "out"-side. Since inside and outside are all determined by the valuations of a line \(L_{i,j}\), it's pretty easy to find the intersection points as you clearly know which lines are involved (one is \(L_{i,j}\) and the other consists of one point inside the triangle and one outside the triangle).