Geometric Primitives & Orientation

This lesson opens the computational geometry module, where the objects are points, segments, and polygons in the plane rather than numbers or graphs. The algorithms ahead, including convex hulls, sweep-line intersection, and closest pairs, look involved, but they nearly all rest on one tiny operation asked over and over: given three points, does the path through them turn left or right? Get that primitive exactly right and the rest is bookkeeping; get it subtly wrong and every structure built on top inherits the error.

The central design decision of this lesson is therefore exact arithmetic. The natural geometric quantities (angles, lengths, slopes) are irrational and force floating point, where a quantity that should be zero comes out as $1 0^{- 16}$ and a collinearity test flips the wrong way. We avoid them. With integer input coordinates, the orientation and area primitives below are polynomials in the coordinates, so they evaluate to exact integers and their signs are never in doubt.¹ Slopes, square roots, and $arctan$ never appear.

Points as vectors

We identify a point $P = (x, y)$ with the vector from the origin to it, which lets us do arithmetic on geometry. For points $A = (a_{x}, a_{y})$ and $B = (b_{x}, b_{y})$ and a scalar $t$ :

A + B = (a_{x} + b_{x}, a_{y} + b_{y}), B - A = (b_{x} - a_{x}, b_{y} - a_{y}), t A = (t a_{x}, t a_{y}) .

The subtraction $B - A$ is the one that does the work: it is the displacement vector pointing from $A$ to $B$ , and almost every primitive below is phrased in terms of such difference vectors anchored at a common point. If $A$ , $B$ have integer coordinates, so does $B - A$ , and exactness is preserved by every one of these operations.

The dot product: angle and projection

The dot product of two vectors measures how much they point the same way:

a \cdot b = a_{x} b_{x} + a_{y} b_{y} = ∣ a ∣ ∣ b ∣ cos θ,

where $θ$ is the angle between them. The second equality is the useful one in reverse: because $∣ a ∣, ∣ b ∣ > 0$ , the sign of the dot product is the sign of $cos θ$ , so it classifies the angle without ever computing it.

Three uses recur. Projection: the scalar projection of $b$ onto $a$ is $(a \cdot b) /∣ a ∣$ , the signed length of $b$ 's shadow along $a$ . Perpendicularity: $a ⊥ b \leftrightarrow a \cdot b = 0$ , an exact integer test. Angle: $cos θ = (a \cdot b) / (∣ a ∣∣ b ∣)$ when the actual angle is genuinely needed (the one place a square root sneaks in). Note the dot product is symmetric and tells us nothing about which side one vector lies on; for that we need its companion.

The dot product is the signed length of

b

's shadow on

a

times

∣ a ∣

The cross product: signed area and orientation

In the plane the cross product of two vectors is a single scalar:

a \times b = a_{x} b_{y} - a_{y} b_{x} = ∣ a ∣ ∣ b ∣ sin θ .

Its magnitude $∣ a \times b ∣$ equals the area of the parallelogram spanned by $a$ and $b$ (and twice the area of the triangle they form). Its sign is the sign of $sin θ$ , which encodes orientation: positive when $b$ lies counterclockwise from $a$ , negative when clockwise, zero when the two are parallel (collinear). Unlike the dot product, the cross product is antisymmetric: $a \times b = - (b \times a)$ . This single quantity, an exact integer for integer inputs, is the seed of nearly everything that follows.

The orientation test

Anchor two difference vectors at a common point $A$ and take their cross product. This is the orientation (or ccw) test, the fundamental primitive of planar computational geometry:

ccw (A, B, C) = sign ((B - A) \times (C - A)) = sign ((b_{x} - a_{x}) (c_{y} - a_{y}) - (b_{y} - a_{y}) (c_{x} - a_{x})) .

It reports the sense of the turn made by the directed path $A \to B \to C$ :

sign ((B - A) \times (C - A))

is the turn direction at

A \to B \to C

