How to Learn Sutherland–Hodgman Polygon Clipping: Half-Planes, Edge Cases, Intersections and Convex Windows

Wait, What?

You can clip an entire polygon by repeatedly asking one four-case question about each edge: did it start inside, end inside, or cross the boundary?

The Sutherland–Hodgman polygon-clipping algorithm is a classic example of turning geometry into a clean streaming procedure. A subject polygon is clipped against one boundary of a convex clipping window at a time. The output vertices from one stage become the input vertices for the next.

For a beginner, the algorithm is a lesson in inside/outside classification. For a professional, it becomes a lesson in orientation predicates, intersection arithmetic, degeneracies, output cleanup, coordinate robustness and choosing the right clipping algorithm for the geometry actually required.

Quick Answer

Learn Sutherland–Hodgman through polygon/window meaning → convex half-planes → inside predicate → four transition cases → segment-boundary intersection → repeated clipping stages → winding/orientation → numerical robustness → degenerate outputs → 3D generalization → comparison with general polygon Boolean algorithms. Do not start by copying code. First make the four transition cases inevitable.

1. Start With the Geometry Job

Suppose a polygon extends beyond a visible window. We want only the part that lies inside that window. If the clipping window is convex, every boundary edge defines a half-plane: one side is inside, the other side is outside.

Clipping against the whole convex window can therefore be decomposed into clipping against one half-plane after another.

This decomposition is the algorithm’s first big idea. A difficult two-dimensional shape operation becomes a sequence of simpler one-boundary operations.

2. Convexity Is What Makes the Repeated Half-Plane View Clean

A convex polygon is exactly the intersection of the half-planes defined by its oriented edges. If a point survives every boundary test, it lies inside the clipping polygon.

That is why the clip window is naturally convex in the standard Sutherland–Hodgman formulation. General polygon Boolean operations involving concave clip regions, holes, multiple contours or self-intersections require more capable representations and algorithms.

3. Define “Inside” With an Orientation Predicate

Take an oriented clip edge from A to B and a test point P. In 2D, the signed cross product

cross(B - A, P - A)

tells which side of the directed edge P lies on. If clip vertices are consistently counter-clockwise, one sign convention can mean inside; if they are clockwise, the sign reverses.

This is why winding order is not cosmetic. An inside test that assumes counter-clockwise boundaries will reject the correct region if the clip polygon is supplied clockwise.

4. The Four Cases Are the Algorithm

Walk around the current subject polygon one segment at a time. Let S be the previous vertex and E the current endpoint. Relative to one clip boundary, there are only four possibilities:

1. inside → inside: output E;
2. inside → outside: output the intersection only;
3. outside → inside: output the intersection, then E;
4. outside → outside: output nothing.

Every correct implementation is a precise encoding of these four transitions.

5. Why These Four Cases Are Correct

If a segment stays inside, its endpoint belongs to the clipped boundary. If it leaves the visible half-plane, only the segment up to the crossing survives, so the intersection is emitted. If it enters, the visible portion begins at the intersection and continues to E. If it stays outside, no part contributes.

The algorithm therefore reconstructs the boundary of the polygon after clipping against one half-plane.

6. One Boundary at a Time

A simple high-level form is:

output = subject_polygon

for each clip edge A -> B:
    input = output
    output = empty list

    S = last vertex of input
    for each vertex E in input:
        classify S and E against A -> B
        emit E and/or intersection using the four cases
        S = E

return output

The crucial pattern is that each stage consumes a vertex list and produces a new one. That makes the procedure easy to trace and test.

7. Trace a Triangle Against a Rectangle

Draw a triangle that crosses the left and top edges of a rectangular window. First clip against the left boundary. Record every S→E transition and the emitted vertices. Take that new polygon and clip it against the right boundary, then bottom, then top.

Do not jump directly to the final answer. The educational value is in seeing that intermediate polygons can gain vertices where intersections are created and lose vertices that lie outside.

