Sutherland–Hodgman convex polygon clipping: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Intersect two strictly convex polygons by clipping the subject against one oriented clip edge at a time.

Visit each oriented clip edge, retaining subject vertices in its inside half-plane and inserting intersections where a subject edge enters or exits. Canonicalize the remaining boundary after all clip edges are processed.

Open the 3D visualization

Sutherland–Hodgman convex polygon clipping example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Sutherland–Hodgman convex polygon clipping

Intersecting two small ordered convex polygons while inspecting each clipping stage.

Choosing an alternative

This routine intersects convex rings, unlike the segment predicate that only classifies one pair of edges. General concave subjects, holes and multi-contour clipping require additional representation or algorithms beyond this bounded contract.

Worked example: input and state changes

Example input

-6,-3;6,-3;6,3;-6,3|-4,-4;4,-4;4,4;-4,4

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Subject and clip boundaries; gold marks the retained intersection.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7,
        8,
        9,
        10,
        11
      ],
      "active": [],
      "kind": "graph",
      "points": [
        [
          -6,
          -3
        ],
        [
          6,
          -3
        ],
        [
          6,
          3
        ],
        [
          -6,
          3
        ],
        [
          -4,
          -4
        ],
        [
          4,
          -4
        ],
        [
          4,
          4
        ],
        [
          -4,
          4
        ],
        [
          -6,
          -3
        ],
        [
          6,
          -3
        ],
        [
          6,
          3
        ],
        [
          -6,
          3
        ]
      ],
      "nodeLabels": [
        "S0",
        "S1",
        "S2",
        "S3",
        "C0",
        "C1",
        "C2",
        "C3",
        "(-6, -3)",
        "(6, -3)",
        "(6, 3)",
        "(-6, 3)"
      ],
      "pointMarkerIndices": [
        8,
        9,
        10,
        11
      ],
      "pointLabelIndices": [
        8,
        9,
        10,
        11
      ],
      "polygons": [
        {
          "indices": [
            0,
            1,
            2,
            3
          ],
          "color": [
            0.25,
            0.35,
            0.5
          ],
          "layer": 0
        },
        {
          "indices": [
            4,
            5,
            6,
            7
          ],
          "color": [
            0.25,
            0.25,
            0.5
          ],
          "layer": 1
        },
        {
          "indices": [
            8,
            9,
            10,
            11
          ],
          "color": [
            0.65,
            0.42,
            0.12
          ],
          "layer": 2
        }
      ],
      "directed": false,
      "chosen": [
        8,
        9,
        10,
        11
      ],
      "visited": [],
      "result": 0,
      "output": []
    }
  2. Step 1: Clip against oriented edge 0: 4 retained vertices.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7,
        8,
        9,
        10,
        11
      ],
      "active": [
        4,
        5
      ],
      "kind": "graph",
      "points": [
        [
          -6,
          -3
        ],
        [
          6,
          -3
        ],
        [
          6,
          3
        ],
        [
          -6,
          3
        ],
        [
          -4,
          -4
        ],
        [
          4,
          -4
        ],
        [
          4,
          4
        ],
        [
          -4,
          4
        ],
        [
          -6,
          -3
        ],
        [
          6,
          -3
        ],
        [
          6,
          3
        ],
        [
          -6,
          3
        ]
      ],
      "nodeLabels": [
        "S0",
        "S1",
        "S2",
        "S3",
        "C0",
        "C1",
        "C2",
        "C3",
        "(-6, -3)",
        "(6, -3)",
        "(6, 3)",
        "(-6, 3)"
      ],
      "pointMarkerIndices": [
        8,
        9,
        10,
        11,
        4,
        5
      ],
      "pointLabelIndices": [
        8,
        9,
        10,
        11
      ],
      "polygons": [
        {
          "indices": [
            0,
            1,
            2,
            3
          ],
          "color": [
            0.25,
            0.35,
            0.5
          ],
          "layer": 0
        },
        {
          "indices": [
            4,
            5,
            6,
            7
          ],
          "color": [
            0.25,
            0.25,
            0.5
          ],
          "layer": 1
        },
        {
          "indices": [
            8,
            9,
            10,
            11
          ],
          "color": [
            0.65,
            0.42,
            0.12
          ],
          "layer": 2
        }
      ],
      "directed": false,
      "chosen": [
        8,
        9,
        10,
        11
      ],
      "visited": [],
      "result": 0,
      "output": []
    }
  3. Step 3: Clip against oriented edge 2: 4 retained vertices.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7,
        8,
        9,
        10,
        11
      ],
      "active": [
        6,
        7
      ],
      "kind": "graph",
      "points": [
        [
          -6,
          -3
        ],
        [
          6,
          -3
        ],
        [
          6,
          3
        ],
        [
          -6,
          3
        ],
        [
          -4,
          -4
        ],
        [
          4,
          -4
        ],
        [
          4,
          4
        ],
        [
          -4,
          4
        ],
        [
          -6,
          -3
        ],
        [
          4,
          -3
        ],
        [
          4,
          3
        ],
        [
          -6,
          3
        ]
      ],
      "nodeLabels": [
        "S0",
        "S1",
        "S2",
        "S3",
        "C0",
        "C1",
        "C2",
        "C3",
        "(-6, -3)",
        "(4, -3)",
        "(4, 3)",
        "(-6, 3)"
      ],
      "pointMarkerIndices": [
        8,
        9,
        10,
        11,
        6,
        7
      ],
      "pointLabelIndices": [
        8,
        9,
        10,
        11
      ],
      "polygons": [
        {
          "indices": [
            0,
            1,
            2,
            3
          ],
          "color": [
            0.25,
            0.35,
            0.5
          ],
          "layer": 0
        },
        {
          "indices": [
            4,
            5,
            6,
            7
          ],
          "color": [
            0.25,
            0.25,
            0.5
          ],
          "layer": 1
        },
        {
          "indices": [
            8,
            9,
            10,
            11
          ],
          "color": [
            0.65,
            0.42,
            0.12
          ],
          "layer": 2
        }
      ],
      "directed": false,
      "chosen": [
        8,
        9,
        10,
        11
      ],
      "visited": [],
      "result": 0,
      "output": []
    }
  4. Step 4: Clip against oriented edge 3: 4 retained vertices.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7,
        8,
        9,
        10,
        11
      ],
      "active": [
        7,
        4
      ],
      "kind": "graph",
      "points": [
        [
          -6,
          -3
        ],
        [
          6,
          -3
        ],
        [
          6,
          3
        ],
        [
          -6,
          3
        ],
        [
          -4,
          -4
        ],
        [
          4,
          -4
        ],
        [
          4,
          4
        ],
        [
          -4,
          4
        ],
        [
          -4,
          -3
        ],
        [
          4,
          -3
        ],
        [
          4,
          3
        ],
        [
          -4,
          3
        ]
      ],
      "nodeLabels": [
        "S0",
        "S1",
        "S2",
        "S3",
        "C0",
        "C1",
        "C2",
        "C3",
        "(-4, -3)",
        "(4, -3)",
        "(4, 3)",
        "(-4, 3)"
      ],
      "pointMarkerIndices": [
        8,
        9,
        10,
        11,
        7,
        4
      ],
      "pointLabelIndices": [
        8,
        9,
        10,
        11
      ],
      "polygons": [
        {
          "indices": [
            0,
            1,
            2,
            3
          ],
          "color": [
            0.25,
            0.35,
            0.5
          ],
          "layer": 0
        },
        {
          "indices": [
            4,
            5,
            6,
            7
          ],
          "color": [
            0.25,
            0.25,
            0.5
          ],
          "layer": 1
        },
        {
          "indices": [
            8,
            9,
            10,
            11
          ],
          "color": [
            0.65,
            0.42,
            0.12
          ],
          "layer": 2
        }
      ],
      "directed": false,
      "chosen": [
        8,
        9,
        10,
        11
      ],
      "visited": [],
      "result": 0,
      "output": []
    }
  5. Step 5: Canonical intersection: 4 boundary vertices.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7,
        8,
        9,
        10,
        11
      ],
      "active": [],
      "kind": "graph",
      "points": [
        [
          -6,
          -3
        ],
        [
          6,
          -3
        ],
        [
          6,
          3
        ],
        [
          -6,
          3
        ],
        [
          -4,
          -4
        ],
        [
          4,
          -4
        ],
        [
          4,
          4
        ],
        [
          -4,
          4
        ],
        [
          -4,
          -3
        ],
        [
          4,
          -3
        ],
        [
          4,
          3
        ],
        [
          -4,
          3
        ]
      ],
      "nodeLabels": [
        "S0",
        "S1",
        "S2",
        "S3",
        "C0",
        "C1",
        "C2",
        "C3",
        "(-4, -3)",
        "(4, -3)",
        "(4, 3)",
        "(-4, 3)"
      ],
      "pointMarkerIndices": [
        8,
        9,
        10,
        11
      ],
      "pointLabelIndices": [
        8,
        9,
        10,
        11
      ],
      "polygons": [
        {
          "indices": [
            0,
            1,
            2,
            3
          ],
          "color": [
            0.25,
            0.35,
            0.5
          ],
          "layer": 0
        },
        {
          "indices": [
            4,
            5,
            6,
            7
          ],
          "color": [
            0.25,
            0.25,
            0.5
          ],
          "layer": 1
        },
        {
          "indices": [
            8,
            9,
            10,
            11
          ],
          "color": [
            0.65,
            0.42,
            0.12
          ],
          "layer": 2
        }
      ],
      "directed": false,
      "chosen": [
        8,
        9,
        10,
        11
      ],
      "visited": [],
      "result": 4,
      "output": [
        -4,
        -3,
        4,
        -3,
        4,
        3,
        -4,
        3
      ]
    }

