Liang–Barsky algorithm: Difference between revisions

Revision as of 10:33, 9 September 2014

Revision as of 10:46, 9 September 2014

Line 26:

# For nonzero <math>p_k</math>, <math>u = \frac{q_k}{p_k}</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_k < 0</math> (i.e. outside to inside). Take <math>u_1</math> to be the largest among <math>\left\{ 0,\frac{q_k}{p_k} \right\}</math>. For <math>u_2</math>, look at boundaries for which <math>p_k > 0</math> (i.e. inside to outside). Take <math>u_2</math> to be the minimum of <math>\left\{ 1, \frac{q_k}{p_k} \right\}</math>. If <math>u_1 > u_2</math>, the line is outside and therefore rejected.

--------------------------------------

C++ implementation of Liang Barsky

--------------------------------------

void liangBarsky(double x1, double y1, double x2, double y2)

{

3,7

3,10

double dx = x2 - x1, dy = y2 - y1;

double u1 = 0.0, u2 = 1.0;

double p[5],q[5];

p[1] = -dx;

p[2] = dx;

p[3] = -dy;

p[4] = dy;

q[1] = x1 - xmin;

q[2] = xmax - x1;

q[3] = y1 - ymin;

q[4] = ymax - y1;

for(int i = 1; i<=4 ; i++)

{

if(p[i]==0 && q[i]<0)

return;

}

double r;

for(int i = 1 ; i<=4 ; i++)

{

r = q[i]/p[i];

if(p[i]<0)

u1 = u1>r?u1:r;

if(p[i]>0)

u2 = u2<r?u2:r;

}

if(u2<1.0)

{

x2 = x1 + u2*dx;

y2 = x1 + u2*dy;

}

if(u1>0.0)

{

x1 = x1 + u1*dx;

y1 = y1 + u1*dy;

}

drawLine(x0, y0, x1, y1);

}

==See also==

Algorithms used for the same purpose: