Project 2: The Sutherland-Hodgman Polygon Clipper

Build a polygon clipper that trims any polygon to a convex window.

Project Overview

Attribute Value
Difficulty Level 2: Intermediate
Time Estimate Weekend
Main Language C++
Alternative Languages C, Rust, Python
Knowledge Area Polygon clipping and inside/outside tests
Tools SVG viewer or plotting tool
Main Book “Computational Geometry: Algorithms and Applications” by de Berg et al.

What you’ll build: A tool that takes a polygon and a clipping window and returns the clipped polygon.

Why it teaches computational geometry: Clipping forces you to reason about edges, intersections, and consistent polygon winding.

Core challenges you’ll face:

  • Handling edge cases where vertices lie on the clip boundary
  • Computing line segment intersections robustly
  • Preserving polygon winding and ordering

Real World Outcome

You will be able to input a polygon and output a new polygon confined to a convex clipping region. The output will be valid, ordered, and suitable for rendering.

Example Output:

$ ./clipper --input subject.svg --clip window.svg --output clipped.svg
Input vertices: 12
Output vertices: 9
Wrote clipped polygon to clipped.svg

Verification steps:

  • Visualize input and output overlays
  • Confirm clipped polygon lies entirely inside the window

The Core Question You’re Answering

“How do I keep only the part of a shape that lies inside a region?”

Clipping is a foundational operation used in rendering, CAD, and GIS.

Concepts You Must Understand First

Stop and research these before coding:

  1. Half-plane tests
    • How do you decide if a point is inside a directed edge?
    • Book Reference: “Computational Geometry: Algorithms and Applications” Ch. 2
  2. Line segment intersection
    • How do you compute intersection points safely?
    • Book Reference: “Geometric Tools for Computer Graphics” by Schneider & Eberly, Ch. 9
  3. Polygon winding
    • Why does vertex order matter for inside/outside tests?
    • Book Reference: “Computational Geometry: Algorithms and Applications” Ch. 1

Questions to Guide Your Design

  1. Boundary cases
    • What happens when a vertex lies exactly on the clip edge?
    • How will you avoid duplicate points?
  2. Representation
    • Will you store polygons as ordered lists of vertices?
    • How will you handle convex vs concave input?

Thinking Exercise

Manual Clip

Clip a square with vertices (0,0), (2,0), (2,2), (0,2) against the half-plane x <= 1.5.

Questions while working:

  • Which vertices remain unchanged?
  • Where are the intersection points?

The Interview Questions They’ll Ask

Prepare to answer these:

  1. “How does Sutherland-Hodgman clipping work?”
  2. “Why does clipping require consistent winding?”
  3. “How do you handle points on the boundary?”
  4. “What happens with concave polygons?”
  5. “How do you validate a polygon output?”

Hints in Layers

Hint 1: Starting Point Clip against one edge at a time.

Hint 2: Next Level For each edge, consider transitions: inside-inside, inside-outside, outside-inside, outside-outside.

Hint 3: Technical Details Compute intersection points only when an edge crosses the boundary.

Hint 4: Tools/Debugging Visualize step-by-step clipping to catch ordering mistakes.

Books That Will Help

Topic Book Chapter
Polygon clipping “Computational Geometry: Algorithms and Applications” by de Berg et al. Ch. 2
Line intersections “Geometric Tools for Computer Graphics” by Schneider & Eberly Ch. 9
Winding order “Computational Geometry: Algorithms and Applications” by de Berg et al. Ch. 1

Implementation Hints

  • Keep each clipping edge operation separate for clarity.
  • Avoid adding duplicate points on boundaries.
  • Verify output polygon orientation matches input.

Learning Milestones

  1. First milestone: You can clip a convex polygon against a rectangle.
  2. Second milestone: You can handle boundary and edge cases.
  3. Final milestone: You can explain why clipping preserves winding.