AlgoScope

Plane Geometry

Almost every question about points in the plane comes down to one number: the cross product of two vectors, which is twice the signed area of the triangle they span. Its sign says whether three points turn left, turn right or line up. From that single test you get whether two segments cross, the area of any polygon by adding up triangles from the origin, and the convex hull by keeping only the points at which the boundary turns the right way. Everything stays in integers, so there is no rounding to worry about. Three classics build on the primitives. Graham scan finds the convex hull by sorting points around the lowest one and keeping only left turns. Closest pair divides the points at the median x, solves each side, and then checks only a thin strip around the divider, which is what makes it O(n log n). The sweep line moves across the plane one endpoint at a time, keeping the segments it currently cuts in height order, and tests only neighbours in that order, because a crossing must make two segments adjacent at some moment.

The player

Convex hull of 8 points.ABCDEFGH

Convex hull of 8 points by monotone chain: sort by x, walk left to right keeping only left turns to get the lower hull, then walk right to left for the upper hull. A point that makes a right turn would be inside the rubber band, so it is popped.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 18, with their answers.

  1. A, H, B: keep H on the lower hull?

    • Keep it, a left turn
    • Pop it, not a left turn

    Answer: Pop it, not a left turn. The turn at H is right turn.

  2. A, B, C: keep B on the lower hull?

    • Keep it, a left turn
    • Pop it, not a left turn

    Answer: Keep it, a left turn. The turn is left, so the chain stays convex.

  3. B, C, D: keep C on the lower hull?

    • Keep it, a left turn
    • Pop it, not a left turn

    Answer: Pop it, not a left turn. The turn at C is right turn.

  4. A, B, D: keep B on the lower hull?

    • Keep it, a left turn
    • Pop it, not a left turn

    Answer: Keep it, a left turn. The turn is left, so the chain stays convex.

  5. B, D, G: keep D on the lower hull?

    • Keep it, a left turn
    • Pop it, not a left turn

    Answer: Keep it, a left turn. The turn is left, so the chain stays convex.

  6. D, G, E: keep G on the lower hull?

    • Keep it, a left turn
    • Pop it, not a left turn

    Answer: Pop it, not a left turn. The turn at G is right turn.

  7. B, D, E: keep D on the lower hull?

    • Keep it, a left turn
    • Pop it, not a left turn

    Answer: Pop it, not a left turn. The turn at D is right turn.

  8. A, B, E: keep B on the lower hull?

    • Keep it, a left turn
    • Pop it, not a left turn

    Answer: Keep it, a left turn. The turn is left, so the chain stays convex.

  9. B, E, F: keep E on the lower hull?

    • Keep it, a left turn
    • Pop it, not a left turn

    Answer: Keep it, a left turn. The turn is left, so the chain stays convex.

  10. F, E, G: keep E on the upper hull?

    • Keep it, a left turn
    • Pop it, not a left turn

    Answer: Pop it, not a left turn. The turn at E is right turn.

  11. F, G, D: keep G on the upper hull?

    • Keep it, a left turn
    • Pop it, not a left turn

    Answer: Keep it, a left turn. The turn is left, so the chain stays convex.

  12. G, D, C: keep D on the upper hull?

    • Keep it, a left turn
    • Pop it, not a left turn

    Answer: Pop it, not a left turn. The turn at D is right turn.

  13. F, G, C: keep G on the upper hull?

    • Keep it, a left turn
    • Pop it, not a left turn

    Answer: Keep it, a left turn. The turn is left, so the chain stays convex.

  14. G, C, B: keep C on the upper hull?

    • Keep it, a left turn
    • Pop it, not a left turn

    Answer: Keep it, a left turn. The turn is left, so the chain stays convex.

  15. C, B, H: keep B on the upper hull?

    • Keep it, a left turn
    • Pop it, not a left turn

    Answer: Pop it, not a left turn. The turn at B is right turn.

  16. G, C, H: keep C on the upper hull?

    • Keep it, a left turn
    • Pop it, not a left turn

    Answer: Pop it, not a left turn. The turn at C is right turn.

  17. F, G, H: keep G on the upper hull?

    • Keep it, a left turn
    • Pop it, not a left turn

    Answer: Keep it, a left turn. The turn is left, so the chain stays convex.

  18. G, H, A: keep H on the upper hull?

    • Keep it, a left turn
    • Pop it, not a left turn

    Answer: Keep it, a left turn. The turn is left, so the chain stays convex.

