Der Line-Clipping Algorithmus von Liang und Barsky

Applet 1. Experimentieren mit dem Liang/Barsky Algorithmus. Sie können die beiden schwarzen mit start und end bezeichneten Punkte verschieben. Der im Innern des Fensters liegende Streckenabschnitt wird fett dargestellt.


Theorie

Um geometrische Objekte wie Punkte und Linien auf einem Ausgabegerät ausgeben zu können, müssen in der Regel Daten über die Abmessungen des Ausgabegerätes bekannt sein. Das auszugebende Objekt wird dann in das Koordinatensystem des Ausgabegerätes transformiert und dort ausgegeben. Unter Umständen müssen überhängende Teile des Objektes abgeschnitten (geclipped) werden.

Ein Standardproblem in diesem Zusammenhang, welches etwa beim Zeichnen von Linien in ein Bildschirmfenster auftritt, ist das Lineclipping an einem rechteckigen Viewport. Gegeben ist eine Strecke zwischen zwei Punkten p1=(p1,x,p1,y) und p2=(p2,x,p2,y) sowie ein rechteckiges Ausgabefenster durch eine linke untere Ecke (xmin,ymin) und eine rechte obere Ecke (xmax,ymax).

Der Algorithmus von Liang und Barsky stellt die Gerade durch p1 und p2 in Parameterform als Funktion eines skalaren Parameters t dar:

(x,y) = (p1,x,p1,y) + (dx,dy) · t
wobei
dx= p2,x - p1,x,
dy= p2,y - p1,y.
Der Parameterbereich [0,1] ergibt das Geradenstück zwischen den beiden Punkten p1 und p2. Das Geradenstück innerhalb der Fenstergrenzen (xmin,ymin), (xmax,ymax) ist durch folgende Ungleichungen charakterisiert:
-dx · t <= p1,x - xmin,
dx · t <= xmax - p1,x,
-dy · t <= p1,y - ymin,
dy · t <= ymax - p1,y.
Diese vier Ungleichungen lassen sich in eine einheitliche Form bringen:
p1 := -dx, q1 := p1,x - xmin ,
p2 := dx , q2 := xmax - p1,x,
p3 := -dy, q3 := p1,y - ymin,
p4 := dy , q4 := ymax - p1,y.
und wir erhalten die folgenden vier Ungleichungen:
pi · t <= qi, i=1,...,4.

Jede der obigen vier Ungleichungen gibt für eine der vier verlängerten Begrenzungskanten des Fensters den Parameterbereich an, der auf der sichtbaren Seite der Begrenzungskante liegt. Für pi=0 verläuft die Gerade parallel zur jeweiligen Begrenzungskante. Ansonsten gibt t=qi/pi den Schnittpunkt von Gerade und verlängerter Begrenzungskante an.

Der Algorithmus von Liang und Barsky berechnet das gesuchte Geradenstück, welches innerhalb des Fensters liegt, durch zwei Parameter t1 und t2:

t1 = max ( {qi / pi : pi<0, i=1,...,4} u {0} ),
t2 = min ( {qi / pi : pi>0, i=1,...,4} u {1} )
Die Einbeziehung der Parameter 0 und 1 in diesen Formeln stellt sicher, daß nur der Streckenteil zwischen p1 und p2 berücksichtigt wird. Ist pi<0, so kommt die gerichtete Gerade durch p1 und p2 vom unsichtbaren Bereich einer Begrenzungskante in den sichtbaren Bereich hinein. Der größte der zugehörigen Schnittpunkt-Parameter bezeichnet den Eintrittspunkt in das Fenster. Ist pi>0, so geht die gerichtete Gerade durch p1 und p2 vom sichtbaren Bereich einer Begrenzungskante hinaus in den unsichtbaren Bereich. Der kleinste der zugehörigen Schnittpunkt-Parameter bezeichnet den Austrittspunkt aus dem Fenster.

Ist nun t1>t2, so liegt die Linie außerhalb des Fensters. Sonst bezeichnet der Parameterbereich zwischen t1 und t2 den gesuchten Streckenabschnitt innerhalb des Fensters.

Das obige Applet veranschaulicht den Liang/Barsky Algorithmus. Sie können interaktiv entweder den Startpunkt p1 (im Applet bezeichnet mit start) oder den Endpunkt p2 (im Applet bezeichnet mit end) verschieben. Es werden jeweils die Schnittpunkte der Gerade mit den vier verlängerten Begrenzungskanten bei den Parameterpositionen qi/pi sowie die Punkte an den Parametern t1 und t2 angezeigt. Der im Innern des Fensters liegende Streckenbereich wird fett gezeichnet. Die Farbe der Parameter qi/pi richtet sich nach dem Vorzeichen von pi. Für die roten Parameter qi/pi gilt pi<0, d. h. sie definieren den (ebenfalls rot dargestellten) Parameter t1. Für die blauen Parameter qi/pi gilt pi>0, d. h. sie definieren den (ebenfalls blau dargestellten) Parameter t2. Wenn sich die Steigung der Gerade ändert, so kann man beobachten, daß sich auch die Zuordnung der Parameter qi/pi zu den Parametern t1 und t2 ändert.