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 P _{i+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 P _{i}
was already inserted in the step before). |
The current
point is outside the clipping region but the next one lies inside |
||

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

for each clipping
edge do |

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