How it runs, step by step

  1. Convex hull of 8 points by monotone chain: sort by x, walk left to right keeping only left turns to get the lower hull, then walk right to left for the upper hull. A point that makes a right turn would be inside the rubber band, so it is popped.

    Convex hull of 8 points.

  2. lower hull: push A (1, 3).

    Push A.

  3. lower hull: push H (2, 8).

    Push H.

  4. lower hull: A, H, B is not a left turn (right turn), so H cannot be on the hull between them. Pop it.

    Pop H.

  5. lower hull: push B (3, 1).

    Push B.

  6. lower hull: push C (4, 6), since A, B, C turns left.

    Push C.

  7. lower hull: B, C, D is not a left turn (right turn), so C cannot be on the hull between them. Pop it.

    Pop C.

  8. lower hull: push D (5, 4), since A, B, D turns left.

    Push D.

  9. lower hull: push G (6, 8), since B, D, G turns left.

    Push G.

  10. lower hull: D, G, E is not a left turn (right turn), so G cannot be on the hull between them. Pop it.

    Pop G.

  11. lower hull: B, D, E is not a left turn (right turn), so D cannot be on the hull between them. Pop it.

    Pop D.

  12. lower hull: push E (7, 2), since A, B, E turns left.

    Push E.

  13. lower hull: push F (8, 7), since B, E, F turns left.

    Push F.

  14. upper hull: push F (8, 7).

    Push F.

  15. upper hull: push E (7, 2).

    Push E.

  16. upper hull: F, E, G is not a left turn (right turn), so E cannot be on the hull between them. Pop it.

    Pop E.

  17. upper hull: push G (6, 8).

    Push G.

  18. upper hull: push D (5, 4), since F, G, D turns left.

    Push D.

  19. upper hull: G, D, C is not a left turn (right turn), so D cannot be on the hull between them. Pop it.

    Pop D.

  20. upper hull: push C (4, 6), since F, G, C turns left.

    Push C.

  21. upper hull: push B (3, 1), since G, C, B turns left.

    Push B.

  22. upper hull: C, B, H is not a left turn (right turn), so B cannot be on the hull between them. Pop it.

    Pop B.

  23. upper hull: G, C, H is not a left turn (right turn), so C cannot be on the hull between them. Pop it.

    Pop C.

  24. upper hull: push H (2, 8), since F, G, H turns left.

    Push H.

  25. upper hull: push A (1, 3), since G, H, A turns left.

    Push A.

  26. Hull: A, B, E, F, G, H, 6 of 8 points, listed counter-clockwise. Sorting costs O(n log n) and each point is pushed and popped at most twice, so the chains take O(n).

    Hull with 6 points.

The code

Plane Geometry, in Python

P = namedtuple("P", "x y")
def sub(a, b): return P(a.x - b.x, a.y - b.y)                      # the vector from b to a
def dot(u, v): return u.x * v.x + u.y * v.y                        # |u||v| cos(angle)
def cross(u, v): return u.x * v.y - u.y * v.x                      # |u||v| sin(angle), signed
def dist2(a, b): return dot(sub(a, b), sub(a, b))                  # squared distance, no square root

def orient(a, b, c):
    z = cross(sub(b, a), sub(c, a))
    return (z > 0) - (z < 0)                                       # +1 left turn, -1 right, 0 collinear

