Liang-Barsky's Line Clipping Algorithm
Liang-Barsky's Line Clipping Algorithm solution
Applet displays result of Liang-Barsky's Line Clipping Algorithm solution. There is initial line and clipping rectangle projected. The clipped part of initial line is highlighted by bolder and more contrast color.
Interactivity affords to change parameters (positions of outer points and cornes) of initial line and clipping rectangle comfortably using mouse functionality:
- finding and marking closest flexible point
- drag & drop idea of relocation outer points of initial line and clipping rectangle corners
Applet Drawing point, in corner right bottom are co-ordinates current
point. Author: Branislav Malinovsky
Specificaton of algorithm
In fact, line clipping means finding two outer points of intersection between rectangle(clipping) and line(clipped). Line segment acquired by junction of these two points is then called clipped line.
Liang-Barsky's Line Clipping Algorithm uses the parametric equations for a line and solves four inequalities to find the range of the parameter for which the line is in the intersection with rectangle.
1. Let P(x1,y1) and Q(x2,y2) be the outer points of initial line
- 2. Set Tmin = 0 and Tmax = 1 (Tmin represents the starting position and Tmax represents ending position of actual phase of clipping the line relatively to initial line; at beginning positions of initial line)
- 3. Use coordinates of clipping edges to find values of individual inequalities (generally t or individualy tL,tR,tT,tB)
From parametric equation x = x1 + (x2-x1)*t, y = y1 + (y2-y1)*t (0<=t<=1):
- let R (R = x1 + t*(x2 - x1)) is x coordinate of right edge - tL = (L-x1)/(x2-x1)
- let L (L = x1 + t*(x2 - x1))is x coordinate of left edge - tR = (R-x1)/(x2-x1)
- let T is y coordinate of top edge - tT = (T-y1)/(y2-y1)
- let B is y coordinate of bottom edge - tB = (B-y1)/(y2-y1)
If ttmax ignore it and go to the next edge otherwise classify the value of t as entering or exiting value (using inner product to classify). If t is entering value set tmin = t. If t is exiting value set tmax =t.
4. If tmin < tmax then draw a line from (x1 + dx*tmin, y1 + dy*tmin) to (x1 + dx*tmax, y1 + dy*tmax).
- 5. If the line crosses over the rectangle, you will see
(x1 + dx*tmin, y1 + dy*tmin) and (x1 + dx*tmax, y1 + dy*tmax)
are intersection between line and edge.