Quelltext der Seite Algorithmus von Sutherland-Hodgman

Der '''Algorithmus von Sutherland-Hodgman''' ist ein nach [[Ivan Sutherland]] und Gary W. Hodgman benannter [[Algorithmus]] der [[Computergrafik]] zum [[Clipping (Computergrafik)|Clipping]] von [[Polygon]]en.

== Grundversion ==
Mit dem Sutherland-Hodgman-Algorithmus kann man mit jedem konvexen Polygon jedes andere Polygon (konvex oder konkav) clippen. Für jede Fensterkante wird die Begrenzungsstrecke zu einer Gerade erweitert, an der sämtliche (relevanten) Polygonkanten gekürzt werden.

[[Datei:Sutherland-Hodgman clipping sample.svg|zentriert|gerahmt|Alle Clipping-Schritte eines Polygons 'W' von einem 5-seitigen Polygon]]

=== Pseudo-Code ===
Der folgende Pseudo-Code clippt ein Polygon nach dem Sutherland-Hodgman-Algorithmus:

   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

== Erweiterte Version ==
Clipping eines Polygons bzgl. eines beliebigen konvexen Polygons. Beschreibung des Polygons durch seine Ecken <math>v_1, \ldots, v_n</math> und Kanten von <math>v_i</math> nach <math>v_{i+1}, (i=1,\ldots,n-1)</math> bzw. von <math>v_n</math> nach <math>v_1</math>. Nun wird in <math>n</math> Teilschritten die Liste der Ecken durchlaufen <math> (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_n \rightarrow v_1) </math> und eine Liste mit <math>n'</math> Polygonecken <math>v'_1, \ldots, v'_{n'}</math> ausgegeben. Beim Übergang <math>v_i \rightarrow v_{i+1}</math> sind vier Fälle möglich.

* <math>v_i</math> und <math>v_{i+1}</math> liegen im Fenster, so wird <math>v_{i+1}</math> übernommen
* liegt <math>v_i</math> außerhalb und <math>v_{i+1}</math> innerhalb, so wird der Schnittpunkt mit der Fensterkante und <math>v_{i+1}</math> übernommen
* liegt <math>v_i</math> innerhalb und <math>v_{i+1}</math> außerhalb, dann wird ebenso der Schnittpunkt mit der Fensterkante übernommen
* sollten <math>v_i</math> und <math>v_{i+1}</math> außerhalb liegen, dann wird entweder kein neuer Punkt übernommen, oder die beiden Schnittpunkte mit den Fensterkanten werden übernommen, falls die Gerade von <math>v_i</math> nach <math>v_{i+1}</math> durch das Clippingfenster verläuft.

== Literatur ==
* 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, S. 32–42

== Weblinks ==
* [https://www.cs.helsinki.fi/group/goa/viewing/leikkaus/intro2.html Sutherland-Hodgman Polygon Clipping]
* [https://www.cc.gatech.edu/grads/h/Hao-wei.Hsieh/Haowei.Hsieh/code2.html Cohen-Sutherland Algorithm for line clipping]

[[Kategorie:Algorithmus (Computergrafik)]]