Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Polygon clipping: Sutherland–Hodgeman algorithm

Sutherland–Hodgeman clips a polygon against a convex clipping region (commonly a rectangle) by iteratively clipping against each clip edge and producing a new polygon.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Polygon clipping is used whenever a rendered scene must be restricted to a viewport or window (for example, in a 2D GUI, a game view, or the windowing stage before projection). The Sutherland–Hodgeman algorithm is a standard, simple method to clip arbitrary (possibly concave) polygons against a convex clipping region (most often an axis-aligned rectangle). It is efficient and easy to implement in graphics pipelines and software renderers.

Key ideas

  • Inside test: for each clip edge you must decide whether a point is “inside” or “outside” relative to that edge. For rectangle edges:

    • Left edge (x = xmin): inside if x >= xmin.
    • Right edge (x = xmax): inside if x <= xmax.
    • Bottom edge (y = ymin): inside if y >= ymin.
    • Top edge (y = ymax): inside if y <= ymax. (These assume the usual Cartesian orientation; reverse inequalities if coordinate convention differs.)
  • Edge processing rule (Sutherland–Hodgeman): clip the polygon against each edge of the clipping region in sequence. For each clip edge, build a new output vertex list by scanning each input polygon edge from a starting vertex S (previous) to an ending vertex E (current). There are four cases:

    1. S inside, E inside -> output E.
    2. S inside, E outside -> output intersection point I of SE with clip edge.
    3. S outside, E inside -> output intersection point I, then output E.
    4. S outside, E outside -> output nothing.

    This rule preserves vertex order and produces the clipped polygon after processing all clip edges. Its time complexity is O(n*k), where n is the current number of vertices and k is the number of clip edges (k=4 for a rectangle).

  • Intersection computation: for a segment from P1(x1,y1) to P2(x2,y2), parametric form P(t) = P1 + t*(P2 - P1), t in [0,1]. Solve for t where the segment meets the clip boundary (a line). For axis-aligned edges this is simple (see Formulas). For a general clip edge given by line through points A and B, compute intersection by solving two-line equations or using determinants.

  • Assumptions and limitations:

    • The clipping region must be convex for the algorithm to produce the correct polygon. For non-convex clipping regions, Sutherland–Hodgeman can fail to produce the desired result.
    • Colinear or degenerate edges (zero-length) must be handled carefully (avoid division by zero when computing t).
  • Correctness intuition: clipping sequentially against each half-space of a convex region yields intersection of half-spaces; polygon after k edges equals original polygon intersected with first k half-spaces. Because intersection is associative and convex clipping region is intersection of its half-spaces, final polygon is original ∩ clipping region.

  • What to draw for exam diagrams: draw an axis-aligned rectangle (label xmin,xmax,ymin,ymax) and a polygon crossing it. Mark one polygon edge S->E and show the four cases (S/E inside/outside) with the intersection point I labeled. For an intersection computation, draw the segment and perpendicular projection to the vertical/horizontal clip line showing t fraction on the segment.

Formulas

P(t) = P1 + t*(P2 - P1), 0 <= t <= 1 — P(t) is the point at parameter t on segment P1->P2. P coordinates are in units of length (e.g., metres if real-world); here we use unitless screen coordinates.

For vertical clip edge x = x_edge (x2 != x1): t = (x_edge - x1) / (x2 - x1) — t is dimensionless. Intersection point: x = x_edge, y = y1 + t*(y2 - y1).

For horizontal clip edge y = y_edge (y2 != y1): t = (y_edge - y1) / (y2 - y1) — t is dimensionless. Intersection point: y = y_edge, x = x1 + t*(x2 - x1).

General intersection of segment (P1->P2) with line (P3->P4): t = ((x1 - x3)*(y3 - y4) - (y1 - y3)*(x3 - x4)) / ((x1 - x2)*(y3 - y4) - (y1 - y2)*(x3 - x4)) — t dimensionless. Then intersection point = P1 + t*(P2 - P1). Ensure denominator != 0 (parallel lines).

