Find the area of overlap of two triangles

Suppose we are given two triangles $ABC$ and $DEF$. We can assume nothing about them other than that they are in the same plane. The triangles may or may not overlap. I want to algorithmically determine the area (possibly $0$) of their overlap; call it $T_{common}$.

We have a multitude of ways of determining the areas of $ABC$ and $DEF$; among the "nicest" are the Heronian formula, which is in terms of the side lengths alone, and

$T = \frac{1}{2} \left| \det\begin{pmatrix}x_A & x_B & x_C \\ y_A & y_B & y_C \\ 1 & 1 & 1\end{pmatrix} \right| = \frac{1}{2} \big| x_A y_B - x_A y_C + x_B y_C - x_B y_A + x_C y_A - x_C y_B \big|$

which is in terms of the coordinates alone.

Obviously, there does exist a function from $A,B,C,D,E,F$ to $T_{common}$, but my question is: is there a "nice" (or even not-"nice") expression for $T_{common}$ in terms of the $x$ and $y$ coordinates of $A,B,C,D,E,F$?

I've drawn out on paper what I think are the various cases, but my issues with this approach are: identifying the case is a job in itself, which I can't easily see how to algorithmise ("just look at a picture" doesn't work for a computer); even within each case the algebra is fiddly and error-prone; and I have little confidence that I've enumerated all possible cases and got the computations right!

In my imagination there is a neat approach using ideas from analysis (treating the triangles as functions from $\mathbb{R}^2$ to $\{0,1\}$ and... multiplying them??) but I have no idea whether that's just a flight of fancy or something workable.

Solution 1:

Here's an approach that doesn't require any ingenuity or case analysis. Use the Sutherland-Hodgman algorithm to clip one triangle against the other, yielding a (possibly degenerate) polygon representing the region of overlap, then compute its area.

Solution 2:

Sorry about the comment -- I hit the return key prematurely.

This isn't really an answer (except in the negative sense).

The common (overlap) area is a function of the coordinates of the 6 points, so it's a mapping from $R^{12}$ into $R$. Think about one of the points moving around, while the other 5 are fixed. When the moving point passes into (or out of) the other triangle, some of the partial derivatives of the area function will be discontinuous (this seems intuitively clear -- the proof is left to someone who has more skill and patience than I do). Anyway, if you believe me, this means that the area function is not smooth. Therefore there can not be some simple formula like Heron's formula that gives the area (because this simple formula would give a smooth function).

Solution 3:

Here is a beginning. Degenerate cases will not be dealt with.

Let ${\bf a}_i$ $\,(i=0,1,2)$ be the vertices of the first, called $A$-triangle, and similarly let ${\bf b}_k$ $\,(k=0,1,2)$ be the vertices of the $B$-triangle. It might help to assume that both triangles are positively oriented, i.e., $({\bf a}_1-{\bf a_0})\wedge({\bf a}_2-{\bf a_0})>0$, and similarly for the ${\bf b}_k$.

Then the prolonged sides of the $A$-triangle are given by $$g_i:\quad s\mapsto (1-s){\bf a}_{i-1}+ s\,{\bf a}_i\qquad(-\infty<s<\infty)\ ,$$ and similarly the prolonged sides of the $B$-triangle are given by $$h_k:\quad t\mapsto (1-t){\bf b}_{k-1}+ t\,{\bf b}_k\qquad(-\infty<t<\infty)\ .$$

Note that the intersection of the two triangles might have from $0$ to $6$ vertices. Therefore it is not too much work to determine the parameter values $(s_{ik},t_{ik})$ of the nine intersection points ${\bf z}_{ik}:=g_i\wedge h_k$.

Now comes the difficult part: Let $I:=[0,1]$. A point ${\bf z}_{ik}$ is an actual intersection point of an $A$-side with a $B$-side iff $(s_{ik},t_{ik})\in I\times I$. By drawing a few figures it should be possible to come up with an algorithm that decides whether (i) one of the triangles is contained in the other, or (ii) they are lying apart, or (iii) they intersect in a convex polygon $P$. In the last case it should even be possible to automatically get the addresses $(i_r,k_r)$ $\,(1\leq r\leq n)$ of $P$'s vertices in a counterclockwise order.

When we are that far we can put $${\bf z}_r:=\bigl(1-s_{i_r k_r}\bigr){\bf a}_{i_r-1}+s_{i_r k_r}{\bf a}_{i_r}\qquad(1\leq r\leq n)$$ and use the well known formula (derived from Green's area formula) for the area of $P={\rm conv}({\bf z}_,\ldots,{\bf z}_n)$.

Solution 4:

Here's a way to think about the problem that might help.

Each side of a triangle defines an infinite line, and this line divides the plane into two halves (called "half-spaces"). So, for example, the side $AB$ defines a line $L_{AB}$ with equation $L_{AB}(x,y) = 0$. The two corresponding half-spaces are $L_{AB}(x,y) \le 0$ and $L_{AB}(x,y) \ge 0$. You can multiply the line equation by $-1$, if necessary, and thereby arrange that the triangle actually lies in the half-space $L_{AB}(x,y) \ge 0$.

Then, the triangle $ABC$ is the intersection of three half-spaces: $L_{AB}(x,y) \ge 0$, $L_{BC}(x,y) \ge 0$, $L_{CA}(x,y) \ge 0$.

The intersection of the two triangles is then the intersection of 6 half-spaces.

Or, saying at another way, the intersection is the set of points $(x,y)$ for which all six of $L_{AB}(x,y)$ through $L_{DF}(x,y)$ are positive. So, if we define $f(x,y) = \min\{L_{AB}(x,y), \ldots, L_{DF}(x,y)\}$, then the triangle is the set $\{(x,y) : f(x,y) \ge 0\}$.

I don't think any of this is very useful computationally. But, it provides a way to enumerate cases, and it converts the problem into a "function-based" one, as suggested by your flight of fancy.