Sutherland–Hodgman Convex Clipping

Clipping asks a concrete question: what portion of one polygon lies inside another? Sutherland–Hodgman answers it elegantly when the clipping polygon is convex. Instead of solving the whole two-dimensional problem at once, it clips the subject polygon against one boundary line at a time.

That repeated simplification is the central idea. A convex polygon is the intersection of the inward half-planes defined by its edges. If a point survives every half-plane test, it is inside the clip polygon. If an edge of the subject crosses a boundary, we insert the crossing point so that the surviving boundary remains connected.

After processing clip edges $0$ through $k$, the current vertex list represents the part of the original subject polygon lying inside all $k+1$ corresponding half-planes.

A polygon as a sequence of half-planes

Assume the clip polygon vertices are listed counterclockwise. For a directed clip edge $A\to B$, the interior lies on its left. A point $P$ is therefore inside that edge when

$$ \operatorname{cross}(B-A,\,P-A) \ge 0. $$

The sign convention reverses if the clip polygon is clockwise. Neither convention is inherently better; inconsistency is the danger. A practical implementation can compute the clip polygon's signed area once, infer its winding, and multiply every cross product by the winding sign.

This view explains both the power and the restriction of the algorithm. Intersecting convex half-planes always leaves a convex region. A concave clip polygon cannot be described as the intersection of just the inward half-planes of all its edges: doing so keeps only a smaller convex kernel, not the concave shape.

One boundary, four transitions

For one clip edge, walk around the current polygon as directed pairs $S\to E$, where $S$ is the previous vertex and $E$ is the current vertex. Only their inside/outside states matter.

Start $S$	End $E$	What the edge does	Output
inside	inside	stays in the accepted half-plane	$E$
inside	outside	exits through the clip line	intersection only
outside	inside	enters through the clip line	intersection, then $E$
outside	outside	remains rejected	nothing

Notice that we emit vertices, not fragments. The emitted sequence is already ordered around the new polygon, so it becomes the input list for the next clip edge. The closing subject edge is handled naturally by starting with $S$ equal to the last vertex and then visiting every vertex as $E$.

Finding the crossing point

Write the subject segment as $S+t(E-S)$ and the clip line as $A+u(B-A)$. Let $r=E-S$ and $d=B-A$. Solving the two-line intersection with 2D cross products gives

$$ t=\frac{\operatorname{cross}(A-S,d)}{\operatorname{cross}(r,d)}, \qquad I=S+tr. $$

In an entering or exiting case, the classification says the segment straddles the boundary, so the infinite-line intersection should fall on the segment, apart from numerical error. If the denominator is nearly zero, the lines are parallel or almost parallel. Do not blindly divide: use the same tolerance policy as the inside test, and treat nearly coincident/on-boundary cases consistently.

A worked trace

Suppose the current subject polygon is the rectangle

$$(-1,1),\ (5,1),\ (5,4),\ (-1,4)$$

and the active clip boundary is the vertical directed edge $(3,0)\to(3,5)$. Because this direction points upward, its left half-plane is $x\le3$.

Begin with $S=(-1,4)$ and $E=(-1,1)$: inside to inside, so emit $(-1,1)$. Next, $(-1,1)\to(5,1)$ exits; its intersection is $(3,1)$, which we emit instead of $(5,1)$. The edge $(5,1)\to(5,4)$ stays outside and emits nothing. Finally, $(5,4)\to(-1,4)$ enters, so emit $(3,4)$ and then $(-1,4)$.

The new list is

$$(-1,1),\ (3,1),\ (3,4),\ (-1,4).$$

The rectangle has been trimmed without any special-case code for rectangles or vertical boundaries.

Run the same procedure for every clip edge. Later passes may introduce more intersections or erase the polygon entirely. If the list becomes empty, stop early: further half-plane intersections cannot bring geometry back.

Reference implementation

from math import fsum

Point = tuple[float, float]

def cross(ax: float, ay: float, bx: float, by: float) -> float:
    return ax * by - ay * bx

def signed_area2(poly: list[Point]) -> float:
    return fsum(poly[i][0] * poly[(i + 1) % len(poly)][1]
                - poly[i][1] * poly[(i + 1) % len(poly)][0]
                for i in range(len(poly)))

