Liang–Barsky algorithm: Difference between revisions

Revision as of 04:46, 9 May 2017

Latest revision as of 07:26, 10 August 2025

(23 intermediate revisions by 17 users not shown)

Line 1:

{{Short description|Line-clipping algorithm}}

In [[computer graphics]], the '''Liang–''' (named after [[You-Dong Liang]] and [[Brian A. Barsky]]) is a [[line clipping]] algorithm. The Liang– 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 + t (x_1 - x_0) = x_0 + t \Delta x\,\!</math>

:<math>y = y_0 + t (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

<source lang="c++">

// Liang Barsky Line Clipping Algorithm

#include<iostream>

#include<graphics.h>

Line 37 ⟶ 41:

// this function gives the maximum

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

float m = 0;

{

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

forif (intm i< = 0;i<n;arr[i++])

{ m = arr[i];

return m;

if(m<arr[i])

{

m = arr[i];

}

}

return m;

}

// this function gives the minimum

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

float mini( float arr[],intm = n)1;

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

{

floatif (m => 1;arr[i])

for(int i m = 0;arr[i<n];i++)

return {m;

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;

// defining variables

float p1q2 = xmax -(x2- x1);

float p2q3 = y1 -p1 ymin;

float p3q4 = ymax -(y2- y1);

float p4 = -p3;

float q1 =exitParams[5], x1-xminentryParams[5];

int float q2exitIndex = xmax1, -entryIndex = x11;

float q3exitParams[0] = y1 - ymin1;

float q4entryParams[0] = ymax - y10;

rectangle(xmin, ymin, xmax, ymax); // drawing the clipping window

float posarr[5], negarr[5];

int posind = 1,negind = 1;

posarr[0] = 1;

negarr[0] = 0;

rectangle(xmin,467 - ymin,xmax,467 - ymax); // drawing the clipping window!

if((p1==0 && q1 < 0) || (p3 ==0 && q3 < 0))

{

outtextxy(80,80,"Line is Parallel to clipping window!");

return;

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(p1!=0)

if (p3 != 0) {

float r1r3 = q1q3 /p1 p3;

float r2r4 = q2q4 /p2 p4;

if (p1p3 < 0) {

entryParams[entryIndex++] = {r3;

negarrexitParams[negindexitIndex++] = r1r4;

} else {

posarr[posind++] = r2; // for negative p1, add it to negative array and add p2 to positive array

entryParams[entryIndex++] = }r4;

exitParams[exitIndex++] = elser3;

{

negarr[negind++] = r2;

posarr[posind++] = r1;

}

}

}

if(p3!=0)

{

float r3 = q3/p3;

float r4 = q4/p4;

float clippedX1, clippedY1, clippedX2, clippedY2;

if(p3<0)

float u1, {u2;

u1 = maxi(entryParams, entryIndex); // maximum of entry points

negarr[negind++] = r3;

u2 = mini(exitParams, exitIndex); // minimum of exit points

posarr[posind++] = r4;

}

else

{

negarr[negind++] = r4;

posarr[posind++] = r3;

}

}

if (u1 > u2) {

float xn1,yn1,xn2,yn2;

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

float rn1,rn2;

return;

rn1 = maxi(negarr,negind); // maximum of negative array

}

rn2 = mini(posarr,posind); // minimum of positive array

xn1clippedX1 = x1 + p2(x2 - x1) *rn1 u1;

yn1clippedY1 = y1 + p4*rn1;(y2 - y1) * // computing new pointsu1;

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

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

setcolor(CYAN);

xn2 = x1 + p2*rn2;

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

yn2 = y1 + p4*rn2;

setlinestyle(1, 1, 0);

setcolor(CYAN);

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

line(x2, y2, clippedX2, clippedY2); // original end to clipped end

}

int main() {

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

cout << "\nLiang-Barsky Line Clipping";

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

setlinestyle(1,1,0);

cout << "\nEnter the coordinates of the window (xmin, ymin, xmax, ymax): ";

float xmin, ymin, xmax, ymax;

line(x1,467 - y1,xn1,467 - yn1);

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

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

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>

int main()

{

cout<<"\nLIANG-BARSKY-LINE-CLIPPING";

cout<<"\nThe System Window Outlay is:(0,0) at bottom left and (631,467) at top right";

cout<<"\nEnter the co- ordinates of the window(wxmin,wxmax,wymin,wymax):";

float xmin,xmax,ymin,ymax;

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

cout<<"\nEnter the End Points of the Line (x1,y1) and (x2,y2):";

float x1, y1, x2, y2;

cin>>x1>>y1>>x2>>y2;

int gd = DETECT, gm;

// 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();

}

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