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:
- S inside, E inside -> output E.
- S inside, E outside -> output intersection point I of SE with clip edge.
- S outside, E inside -> output intersection point I, then output E.
- 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
- What are the four cases used when processing an input edge S->E?
- For a segment (1,1)->(4,1) clipped by vertical line x=2, what is the intersection point?
- 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?