Worked examples

Example 1 — numerical, step-by-step (university exam style): Given polygon P: A(1,1), B(4,1), C(4,4), D(1,4) (in that order, a square). Clip window: xmin=2, xmax=3, ymin=2, ymax=3. Clip the polygon and give final clipped polygon vertices.

Step 1 — Clip against left edge x = 2. Process edges AB, BC, CD, DA with inside = x >= 2:

  • AB: S=A(1,1) outside, E=B(4,1) inside => intersection t = (2-1)/(4-1) = 1/3. I1 = (2, 1). Output I1, then B.
  • BC: S=B inside, E=C inside => output C(4,4).
  • CD: S=C inside, E=D(1,4) outside => intersection t = (2-4)/(1-4) = 2/3. I2 = (2,4). Output I2.
  • DA: both outside => nothing. Output polygon after left clip: (2,1), (4,1), (4,4), (2,4).

Step 2 — Clip against right edge x = 3 (inside: x <= 3):

  • (2,1)->(4,1): inside->outside => t = (3-2)/(4-2)=1/2 => (3,1).
  • (4,1)->(4,4): outside->outside => none.
  • (4,4)->(2,4): outside->inside => t = (3-4)/(2-4)=1/2 => (3,4), then (2,4).
  • (2,4)->(2,1): inside->inside => (2,1). Output: (3,1), (3,4), (2,4), (2,1).

Step 3 — Clip against bottom y = 2 (inside: y >= 2):

  • (3,1)->(3,4): outside->inside => t = (2-1)/(4-1)=1/3 => (3,2), then (3,4).
  • (3,4)->(2,4): inside->inside => (2,4).
  • (2,4)->(2,1): inside->outside => t = (2-4)/(1-4)=2/3 => (2,2).
  • (2,1)->(3,1): outside->outside => none. Output: (3,2), (3,4), (2,4), (2,2).

Step 4 — Clip against top y = 3 (inside: y <= 3):

  • (3,2)->(3,4): inside->outside => t = (3-2)/(4-2)=1/2 => (3,3).
  • (3,4)->(2,4): outside->outside => none.
  • (2,4)->(2,2): outside->inside => t = (3-4)/(2-4)=1/2 => (2,3), then (2,2).
  • (2,2)->(3,2): inside->inside => (3,2). Final clipped polygon: (3,3), (2,3), (2,2), (3,2). Final answer (ordered): (2,2), (3,2), (3,3), (2,3) (a unit square), which is the intersection of original square and clipping rectangle.

Example 2 — code (C++) Complete program implementing Sutherland–Hodgeman for an axis-aligned rectangular window. This program reads no stdin; it contains a sample polygon and window and prints clipped vertices. (In exams, explain algorithm and give pseudo-code; in assignments, adapt to file or stdin as needed.)

#include <bits/stdc++.h>
using namespace std;
using P = pair<double,double>;

bool inside_left(const P &p, double xmin){ return p.first >= xmin; }
bool inside_right(const P &p, double xmax){ return p.first <= xmax; }
bool inside_bottom(const P &p, double ymin){ return p.second >= ymin; }
bool inside_top(const P &p, double ymax){ return p.second <= ymax; }

P intersect_vertical(const P &p1,const P &p2,double x){
    double x1=p1.first, y1=p1.second, x2=p2.first, y2=p2.second;
    double t = (x - x1) / (x2 - x1);
    return {x, y1 + t*(y2 - y1)};
}

P intersect_horizontal(const P &p1,const P &p2,double y){
    double x1=p1.first, y1=p1.second, x2=p2.first, y2=p2.second;
    double t = (y - y1) / (y2 - y1);
    return {x1 + t*(x2 - x1), y};
}

vector<P> clip_edge(const vector<P>&in, int edge, double val){
    // edge: 0=left,1=right,2=bottom,3=top
    vector<P> out;
    if(in.empty()) return out;
    for(size_t i=0;i<in.size();++i){
        P S = in[(i+in.size()-1)%in.size()];
        P E = in[i];
        bool Sin, Ein;
        switch(edge){
            case 0: Sin = inside_left(S,val); Ein = inside_left(E,val); break;
            case 1: Sin = inside_right(S,val); Ein = inside_right(E,val); break;
            case 2: Sin = inside_bottom(S,val); Ein = inside_bottom(E,val); break;
            default: Sin = inside_top(S,val); Ein = inside_top(E,val); break;
        }
        if(Sin && Ein){
            out.push_back(E);
        } else if(Sin && !Ein){
            // output intersection
            if(edge==0 || edge==1) out.push_back(intersect_vertical(S,E,val));
            else out.push_back(intersect_horizontal(S,E,val));
        } else if(!Sin && Ein){
            // output intersection then E
            if(edge==0 || edge==1) out.push_back(intersect_vertical(S,E,val));
            else out.push_back(intersect_horizontal(S,E,val));
            out.push_back(E);
        } // else both outside -> nothing
    }
    return out;
}

int main(){
    vector<P> poly = {{1,1},{4,1},{4,4},{1,4}}; // sample polygon
    double xmin=2, xmax=3, ymin=2, ymax=3;
    vector<P> res = poly;
    res = clip_edge(res,0,xmin);
    res = clip_edge(res,1,xmax);
    res = clip_edge(res,2,ymin);
    res = clip_edge(res,3,ymax);
    cout.setf(std::ios::fixed); cout<<setprecision(6);
    cout<<"Clipped polygon vertices (in order):\n";
    for(auto &p:res) cout<<p.first<<" "<<p.second<<"\n";
    return 0;
}

Sample program output (exact): Clipped polygon vertices (in order): 3.000000 3.000000 2.000000 3.000000 2.000000 2.000000 3.000000 2.000000

(The vertex order may differ by rotation but represents the same polygon.)

Common mistakes

  • Losing vertex order (mixing S and E) — preserve input ordering to keep polygon consistent.
  • Assuming Sutherland–Hodgeman works for non-convex clipping regions — it may not.
  • Rounding/truncation errors: use doubles and be consistent with epsilon tests for on-edge points.

For your exam

Types of questions you will see:

  • Definitions: define polygon clipping, inside test, convex clipping region, parametric line.
  • Short notes: describe algorithm steps, complexity, and limitations.
  • Derivations: derive intersection parameter t for vertical/horizontal edges and for general two-line intersection.
  • Numericals: clip a small polygon step-by-step against a rectangle and provide final vertices (show calculations for intersection t values).
  • Programs / pseudo-code: give full Sutherland–Hodgeman pseudo-code or C/C++ function.
  • Diagrams: draw polygon and clip rectangle, show a few sample edges illustrating the 4 cases and label intersection point.

What full-marks answers include:

  • Correct definition and statement that the clip region must be convex.
  • Exact step-by-step algorithm (the 4-cases rule) and explanation why sequential clipping gives intersection of half-spaces.
  • Correct intersection formulas and handling of edge cases (parallel/colinear).
  • For numericals: show calculations of t clearly, intermediate polygon after each clip edge, and final vertex list in order.

Quick check

  1. What are the four cases used when processing an input edge S->E?
  2. For a segment (1,1)->(4,1) clipped by vertical line x=2, what is the intersection point?
  3. Why must the clipping region be convex for Sutherland–Hodgeman to work correctly?

Answers: 1) S in/E in -> output E; S in/E out -> output I; S out/E in -> output I and E; S out/E out -> output nothing. 2) t=(2-1)/(4-1)=1/3 -> intersection (2,1). 3) Because algorithm clips by intersecting half-spaces sequentially; only intersections of convex half-spaces form the convex clipping region — non-convex regions require more complex handling.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?