def intersect(a, b, c, d):
    o1 = orient(a, b, c); o2 = orient(a, b, d)
    o3 = orient(c, d, a); o4 = orient(c, d, b)
    return o1 != o2 and o3 != o4                                   # each straddles the other's line

def area2(poly): return sum(cross(poly[i], poly[(i + 1) % len(poly)]) for i in range(len(poly)))

def hull(points):
    ordered = sorted(points, key=lambda p: (p.x, p.y))
    lower = []
    for p in ordered:
        while len(lower) >= 2 and orient(lower[-2], lower[-1], p) <= 0: lower.pop()
        lower.append(p)
    upper = []
    for p in reversed(ordered):
        while len(upper) >= 2 and orient(upper[-2], upper[-1], p) <= 0: upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]

def graham_scan(points):
    pivot = min(points, key=lambda p: (p.y, p.x))                  # lowest point, leftmost on a tie
    rest = sorted([p for p in points if p != pivot], key=cmp_to_key(  # by angle around the pivot
        lambda a, b: -o if (o := orient(pivot, a, b)) != 0 else dist2(pivot, a) - dist2(pivot, b)))
    stack = [pivot]
    for p in rest:
        while len(stack) >= 2 and orient(stack[-2], stack[-1], p) <= 0: stack.pop()
        stack.append(p)                                            # only left turns survive
    return stack

def closest(ps):                                                   # ps sorted by x; returns dist2
    if len(ps) <= 3: return min(dist2(ps[i], ps[j]) for i in range(len(ps)) for j in range(i + 1, len(ps)))
    mid = len(ps) // 2; x = ps[mid].x
    d = min(closest(ps[:mid]), closest(ps[mid:]))                  # best on either side
    strip = sorted([p for p in ps if (p.x - x) * (p.x - x) < d], key=lambda p: p.y)  # near the divider
    for i in range(len(strip)):
        for j in range(i + 1, len(strip)):
            if (strip[j].y - strip[i].y) ** 2 >= d: break          # too far up: stop
            d = min(d, dist2(strip[i], strip[j]))
    return d

def any_intersect(segs):                                           # Shamos-Hoey sweep
    events = sorted([e for s in segs for e in (Event(s.left.x, s, True), Event(s.right.x, s, False))], key=lambda e: e.x)
    active = SortedSet(key=lambda s: s.y_at(sweep_x))              # ordered by height at the sweep
    for e in events:
        sweep_x = e.x
        if e.insert:
            active.add(e.seg)                                      # check only the new neighbours
            if any(intersect(n, e.seg) for n in (active.lower(e.seg), active.higher(e.seg)) if n is not None): return True
        else:
            above = active.higher(e.seg); below = active.lower(e.seg)
            active.remove(e.seg)                                   # its neighbours meet: check them
            if above is not None and below is not None and intersect(above, below): return True
    return False

Plane Geometry, in JavaScript

const P = (x, y) => ({ x, y });
const sub = (a, b) => P(a.x - b.x, a.y - b.y);                      // the vector from b to a
const dot = (u, v) => u.x * v.x + u.y * v.y;                        // |u||v| cos(angle)
const cross = (u, v) => u.x * v.y - u.y * v.x;                      // |u||v| sin(angle), signed
const dist2 = (a, b) => dot(sub(a, b), sub(a, b));                  // squared distance, no square root

const orient = (a, b, c) => Math.sign(cross(sub(b, a), sub(c, a))); // +1 left turn, -1 right, 0 collinear

function intersect(a, b, c, d) {
  const o1 = orient(a, b, c); const o2 = orient(a, b, d);
  const o3 = orient(c, d, a); const o4 = orient(c, d, b);
  return o1 !== o2 && o3 !== o4;                                    // each straddles the other's line
}

const area2 = (poly) => poly.reduce((sum, _, i) => sum + cross(poly[i], poly[(i + 1) % poly.length]), 0);

function hull(points) {
  const ordered = [...points].sort((a, b) => a.x - b.x || a.y - b.y);
  const lower = [];
  for (const p of ordered) {
    while (lower.length >= 2 && orient(lower[lower.length - 2], lower[lower.length - 1], p) <= 0) lower.pop();
    lower.push(p);
  }
  const upper = [];
  for (const p of [...ordered].reverse()) {
    while (upper.length >= 2 && orient(upper[upper.length - 2], upper[upper.length - 1], p) <= 0) upper.pop();
    upper.push(p);
  }
  return [...lower.slice(0, -1), ...upper.slice(0, -1)];
}

function grahamScan(points) {
  const pivot = points.reduce((best, p) => ((p.y - best.y || p.x - best.x) < 0 ? p : best));  // lowest point, leftmost on a tie
  const rest = points.filter((p) => p !== pivot).sort((a, b) => {                             // by angle around the pivot
    const o = orient(pivot, a, b); return o !== 0 ? -o : dist2(pivot, a) - dist2(pivot, b);
  });
  const stack = [pivot];
  for (const p of rest) {
    while (stack.length >= 2 && orient(stack[stack.length - 2], stack[stack.length - 1], p) <= 0) stack.pop();
    stack.push(p);                                                  // only left turns survive
  }
  return stack;
}

function closest(ps) {                                              // ps sorted by x; returns dist2
  if (ps.length <= 3) return Math.min(...ps.flatMap((_, i) => ps.slice(i + 1).map((q) => dist2(ps[i], q))));
  const mid = Math.floor(ps.length / 2); const x = ps[mid].x;
  let d = Math.min(closest(ps.slice(0, mid)), closest(ps.slice(mid)));            // best on either side
  const strip = ps.filter((p) => (p.x - x) * (p.x - x) < d).sort((a, b) => a.y - b.y);  // near the divider
  for (let i = 0; i < strip.length; i++) {
    for (let j = i + 1; j < strip.length; j++) {
      if ((strip[j].y - strip[i].y) ** 2 >= d) break;                              // too far up: stop
      d = Math.min(d, dist2(strip[i], strip[j]));
    }
  }
  return d;
}

function anyIntersect(segs) {                                       // Shamos-Hoey sweep
  const events = segs.flatMap((s) => [new Event(s.left.x, s, true), new Event(s.right.x, s, false)]).sort((a, b) => a.x - b.x);
  const active = new SortedSet((s) => s.yAt(sweepX));               // ordered by height at the sweep
  for (const e of events) {
    sweepX = e.x;
    if (e.insert) {
      active.add(e.seg);                                            // check only the new neighbours
      if ([active.lower(e.seg), active.higher(e.seg)].some((n) => n != null && intersect(n, e.seg))) return true;
    } else {
      const above = active.higher(e.seg); const below = active.lower(e.seg);
      active.remove(e.seg);                                         // its neighbours meet: check them
      if (above != null && below != null && intersect(above, below)) return true;
    }
  }
  return false;
}

Plane Geometry, in Kotlin

data class P(val x: Int, val y: Int)
fun sub(a: P, b: P) = P(a.x - b.x, a.y - b.y)                      // the vector from b to a
fun dot(u: P, v: P) = u.x * v.x + u.y * v.y                        // |u||v| cos(angle)
fun cross(u: P, v: P) = u.x * v.y - u.y * v.x                      // |u||v| sin(angle), signed
fun dist2(a: P, b: P) = dot(sub(a, b), sub(a, b))                  // squared distance, no square root

fun orient(a: P, b: P, c: P) = cross(sub(b, a), sub(c, a)).sign    // +1 left turn, -1 right, 0 collinear

fun intersect(a: P, b: P, c: P, d: P): Boolean {
    val o1 = orient(a, b, c); val o2 = orient(a, b, d)
    val o3 = orient(c, d, a); val o4 = orient(c, d, b)
    return o1 != o2 && o3 != o4                                    // each straddles the other's line
}

