Wikipedia

Liang–Barsky algorithm: Difference between revisions

Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
Link suggestions feature: 2 links added.
 
(28 intermediate revisions by 21 users not shown)
Line 1:
{{Short description|Line-clipping algorithm}}
In [[computer graphics]], the '''Liang–Barsky algorithm''' (named after [[You-Dong Liang]] and [[Brian A. Barsky]]) is a [[line clipping]] algorithm. The Liang–Barsky algorithm uses the parametric equation of a line and inequalities describing the range of the clipping window to determine the intersections between the line and the [[clip window]]. With these intersections it knows which portion of the line should be drawn. This algorithm is significantly more efficient than [[Cohen–Sutherland]].The idea of the Liang-Barsky clipping algorithm is to do as much testing as possible before computing line intersections.
In [[computer graphics]], the '''Liang–Barsky algorithm''' (named after [[You-Dong Liang]] and [[Brian A. Barsky]]) is a [[line clipping]] algorithm. The Liang–Barsky algorithm uses the [[parametric equation]] of a line and inequalities describing the range of the clipping window to determine the intersections between the line and the [[clip window]]. With these intersections, it knows which portion of the line should be drawn. So this algorithm is significantly more efficient than [[Cohen–Sutherland]]. The idea of the Liang–Barsky clipping algorithm is to do as much testing as possible before computing line intersections.
 
The algorithm uses the parametric form of a straight line:
 
:<math>x = x_0 + t (x_1 - x_0) = x_0 + t \Delta x,</math>
Consider first the usual parametric form of a straight line:
:<math>y = y_0 + t (y_1 - y_0) = y_0 + t \Delta y.</math>
 
:<math>x = x_0 + u (x_1 - x_0) = x_0 + t \Delta x\,\!</math>
:<math>y = y_0 + u (y_1 - y_0) = y_0 + t \Delta y\,\!</math>
 
A point is in the clip window, if
:<math>x_{\text{min}} \le x_0 + t \Delta x \le x_{\text{max}}\,\!</math>
and
:<math>y_{\text{min}} \le y_0 + t \Delta y \le y_{\text{max}}\,\!</math>,
which can be expressed as the 4 inequalities
:<math>t p_i \le q_i, \quad i = 1, 2, 3, 4\,\!</math>,
where
 
:<math>
:<math>p_1 = -\Delta x , q_1 = x_0 - x_{\text{min}}\,\!</math> (left)
\begin{align}
:<math>p_2 = \Delta x , q_2 = x_{\text{max}} - x_0\,\!</math> (right)
:<math>p_3 p_1 &= -\Delta y x, & q_1 q_3 &= y_0x_0 - y_x_\text{min}\, & &\!</math> text{(bottomleft)} \\
:<math>p_4 p_2 &= \Delta y x, & q_2 q_4 &= y_x_\text{max} - y_0\x_0, & &\!</math> text{(topright)} \\
p_3 &= -\Delta y, & q_3 &= y_0 - y_\text{min}, & &\text{(bottom)} \\
p_4 &= \Delta y, & q_4 &= y_\text{max} - y_0. & &\text{(top)}
\end{align}
</math>
 
To compute the final [[line segment]]:
# A line parallel to a clipping window edge has <math>p_i = 0</math> for that boundary.
# If for that <math>i</math>, <math>q_i < 0</math>, then the line is completely outside and can be eliminated.
# When <math>p_i < 0</math>, the line proceeds outside to inside the clip window, and when <math>p_i > 0</math>, the line proceeds inside to outside.
# For nonzero <math>p_kp_i</math>, <math>u = \frac{q_i}{ / p_i}</math> gives <math>t</math> for the intersection point of the line and the window edge (possibly projected).
# ForThe eachtwo actual intersections of the line with the window edges, calculateif they exist, are described by <math>u_1</math> and <math>u_2</math>, calculated as follows. For <math>u_1</math>, look at boundaries for which <math>p_i < 0</math> (i.e. outside to inside). Take <math>u_1</math> to be the largest among <math>\left\{ 0,\frac{ q_i}{ / p_i} \right\}</math>. For <math>u_2</math>, look at boundaries for which <math>p_i > 0</math> (i.e. inside to outside). Take <math>u_2</math> to be the minimum of <math>\left\{ 1, \frac{q_i}{ / p_i} \right\}</math>.
# If <math>u_1 > u_2</math>, the line is entirely outside andthe thereforeclip window. If <math>u_1 < 0 < 1 < u_2</math> it is entirely inside rejectedit.
 
<syntaxhighlight lang="c++">
// Liang–Barsky line-clipping algorithm
#include<iostream>
#include<graphics.h>
#include<math.h>
 
using namespace std;
 
