Sutherland–Hodgman algorithm

The algorithm of Sutherland - Hodgman is a named after Ivan Sutherland and Gary W. Hodgman algorithm in computer graphics for clipping of polygons.

Basic version

With the Sutherland - Hodgman algorithm can be clipped with each polygon convex polygon each other ( convex or concave). For each edge of the window, the limiting distance is extended to a straight line be cut at all (relevant) polygon edges.

Pseudo-code

The following pseudo - code is clipping a polygon according to the Sutherland - Hodgman algorithm:

List output-list = subject polygon;    for ( Edge edge clip in clip polygon ) do       List list = input output-list;       outputList.clear ();       Point S = inputList.last;       for ( Point E in input list) do          if ( E inside clip edge ) then             if ( S not inside clip edge ) then                outputList.add ( Compute Intersection ( S, E, clip edge) );             end if             outputList.add (E);          else if ( S inside clip edge ) then             outputList.add ( Compute Intersection ( S, E, clip edge) );          end if          S = E;       done    done Extended version

Clipping a polygon with respect to an arbitrary convex polygon. Description of the polygon according to its corners and edges from to or from. Now, in steps the list of corners is run and output a list of polygon vertices. During the transition, four cases are possible.

• And are in the window, so is taken
• Outside and inside, so the intersection is taken over by the window edge and
• Lies within and outside, the intersection is taken as the window edge
• And should be outside, then either there is no new point is taken, or the two intersections with the window edges are taken, if the straight line extends from to by the clipping window.