Liang–Barsky algorithm: Difference between revisions

Revision as of 16:56, 16 May 2017

Revision as of 21:16, 1 June 2017

Line 1:

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-BarskyLiang–Barsky clipping algorithm is to do as much testing as possible before computing line intersections.

Consider first the usual parametric form of a straight line:

:<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_k</math>, <math>u = \frac{q_i}{ / p_i}</math> gives the intersection point.

# For each line, calculate <math>u_1</math> and <math>u_2</math>. 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 outside and therefore rejected.

<source lang="c++">

// Liang --Barsky line-clipping Line Clipping Algorithmalgorithm

#include<iostream>

#include<graphics.h>

Line 37 ⟶ 39:

// 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 =posarr[5], x1-xminnegarr[5];

int float q2posind = xmax1, -negind = x11;

float q3posarr[0] = y1 - ymin1;

float q4negarr[0] = ymax - y10;

rectangle(xmin, 467 - ymin, xmax, 467 - 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) || (p3 == 0 && q3 < 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) {

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

posarr[posind++] = r2; // and add p2 to positive array

} else {

negarr[negind++] = r2;

posarr[posind++] = r1;

}

}

if(p1!=0)

if (p3 != 0) {

float r1r3 = q1q3 /p1 p3;

float r2r4 = q2q4 /p2 p4;

if (p1p3 < 0) {

negarr[negind++] = {r3;

negarrposarr[negindposind++] = r1r4;

} else {

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

negarr[negind++] = }r4;

posarr[posind++] = elser3;

{

negarr[negind++] = r2;

posarr[posind++] = r1;

}

}

}

if(p3!=0)

{

float r3 = q3/p3;

float r4 = q4/p4;

float xn1, yn1, xn2, yn2;

if(p3<0)

float rn1, {rn2;

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

negarr[negind++] = r3;

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

posarr[posind++] = r4;

}

else

{

negarr[negind++] = r4;

posarr[posind++] = r3;

}

}

xn1 = x1 + p2 * rn1;

float xn1,yn1,xn2,yn2;

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

float rn1,rn2;

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

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

xn1xn2 = x1 + p2 *rn1 rn2;

yn1yn2 = y1 + p4 *rn1 rn2; // computing new points

setcolor(CYAN);

xn2 = x1 + p2*rn2;

yn2 = y1 + p4*rn2;

setcolor(CYAN);

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

setlinestyle(1,1,0);

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

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

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

setlinestyle(1, 1, 0);

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

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

}

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<<"\nLIANG-BARSKY-LINE-CLIPPING";

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

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

float xmin, xmax, ymin, ymax;

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

cin float>> xmin,xmax, >> ymin, >> xmax >> ymax;

cout << "\nEnter the end points of the line (x1, y1) and (x2, y2):";

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

float x1, y1, x2, y2;

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

cin 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: