Algorithmus von Sutherland-Hodgman

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Der Algorithmus von Sutherland-Hodgman ist ein nach Ivan Sutherland und Gary W. Hodgman benannter Algorithmus der Computergrafik zum Clipping von Polygonen.

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.

Alle Clipping-Schritte eines Polygons 'W' von einem 5-seitigen Polygon

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

[Bearbeiten | Quelltext bearbeiten]

Clipping eines Polygons bzgl. eines beliebigen konvexen Polygons. Beschreibung des Polygons durch seine Ecken und Kanten von nach bzw. von nach . Nun wird in Teilschritten die Liste der Ecken durchlaufen und eine Liste mit Polygonecken ausgegeben. Beim Übergang sind vier Fälle möglich.

  • und liegen im Fenster, so wird übernommen
  • liegt außerhalb und innerhalb, so wird der Schnittpunkt mit der Fensterkante und übernommen
  • liegt innerhalb und außerhalb, dann wird ebenso der Schnittpunkt mit der Fensterkante übernommen
  • sollten und außerhalb liegen, dann wird entweder kein neuer Punkt übernommen, oder die beiden Schnittpunkte mit den Fensterkanten werden übernommen, falls die Gerade von nach durch das Clippingfenster verläuft.