Line Segments and Cross Products

The Cross Product

For two vectors $\mathbf{a} = (a_x, a_y)$ and $\mathbf{b} = (b_x, b_y)$ in the plane, the cross product (or 2D cross product, or perpendicular dot product) is:

$\mathbf{a} \times \mathbf{b} = a_x b_y - a_y b_x = \det\begin{pmatrix} a_x & a_y \\ b_x & b_y \end{pmatrix}$

This is a scalar representing the signed area of the parallelogram spanned by $\mathbf{a}$ and $\mathbf{b}$.

Sign Interpretation

Given vectors $\mathbf{a}$ and $\mathbf{b}$ originating from the same point:

Cross product	Meaning
$\mathbf{a} \times \mathbf{b} > 0$	$\mathbf{b}$ is counter-clockwise (left) from $\mathbf{a}$
$\mathbf{a} \times \mathbf{b} < 0$	$\mathbf{b}$ is clockwise (right) from $\mathbf{a}$
$\mathbf{a} \times \mathbf{b} = 0$	$\mathbf{a}$ and $\mathbf{b}$ are collinear (same or opposite direction)

Properties

• Anti-symmetry: $\mathbf{a} \times \mathbf{b} = -(\mathbf{b} \times \mathbf{a})$
• Relation to angle: $\mathbf{a} \times \mathbf{b} = |\mathbf{a}| |\mathbf{b}| \sin \theta$, where $\theta$ is the angle from $\mathbf{a}$ to $\mathbf{b}$.
• No trigonometry needed: computed with only two multiplications and one subtraction. This is exact for integer coordinates and fast in floating point.

Orientation Test

To determine the orientation of three points $P, Q, R$, use:

$\text{orient}(P, Q, R) = (Q - P) \times (R - P) = (Q_x - P_x)(R_y - P_y) - (Q_y - P_y)(R_x - P_x)$

Result	Meaning	Turn direction
$> 0$	$R$ is left of $P \to Q$	Counter-clockwise (left turn)
$< 0$	$R$ is right of $P \to Q$	Clockwise (right turn)
$= 0$	$P, Q, R$ are collinear	Straight

This is the fundamental building block for all geometric algorithms in this module. It is used for: sorting by polar angle, checking convexity, detecting segment intersections, and building convex hulls.

Line Segment Definition

A line segment $p_1 p_2$ is the set of points $\{ \alpha p_1 + (1-\alpha) p_2 \mid 0 \le \alpha \le 1 \}$. These are convex combinations of the endpoints. If we allow any $\alpha \in \mathbb{R}$, we get the (infinite) line through $p_1$ and $p_2$, which is the extension of the segment.

A directed segment $p_1 \to p_2$ has an implied direction from $p_1$ to $p_2$.

Convex Combinations

A point $p_3$ is on the segment $p_1 p_2$ iff there exists $\alpha \in [0,1]$ such that:

$p_3 = \alpha p_1 + (1-\alpha) p_2$

Or, in coordinates: $x_3 = \alpha x_1 + (1-\alpha)x_2$, $y_3 = \alpha y_1 + (1-\alpha)y_2$.

Worked Example: Orientation

Points: $P = (1,1)$, $Q = (4,2)$, $R = (2,5)$.

$\overrightarrow{PQ} = (4-1, 2-1) = (3, 1)$

$\overrightarrow{PR} = (2-1, 5-1) = (1, 4)$

$\text{orient}(P,Q,R) = 3 \times 4 - 1 \times 1 = 12 - 1 = 11 > 0$

$R$ is to the left of $\overrightarrow{PQ}$ — a counter-clockwise turn.

Another point $S = (5, 5/3)$: $\overrightarrow{PS} = (4, 2/3)$, cross product $3 \times (2/3) - 1 \times 4 = 2 - 4 = -2 < 0$ → clockwise turn.

Avoiding Division and Trigonometry

Using the equation $y = mx + c$ to find intersections requires division by $(m_1 - m_2)$, which becomes numerically unstable when lines are nearly parallel (the problem is ill-conditioned: small changes in input cause large changes in output). Cross products use only addition and multiplication, maintaining infinite precision for integer inputs (no rounding until the final comparison).

Summary

Concept	Formula / Rule
Cross product	$a_x b_y - a_y b_x$
Positive	$\mathbf{b}$ is CCW from $\mathbf{a}$
Negative	$\mathbf{b}$ is CW from $\mathbf{a}$
Zero	Collinear
Orientation test	$\text{orient}(P,Q,R) = (Q-P) \times (R-P)$
Convex combination	$p_3 = \alpha p_1 + (1-\alpha)p_2$, $0 \le \alpha \le 1$
Numerical advantage	No trig, no division, exact for integers