def clip_convex(subject: list[Point], clipper: list[Point],
                eps: float = 1e-12) -> list[Point]:
    if len(subject) < 3 or len(clipper) < 3:
        return []
    winding = 1.0 if signed_area2(clipper) > 0.0 else -1.0
    output = subject[:]

    for i, a in enumerate(clipper):
        b = clipper[(i + 1) % len(clipper)]
        dx, dy = b[0] - a[0], b[1] - a[1]

        def side(p: Point) -> float:
            return winding * cross(dx, dy, p[0] - a[0], p[1] - a[1])

        def intersection(s: Point, e: Point) -> Point:
            rx, ry = e[0] - s[0], e[1] - s[1]
            denom = cross(rx, ry, dx, dy)
            if abs(denom) <= eps:
                # Classification should make this rare; choose the endpoint
                # closer to the boundary rather than divide by tiny denom.
                return s if abs(side(s)) < abs(side(e)) else e
            t = cross(a[0] - s[0], a[1] - s[1], dx, dy) / denom
            return (s[0] + t * rx, s[1] + t * ry)

        incoming, output = output, []
        if not incoming:
            break
        s = incoming[-1]
        s_in = side(s) >= -eps
        for e in incoming:
            e_in = side(e) >= -eps
            if s_in and e_in:
                output.append(e)
            elif s_in and not e_in:
                output.append(intersection(s, e))
            elif not s_in and e_in:
                output.append(intersection(s, e))
                output.append(e)
            s, s_in = e, e_in
    return output

This is an educational floating-point implementation, not an exact geometric kernel. eps has coordinate units hidden inside a cross product, so a fixed value is not scale invariant. Large coordinates, nearly parallel edges, and points extremely close to a boundary can still be misclassified. Production systems often normalize coordinates, use a scale-aware error bound, remove consecutive duplicate vertices, and rely on adaptive or exact orientation predicates. The fallback in intersection avoids an unstable division; it does not mathematically resolve ambiguous geometry.

Cost and output growth

Let $m$ be the number of subject vertices and $n$ the number of clip vertices. Each clip edge scans the current output once. For convex clipping, the intermediate polygon remains convex when the subject is convex; for a general simple subject, its vertex count can change, but the standard bound is reported as $O(mn)$ time. Storage is linear in the current output size, and two vertex buffers can be reused.

The appeal is not asymptotic brilliance. It is the tiny, local state machine: one line, one edge transition, one output stream.

Degeneracies worth deciding explicitly

Points on the boundary: treating side >= -eps as inside preserves shared edges, but may create repeated vertices.
Vertex touches: an entering and exiting event can coincide at one point. Deduplicate consecutive outputs within a coherent tolerance.
Collinear overlaps: there is no unique line intersection. Keeping boundary points is usually sensible for closed-set clipping.
Zero-length edges: repeated subject or clip vertices should be removed before clipping; a zero-length clip edge defines no half-plane.
Collapsed results: the mathematical result may be a segment or point. Decide whether your API returns lower-dimensional geometry or only polygons with nonzero area.
Self-intersecting subjects: a vertex loop may no longer represent the intended filled region under a simple winding rule. Sanitize or use an overlay algorithm.

Worked Example

Trace the four cases by hand

Draw any triangle that crosses the line $x=0$. Direct the boundary downward so its left side is $x>0$. Walk the triangle cyclically, label every vertex I or O, and use the case table to write the emitted sequence. Then reverse the boundary direction without changing the inequality. Which half-plane survives, and why? Finally, move one vertex exactly onto $x=0$ and compare >= 0 with > 0.

Why convexity is non-negotiable

With a convex clipper, “inside every edge” is equivalent to “inside the polygon.” A concave polygon breaks that equivalence. Near a reflex vertex, the polygon interior is not the common intersection of the local inward half-planes. Repeated clipping can remove valid lobes, and one output list cannot naturally represent a result that splits into disconnected components.

Sutherland–Hodgman also does not compute a complete polygon Boolean arrangement. It is excellent for subject ∩ convex clipper, especially viewport clipping and graphics pipelines. It does not directly provide union, difference, XOR, holes, multiple components, or full edge provenance. General polygon Boolean overlay must discover all intersections, split edges, classify faces or fragments, and reconstruct one or more boundary cycles.

For that broader machinery—and to see where this focused half-plane method fits—return to Subdivision, overlay, and polygon Boolean operations.

The intuition to keep

Do not memorize Sutherland–Hodgman as nested loops. Remember the geometry: a convex window is a conjunction of half-plane promises. Each pass enforces one promise, and the four-case transition table repairs the boundary wherever it crosses that promise's line. By the final pass, every surviving point satisfies them all.

Cookie Consent

Sutherland–Hodgman Convex Clipping

Table of Contents