Three properties make this primitive so powerful. It uses only additions and multiplications of the input coordinates, so for integer inputs it is exact. It is antisymmetric in a way that respects the geometry: swapping $B$ and $C$ flips the sign, matching the reversal of the turn. And it answers, in $O (1)$ , the question every higher geometric algorithm reduces to — which side of the line $A B$ does $C$ lie on? The collinearity test are $A$ , $B$ , $C$ on one line? is just $ccw (A, B, C) = 0$ , with no division by a slope and hence no vertical-line special case.

Algorithm:

\textsc{Orientation}(A, B, C)

— sign of the turn, exact integer arithmetic

1
$d \gets (b_x - a_x)(c_y - a_y) - (b_y - a_y)(c_x - a_x)$
2
if $d > 0$ then
3
return $+1$
left turn
4
else if $d < 0$ then
5
return $-1$
right turn
6
else
7
return $0$
collinear

Segment intersection

When do two segments $\overline{A B}$ and $\overline{C D}$ cross? The slope-and-solve approach drags in division and degenerate cases; orientation makes it a handful of sign comparisons. The key idea is straddling: segment $\overline{A B}$ straddles the line through $C$ and $D$ when its endpoints fall on opposite sides of that line, that is, when $ccw (C, D, A)$ and $ccw (C, D, B)$ have opposite signs.

Why. If $C$ and $D$ are strictly on opposite sides of line $A B$ , the open segment $\overline{C D}$ crosses that line exactly once, at some point $P$ ; the symmetric condition forces $P$ to also lie strictly between $A$ and $B$ . Both products being negative pins the crossing to the interior of both segments. The two ccw evaluations are exact integers, so this test has no rounding error and never computes the intersection point itself.

The boundary, when some ccw is $0$ and three points are collinear, needs care, and is where naive implementations break. The case logic:

All four products nonzero (the generic case): intersect iff both products are strictly negative, as above.
Exactly one $ccw$ is $0$ , say $ccw (A, B, C) = 0$ : then $C$ lies on the line $A B$ ; the segments touch iff $C$ lies on the segment $\overline{A B}$ , i.e. $C$ 's coordinates are within the bounding box of $A$ and $B$ (an on-segment check: $min (a_{x}, b_{x}) \leq c_{x} \leq max (a_{x}, b_{x})$ and likewise for $y$ ).
The segments are collinear (all four ccw vanish): they overlap iff their $1$ -D projections onto the $x$ -axis (or $y$ , if vertical) overlap, again a bounding-box / interval-overlap test, no geometry beyond comparisons.

Algorithm:

\textsc{SegmentsIntersect}(A,B,C,D)

— proper crossings plus collinear/touching

1
$d_1 \gets \textsc{Orientation}(C,D,A);\ \ d_2 \gets \textsc{Orientation}(C,D,B)$
2
$d_3 \gets \textsc{Orientation}(A,B,C);\ \ d_4 \gets \textsc{Orientation}(A,B,D)$
3
if $d_1 d_2 < 0$ and $d_3 d_4 < 0$ then
4
return true
proper crossing
5
if $d_1 = 0$ and $\textsc{OnSegment}(C,D,A)$ then return true
6
if $d_2 = 0$ and $\textsc{OnSegment}(C,D,B)$ then return true
7
if $d_3 = 0$ and $\textsc{OnSegment}(A,B,C)$ then return true
8
if $d_4 = 0$ and $\textsc{OnSegment}(A,B,D)$ then return true
9
return false

\overline{A B}, \overline{C D}

cross iff each straddles the other

Polygon area: the shoelace formula

Given a polygon as an ordered list of vertices $P_{0}, P_{1}, \dots, P_{n - 1}$ (indices modulo $n$ ), its area is the shoelace formula:

Area = \frac{1}{2} i = 0 \sum n - 1 (x_{i} y_{i + 1} - x_{i + 1} y_{i}) = \frac{1}{2} i = 0 \sum n - 1 P_{i} \times P_{i + 1} .

