4 min read
On this page

Computational Geometry Basics

Computational geometry solves problems involving geometric objects (points, lines, polygons). This covers the fundamental algorithms; advanced topics are in topic 47.

Primitives

Orientation Test (Cross Product)

Given three points P₁, P₂, P₃, determine if they make a left turn, right turn, or are collinear.

Cross product of vectors (P₂ - P₁) and (P₃ - P₁):

cross = (x₂ - x₁)(y₃ - y₁) - (y₂ - y₁)(x₃ - x₁)
  • cross > 0: Counterclockwise (left turn)
  • cross < 0: Clockwise (right turn)
  • cross = 0: Collinear
FUNCTION CROSS(o, a, b)
    RETURN (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)

This is the most fundamental operation in computational geometry. Used in convex hull, polygon area, line intersection, point-in-polygon, and more.

Line Segment Intersection

Two segments P₁P₂ and P₃P₄ intersect iff:

  1. P₃ and P₄ are on opposite sides of line P₁P₂ (cross products have different signs), AND
  2. P₁ and P₂ are on opposite sides of line P₃P₄.

Plus special cases for collinear segments.

FUNCTION SEGMENTS_INTERSECT(p1, p2, p3, p4)
    d1 ← CROSS(p3, p4, p1)
    d2 ← CROSS(p3, p4, p2)
    d3 ← CROSS(p1, p2, p3)
    d4 ← CROSS(p1, p2, p4)

    IF ((d1 > 0 AND d2 < 0) OR (d1 < 0 AND d2 > 0)) AND
       ((d3 > 0 AND d4 < 0) OR (d3 < 0 AND d4 > 0))
        RETURN true
    // Handle collinear/endpoint cases...
    RETURN false

Convex Hull

The convex hull of a set of points is the smallest convex polygon enclosing all points (like a rubber band around pins).

Graham Scan

  1. Find the lowest point (break ties by leftmost).
  2. Sort remaining points by polar angle with respect to the lowest point.
  3. Process points in order. For each point:
    • While the last two points in the hull and the new point make a clockwise turn (or are collinear), remove the middle point.
    • Add the new point.
FUNCTION CONVEX_HULL_GRAHAM(points)
    n ← length(points)
    IF n < 3 THEN RETURN points

    // Find lowest point
    min_idx ← index of point with smallest y (break ties by smallest x)
    SWAP(points[0], points[min_idx])
    origin ← points[0]

    // Sort by polar angle relative to origin
    SORT points[1..] BY polar angle from origin

    hull ← [points[0], points[1]]
    FOR i ← 2 TO n - 1
        WHILE length(hull) > 1 AND CROSS(hull[second-to-last], hull[last], points[i]) ≤ 0
            REMOVE last element FROM hull
        APPEND points[i] TO hull
    RETURN hull

Time: O(n log n) (sorting dominates).

Andrew's Monotone Chain

Build upper hull and lower hull separately. Sort points by x-coordinate.

FUNCTION CONVEX_HULL_ANDREW(points)
    n ← length(points)
    IF n < 3 THEN RETURN points
    SORT points BY x-coordinate (break ties by y)

    hull ← empty list

    // Lower hull
    FOR EACH p IN points (left to right)
        WHILE length(hull) ≥ 2 AND CROSS(hull[second-to-last], hull[last], p) ≤ 0
            REMOVE last element FROM hull
        APPEND p TO hull

    // Upper hull
    lower_len ← length(hull) + 1
    FOR EACH p IN points (right to left)
        WHILE length(hull) ≥ lower_len AND CROSS(hull[second-to-last], hull[last], p) ≤ 0
            REMOVE last element FROM hull
        APPEND p TO hull
    REMOVE last element FROM hull   // remove duplicate last point
    RETURN hull

Time: O(n log n). Often preferred over Graham scan (simpler, handles collinear points more naturally).

Jarvis March (Gift Wrapping)

Start from the leftmost point. At each step, find the point that makes the smallest counterclockwise angle with the current direction.

Time: O(nh) where h = number of hull points. Output-sensitive — fast when the hull has few vertices.

Line Segment Intersection (Sweep Line)

Given n line segments, find all intersection points.

Bentley-Ottmann Algorithm

Sweep line: A vertical line sweeps left to right. Maintain a status structure (balanced BST) of segments ordered by y-coordinate at the sweep line.

Events (processed left to right):

  • Left endpoint: Insert segment into status. Check intersection with neighbors.
  • Right endpoint: Remove segment. Check if its former neighbors now intersect.
  • Intersection: Swap the two segments in the status. Check new neighbors.

Time: O((n + k) log n) where k = number of intersections. Much better than O(n²) brute force when k is small.

Closest Pair of Points

Find the two points with minimum Euclidean distance.

Divide-and-conquer algorithm covered in the divide-and-conquer file. O(n log n).

Point in Polygon

Ray Casting

Cast a ray from the point to infinity. Count intersections with polygon edges.

  • Odd count: Inside.
  • Even count: Outside.
FUNCTION POINT_IN_POLYGON(point, polygon)
    n ← length(polygon)
    inside ← false
    (px, py) ← point
    j ← n - 1

    FOR i ← 0 TO n - 1
        (xi, yi) ← polygon[i]
        (xj, yj) ← polygon[j]

        IF ((yi > py) ≠ (yj > py)) AND
           (px < (xj - xi) * (py - yi) / (yj - yi) + xi)
            inside ← NOT inside
        j ← i
    RETURN inside

Time: O(n) per query. For many queries, preprocess the polygon for O(log n) queries.

Winding Number

Count how many times the polygon winds around the point. Non-zero = inside (for non-simple polygons, this gives different results than ray casting).

Polygon Area

Shoelace formula: For polygon with vertices (x₁,y₁), ..., (xₙ,yₙ):

Area = ½ |Σᵢ (xᵢyᵢ₊₁ - xᵢ₊₁yᵢ)|

where indices are modulo n.

FUNCTION POLYGON_AREA(polygon)
    n ← length(polygon)
    area ← 0
    FOR i ← 0 TO n - 1
        j ← (i + 1) MOD n
        area ← area + polygon[i].x * polygon[j].y
        area ← area - polygon[j].x * polygon[i].y
    RETURN |area| / 2

Time: O(n). The signed area is positive for counterclockwise ordering, negative for clockwise.

Triangulation

Decompose a polygon into triangles.

Ear clipping: Find an "ear" (a triangle formed by three consecutive vertices that contains no other vertex). Remove it. Repeat. O(n²).

Monotone polygon triangulation: Decompose into y-monotone polygons, then triangulate each in O(n) total.

Delaunay triangulation: Triangulation of a point set that maximizes the minimum angle. Covered in topic 47.

Applications in CS

  • Computer graphics: Convex hull for collision detection bounding. Point-in-polygon for picking/selection. Triangulation for rendering.
  • GIS: Point-in-polygon for geofencing. Polygon area for land measurement. Spatial queries.
  • Robotics: Convex hull for workspace boundaries. Line intersection for collision detection. Motion planning.
  • Game development: Collision detection (GJK algorithm uses convex hulls). Navigation mesh generation uses triangulation.
  • Computer vision: Convex hull of feature points. Line detection (Hough transform).
  • VLSI: Wire routing (line intersection). Chip floorplanning (polygon operations).
  • Computational biology: Protein surface analysis, molecular docking.