Expected final state

Canonical intersection: 4 boundary vertices.

Complexity and input bounds

Family: Geometry. Time complexity: O(m(n+m)+(n+m)^2).

Implementation detail: Subject has 3..8 vertices and clip ring 3..6, finite coordinates -20..20, either winding. Downloads validate strict global convexity, return the output vertex count and write interleaved x/y doubles. Final vertices are CCW from the lexicographic minimum; points and segments are supported. Capacity 2*(n+m) suffices. Invalid inputs return -1 without writes. Half-plane tolerance 1e-9 and duplicate/collinearity threshold 1e-8 are explicit. Independent fixtures intersect edges and collect contained vertices, including reversed clip winding and boundary-only intersections, in every language.

Space complexity: O(n+m) working boundary storage excluding recorded frames and input.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

Subject x,y pairs separated by ;, then |clip x,y pairs. Subject 3..8 vertices, clip 3..6, coordinates -20..20, either winding. Both rings must be strictly convex and ordered; boundary intersections may be points or segments.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

Account for clockwise clip orientation. Preserve points on the boundary, remove repeated intersections, and distinguish an empty result from a touching point or segment. Reject unordered, concave or self-intersecting input rings.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
// Sutherland-Hodgman intersection of ordered strictly convex polygons: subject n 3..8, clip m 3..6, finite coordinates -20..20, either winding. Validate global convexity with 1e-10 threshold. Return number of CCW boundary vertices starting at lexicographic minimum, write 2*count x/y doubles; capacity 2*(n+m) suffices. Empty returns 0; touching intersections may have one or two vertices. Invalid inputs return -1 without writes. Half-plane threshold 1e-9 and duplicate/collinearity canonicalization threshold 1e-8; floating geometry is tolerance-based. Inputs unchanged. O(m*(n+m)+(n+m)^2) bounded clipping/canonicalization, O(n+m) scratch. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(sx, sy, n, cx, cy, m, output) {
    if (n < 3 || n > 8 || m < 3 || m > 6) { return -1; } let workX = Array(256).fill(0); let workY = Array(256).fill(0); let tempX = Array(256).fill(0); let tempY = Array(256).fill(0); let count = 0; let nextCount = 0; let previousInside = 0; let currentInside = 0; let previousX = 0.0; let previousY = 0.0; let currentX = 0.0; let currentY = 0.0; let previousDistance = 0.0; let currentDistance = 0.0; let ratio = 0.0; let size = 0; let nextEdge = 0; let sign = 0.0; let clipSign = 0.0; let orientation = 0.0;
    for (let ring = 0; ring < 2; ring++) { size = n; if (ring == 1) { size = m; } for (let i = 0; i < size; i++) { if (ring == 0) { workX[i] = sx[i]; workY[i] = sy[i]; } else { workX[i] = cx[i]; workY[i] = cy[i]; } if (Math.abs(workX[i]) > 20.0 || Math.abs(workY[i]) > 20.0 || workX[i] != workX[i] || workY[i] != workY[i]) { return -1; } } orientation = (workX[1]-workX[0])*(workY[2]-workY[0])-(workY[1]-workY[0])*(workX[2]-workX[0]); if (Math.abs(orientation) <= 1e-10) { return -1; } sign = -1.0; if (orientation > 0.0) { sign = 1.0; } for (let i = 0; i < size; i++) { nextEdge = (i+1)%size; for (let j = 0; j < size; j++) { if (j != i && j != nextEdge) { orientation = (workX[nextEdge]-workX[i])*(workY[j]-workY[i])-(workY[nextEdge]-workY[i])*(workX[j]-workX[i]); if (sign*orientation <= 1e-10) { return -1; } } } } if (ring == 1) { clipSign = sign; } }
    count = n; for (let i = 0; i < n; i++) { workX[i] = sx[i]; workY[i] = sy[i]; }
    for (let edge = 0; edge < m; edge++) { nextEdge = (edge+1)%m; if (count > 0) { nextCount = 0; previousX = workX[count-1]; previousY = workY[count-1]; previousDistance = clipSign*((cx[nextEdge]-cx[edge])*(previousY-cy[edge])-(cy[nextEdge]-cy[edge])*(previousX-cx[edge])); previousInside = 0; if (previousDistance >= -1e-9) { previousInside = 1; } for (let point = 0; point < count; point++) { currentX = workX[point]; currentY = workY[point]; currentDistance = clipSign*((cx[nextEdge]-cx[edge])*(currentY-cy[edge])-(cy[nextEdge]-cy[edge])*(currentX-cx[edge])); currentInside = 0; if (currentDistance >= -1e-9) { currentInside = 1; } if (previousInside != currentInside) { ratio = previousDistance/(previousDistance-currentDistance); tempX[nextCount] = previousX+ratio*(currentX-previousX); tempY[nextCount] = previousY+ratio*(currentY-previousY); nextCount++; } if (currentInside != 0) { tempX[nextCount] = currentX; tempY[nextCount] = currentY; nextCount++; } previousX = currentX; previousY = currentY; previousDistance = currentDistance; previousInside = currentInside; } count = nextCount; for (let point = 0; point < count; point++) { workX[point] = tempX[point]; workY[point] = tempY[point]; } } }
    let packed = 0; let changed = 0; let prior = 0; let nextIndex = 0; let best = 0; let last = 0; let cursor = 0; let area = 0.0; let turn = 0.0; let keyX = 0.0; let keyY = 0.0;
    for (let i = 0; i < count; i++) { if (packed == 0 || Math.abs(workX[i]-workX[packed-1])+Math.abs(workY[i]-workY[packed-1]) > 1e-8) { workX[packed] = workX[i]; workY[packed] = workY[i]; packed++; } } count = packed; if (count > 1 && Math.abs(workX[0]-workX[count-1])+Math.abs(workY[0]-workY[count-1]) <= 1e-8) { count--; }
    if (count > 1) { for (let i = 0; i < count; i++) { nextIndex = (i+1)%count; area += workX[i]*workY[nextIndex]-workY[i]*workX[nextIndex]; } if (Math.abs(area) <= 1e-8) { best = 0; last = 0; for (let i = 1; i < count; i++) { if (workX[i] < workX[best]-1e-8 || (Math.abs(workX[i]-workX[best]) <= 1e-8 && workY[i] < workY[best])) { best = i; } if (workX[i] > workX[last]+1e-8 || (Math.abs(workX[i]-workX[last]) <= 1e-8 && workY[i] > workY[last])) { last = i; } } keyX = workX[last]; keyY = workY[last]; workX[0] = workX[best]; workY[0] = workY[best]; count = 1; if (Math.abs(keyX-workX[0])+Math.abs(keyY-workY[0]) > 1e-8) { workX[1] = keyX; workY[1] = keyY; count = 2; } }
    else { changed = 1; while (changed != 0 && count > 2) { changed = 0; for (let i = 0; i < count && changed == 0; i++) { prior = (i+count-1)%count; nextIndex = (i+1)%count; turn = (workX[i]-workX[prior])*(workY[nextIndex]-workY[prior])-(workY[i]-workY[prior])*(workX[nextIndex]-workX[prior]); if (Math.abs(turn) <= 1e-8) { for (let j = i; j < count-1; j++) { workX[j] = workX[j+1]; workY[j] = workY[j+1]; } count--; changed = 1; } } } if (area < 0.0) { for (let i = 0; i < count/2; i++) { cursor = count-1-i; keyX = workX[i]; keyY = workY[i]; workX[i] = workX[cursor]; workY[i] = workY[cursor]; workX[cursor] = keyX; workY[cursor] = keyY; } } }
    } if (count > 0) { best = 0; for (let i = 1; i < count; i++) { if (workX[i] < workX[best]-1e-8 || (Math.abs(workX[i]-workX[best]) <= 1e-8 && workY[i] < workY[best])) { best = i; } } for (let i = 0; i < count; i++) { tempX[i] = workX[(best+i)%count]; tempY[i] = workY[(best+i)%count]; } for (let i = 0; i < count; i++) { workX[i] = tempX[i]; workY[i] = tempY[i]; } }
    for (let i = 0; i < count; i++) { output[2*i] = workX[i]; output[2*i+1] = workY[i]; } return count;
}

Source

Original reentrant clipping research. This teaching specialization accepts strictly convex subject and clip rings with a bounded floating-tolerance contract; it does not claim the full subject-polygon or viewing-volume generality of the paper.