---
title: Geometric Primitives & Orientation
module: Computational Geometry
moduleNumber: 11
lessonNumber: 1
order: 1101
summary: |
  Computational geometry is built on a single reliable primitive — the
  **orientation test**, a sign of a cross product that tells whether three points
  turn left, right, or lie collinear. From points-as-vectors and the dot and
  cross products we derive orientation, segment intersection, the shoelace area
  formula, and point-in-polygon tests, keeping all arithmetic **exact and
  integer** so that no floating-point rounding can corrupt a sign.
topics: [Geometry]
sources:
  - book: CLRS
    ref: "Ch. 33 — Computational Geometry (§33.1)"
  - book: Skiena
    ref: "§ — Computational Geometry"
  - book: Erickson
    ref: "Ch. — (geometry)"
practice:
  - title: 'Check If It Is a Straight Line'
    slug: check-if-it-is-a-straight-line
    difficulty: Easy
  - title: 'Valid Boomerang'
    slug: valid-boomerang
    difficulty: Easy
  - title: 'Largest Triangle Area'
    slug: largest-triangle-area
    difficulty: Easy
  - title: 'Minimum Area Rectangle'
    slug: minimum-area-rectangle
    difficulty: Medium
---

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](/algorithms/computational-geometry/convex-hull),
[sweep-line intersection](/algorithms/computational-geometry/sweep-line), and
[closest pairs](/algorithms/divide-and-conquer/selection), look involved, but
they nearly all rest on one small operation applied repeatedly:
_given three points, does the path through them turn left or right?_ If that
primitive is exact, the rest is bookkeeping; if it is subtly wrong,
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
$10^{-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.[^clrs-primitives] 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), \qquad
B - A = (b_x - a_x,\; b_y - a_y), \qquad
tA = (t\,a_x,\; t\,a_y).
$$

The subtraction $B - A$ is the most important of these: 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.

::impl{algo="vector"}

## The dot product: angle and projection

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

$$
\vec a \cdot \vec b \;=\; a_x b_x + a_y b_y \;=\; |\vec a|\,|\vec b|\cos\theta,
$$

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

> **Fact (Acute-angle test).** The angle between $\vec a$ and $\vec b$ is **acute** iff $\vec a \cdot \vec b > 0$,
> **right** (perpendicular) iff $\vec a \cdot \vec b = 0$, and **obtuse** iff
> $\vec a \cdot \vec b < 0$.

Three uses recur. _Projection_: the scalar projection of $\vec b$ onto $\vec a$ is
$(\vec a \cdot \vec b)/|\vec a|$, the signed length of $\vec b$'s shadow along
$\vec a$. _Perpendicularity_: $\vec a \perp \vec b \iff \vec a \cdot \vec b = 0$,
an exact integer test. _Angle_: $\cos\theta = (\vec a \cdot \vec b)/(|\vec a||\vec b|)$
when the actual angle is genuinely needed (the one place a square root sneaks in).
The dot product is symmetric and says nothing about _which side_ one
vector lies on; for that we need the cross product.

