Computational geometry is the algorithmic toolkit that powers graphics, GIS, robotics, and game physics: “does this polygon contain this point”, “do these two segments cross”, “what is the smallest enclosing polygon of these city points”. The primitives look simple buteed precision — the corner cases (collinear points, integer overflow, parallel lines) are where naive implementations fail. This topic covers the four algorithms that close 80% of geometry problems.

Orientation by Cross Product

The single invariant underpinning every geometry algorithm: the cross product decides orientation.

For three points p, q, r, the orientation of the path p → q → r is the sign of:

orient(p, q, r) = (q.x - p.x) * (r.y - p.y)  -  (q.y - p.y) * (r.x - p.x)
                  ↑ cross product of (q-p) and (r-p)

The cross product is by far the most-used primitive — most geometry algorithms are a sequence of cross products. Two implementation truths that matter:

• Integer arithmetic — if all inputs are integers, the cross product stays integer; no floating-point error. Use integer coordinates wherever possible; only fall to floating point when the input forces it.
• Order of operations — compute the cross product as exactly written; don’t simplify in a way that introduces cancellation error on near-collinear points. The sign matters more than the magnitude.

Two consequences that recur everywhere:

1. Segments pq and rs intersect iff the orientations orient(p, q, r) and orient(p, q, s) differ and orient(r, s, p) and orient(r, s, q) differ. (With collinear cases handled as overlaps, separately.)
2. Point r lies on segment pq (assuming orient(p, q, r) == 0) iff r.x is between min(p.x, q.x) and max(p.x, q.x) and similar for y.

Sweep Line

The sweep line is the meta-pattern of computational geometry. The setup:

• Sort the geometric objects (segments, points) by x-coordinate (or y).
• Imagine a vertical line sweeping left-to-right; at each event (an endpoint of a segment, a vertex of a polygon, a candidate collision) the algorithm updates state.
• The state at this moment is enough to answer the question with the data seen so far.

The standard win: O(n²) brute-force becomes O(n log n) because exposure order is sorted once and each event is processed in O(log n) (via balanced BST or a heap).

The mental shift: geometric queries change as their inputs move; the sweep line exposes these changes in O(log n) per event instead of O(n) per query.

Convex Hull

The convex hull of a point set is the smallest convex polygon containing every point. Two classic algorithms:

Graham Scan — O(n log n)

1. Pick the bottommost point as the anchor p0.
2. Sort all other points by polar angle around p0.
3. Walk the sorted points, maintaining a stack: at each new point, while the top two points of the stack plus the new one form a right turn (or are collinear), pop the stack. Then push the new point.

The stack at the end contains the hull vertices in counterclockwise order. The walk is O(n); the sort dominates at O(n log n).

Andrew’s Monotone Chain — O(n log n), the production-grade choice

1. Sort points lexicographically by (x, y).
2. Lower hull: walk left to right, maintaining a stack; pop while the last three make a non-strict-left turn.
3. Upper hull: walk right to left, same rule.
4. Concatenate the two halves (without duplicating endpoints).

The monoticity of the input — already sorted by x — makes the algorithm clean: each pop is amortised O(1). Andrew’s is preferred over Graham because it’s easier to implement robustly (no polar-angle tie-breaking) and uses integer arithmetic throughout.

Segment Intersection

Detecting all intersections among n segments: O(n²) naive, O((n + k) log n) by Bentley-Ottmann’s sweep (k = number of intersections).

The sweep:

1. Sort all segment endpoints by x.
2. Sweep left-to-right; maintain a balanced BST of segments ordered by their y-coordinate at the current sweep position.
3. At each event (left endpoint, right endpoint, or potential intersection), update the BST; segments that become adjacent in the tree are tested for intersection using the cross-product.
4. If two segments intersect, add the intersection as a future event; when the sweep reaches it, swap the two segments’ positions in the tree.

Point-in-Polygon

Two algorithms; one is much harder to break:

The production discipline:

1. For convex polygons: precompute vertex normals and use orientation tests — O(log n) via binary search per polygon.
2. For simple polygons: winding number is the right answer — handles concavities and self-touching cases gracefully.
3. Avoid floating-point near degeneracy: when the query point lies on a polygon edge, the geometry says “boundary”; implementations must decide an explicit policy.

Practice Trajectory

1. Implement orient(p, q, r) with integer arithmetic. Use it to implement segment-segment intersection handling all collinear overlaps. Run 50 test cases verifying the six possible relative configurations.
2. Build Andrew’s monotone chain convex hull on a random point set of 1000 points. Verify the hull passes the left-turn invariant at every vertex (every three consecutive hull vertices make a strict left turn).
3. Find all intersections among n segments using O(n²) brute force, then implement Bentley-Ottmann and verify the answer matches on randomly generated segments. Compare runtimes as n grows.
4. Implement point-in-polygon with both even-odd and winding number. Generate a polygon with a “spike” (a vertex lying exactly on a ray candidate); confirm which algorithm correctly classifies points near the spike.
5. Find the closest pair among n 2D points using sweep (O(n log n)) — or alternatively, divide-and-conquer. Compare against brute-force on 10K random points.

When It’s the Right Tool