Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 50 ยท Clipping

Polygon Clipping: Sutherland-Hodgman

Clip polygons against a window one edge at a time with the Sutherland-Hodgman algorithm: the four cases, concave pitfalls, Weiler-Atherton and a live clipper.

Clipping a line gives you a line. Clipping a polygon is harder, because the result must still be a polygon: if a triangle sticks out of the window you cannot just cut its edges, you also need new edges along the window boundary to close the shape again. Imagine a filled star partly outside the screen. Drawing only the clipped outline would leave an open shape that cannot be filled.

The classic solution is the Sutherland-Hodgman algorithm. It is based on one simple idea: divide and conquer by edge. Instead of clipping against the whole window at once, clip the polygon against a single infinite boundary line (say, everything to the left of xmin is cut away), then feed the result into the next boundary, and so on. Clipping against one straight line is easy, and four easy steps give the answer for a rectangle.

Clipping against one edge

Treat one window edge as an infinite line. It splits the plane into an inside half and an outside half. Walk around the polygon edge by edge. For each polygon edge, look at its start vertex S and its end vertex E and ask which side each is on. There are exactly four cases, and each one outputs zero, one or two vertices into the new polygon:

Case S E Output
1 inside inside E
2 inside outside the intersection point I
3 outside outside nothing
4 outside inside I, then E
flowchart TD
  A["Polygon edge S to E"] --> B{"Is E inside?"}
  B -->|"yes"| C{"Is S inside?"}
  B -->|"no"| D{"Is S inside?"}
  C -->|"yes"| E1["Case 1: output E"]
  C -->|"no"| E4["Case 4: output I, then E"]
  D -->|"yes"| E2["Case 2: output I"]
  D -->|"no"| E3["Case 3: output nothing"]

Each polygon edge, tested against one clip boundary, produces 0, 1 or 2 output vertices.

Because the walk is cyclic, the first edge uses the last vertex as S. The intersection I of segment S-E with a vertical boundary x = c is found with the same parametric idea you met in Liang-Barsky clipping:

TEXT
t = (c - S.x) / (E.x - S.x)
I = (c, S.y + t * (E.y - S.y))

For a horizontal boundary y = c, swap the roles of x and y. The division is safe, because a segment that crosses the boundary cannot have E.x == S.x when the boundary is vertical.

Clipping against the whole window

Run the single-edge routine four times, once per boundary (left, right, bottom, top, in any order). The output of one pass is the input of the next:

flowchart LR
  P["input polygon"] --> L["clip left"]
  L --> R["clip right"]
  R --> B["clip bottom"]
  B --> T["clip top"]
  T --> O["clipped polygon"]

A pipeline of four identical stages.

This structure is why the algorithm matters beyond rectangles. A hardware pipeline can be built as a chain of identical clip units, and the same code clips against any convex boundary, including the six planes of a 3D view frustum, simply by changing the inside test and the intersection formula.

The code is short:

JavaScript
function clipEdge(poly, isInside, intersect) {
  const out = [];
  for (let i = 0; i < poly.length; i++) {
    const s = poly[(i + poly.length - 1) % poly.length]; // previous vertex
    const e = poly[i];
    if (isInside(e)) {
      if (!isInside(s)) out.push(intersect(s, e)); // case 4
      out.push(e);                                  // cases 1 and 4
    } else if (isInside(s)) {
      out.push(intersect(s, e));                    // case 2
    }                                               // case 3: nothing
  }
  return out;
}

Notice how the four cases collapse into three lines of logic: output E if it is inside, and output the intersection whenever the edge crosses the boundary.

Try it: watch the pipeline run

Use the buttons to step through the four passes. At each step the current polygon is drawn in blue, and the number of vertices is shown. The select box lets you try a pentagon (convex), a star (concave) and a U shape (concave, with a surprise at the end).

Sutherland-Hodgman, one boundary at a time

For the pentagon and the star, the final blue shape is exactly the part of the original inside the window. Look at the star carefully: where a spike leaves the window, new vertices (red dots) appear on the boundary, and the new edges run along the window edge. That is how the polygon stays closed.

