Computational geometry

Overview

Computational geometry solves problems about points, lines, and shapes: orientation, intersections, areas, convex hulls, and distances. Interview problems in this area mostly rely on a few robust primitives computed with integers, such as the cross product, rather than floating-point angles or slopes.

The cross product of vectors AB and AC tells you whether C is to the left of, to the right of, or on the line AB. From it you get polygon area (shoelace formula), convexity checks, and convex hulls (Andrew's monotone chain). Counting points on a line uses reduced slopes stored as integer pairs to avoid floating-point errors.

When to use it

• Input is a list of points, rectangles, or segments.
• Questions about collinearity, orientation, area, or enclosing shapes.
• Distances and nearest points (k closest, closest pair).
• Rectangle overlap and area of unions.

Problem patterns it solves

Where it is used in real software

Key terms

Cross product

cross(O, A, B) = (A.x - O.x)(B.y - O.y) - (A.y - O.y)(B.x - O.x). Positive: counter-clockwise turn.

Collinear

Cross product is 0: the three points are on one line.

Shoelace formula

Polygon area = |sum of (x_i y_(i+1) - x_(i+1) y_i)| / 2.

Convex hull

Smallest convex polygon containing all points.

Squared distance

dx^2 + dy^2; compare squared values to avoid sqrt.

Andrew's monotone chain convex hull

1. 1
   Sort points by x, then y

   O(n log n).

2. 2
   Build the lower hull

   For each point, while the last two hull points and this point make a non-left turn (cross <= 0), pop. Then push.

3. 3
   Build the upper hull

   Same procedure iterating points in reverse order.

4. 4
   Concatenate

   Remove the last point of each chain (it repeats the first of the other).

5. 5
   Collinear points

   Use cross < 0 instead of <= 0 to keep points on the hull edges when required.

Orientation tests with the cross product

O = (0, 0), A = (2, 0)

One integer formula answers left, right, or on-the-line with no division or floating point. Every hull, convexity, and intersection algorithm below is built on it.

Implementation

1const cross = (o, a, b) => (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);2 3// Shoelace formula4function polygonArea(points) {5  let twice = 0;6  for (let i = 0; i < points.length; i++) {7    const [x1, y1] = points[i];8    const [x2, y2] = points[(i + 1) % points.length];9    twice += x1 * y2 - x2 * y1;10  }11  return Math.abs(twice) / 2;12}13 14// Monotone chain convex hull (drops collinear edge points)15function convexHull(points) {16  const pts = [...points].sort((a, b) => a[0] - b[0] || a[1] - b[1]);17  if (pts.length <= 2) return pts;18  const build = (list) => {19    const hull = [];20    for (const p of list) {21      while (hull.length >= 2 && cross(hull.at(-2), hull.at(-1), p) <= 0) hull.pop();22      hull.push(p);23    }24    hull.pop();25    return hull;26  };27  return [...build(pts), ...build([...pts].reverse())];28}29 30// 149. Max Points on a Line: slopes as reduced integer pairs31function maxPoints(points) {32  const gcd = (a, b) => (b === 0 ? Math.abs(a) : gcd(b, a % b));33  let best = Math.min(points.length, 1);34  for (let i = 0; i < points.length; i++) {35    const slopes = new Map();36    for (let j = i + 1; j < points.length; j++) {37      let dx = points[j][0] - points[i][0], dy = points[j][1] - points[i][1];38      const g = gcd(dx, dy);39      dx /= g; dy /= g;40      if (dx < 0 || (dx === 0 && dy < 0)) { dx = -dx; dy = -dy; } // normalize sign41      const key = dx + "/" + dy;42      slopes.set(key, (slopes.get(key) ?? 1) + 1);43      best = Math.max(best, slopes.get(key));44    }45  }46  return best;47}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Using slope dy / dx as a float key.

  Fix: Use the reduced pair (dx / g, dy / g) with a normalized sign; vertical lines have dx = 0.

• Comparing distances with sqrt.

  Fix: Compare squared distances to stay exact and faster.

• Touching rectangles counted as overlapping.

  Fix: Overlap requires strictly positive width and height (use >, not >=).

Interview questions

Practice problems