2D Clipping with the Sutherland-Hodgman-Algorithm
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:
points are inside the clipping region
=> add the second one to the result polygon, here it's Pi+1.
points are outside the clipping region
=> insert none of them to the result polygon.
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).
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
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