fun area2(poly: List<P>) = poly.indices.sumOf { i -> cross(poly[i], poly[(i + 1) % poly.size]) }

fun hull(points: List<P>): List<P> {
    val sorted = points.sortedWith(compareBy({ it.x }, { it.y }))
    val lower = mutableListOf<P>()
    for (p in sorted) {
        while (lower.size >= 2 && orient(lower[lower.size - 2], lower.last(), p) <= 0) lower.removeLast()
        lower += p
    }
    val upper = mutableListOf<P>()
    for (p in sorted.asReversed()) {
        while (upper.size >= 2 && orient(upper[upper.size - 2], upper.last(), p) <= 0) upper.removeLast()
        upper += p
    }
    return lower.dropLast(1) + upper.dropLast(1)
}

fun grahamScan(points: List<P>): List<P> {
    val pivot = points.minWith(compareBy({ it.y }, { it.x }))          // lowest point, leftmost on a tie
    val rest = (points - pivot).sortedWith { a, b ->                   // by angle around the pivot
        val o = orient(pivot, a, b); if (o != 0) -o else dist2(pivot, a) - dist2(pivot, b) }
    val stack = mutableListOf(pivot)
    for (p in rest) {
        while (stack.size >= 2 && orient(stack[stack.size - 2], stack.last(), p) <= 0) stack.removeLast()
        stack += p                                                    // only left turns survive
    }
    return stack
}

fun closest(ps: List<P>): Int {                                       // ps sorted by x; returns dist2
    if (ps.size <= 3) return ps.indices.flatMap { i -> ps.indices.drop(i + 1).map { dist2(ps[i], ps[it]) } }.min()
    val mid = ps.size / 2; val x = ps[mid].x
    var d = min(closest(ps.subList(0, mid)), closest(ps.subList(mid, ps.size)))   // best on either side
    val strip = ps.filter { (it.x - x) * (it.x - x) < d }.sortedBy { it.y }          // near the divider
    for (i in strip.indices) for (j in i + 1 until strip.size) {
        if ((strip[j].y - strip[i].y).let { it * it } >= d) break                     // too far up: stop
        d = min(d, dist2(strip[i], strip[j]))
    }
    return d
}

fun anyIntersect(segs: List<Seg>): Boolean {                          // Shamos-Hoey sweep
    val events = segs.flatMap { listOf(Event(it.left.x, it, true), Event(it.right.x, it, false)) }.sortedBy { it.x }
    val active = sortedSetOf(compareBy<Seg> { it.yAt(sweepX) })      // ordered by height at the sweep
    for (e in events) {
        sweepX = e.x
        if (e.insert) {
            active += e.seg                                           // check only the new neighbours
            if (listOfNotNull(active.lower(e.seg), active.higher(e.seg)).any { intersect(it, e.seg) }) return true
        } else {
            val above = active.higher(e.seg); val below = active.lower(e.seg)
            active -= e.seg                                           // its neighbours meet: check them
            if (above != null && below != null && intersect(above, below)) return true
        }
    }
    return false
}

This lesson has no write-it-yourself editor. It is free, like every lesson, and nothing here is locked.

Remember

  • cross(u, v) = ux vy - uy vx: zero when parallel, positive for a left turn, twice the triangle area.
  • Segments cross when each one's endpoints fall on opposite sides of the other's line: four orientation tests.
  • Hulls keep only left turns (monotone chain sorts by x, Graham by angle). Closest pair checks a strip around the divider. A sweep line tests only neighbours in its active set.

Where this is used

Spatial queries in PostGISDatabases

ST_Intersects and ST_Contains in PostGIS hand the work to the GEOS library, where the answer bottoms out in orientation tests on triples of vertices. Because one wrong sign on a nearly collinear triple would report that two roads never meet, GEOS computes the determinant in ordinary doubles behind an error bound and, when the result is too close to zero to trust, recomputes it in double-double arithmetic. ST_Area never reaches GEOS at all: PostGIS sums the shoelace terms over each ring itself and subtracts the holes. The split is why a geometry engine ships its own predicate code instead of trusting plain doubles.

