Orientation Predicate

computational-geometry geometry

Definition

Orientation Predicate

Let $A=(x_A,y_A)$, $B=(x_B,y_B)$, and $C=(x_C,y_C)$ be points in the plane. The orientation predicate is

$$\mathrm{Orient}(A,B,C)=(x_B-x_A)(y_C-y_A)-(y_B-y_A)(x_C-x_A).$$

Its sign tells how $C$ lies relative to the directed line $A\to B$:

$$\begin{array}{rl}\mathrm{Orient}(A,B,C)>0& ⟺C\text{ lies left of }A\to B,\\ \mathrm{Orient}(A,B,C)<0& ⟺C\text{ lies right of }A\to B,\\ \mathrm{Orient}(A,B,C)=0& ⟺A,B,C\text{ are collinear.}\end{array}$$

Intuition

Intuition

The predicate measures the turn from the vector $A\to B$ to the vector $A\to C$.

• A positive value means an anticlockwise turn.
• A negative value means a clockwise turn.
• A zero value means no turn, so the three points lie on one line.

The absolute value is twice the area of the triangle $ABC$:

$$\mathrm{Area}(ABC)=\frac{1}{2}\left|\mathrm{Orient}(A,B,C)\right|.$$

Why the Formula Works

Move $A$ to the origin. This does not change whether $C$ is left or right of $A\to B$. The shifted points are

$$B^{\prime }=B-A=(x_{B^{\prime }},y_{B^{\prime }}),C^{\prime }=C-A=(x_{C^{\prime }},y_{C^{\prime }}).$$

The points $B^{\prime }$ and $C^{\prime }$ span a parallelogram from the origin. Its signed area is the $2\times 2$ determinant

$$\left|\begin{array}{cc}{x}_{B^{\prime }}& x_{C^{\prime }}\\ y_{B^{\prime }}& y_{C^{\prime }}\end{array}\right|=x_{B^{\prime }}{y}_{C^{\prime }}-y_{B^{\prime }}{x}_{C^{\prime }}.$$

The sign records the order of the two shifted points:

• positive if $B^{\prime }$ turns anticlockwise to $C^{\prime }$,
• negative if $B^{\prime }$ turns clockwise to $C^{\prime }$,
• zero if the parallelogram collapses to a line.

Substituting

$$\begin{array}{rlrl}{x}_{B^{\prime }}& =x_B-x_A,& y_{B^{\prime }}& =y_B-y_A,\\ x_{C^{\prime }}& =x_C-x_A,& y_{C^{\prime }}& =y_C-y_A\end{array}$$

gives

$$\mathrm{Orient}(A,B,C)=(x_B-x_A)(y_C-y_A)-(y_B-y_A)(x_C-x_A).$$

Coordinate Convention

The left/right interpretation assumes the usual Cartesian plane, where the $y$-axis points upward. In screen coordinates, where the $y$-axis often points downward, the sign interpretation is reversed.

Examples

Left of a horizontal directed line

Let $A=(0,0)$, $B=(4,0)$, and $C=(1,2)$. Then

$$\mathrm{Orient}(A,B,C)=(4-0)(2-0)-(0-0)(1-0)=8>0.$$

Hence $C$ lies left of $A\to B$.

Right of a horizontal directed line

Let $A=(0,0)$, $B=(4,0)$, and $C=(1,-2)$. Then

$$\mathrm{Orient}(A,B,C)=(4-0)(-2-0)-(0-0)(1-0)=-8<0.$$

Hence $C$ lies right of $A\to B$.

Collinear points

Let $A=(0,0)$, $B=(4,0)$, and $C=(2,0)$. Then

$$\mathrm{Orient}(A,B,C)=(4-0)(0-0)-(0-0)(2-0)=0.$$

Hence $A$, $B$, and $C$ are collinear.