8. Segment–Line Intersection Must Match the Boundary Model

When S→E crosses a clip boundary A→B, compute the intersection of the two supporting lines, then use the point that lies on the subject segment.

A vector form can be derived from:

S + t(E - S) = A + u(B - A)

Solving for t gives the point along the subject segment. In exact mathematics this is straightforward. In floating-point arithmetic, nearly parallel lines and large coordinate magnitudes require care.

9. Boundary Points Need a Deliberate Convention

What happens when the cross product is exactly zero? The point lies on the clipping line. Most clipping systems treat boundary points as inside, but the choice should be explicit.

With floating-point values, “exactly zero” is fragile. A small tolerance may help, but a single global epsilon can also create inconsistent topology at very different coordinate scales. Robust geometry requires more thought than adding 1e-9 everywhere.

10. Winding and Sign Errors Produce Perfectly Wrong Results

If the clip polygon orientation is reversed but the inside predicate is not, the algorithm may keep the exterior instead of the interior. Professional implementations therefore either:

• require a documented winding order;
• detect orientation and adapt the predicate;
• normalize the polygon before clipping.

Test both clockwise and counter-clockwise input explicitly.

11. Empty Polygons Should Stop Early

After clipping against one boundary, the output list may become empty. Once that happens, no later half-plane can restore geometry. Return immediately.

This is a small optimization, but also a useful correctness observation: intersection is monotone. Every clipping stage can only remove points, never reintroduce regions already discarded.

12. Degenerate Output Needs Cleanup Policy

Clipping can produce:

• duplicate consecutive vertices;
• zero-length edges;
• collinear runs;
• a line segment instead of an area polygon;
• a single point;
• an empty result.

Whether these are valid outputs depends on the downstream system. A rendering pipeline, GIS Boolean operation and collision system may need different cleanup rules. Do not silently delete collinear vertices unless the consumer permits it.

13. Concave Subjects and Multiple Components Need Care

The original Sutherland–Hodgman family was designed to clip reentrant polygons against convex boundaries, but practical software must be clear about its output representation. Intersections involving concave shapes can create geometrically awkward results, and a single flat vertex list may not be enough for all Boolean outcomes involving multiple contours or holes.

If the real job is arbitrary polygon intersection, union, difference, holes or self-intersections, use a general polygon-clipping library or algorithm whose data model explicitly represents those cases.

14. The Original Idea Extends Beyond 2D

Sutherland and Hodgman’s 1974 paper describes a family of reentrant clipping algorithms, including clipping polygons against irregular convex plane-faced volumes in three dimensions. The same conceptual pattern survives: classify against one boundary plane at a time and pass the surviving polygon onward.

That connection makes this more than a historical 2D graphics trick. It teaches a reusable geometric principle: represent a convex region as an intersection of half-spaces.

15. Graphics Pipelines Generalize the Same Half-Space Thinking

Modern rendering pipelines clip primitives against a view volume before rasterization. Production GPU pipelines use homogeneous coordinates and implementation-specific stages rather than a classroom Sutherland–Hodgman loop, but the conceptual connection is strong: primitives are constrained by a collection of clipping planes.

This is a useful learning bridge from 2D computational geometry to the 3D graphics pipeline.

16. Robust Production Libraries Often Use Different Algorithms

Current general-purpose polygon-clipping libraries solve a wider problem than Sutherland–Hodgman. Clipper2, for example, supports polygon Boolean operations and performs clipping internally with integer coordinates to improve numerical robustness, even when its public API accepts floating-point paths through scaling.

That does not make Sutherland–Hodgman obsolete. It defines its ownership boundary: simple convex-window clipping is elegant and teachable; arbitrary topology and robust industrial Boolean geometry require a broader tool.

17. Compare the Right Algorithms

