Inverted Sutherland-Hodgman

Convex polygon subtraction via half-space splitting

The Problem

You have a convex polygon and you want to cut a convex hole out of it. Boolean subtraction — the shape that remains when you remove one polygon from another.

This comes up everywhere: CSG modeling, destructible terrain, shadow volumes, navmesh hole-punching, portals and occlusion culling. It sounds simple, but the documented solutions are either over-engineered or not written down anywhere. Fortunately, Sutherland-Hodgman already encodes the answer — it just needs one small tweak.

Prior Art

Weiler-Atherton (1977) walks intersecting edge lists and chases pointers between inside/outside contour chains. It handles concave polygons, but the implementation is notoriously tricky — edge crossings, degenerate tangencies, linked structures. Overkill when both polygons are convex.

Greiner-Hormann (1998) and modern libraries like Clipper2 solve the general boolean case on arbitrary polygons. Powerful, but heavyweight — sorted edge tables, winding rules, concave-on-concave overlap. Works, but doesn't leverage convexity.

Sutherland-Hodgman (1974) is the closest fit: clip a polygon against each edge of a convex window, keeping the inside half each time. Elegant, but it computes the intersection, not the difference — and it outputs one polygon, not the fragments left behind.

What if we just invert it? Keep the outside at each edge instead of the inside.

Sutherland-Hodgman's Key Insight

A line can only enter and exit a convex polygon once. So splitting a convex polygon by a line always produces exactly two convex polygons — no concavity, no multi-part results. Invert Sutherland-Hodgman: instead of keeping the inside, peel off the outside at each edge. Every fragment stays convex, and the outside pieces are the answer.

Why it's always convex: A line can only enter and exit a convex polygon once, producing exactly two convex pieces. This holds for every intermediate fragment, so we never need to handle concave polygons or triangulation. The fragment count grows linearly with operand edges, not explosively.

The Algorithm

// "Inverted Sutherland-Hodgman" — same edge walk, but keep outside instead of inside
function subtract(subject, operand):
    remaining ← [subject]          // polygons that might still be inside
    result    ← []                  // polygons confirmed outside

    for each edge E of operand:     // each edge defines a half-space
        for each poly P in remaining:
            outside, inside ← split(P, E)
            if outside: result.add(outside)     // ✓ definitely survives
            if inside:  next_remaining.add(inside) // ? needs more clipping
        remaining ← next_remaining

    // anything still in remaining is fully inside the operand — discard
    return result

Step by Step

Subtract the red diamond from the blue square. The diamond has 4 edges, so we make 4 half-space clips:

remaining

survived (result)

clip line

operand

The Split

Each split classifies vertices, then walks the polygon building two halves simultaneously:

function split(polygon, halfSpace, eps):
    // 1. Classify every vertex
    for each vertex V:
        d ← signedDistance(V, halfSpace)
        if d > +eps:  V is OUTSIDE
        if d < −eps:  V is INSIDE
        else:         V is ON_BOUNDARY  → goes in BOTH halves

    // 2. Walk edges, collect vertices into two lists
    for each edge (Vᵢ → Vⱼ):
        add Vᵢ to its side (or both if on boundary)
        if Vᵢ and Vⱼ are on opposite sides:
            X ← intersect(edge, halfSpace)
            add X to BOTH halves        ← shared vertex prevents T-junctions

    // 3. Cleanup: snap near-duplicate vertices, discard slivers
    return { outside, inside }

Epsilon Robustness

The clip line isn't a razor — it's a thick band of width 2ε. Points inside the band are ON_BOUNDARY and go into both halves, preventing T-junctions and sliver explosions.

// Epsilon hierarchy (each 10× larger than the last)
parameterClamp  = 1e-10   // intersection t-value clamping
pointOnLine     = 1e-8    // thick half-space band width
vertexSnap      = 1e-7    // merge near-duplicate vertices
minSliverParam  = 1e-6    // discard thin fragments (2·area/perimeter)