Contents · Computational Geometry

Preliminaries: Orientation, Cross Product, Sorting
Convex Hull (Graham Scan / Monotone Chain)
Closest Pair of Points (Divide & Conquer)
Half-Plane Intersection
Robustness and Tricks
Exercises

Preliminaries: Orientation, Cross Product, Sorting

Basics | 6-minute read

function cross(ax, ay, bx, by) { return ax*by - ay*bx; }
function orient(a, b, c) { // +: left turn, -: right, 0: collinear
  return cross(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}

Sorting: for monotone chain, sort points by (x, y).
Epsilon: beware float comparisons; prefer integer if possible.

Convex Hull (Monotone Chain)

Hull | 7-minute read

// Returns hull in counter-clockwise order without repeating first point
function convexHull(points) {
  const pts = points.slice().sort((a,b) => a.x - b.x || a.y - b.y);
  if (pts.length <= 1) return pts;
  const lower = [];
  for (const p of pts) {
    while (lower.length >= 2 && orient(lower[lower.length-2], lower[lower.length-1], p) <= 0) lower.pop();
    lower.push(p);
  }
  const upper = [];
  for (let i = pts.length - 1; i >= 0; i--) {
    const p = pts[i];
    while (upper.length >= 2 && orient(upper[upper.length-2], upper[upper.length-1], p) <= 0) upper.pop();
    upper.push(p);
  }
  upper.pop(); lower.pop();
  return lower.concat(upper);
}

Complexity: O(n log n) due to sorting.
Variants: Graham scan (sort by polar angle), Andrew's monotone chain.

Closest Pair of Points (Divide & Conquer)

Distance | 8-minute read

function closestPair(points) {
  const pts = points.slice().sort((a,b) => a.x - b.x);
  function dist2(i, j) { const dx = pts[i].x - pts[j].x, dy = pts[i].y - pts[j].y; return dx*dx + dy*dy; }
  function solve(l, r) {
    if (r - l <= 3) {
      let best = Infinity;
      for (let i=l;i a.y - b.y);
      return best;
    }
    const m = (l + r) >> 1; const midx = pts[m].x;
    const dl = solve(l, m), dr = solve(m, r); let d = Math.min(dl, dr);
    const strip = [];
    for (let i=l;i a.y - b.y);
    for (let i=0;i


                    
                        Complexity: O(n log n).
                        Strip rule: only check next ~7 neighbors in y-order.



            

            
                Half-Plane Intersection
                HPI | 9-minute read
                
                    Intersection of half-planes yields a convex polygon (possibly empty/unbounded). Standard solution sorts lines by angle and maintains a deque, removing lines that make the intersection infeasible.
Outline:
1) Normalize lines, sort by angle
2) Maintain deque of candidate lines
3) While last two intersect outside the new half-plane, pop back; similarly for front
4) Intersections of adjacent lines form the polygon vertices

                
            

            

            
                Robustness and Tricks
                Caveats | 6-minute read
                
                    
                        Precision: use 64-bit integers or exact arithmetic when possible.
                        EPS: for doubles, compare with an epsilon and be consistent.
                        Degeneracies: collinear points, duplicates; decide whether to keep collinear hull edges.
                    
                
            

            

            
                Exercises
                Hands-on | 5-minute read
                
                    
                        Implement monotone chain and handle collinear points per your needs (keep/remove).
                        Closest pair returning the pair itself, not just distance.
                        Half-plane intersection for polygon clipping against multiple constraints.
                    
                    Prefer stable numeric strategies; geometry bugs are often precision bugs.