$$
% caption: The dot product is the signed length of $\vec b$'s shadow on $\vec a$, times
%          $|\vec a|$. Here $\vec b$'s shadow reaches $x=3$, so the projection is $3$; the
%          angle $\theta$ between the vectors sets its sign.
\begin{tikzpicture}[
  every node/.style={font=\small},
  dot/.style={circle, fill, inner sep=1.3pt},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node[dot, label=below left:$O$] (O) at (0,0) {};
  \draw[->, thick] (O) -- (4,0) node[pos=0.62, below] {a};
  \draw[->, acc, thick] (O) -- (3,2) node[above left] {b};
  \node[dot] (F) at (3,0) {};
  \draw[dashed] (3,2) -- (F);
  % the shadow of b along a, drawn as a thick bar under the axis
  \draw[acc, very thick] (0,-0.5) -- (3,-0.5);
  \node[acc, font=\footnotesize] at (1.5,-0.9) {shadow of b on a, length 3};
  % right-angle mark at the foot of the perpendicular
  \draw (2.78,0) -- (2.78,0.22) -- (3,0.22);
  % angle arc between the two vectors
  \draw[black] (0.8,0) arc (0:34:0.8);
  \node[font=\footnotesize] at (1.05,0.28) {ang.};
\end{tikzpicture}
$$

::impl{algo="dot_product"}

## The cross product: signed area and orientation

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

$$
\vec a \times \vec b \;=\; a_x b_y - a_y b_x \;=\; |\vec a|\,|\vec b|\sin\theta.
$$

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

For example, take
$\vec a = (4, 1)$ and $\vec b = (1, 3)$. Then

$$
\vec a \times \vec b = a_x b_y - a_y b_x = 4\cdot 3 - 1\cdot 1 = 11,
\qquad
\vec b \times \vec a = 1\cdot 1 - 3\cdot 4 = -11.
$$

The value $11$ is the area of the parallelogram those two vectors span, so the
triangle $O$–$\vec a$–$\vec b$ has area $\tfrac{11}{2}$; the positive sign says
$\vec b$ sits counterclockwise from $\vec a$, and swapping the arguments flips the
sign but not the magnitude. Contrast the dot product on the same vectors,
$\vec a \cdot \vec b = 4\cdot 1 + 1\cdot 3 = 7 > 0$, which only reports that the
angle between them is acute — it cannot tell counterclockwise from clockwise. The
two products are complementary: dot for _how aligned_, cross for _which side and
how much area_.

::impl{algo="cross_product"}

## 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\!\parens{(B - A) \times (C - A)}
\;=\; \sign\!\parens{(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$:

> **Fact (Left turn test).** $\ccw(A,B,C) = +1$: the points make a **left turn** (counterclockwise).
> $\ccw(A,B,C) = -1$: a **right turn** (clockwise).
> $\ccw(A,B,C) = 0$: the three points are **collinear**.

$$
% caption: $\sign((B-A)\times(C-A))$ is the turn direction at $A\to B\to C$
\begin{tikzpicture}[
  every node/.style={font=\small},
  dot/.style={circle, fill, inner sep=1.3pt},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % parallelogram spanned by (B-A) and (C-A), shaded
  \fill[acc, opacity=0.12] (0,0) -- (3.2,0.4) -- (4.0,2.4) -- (0.8,2.0) -- cycle;
  % the two anchored vectors
  \node[dot, label=below left:$A$] (A) at (0,0) {};
  \node[dot, label=below right:$B$] (B) at (3.2,0.4) {};
  \node[dot, label=above:$C$] (C) at (0.8,2.0) {};
  \draw[->, acc, thick] (A) -- (B) node[pos=0.55, below] {B - A};
  \draw[->, acc, thick] (A) -- (C) node[midway, left] {C - A};
  % the left turn highlighted
  \draw[->, acc, very thick] (B) to[bend left=18] (C);
  \node[acc] at (2.9,1.9) {left turn (+)};
  % a right-turn alternative below (discarded sense -> red)
  \node[dot, label=below:{$C_2$}] (Cp) at (3.6,-1.1) {};
  \draw[->, red!75!black, thick] (B) to[bend right=15] (Cp);
  \node[red!75!black] at (4.6,-0.5) {right (-)};
\end{tikzpicture}
$$

The three outcomes are best seen on concrete integer coordinates. Fix
$A = (0,0)$ and $B = (4,0)$ and slide the third point: $C$ above the line $AB$
gives a left turn, $C$ below gives a right turn, and $C$ on the line gives $0$.
Each value below is a single subtraction of products, exact to the last bit.

$$
% caption: One primitive, three signs. With $A=(0,0)$, $B=(4,0)$: $C$ above gives $+8$
%          (left), on the line gives $0$ (collinear), below gives $-8$ (right).
\begin{tikzpicture}[
  every node/.style={font=\footnotesize},
  dot/.style={circle, fill, inner sep=1.4pt},
  >=stealth, x=8mm, y=8mm]
  \definecolor{acc}{HTML}{2348F2}
  % panels: C above (left turn, +), on the line (collinear, 0), below (right, -).
  % label y is chosen per panel to clear the point C.
  \foreach \dx/\cy/\clab/\ly/\sgn/\word/\col in {
      0/2/above/{-1.4}/{+8}/{\texttt{left}}/{acc},
      6/0/{above right}/{-1.4}/{\ 0}/{\texttt{collinear}}/{black},
      12/{-2}/below/{2.0}/{-8}/{\texttt{right}}/{red!75!black}} {
    \begin{scope}[shift={(\dx,0)}]
      \node[dot, label=below left:$A$] (A) at (0,0) {};
      \node[dot, label=below right:$B$] (B) at (4,0) {};
      \node[dot, \col, label=\clab:$C$] (C) at (2,\cy) {};
      \draw[acc, ->] (A) -- (B);
      \draw[\col, ->] (B) to[bend left=12] (C);
      \node[\col] at (2,\ly) {ccw = \sgn\ (\word)};
    \end{scope}
  }
\end{tikzpicture}
$$

Three properties matter. The test 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
$AB$ 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
caption: $\textsc{Orientation}(A, B, C)$ — sign of the turn, exact integer arithmetic
$d \gets (b_x - a_x)(c_y - a_y) - (b_y - a_y)(c_x - a_x)$
if $d > 0$ then
  return $+1$   // left turn
else if $d < 0$ then
  return $-1$   // right turn
else
  return $0$    // collinear
```

To see the arithmetic end to end, fix $A = (1,1)$ and $B = (5,3)$ and test three
different third points, evaluating $d = (b_x-a_x)(c_y-a_y) - (b_y-a_y)(c_x-a_x)$
with $(b_x-a_x, b_y-a_y) = (4, 2)$ throughout:

| $C$ | $(c_x-a_x,\ c_y-a_y)$ | $d = 4(c_y{-}1) - 2(c_x{-}1)$ | verdict |
| --- | --- | --- | --- |
| $(2, 4)$ | $(1, 3)$ | $4\cdot 3 - 2\cdot 1 = 10 > 0$ | left turn |
| $(3, 2)$ | $(2, 1)$ | $4\cdot 1 - 2\cdot 2 = 0$ | collinear |
| $(4, 1)$ | $(3, 0)$ | $4\cdot 0 - 2\cdot 3 = -6 < 0$ | right turn |

The middle row is the important one: $(3,2)$ is the exact midpoint of $A$ and $B$,
so it lies _on_ the line, and the primitive returns a clean integer $0$ rather
than a floating-point near-zero that a threshold test might misclassify. That
exactness is why the collinearity test never needs an epsilon.

::impl{algo="orientation"}

## Segment intersection

When do two segments $\overline{AB}$ and $\overline{CD}$ cross? The slope-and-solve
approach drags in division and degenerate cases; orientation makes it a handful of
sign comparisons. **Straddling** drives it: segment $\overline{AB}$ _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_.

> **Claim (proper intersection).** Segments $\overline{AB}$ and $\overline{CD}$
> intersect at an interior point iff each straddles the other's supporting line:
> $$\ccw(A,B,C)\cdot\ccw(A,B,D) < 0 \quad\text{and}\quad \ccw(C,D,A)\cdot\ccw(C,D,B) < 0.$$

> **Proof.** If $C$ and $D$ are strictly on opposite sides of line $AB$, the open
> segment $\overline{CD}$ crosses that line exactly once, at some point $P$; the
> symmetric straddling condition forces $P$ to also lie strictly between $A$ and
> $B$. Both products being negative thus pins the crossing to the interior of
> _both_ segments, and conversely an interior crossing makes each pair of
> endpoints straddle the other line. $\qed$

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_ $AB$; the segments touch iff $C$ lies _on the segment_
  $\overline{AB}$, i.e. $C$'s coordinates are within the bounding box of $A$ and
  $B$ (an `on-segment` check: $\min(a_x,b_x)\le c_x\le\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
caption: $\textsc{SegmentsIntersect}(A,B,C,D)$ — proper crossings plus collinear/touching
$d_1 \gets \textsc{Orientation}(C,D,A);\ \ d_2 \gets \textsc{Orientation}(C,D,B)$
$d_3 \gets \textsc{Orientation}(A,B,C);\ \ d_4 \gets \textsc{Orientation}(A,B,D)$
if $d_1 d_2 < 0$ and $d_3 d_4 < 0$ then
  return true   // proper crossing
if $d_1 = 0$ and $\textsc{OnSegment}(C,D,A)$ then return true
if $d_2 = 0$ and $\textsc{OnSegment}(C,D,B)$ then return true
if $d_3 = 0$ and $\textsc{OnSegment}(A,B,C)$ then return true
if $d_4 = 0$ and $\textsc{OnSegment}(A,B,D)$ then return true
return false
```

$$
% caption: $\overline{AB},\overline{CD}$ cross iff each straddles the other
\begin{tikzpicture}[
  every node/.style={font=\small},
  dot/.style={circle, fill, inner sep=1.3pt},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % crossing pair
  \node[dot, label=left:$A$]  (A) at (0,0)   {};
  \node[dot, label=right:$B$] (B) at (3,1.6) {};
  \node[dot, label=above:$C$] (C) at (0.4,1.8){};
  \node[dot, label=below:$D$] (D) at (2.8,-0.2){};
  \draw[thick] (A) -- (B);
  \draw[thick] (C) -- (D);
  \node[dot, fill=acc] (X) at (1.62,0.86) {};
  \node[acc] at (2.0,1.3) {cross};
  \node[font=\footnotesize] at (0.1,-0.85) {ccw(A B C) $>$ 0,\ \ ccw(A B D) $<$ 0};
  \node[font=\footnotesize] at (0.1,-1.3) {ccw(C D A) $<$ 0,\ \ ccw(C D B) $>$ 0};
  % non-crossing / collinear case to the right
  \begin{scope}[xshift=6.2cm]
    \node[dot, label=left:$A$]  (A2) at (0,0)   {};
    \node[dot, label=right:$B$] (B2) at (2.6,0) {};
    \node[dot, label=left:$C$]  (C2) at (0.6,0.9){};
    \node[dot, label=right:$D$] (D2) at (2.4,0.9){};
    \draw[thick] (A2) -- (B2);
    \draw[thick] (C2) -- (D2);
    \node[font=\footnotesize] at (1.3,-0.7) {same side $\Rightarrow$ no cross};
  \end{scope}
\end{tikzpicture}
$$

Run the generic case on integers. Let $\overline{AB}$ go from $A=(0,0)$ to
$B=(4,4)$ and $\overline{CD}$ from $C=(0,4)$ to $D=(4,0)$ — the two diagonals of a
square, which plainly cross at $(2,2)$. The four orientations are

$$
\begin{aligned}
d_1 &= \ccw(C,D,A) = (4-0)(0-4)-(0-4)(0-0) = -16 < 0,\\
d_2 &= \ccw(C,D,B) = (4-0)(4-4)-(0-4)(4-0) = +16 > 0,\\
d_3 &= \ccw(A,B,C) = (4-0)(4-0)-(4-0)(0-0) = +16 > 0,\\
d_4 &= \ccw(A,B,D) = (4-0)(0-0)-(4-0)(4-0) = -16 < 0.
\end{aligned}
$$

Both products $d_1 d_2 = -256 < 0$ and $d_3 d_4 = -256 < 0$ are negative, so each
segment straddles the other's line and the test reports a proper crossing — all
without ever solving for the point $(2,2)$. Now shorten the second segment to
$C=(0,4)$, $D=(1,3)$, a stub that stops well short of the diagonal $AB$. Both $C$
and $D$ lie on the same side of line $AB$ (the line $y=x$): $d_3 = \ccw(A,B,C) = +16 > 0$
and $d_4 = \ccw(A,B,D) = (4)(3)-(4)(1) = +8 > 0$, so $d_3 d_4 > 0$ and
the test reports **no** crossing, again with no coordinates computed.

::impl{algo="segment_intersect"}

## 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**:

$$
\text{Area} \;=\; \frac12\abs{\sum_{i=0}^{n-1}\parens{x_i\, y_{i+1} - x_{i+1}\, y_i}}
\;=\; \frac12\abs{\sum_{i=0}^{n-1} P_i \times P_{i+1}}.
$$

Each term $x_i y_{i+1} - x_{i+1} y_i$ equals the cross product $P_i \times P_{i+1}$,
so the area is _a sum of cross products, halved_.

> **Intuition.** $\frac12(P_i \times P_{i+1})$ is the signed area of the triangle
> $O P_i P_{i+1}$ from the origin. As $i$ sweeps the boundary, the triangles
> outside the polygon are swept once forward and once backward and cancel, leaving
> exactly the enclosed area. The origin need not be inside the polygon — the signs
> handle it.

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.[^skiena-area] The full derivation — the trapezoid sum that proves
the formula — is in
[Polygons & Proximity](/algorithms/computational-geometry/polygons-and-proximity).

$$
% caption: Shoelace sums signed triangles $\tfrac12(P_i\times P_{i+1})$ from $O$; exterior
%          sweeps cancel
\begin{tikzpicture}[
  every node/.style={font=\small},
  dot/.style={circle, fill, inner sep=1.3pt},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % each signed triangle gets its own hue so the faces read apart; warm red = the
  % negative (exterior) sweep that cancels, cool blue/green = the two positive faces.
  % SOLID theme tints (no opacity, no white label boxes) so the pipeline remaps them
  % cleanly for dark mode — opacity blends against white and bakes in a light cast.
  \node[dot, label=below left:$O$] (O) at (0,0) {};
  \node[dot, label={[label distance=1pt]above right:$P_0$}] (P0) at (1,0.5) {};
  \node[dot, label=right:$P_1$] (P1) at (4,1) {};
  \node[dot, label=above:$P_2$] (P2) at (2.5,3) {};
  \fill[acc!20] (O.center) -- (P0.center) -- (P1.center) -- cycle;
  \fill[green!30] (O.center) -- (P1.center) -- (P2.center) -- cycle;
  \fill[red!25] (O.center) -- (P2.center) -- (P0.center) -- cycle;
  \draw[acc, very thick] (P0) -- (P1) -- (P2) -- cycle;
  \draw[dashed] (O) -- (P0);
  \draw[dashed] (O) -- (P1);
  \draw[dashed] (O) -- (P2);
  \node[font=\footnotesize, acc] at (2.45,0.5) {+};
  \node[font=\footnotesize, green!55!black] at (3.05,1.7) {+};
  \node[font=\footnotesize, red!75!black] at (1.2,1.5) {-};
\end{tikzpicture}
$$

For example, take the square listed
counterclockwise, $P_0=(0,0)$, $P_1=(2,0)$, $P_2=(2,2)$, $P_3=(0,2)$. The four
cross terms $x_i y_{i+1}-x_{i+1}y_i$ are $0\cdot0-2\cdot0=0$, $2\cdot2-2\cdot0=4$,
$2\cdot2-0\cdot2=4$, and $0\cdot0-0\cdot2=0$, summing to $8$. Halved, the area is
$4$ — the $2\times 2$ square, exactly. Reverse the vertex order and the sum is
$-8$; the sign flip is the only difference, and it reports the winding direction.

::impl{algo="shoelace_area"}

## 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.[^erickson-pip]

$$
% caption: Ray casting: a $+x$ ray crossing an odd count of edges means inside
\begin{tikzpicture}[
  every node/.style={font=\small},
  dot/.style={circle, fill, inner sep=1.3pt},
  >=stealth, scale=0.9]
  \definecolor{acc}{HTML}{2348F2}
  \draw[thick]
    (0,0) -- (5,0) -- (5,4) -- (2.5,2) -- (0,4) -- cycle;
  \node[dot, fill=acc, label={[fill=white, inner sep=1pt]above left:$q$}] (q) at (0.6,3) {};
  \draw[acc, very thick, ->] (q) -- (6.0,3);
  \fill[acc] (1.25,3) circle (1.4pt);
  \fill[acc] (3.75,3) circle (1.4pt);
  \fill[acc] (5,3)    circle (1.4pt);
  % count labels sit clear to the right of each ray (the polygon ends at x=5)
  \node[acc, font=\footnotesize, anchor=west] at (6.15,3.18) {odd (3) $\Rightarrow$ inside};
  % q2 is just above the notch vertex, hence OUTSIDE; label it down in the clear left lobe
  \node[dot] (q2) at (2.5,2.5) {};
  \node[font=\small] (q2l) at (1.75,1.95) {$q_2$};
  \draw[thin, black] (q2l) -- (q2);
  \draw[dashed, ->] (q2) -- (6.0,2.5);
  \fill (3.125,2.5) circle (1.4pt);
  \fill (5,2.5) circle (1.4pt);
  \node[font=\footnotesize, anchor=west] at (6.15,2.32) {even (2) $\Rightarrow$ outside};
\end{tikzpicture}
$$

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 $\langle P_k, P_{k+1}\rangle$
that could contain $q$; one last orientation test against the edge
$\overline{P_k P_{k+1}}$ decides inside vs. outside.

$$
% caption: Convex $O(\log n)$ point location: binary-search the fan from $P_0$ for $q$'s
%          wedge, then one $\ccw$ on the far edge
\begin{tikzpicture}[
  every node/.style={font=\small},
  dot/.style={circle, fill, inner sep=1.3pt},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % convex polygon, vertices in CCW order around P0 at lower left
  \node[dot, label=below left:$P_0$]  (P0) at (0,0)     {};
  \node[dot, label=below:$P_1$]       (P1) at (3.4,-0.2){};
  \node[dot, label=right:$P_2$]       (P2) at (4.6,1.8) {};
  \node[dot, label=above:$P_3$]       (P3) at (2.8,3.4) {};
  \node[dot, label=above left:$P_4$]  (P4) at (0.6,3.0) {};
  % the located wedge, shaded
  \fill[acc, opacity=0.15] (P0.center) -- (P2.center) -- (P3.center) -- cycle;
  \draw[acc, very thick] (P0) -- (P1) -- (P2) -- (P3) -- (P4) -- cycle;
  % the diagonal fan from P0 (binary-search rays)
  \draw[dashed] (P0) -- (P2);
  \draw[dashed] (P0) -- (P3);
  % query point inside the located wedge
  \node[dot, fill=acc, label={[fill=white, inner sep=1pt]right:$q$}] (q) at (2.7,1.9) {};
  % the deciding edge highlighted in red (the final ccw)
  \draw[red!75!black, very thick] (P2) -- (P3);
  \node[red!75!black, font=\footnotesize, align=center] at (5.15,3.1)
    {f\/inal ccw\\on edge $P_2 P_3$};
  \draw[red!75!black, ->, thick] (4.55,2.85) to[bend right=14] (3.75,2.65);
  \node[acc, font=\footnotesize] at (1.55,1.35) {wedge $P_2 P_3$};
\end{tikzpicture}
$$

::impl{algo="point_in_polygon_primitive"}

## Robust predicates and adaptive precision

The lesson's exact-integer stance works whenever inputs are integers and the
predicates stay low-degree — orientation is degree $2$, the in-circle test used
by Delaunay triangulation is degree $4$. But real geometric software must handle
**floating-point** inputs (coordinates from sensors, CAD, GIS), and there the
orientation determinant $(b_x-a_x)(c_y-a_y)-(b_y-a_y)(c_x-a_x)$ can suffer
_catastrophic cancellation_: when three points are nearly collinear the two
products are nearly equal, and subtracting them in `double` can return a value
whose **sign is wrong**. A wrong sign is worse than a small numerical error: it can
make a hull algorithm loop forever, or a triangulation report a non-planar mesh.
Integer arithmetic avoids this failure entirely.

The standard fix is **adaptive-precision exact predicates**, developed by Jonathan
Shewchuk (1997).[^shewchuk] The idea reconciles speed with correctness. First
evaluate the determinant in fast floating point _together with an error bound_ on
the roundoff; if the computed value exceeds that bound in magnitude, its sign is
certified correct and we return immediately — the common case, at nearly the cost
of the naive test. Only when the value falls inside the error bound (the points
are close to collinear, exactly when the sign is in doubt) does the code fall back
to slower **exact arithmetic**, and even then it computes just enough extra digits
to resolve the sign, not the full exact value. This staged strategy is what makes
industrial-strength libraries reliable.

$$
% caption: Adaptive predicate: fast float estimate with an error bound; certify the
%          sign when it clears the bound, else escalate precision until it does.
\begin{tikzpicture}[>=Stealth, font=\small,
    b/.style={draw, minimum height=9mm, minimum width=30mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[b] (est)  at (0,0)    {f\/loat estimate\\+ error bound};
  \node[b, draw=acc] (chk) at (4.6,0) {estimate exceeds\\error bound?};
  \node[b] (fast) at (9.4,0.9) {return sign\\(fast path)};
  \node[b] (exact) at (9.4,-0.9) {escalate to\\exact digits};
  \draw[->] (est) -- (chk);
  \draw[->, acc] (chk.north) |- (fast.west) node[pos=0.75, above, font=\scriptsize]{yes};
  \draw[->] (chk.south) |- (exact.west) node[pos=0.75, below, font=\scriptsize]{no};
  \draw[->] (exact.east) .. controls (11.9,-0.9) and (11.9,0.9) .. (fast.east);
\end{tikzpicture}
$$

The alternative philosophy, followed by CGAL's _exact geometric computation_
paradigm, is to make every predicate exact from the start using number types that
carry as much precision as needed, accepting a constant-factor slowdown for a
guarantee of topological consistency.[^cgal] The choice between
_epsilon comparisons_ and _exact predicates_ is not pedantry:
downstream combinatorics depends on the orientation sign as a discrete
decision, so a single flipped sign corrupts the whole structure. Keeping inputs
integer, as we do here, is the simplest way to get exactness for free.

## 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** $\vec a\cdot\vec b = a_xb_x+a_yb_y$ has the sign of
  $\cos\theta$: positive/zero/negative $\Rightarrow$ acute/right/obtuse — it
  handles projection, perpendicularity, and angle.
- The **cross product** $\vec a\times\vec b = a_xb_y-a_yb_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** $\frac12\abs{\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-primitives]: **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-area]: **Skiena**, § — Computational Geometry: the shoelace (surveyor's) formula for polygon area as a sum of cross products, whose sign gives vertex orientation.
[^erickson-pip]: **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.
[^shewchuk]: Jonathan R. Shewchuk, "Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates," _Discrete & Computational Geometry_ 18(3), 1997 — fast float estimate with a certified error bound, escalating to exact arithmetic only when the sign is in doubt.
[^cgal]: The CGAL project (Computational Geometry Algorithms Library) and the _exact geometric computation_ paradigm of Yap and Dubé — evaluating predicates with exact number types to guarantee topological consistency at a constant-factor cost.