Polygon triangulation for map tilesGraphics

A GPU draws triangles, not polygons, so Mapbox's earcut library cuts every building and lake outline in a vector tile into triangles before rendering. It picks an ear by checking that the corner turns the right way and that no other vertex falls inside that triangle, and both of those are orientation tests. It also takes the sign of the shoelace sum over each ring and reverses the ring when the sign is wrong, so an outer ring and its holes always wind in opposite directions, which is what the step that bridges a hole into the outer ring depends on.

Collision shapes in physics enginesGames

Box2D will not take an arbitrary polygon: a polygon shape is built from the convex hull of the points you supply, and anything tucked inside the hull is dropped. Collision between two convex shapes can be settled by the separating axis test, which only has to try each polygon's edge normals, and a single concave dent destroys that guarantee. So the engine forces convexity up front and makes you build a concave body out of several convex pieces.

Design rule checking in chip layoutHardware design

A layout holds hundreds of millions of rectangles and the checker must report every pair that overlaps or sits closer than the process allows. All-pairs comparison is hopeless, so the tool sweeps a line across the die, keeps only the edges the line currently cuts in height order, and tests each new edge against its two neighbours. The textbook form is Bentley and Ottmann's 1979 algorithm, which reports every intersecting pair among n segments in O((n + k) log n) for k intersections, against O(n^2) for comparing every pair.

Why it works this way

Why the cross product and not slopes or angles?

Slope is a division, so it blows up on a vertical segment and turns exact inputs into floats you then have to compare for equality. atan2 has the same rounding problem and is far slower. cross(u, v) is two multiplications and a subtraction, it stays in integers, and its sign alone answers the question you actually asked: which side of the line through a and b does c fall on. You almost never need the angle itself, only which way it turns.

Integers do not mean safe: know where the cross product overflows

Each subtraction doubles the coordinate range, and then two of those differences are multiplied and subtracted, so for coordinates in [-c, c] the worst case is about 8c^2. On a 32-bit Int that runs out at c around 16,000, small enough to hit by accident. A signed 64-bit Long holds up to c around 1.07 x 10^9, so the 10^9 coordinates ordinary for map data stored in fixed point fit with almost no margin left, and anything larger, or a squared distance computed on the same values, breaks it. The failure is silent: you get a plausible wrong sign rather than a crash, and the hull comes back with a dent in it. Work out your own bound before you trust the sign.

What the four-orientation test really does with touching segments

The strict crossing test is o1 * o2 < 0 && o3 * o4 < 0: each segment's endpoints must land on strictly opposite sides of the other's line. The looser o1 != o2 && o3 != o4 above is not the same test, because a zero counts as different from a nonzero. Two segments sharing an endpoint, or one whose endpoint rests in the middle of the other, come back true from the loose form and false from the strict one. The case neither form handles is collinearity: two segments on the same line give all four orientations zero, so both answer false even when the segments overlap along a stretch. Covering that means adding, for each orientation that came out zero, a check that the third point actually lies between the other two. Whether touching should count is a decision about your problem, but it has to be a decision rather than an accident of which form you copied.

Why the strip in closest pair costs only O(n)

Once both halves are solved you know no two points on the same side are closer than d, so a d-by-d square lying entirely on one side holds at most four points: cut it into four squares of side d/2, and each of those has diagonal shorter than d, so each can hold only one. A strip point only needs comparing against points within d above it, a 2d-by-d rectangle straddling the divider, which by the same cut holds at most eight. So the inner loop's break on y difference fires after a constant number of steps. That constant is what turns the strip pass from quadratic into linear, and it is why the strip has to be sorted by y instead of scanned in any order.

Read more

Next up

Extended Euclid

gcd(48, 18) with coefficients

Next lesson: Extended Euclid