Triangle Containment (102)

In Problem 102, we're given a list of vertices of triangles. For each triangle, we're supposed to check whether the coordinate origin is contained within the triangle and count these.

There are many different ways to check whether a point is contained in a triangle. We will use cross products. Let $O$ be the coordinate origin, $A$, $B$ and $C$ the vertices of the triangle. We can define vectors along the edges, $AB$, $BC$, and $CA$. We can also define vectors from the origin to the vertices: $OA$, $OB$, $OC$.

Without loss of generality, let us assume that the vertices are arranged in a counterclockwise fashion. If the origin is within the triangle, the connections from one vertex to the origin will always be left of the connection to the next vertex. This holds for all three vertices. If the origin is outside, some of these origin connections will be on the left, others on the right.

We can express this “left or right” relation with a cross product. Since we're in two dimensions only, we only need to look at the third component of the cross product. For two vectors $\overrightarrow{a}$ and $\overrightarrow{b}$, the cross product vector $\overrightarrow{c}$ is defined as

$$c_i={ϵ}_{ijk}{a}_j{b}_k,$$

where ${ϵ}_{ijk}$ is the Levi-Civita symbol and summation convention is assumed.

In our concrete case we're interested in $c_3$:

$$c_3=a_1{b}_2-a_2{b}_1.$$

Setting $\overrightarrow{a}=OA$ and $\overrightarrow{b}=AB$, or a similar pattern, with all three vertices, we can form three such cross products. If all three cross products have the same sign, we know that the origin has to be within the triangle. If the signs differ, it must be outside.