Overview
Sutherland-Hodgman processes polygon vertices edge by edge, emitting new vertices where polygon edges cross clip boundaries.
CoreSource checked
Sutherland-Hodgman Polygon Clipping
Clips a polygon against each boundary of a convex clipping region.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Geometry
- Difficulty
- Intermediate
- Family
- Polygon Clipping
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
half-plane testedge intersectionpolygon clippingconvex boundary
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n * m)
Average
O(n * m)
Worst
O(n * m)
Space
O(n + m)
When to Use
- Use when a polygon must be clipped to a convex viewport or convex region.
- Use when viewport clipping is a central requirement.
When Not to Use
- Avoid when the clipping region is concave and requires a more general polygon clipping method.
- Avoid when floating-point precision or degenerate geometry cannot be handled robustly.
What It Does
- Processes clip edges one at a time
- Keeps vertices inside the boundary
- Adds intersection points where edges cross
Use Cases
- Viewport clipping
- 2D graphics
- Convex polygon operations
Inputs
- Subject polygon
- Convex clip polygon
Outputs
- Clipped polygon
Key Formulas (1)
Line interpolation
p = p1 + t · (p2 − p1)
p = p1 + t * (p2 - p1)Computes the boundary crossing point along a polygon edge.
Pseudocode
- 1.Start with the subject polygon vertices
- 2.For each clip boundary, walk every polygon edge
- 3.Emit inside end vertices
- 4.Emit intersection points when an edge crosses the boundary
- 5.Use the emitted polygon for the next boundary
Canonical Example
- Input
- square clipped by left boundary x >= 0
- Output
- polygon with outside-left vertices removed
- Explanation
- Crossing edges contribute new boundary intersection points.
Implementation Notes
- Handle edges that lie exactly on the clip boundary deliberately.
- Use robust predicates or tolerances when near-degenerate inputs are expected.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Inside tests must use a consistent winding direction for clip edges.
- Collinear, overlapping, and duplicate points need explicit tie-breaking rules.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasShow a polygon being clipped one boundary at a time until only the inside portion remains.
Step 1 of 5: Start with the subject polygon vertices
geometry-diagramNotes
The standard algorithm assumes a convex clipping polygon.
Sources (1)
What each reference supports for this entry.
Sutherland and Hodgman 1974
PaperOriginal polygon clipping paper for clipping ordered vertex sequences against convex regions.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pagePolygon clipping computes intersections between polygon edges and clip boundaries.
Alternative toWeiler-Atherton Polygon Clipping
Both clip polygons against boundaries with different support for complex cases.
Related Algorithms
Tags
GeometryPolygon ClippingPolygonsComputational Geometry