• Cohen–Sutherland / Liang–Barsky: primarily line-segment clipping jobs.
• Sutherland–Hodgman: polygon clipped successively by convex half-planes.
• Weiler–Atherton: supports broader polygon clipping cases and contour traversal.
• Vatti-style/general Boolean clippers: target arbitrary polygon Boolean operations.

Algorithm choice begins with the geometry contract, not the most famous name.

18. Complexity Is Usually Easy to Understand but Output Size Can Grow

For each clip boundary, the algorithm walks the current polygon once. If the clip polygon has m edges and the current subject has n vertices, the basic classroom intuition is roughly O(mn), though the number of intermediate vertices can change as clipping creates intersections.

For a rectangle, m is only four, so the procedure is particularly simple and efficient.

19. Verification Should Be Geometric, Not Visual Only

A plotted result can look correct while hiding orientation or tolerance failures. Test invariants:

• every output point is inside or on every clip half-plane;
• every emitted intersection lies on the relevant subject segment and clip boundary within the chosen numeric model;
• clipping an already-inside polygon leaves it equivalent;
• clipping a fully outside polygon returns empty;
• reversing the subject winding preserves geometry;
• reversing the clip winding is either handled or rejected according to contract.

For randomized small tests, compare area and geometry against a trusted robust clipping library.

20. A Better Way to Learn It

This algorithm is ideal for worked examples and code tracing. PRIMM recommends predicting and investigating running code before learners create their own version. Subgoal-labelled worked examples encourage naming the procedural steps, while Parsons problems reduce syntax load so the learner can focus on ordering.

For Sutherland–Hodgman, the subgoals are unusually visible: classify S, classify E, choose one of four transitions, compute an intersection if needed, emit vertices, then repeat for the next clip edge. Put those four cases on cards and ask learners to reconstruct the loop before writing code.

Common Failure States

• Using an inside test with the wrong clip-polygon winding.
• Forgetting the closing segment from the last polygon vertex back to the first.
• Emitting E during inside→outside instead of only the intersection.
• Emitting only E during outside→inside and losing the entry intersection.
• Computing line intersections without handling parallel or nearly parallel cases.
• Using a fixed epsilon without considering coordinate scale.
• Assuming one vertex list represents every possible arbitrary polygon Boolean result.
• Deleting duplicate or collinear vertices without knowing downstream requirements.

Practice Ladder

• Beginner: classify points against one directed line using a cross product.
• Foundation: clip a polyline segment stream against one half-plane using the four cases.
• Intermediate: implement polygon clipping against an axis-aligned rectangle and verify all four transitions.
• Advanced: support an arbitrary convex clip polygon with automatic winding detection and robust boundary handling.
• Professional: compare the result against a robust polygon Boolean library across random, degenerate and large-coordinate tests; document precisely which polygon classes your implementation supports.
• Explanation test: derive the four transition outputs without looking at code.

Learning Hall Boundary

This article owns the Sutherland–Hodgman specialist job: convex-window polygon clipping through half-plane classification and boundary intersections. It does not replace eduKateSengkang’s existing computational-geometry overview, convex-hull, sweep-line, robust-predicate, rasterization, MindOS, Bolt or Student/Studying Interface canonical jobs.

Evidence Boundary

The foundational reference is Ivan E. Sutherland and Gary W. Hodgman, Reentrant Polygon Clipping, Communications of the ACM, 1974, DOI 10.1145/360767.360802. The paper describes clipping reentrant polygons against convex windows and plane-faced volumes. Modern production contrast comes from current Clipper2 documentation, which emphasizes integer-coordinate internal clipping for numerical robustness and supports a much broader polygon-Boolean job. The learning progression is informed by PRIMM, subgoal-labelled worked examples, algorithm-visualisation research and recent Parsons-problem scaffolding in computing education.

Professional rule: you understand Sutherland–Hodgman when you can derive every emitted vertex from the four inside/outside transitions, state the orientation convention behind the half-plane test, and know when the geometry contract has grown beyond what this algorithm should own.