Algorithmus von Cohen-Sutherland
# Algorithmus von Cohen-Sutherland

Der Algorithmus von Cohen-Sutherland ist ein Algorithmus zum Abschneiden (Clipping) von Linien an einem Rechteck. Er ist nach seinen Erfindern Danny Cohen und Ivan Sutherland benannt. Der Algorithmus gilt als populärster, wenn auch nicht effizientester für seine Zwecke. Er eignet sich besonders für Fälle, in denen ein hoher Anteil der zu clippenden Linien inner- oder außerhalb des Rechtecks liegt.

## Schritte

Zuerst werden jeweils für die beiden Endpunkte der zu zeichnenden Linie vier Flags ermittelt, die gesetzt werden, wenn sich der Endpunkt links des Rechtecks, rechts davon, darunter oder darüber befindet. Ist keines der Flags gesetzt, dann liegen beide Endpunkte innerhalb des Rechtecks, es ist kein Clipping notwendig und die Linie kann einfach gezeichnet werden.
Wenn dieser triviale Fall nicht eintritt, werden im nächsten Schritt die einander entsprechenden Flags beider Endpunkte angesehen. Ist mindestens eines dieser Flags bei beiden Endpunkten gesetzt, so befindet sich die gesamte Linie außerhalb des Rechtecks und die Linie braucht nicht gezeichnet zu werden.
Wenn auch dieser einfache Fall nicht auftritt, wird der Schnittpunkt einer (beliebigen) Rechteck-Seite mit dem Liniensegment berechnet und der überlappende Teil erneut getestet (und eventuell gekürzt), bis schließlich beide Punkte innerhalb des Rechtecks liegen.

## Implementierung

Das folgende Programm gibt ein Beispiel einer Implementierung des Cohen-Sutherland-Algorithmus in C++, anhand dessen man die Funktionsweise gut nachvollziehen kann.