Liang–Barsky algorithm: Difference between revisions

Revision as of 21:16, 1 June 2017

Latest revision as of 07:26, 10 August 2025

(20 intermediate revisions by 16 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. ThisSo 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.

ConsiderThe firstalgorithm theuses usualthe parametric form of a straight line:

:<math>x = x_0 + t (x_1 - x_0) = x_0 + t \Delta x,</math>

Line 23 ⟶ 24:

</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 = 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>\{0, q_i / p_i\}</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>\{1, q_i / p_i\}</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.

<sourcesyntaxhighlight lang="c++">

// Liang--BarskyLiang–Barsky line-clipping algorithm

#include<iostream>

#include<graphics.h>

Line 39 ⟶ 41:

// this function gives the maximum

float maxi(float arr[], int n) {

float m = 0;

for (int i = 0; i < n; ++i)

Line 69 ⟶ 71:

float q4 = ymax - y1;

float posarrexitParams[5], negarrentryParams[5];

int posindexitIndex = 1, negindentryIndex = 1;

posarrexitParams[0] = 1;

negarrentryParams[0] = 0;

rectangle(xmin, 467 - ymin, xmax, 467 - 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 Parallelparallel to clipping window!");

return;

}

Line 84 ⟶ 86:

float r2 = q2 / p2;

if (p1 < 0) {

entryParams[entryIndex++] = r1;

negarr[negind++] = r1; // for negative p1, add it to negative array

posarrexitParams[posindexitIndex++] = r2; // and add p2 to positive array

} else {

negarrentryParams[negindentryIndex++] = r2;

posarrexitParams[posindexitIndex++] = r1;

}

}

Line 95 ⟶ 97:

float r4 = q4 / p4;

if (p3 < 0) {

negarrentryParams[negindentryIndex++] = r3;

posarrexitParams[posindexitIndex++] = r4;

} else {

negarrentryParams[negindentryIndex++] = r4;

posarrexitParams[posindexitIndex++] = r3;

}

}

float xn1clippedX1, yn1clippedY1, xn2clippedX2, yn2clippedY2;

float rn1u1, rn2u2;

rn1u1 = maxi(negarrentryParams, negindentryIndex); // maximum of negativeentry arraypoints

rn2u2 = mini(posarrexitParams, posindexitIndex); // minimum of positiveexit arraypoints

xn1if =(u1 x1> +u2) p2 * rn1;{

outtextxy(80, 80, "Line is outside the clipping window!");

yn1 = y1 + p4 * rn1; // computing new points

return;

}

xn2clippedX1 = x1 + p2(x2 - x1) * rn2u1;

yn2clippedY1 = y1 + p4(y2 - y1) * rn2u1;

clippedX2 = x1 + (x2 - x1) * u2;

clippedY2 = y1 + (y2 - y1) * u2;

setcolor(CYAN);

line(clippedX1, clippedY1, clippedX2, clippedY2); // draw clipped segment

line(xn1, 467 - yn1, xn2, 467 - yn2); // the drawing the new line

setlinestyle(1, 1, 0);

line(x1, y1, clippedX1, clippedY1); // original start to clipped start

line(x1x2, 467 - y1y2, xn1clippedX2, 467 - yn1clippedY2); // original end to clipped end

line(x2, 467 - y2, xn2, 467 - yn2);

}

int main() {

cout << "\nLiang-barskyBarsky lineLine clippingClipping";

cout << "\nThe system window outlaylayout is: (0,0) at bottom left and (631, 467) at top right";

cout << "\nEnter the co-ordinatescoordinates of the window (wxminxmin, wxmaxymin, wyminxmax, wymaxymax): ";

float xmin, xmaxymin, yminxmax, ymax;

cin >> xmin >> ymin >> xmax >> ymax;

cout << "\nEnter the end pointsendpoints 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

// using the winbgim library for C++, initializing the graphics mode

initgraph(&gd, &gm, "");

liang_barsky_clipper(xmin, ymin, xmax, ymax, x1, y1, x2, y2);

getch();

closegraph();

}

</syntaxhighlight>

</source>

==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-}}