[GC] To left test

The following function returns true if a point $p_3$ is to the left of the line segment $\overrightarrow{p_1p_2}$.

// ToLeft returns true if p3 is to the left of the line p1p2.
inline bool ToLeft(const Point& p1, const Point& p2, const Point& p3) {
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x) > 0;
  }

There are multiple ways to prove this. One of them is to use the cross product of two vectors. In a right-handed Cartesian coordinate system, $p_3$ is to the left of the line segment $\overrightarrow{p_1p_2}$ if and only if the cross product of $\overrightarrow{p_1p_2}$ and $\overrightarrow{p_1p_3}$ is positive (i.e., the resulted vector points along the positive z-axis).

Let $\vec{i},\vec{j},\vec{k}$ be the unit vectors along the x, y, and z axes, respectively, and $(x_i, y_i)$ be the coordinate of point $p_i$ in the $xy$-plane.

$$ \begin{aligned} \overrightarrow{p_1p_2} \times \overrightarrow{p_1p_3} &= ((x_2 - x_1)\vec{i} + (y_2 - y_1)\vec{j}) \times ((x_3 - x_1)\vec{i} + (y_3 - y_1)\vec{j}) \\ &= (x_2 - x_1)(x_3 - x_1)(\vec{i} \times \vec{i}) + (y_2 - y_1)(y_3 - y_1)(\vec{j} \times \vec{j}) \\ &\quad + (x_2 - x_1)(y_3 - y_1)(\vec{i} \times \vec{j}) + (y_2 - y_1)(x_3 - x_1)(\vec{j} \times \vec{i}) \\ \end{aligned} $$

By the definition and the Anticommutative Property of the cross product, we have

$$ \begin{aligned} \vec{i} \times \vec{i} &= \vec{j} \times \vec{j} = 0, \\ \vec{i} \times \vec{j} &= -\vec{j} \times \vec{i} = \vec{k}. \end{aligned} $$

Therefore, the cross product of $\overrightarrow{p_1p_2}$ and $\overrightarrow{p_1p_3}$ is

$$ \begin{aligned} \overrightarrow{p_1p_2} \times \overrightarrow{p_1p_3} &= ((x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1))\vec{k} \end{aligned} $$

Let the coefficient of $\vec{k}$ to be positive, we can derive the function ToLeft(p1, p2, p3) as shown above.

The inequality $(x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1) > 0$ can also be written as the following determinant:

$$ \begin{vmatrix} x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \end{vmatrix} > 0. $$

Examples

By the function ToLeft(p1, p2, p), we can determine whether a point is located inside a triangle $\triangle p_1p_2p_3$ or not.

// InTriangle returns true if p is inside the triangle p1p2p3.
inline bool InTriangle(const Point& p1, const Point& p2, const Point& p3, const Point& p) {
    return ToLeft(p1, p2, p) && ToLeft(p2, p3, p) && ToLeft(p3, p1, p);
  }