The concave pitfall

Sutherland-Hodgman always returns one polygon. That is a problem when the true answer is several separate pieces. Take the U shape from the demo, whose two prongs stick up and whose base lies below the bottom edge of the window. After the bottom boundary has cut away the base, the correct result is two separate rectangles (the prongs). The algorithm instead returns one polygon whose vertex list contains a "bridge" along the window edge, an edge that is walked twice, once in each direction.

If you fill that polygon, nothing looks wrong, because the doubled edge has no area. But if you stroke the outline you may see an extra line along the boundary, and any later algorithm that assumes a simple polygon (an area calculation by edges, a triangulation, a hit test) can misbehave.

The following console example clips the U shape against only the bottom boundary and checks what comes out.

JS The bridge edge of a concave clip

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The area comes out right (9,900), because the bridge is traversed twice in opposite directions and its contributions cancel. That also explains why filling is safe, even though the vertex list is not a clean description of two rectangles.

Ways to handle it

  • Clip convex polygons. Break a concave polygon into convex pieces (triangles are the simplest) and clip each one. Graphics hardware clips triangles for exactly this reason.
  • Accept the bridge if the result is only going to be filled.
  • Post-process the output: find collinear overlapping edges on the boundary and split the polygon there.
  • Use a more general algorithm, such as Weiler-Atherton, when you need exact topology.

Weiler-Atherton in outline

The Weiler-Atherton algorithm clips a polygon (even a concave one, even with holes) against any polygon, concave windows included, and returns a separate polygon for each visible piece. It is more bookkeeping than math. The recipe, shown here as read-only pseudocode, is:

TEXT
1. Compute all intersection points between the subject polygon and the clip polygon.
2. Insert each intersection into both vertex lists, in order along each boundary.
3. Mark every intersection as ENTERING (the subject goes from outside to inside the clip polygon)
   or LEAVING (inside to outside).
4. While an unused ENTERING intersection exists:
     start a new output polygon at it
     follow the SUBJECT boundary until the next intersection (a LEAVING one)
     switch to the CLIP boundary and follow it until the next intersection
     keep alternating until you return to the start; the loop is one output polygon

Each output polygon is a closed loop that alternates between running along the subject and running along the window. For the U shape, the algorithm finds two separate loops, one per prong, and so avoids the bridge. The price is more complex data structures (linked lists of vertices with links between the two lists), and special cases for touching or coincident edges. Modern libraries use refined versions of this idea (Greiner-Hormann, Vatti, Martinez) for general polygon boolean operations.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A polygon edge goes from a vertex S that is outside the boundary to a vertex E that is inside. What does Sutherland-Hodgman output?

    This is case 4: the edge enters the window, so the output gets the crossing point and then the inside end vertex.
  2. 2. Why does the algorithm clip against one boundary at a time?

    Each stage handles one half-plane with four simple cases, and its output is the input of the next stage. This also generalises to 3D clip planes.
  3. 3. What can go wrong when Sutherland-Hodgman clips a concave polygon?

    The algorithm outputs a single vertex list. When the true result is several pieces, they are joined by edges along the window boundary.
  4. 4. Which algorithm correctly returns separate polygons for concave clipping cases?

    Weiler-Atherton tracks entering and leaving intersections and alternates between the subject and the window boundary, producing one loop per visible piece.

Summary

  • Sutherland-Hodgman clips a polygon against one boundary at a time, so a rectangle needs four passes in a row.
  • For each edge S to E there are four cases: both inside (output E), leaving (output the intersection), both outside (output nothing), entering (output the intersection and E).
  • The new polygon gets extra edges along the boundary, which keeps it closed and fillable.
  • For concave input the algorithm may leave overlapping bridge edges; clip convex pieces (triangles) or use Weiler-Atherton when you need exact pieces.

Next, we leave geometry for a while and look at light itself: RGB, CMY and CMYK Color Models.