Sutherland-Hodgman's algorithm

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

Basic version

With the Sutherland-Hodgman algorithm you can clip any other polygon (convex or concave) with any convex polygon. For each window edge, the boundary line is extended to a straight line on which all (relevant) polygon edges are shortened.

All steps of clipping a polygon 'W' from a 5-sided polygon

Pseudo code

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

  List outputList = subjectPolygon;
  for (Edge clipEdge in clipPolygon) do
     List inputList = outputList;
     outputList.clear();
     Point S = inputList.last;
     for (Point E in inputList) do
        if (E inside clipEdge) then
           if (S not inside clipEdge) then
              outputList.add(ComputeIntersection(S,E,clipEdge));
           end if
           outputList.add(E);
        else if (S inside clipEdge) then
           outputList.add(ComputeIntersection(S,E,clipEdge));
        end if
        S = E;
     done
  done

Extended version

Clipping of a polygon with respect to any convex polygon. Description of the polygon by its corners and edges from to and from to . Now the list of corners is run through in partial steps and a list of polygon corners is output. There are four possible cases of transition . ${\displaystyle v_{1},\ldots ,v_{n}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i+1},(i=1,\ldots ,n-1)}$ ${\displaystyle v_{n}}$ ${\displaystyle v_{1}}$ ${\displaystyle n}$ ${\displaystyle (v_{1}\rightarrow v_{2}\rightarrow \ldots \rightarrow v_{n}\rightarrow v_{1})}$ ${\displaystyle n'}$ ${\displaystyle v'_{1},\ldots ,v'_{n'}}$ ${\displaystyle v_{i}\rightarrow v_{i+1}}$

• ${\displaystyle v_{i}}$and are in the window, it is accepted ${\displaystyle v_{i+1}}$ ${\displaystyle v_{i+1}}$
• lies outside and inside, the point of intersection with the window edge and is adopted ${\displaystyle v_{i}}$ ${\displaystyle v_{i+1}}$ ${\displaystyle v_{i+1}}$
• lies inside and outside, then the point of intersection with the window edge is also adopted ${\displaystyle v_{i}}$ ${\displaystyle v_{i+1}}$
• and should lie outside, then either no new point is adopted, or the two intersection points with the window edges are adopted if the straight line runs from to through the clipping window . ${\displaystyle v_{i}}$ ${\displaystyle v_{i+1}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i+1}}$

literature

• Mel Slater, Anthony Steed, Yiorgos Chrysanthou: Computer Graphics and Virtual Environments: From Realism to Real-Time. Addison-Wesley, ISBN 0-201-62420-6
• Ivan Sutherland , Gary W. Hodgman: Reentrant Polygon Clipping. In: Communications of the ACM , vol. 17, 1974, pp. 32-42

Web links

• Sutherland-Hodgman polygon clipping
• Cohen-Sutherland Algorithm for line clipping