Each term $x_{i} y_{i + 1} - x_{i + 1} y_{i}$ is exactly the cross product $P_{i} \times P_{i + 1}$ , so the area is a sum of cross products, halved.

Drop the absolute value and the sign of the sum carries orientation: positive means the vertices are listed counterclockwise, negative means clockwise. This is the cheapest way to detect the winding direction of a polygon, and because the sum is an integer for integer vertices, the area comes out as an exact half-integer.²

Shoelace sums signed triangles

\frac{1}{2} (P_{i} \times P_{i + 1})

from

O

; exterior sweeps cancel

Point in polygon

Is a query point $q$ inside a polygon? Two exact strategies, both built from the primitives above. Ray casting shoots a ray from $q$ in a fixed direction (say $+ x$ ) and counts how many polygon edges it crosses: an odd count means $q$ is inside, even means outside — the Jordan-curve parity argument. Each ray-vs-edge crossing is decided with the same straddle/orientation tests, with careful tie-breaking when the ray grazes a vertex (count an edge only if exactly one endpoint is strictly above the ray). The winding number alternative sums the signed angles the polygon's edges subtend at $q$ (computed from cross- and dot-product signs, not actual angles); a total winding of $0$ means outside, $\pm 1$ means inside, and unlike parity it stays correct for self-intersecting polygons. For a convex polygon both can be sped up to $O (log n)$ : binary-search the vertex fan around $P_{0}$ to find the wedge containing $q$ using orientation tests, then one final ccw against the bounding edge decides inside vs. outside.³

Ray casting: a

+ x

ray crossing an odd count of edges means inside

For a convex polygon the fan of diagonals from $P_{0}$ cuts the interior into triangular wedges in angular order, so a single binary search on $ccw (P_{0}, P_{i}, q)$ locates the wedge $⟨ P_{k}, P_{k + 1} ⟩$ that could contain $q$ ; one last orientation test against the edge $\overline{P_{k} P_{k + 1}}$ decides inside vs. outside.

Convex

O (log n)

point location: binary-search the fan from

P_{0}

for

q

's wedge, then one

ccw

on the far edge

Takeaways

Treat points as vectors; the difference $B - A$ is the displacement that almost every primitive is built from, and integer inputs stay integer.
The dot product $a \cdot b = a_{x} b_{x} + a_{y} b_{y}$ has the sign of $cos θ$ : positive/zero/negative $\Rightarrow$ acute/right/obtuse — it handles projection, perpendicularity, and angle.
The cross product $a \times b = a_{x} b_{y} - a_{y} b_{x}$ gives signed parallelogram area in its magnitude and orientation in its sign.
The orientation test $ccw (A, B, C) = sign ((B - A) \times (C - A))$ reports left/right/collinear in $O (1)$ exact integer arithmetic — the primitive that hull, intersection, and point-location all reduce to.
Segments cross iff each straddles the other's line (opposite ccw signs on both); collinear and touching cases fall to on-segment bounding-box checks.
The shoelace formula $\frac{1}{2} \sum P_{i} \times P_{i + 1}$ is a sum of cross products giving area, and its sign reveals CCW vs. CW winding.
Point-in-polygon is ray-casting parity or winding number; a convex polygon admits an $O (log n)$ orientation-based binary search.

CLRS, Ch. 33 — Computational Geometry (§33.1): cross-product primitives, the orientation/turn test, and segment-intersection via straddling, all in exact arithmetic to avoid round-off. ↩
Skiena, § — Computational Geometry: the shoelace (surveyor's) formula for polygon area as a sum of cross products, whose sign gives vertex orientation. ↩
Erickson, Ch. — (geometry): point-in-polygon by ray-crossing parity and winding number, and the $O (log n)$ convex case via orientation-guided binary search. ↩

Points as vectors

The dot product: angle and projection

The cross product: signed area and orientation

The orientation test

Segment intersection

Polygon area: the shoelace formula

Point in polygon

Takeaways

Footnotes