// this function gives the maximum
float maxi(float arr[], int n) {
float m = 0;
for (int i = 0; i < n; ++i)
if (m < arr[i])
m = arr[i];
return m;
}
 
// this function gives the minimum
float mini(float arr[], int n) {
float m = 1;
for (int i = 0; i < n; ++i)
if (m > arr[i])
m = arr[i];
return m;
}
 
void liang_barsky_clipper(float xmin, float ymin, float xmax, float ymax,
float x1, float y1, float x2, float y2) {
// defining variables
float p1 = -(x2 - x1);
float p2 = -p1;
float p3 = -(y2 - y1);
float p4 = -p3;
 
float q1 = x1 - xmin;
float q2 = xmax - x1;
float q3 = y1 - ymin;
float q4 = ymax - y1;
 
float exitParams[5], entryParams[5];
int exitIndex = 1, entryIndex = 1;
exitParams[0] = 1;
entryParams[0] = 0;
 
rectangle(xmin, ymin, xmax, ymax); // drawing the clipping window
 
if ((p1 == 0 && q1 < 0) || (p2 == 0 && q2 < 0) || (p3 == 0 && q3 < 0) || (p4 == 0 && q4 < 0)) {
outtextxy(80, 80, "Line is parallel to clipping window!");
return;
}
if (p1 != 0) {
float r1 = q1 / p1;
float r2 = q2 / p2;
if (p1 < 0) {
entryParams[entryIndex++] = r1;
exitParams[exitIndex++] = r2;
} else {
entryParams[entryIndex++] = r2;
exitParams[exitIndex++] = r1;
}
}
if (p3 != 0) {
float r3 = q3 / p3;
float r4 = q4 / p4;
if (p3 < 0) {
entryParams[entryIndex++] = r3;
exitParams[exitIndex++] = r4;
} else {
entryParams[entryIndex++] = r4;
exitParams[exitIndex++] = r3;
}
}
 
float clippedX1, clippedY1, clippedX2, clippedY2;
float u1, u2;
u1 = maxi(entryParams, entryIndex); // maximum of entry points
u2 = mini(exitParams, exitIndex); // minimum of exit points
 
if (u1 > u2) {
outtextxy(80, 80, "Line is outside the clipping window!");
return;
}
 
clippedX1 = x1 + (x2 - x1) * u1;
clippedY1 = y1 + (y2 - y1) * u1;
clippedX2 = x1 + (x2 - x1) * u2;
clippedY2 = y1 + (y2 - y1) * u2;
 
setcolor(CYAN);
line(clippedX1, clippedY1, clippedX2, clippedY2); // draw clipped segment
 
setlinestyle(1, 1, 0);
line(x1, y1, clippedX1, clippedY1); // original start to clipped start
line(x2, y2, clippedX2, clippedY2); // original end to clipped end
}
 
int main() {
cout << "\nLiang-Barsky Line Clipping";
cout << "\nThe system window layout is: (0,0) at bottom left and (631, 467) at top right";
cout << "\nEnter the coordinates of the window (xmin, ymin, xmax, ymax): ";
float xmin, ymin, xmax, ymax;
cin >> xmin >> ymin >> xmax >> ymax;
 
cout << "\nEnter the endpoints of the line (x1, y1) and (x2, y2): ";
float x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
 
int gd = DETECT, gm;
initgraph(&gd, &gm, ""); // using winbgim
 
liang_barsky_clipper(xmin, ymin, xmax, ymax, x1, y1, x2, y2);
getch();
closegraph();
}
</syntaxhighlight>
 
==See also==
Algorithms used for the same purpose:
* [[Cyrus–Beck algorithm]]
* [[Nicholl–Lee–Nicholl algorithm]]
* [[Fast- clipping]]
 
==References==
* Liang, Y. D., and Barsky, B., "[https://dl.acm.org/doi/pdf/10.1145/357332.357333 A New Concept and Method for Line Clipping]", ''ACM Transactions on Graphics'', 3(1):1-221–22, January 1984.
* Liang, Y. D., B. A., Barsky, and M. Slater, ''[https://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-688.pdf Some Improvements to a Parametric Line Clipping Algorithm]'', CSD-92-688, Computer Science Division, University of California, Berkeley, 1992.
* James D. Foley. ''[https://books.google.com/books/about/Computer_graphics.html?id=-4ngT05gmAQC Computer graphics: principles and practice]''. Addison-Wesley Professional, 1996. p.&nbsp;117.
 
==External links==
* http://hinjang.com/articles/04.html#eight
* [http://www.skytopia.com/project/articles/compsci/clipping.html Skytopia: The Liang-Barsky line clipping algorithm in a nutshell!]
 
{{DEFAULTSORT:Liang-Barsky algorithm}}
[[Category:Line clipping algorithms]]
Retrieved from "https://en.wikipedia.org/wiki/Liang–Barsky_algorithm"