2D Clipping with the Sutherland-Hodgman-Algorithm

Download Applet with Source (23kb)

View Applet online

The Sutherland-Hodgman-Algorithm is a well-known algorithm for clipping a polygon against a rectangle.
To accomplish this task, it is not enough to clip the lines one by one with e.g the Cohen-Sutherland-Algorithm. Consider the concave polygon in the picture below - by just clipping the lines it is divided in several separate polygons.

Ok so it's clear that at least the intersection points of the polygon with the clipping rectangle must be connected. But there are also some special cases which needs extra observation, for example clipping 'around' an edge of the clipping rectangle. Look at the next picture - just clipping the lines results in a wrong polygon!

The Sutherland-Hodgman-Algorithm handles these cases without problems and has linear time complexity. It clips the polygon against the four clipping edges one after another. For each clipping edge it travels all edges of the polygon and creates the clipped polygon after the four following rules:

 Both points are inside the clipping region
=> add the second one to the result polygon, here it's Pi+1.		 Both points are outside the clipping region
=> insert none of them to the result polygon.
     
The current point is inside the clipping region but the next one lies outside
=> we add the intersection point I to the result polygon (note that Pi was already inserted in the step before).

The current point is outside the clipping region but the next one lies inside
=> we add the intersection point I and the next point Pi+1 to the result polygon.
     

Ok, in fact that's all - nice and easy isn't it. So here some pseudocode of the algorithm:

for each clipping edge do
     for (i = 0; i < Polygon.length -1; i++)
          Pi = Polygon.vertex[i];
          Pi+1 = Polygon.vertex[i+1];
          if (Pi is inside clipping region)
               if (Pi+1 is inside clipping region)
                    clippedPolygon.add(Pi+1)
               else
                    clippedPolygon.add(intersectionPoint(Pi, Pi+1, currentEdge)
          else
               if (Pi+1 is inside clipping region)
                    clippedPolygon.add(intersectionPoint(Pi, Pi+1, currentEdge)
                    clippedPolygon.add(Pi+1)
     end for
     Polygon = clippedPolygon     // keep on working with the new polygon
end for

Ok and here a screenshot of my applet: left is the original polygon, right the clipped one:

Ok that's all. Hope you enjoyed this little article and the applet and found the source useful!

Sunshine, December 2007

This site is part of Sunshine's Homepage