C和C ++中的Liang Barsky线裁剪算法
Here you will learn about liang barsky line clipping algorithm in C and C++.
在这里，您将了解C和C ++中的liang barsky线裁剪算法。
This Algorithm was developed by Liang and Barsky. It is used for line clipping as it is more efficient than Cyrus Beck algorithm and Cohen Sutherland algorithm because it uses more efficient parametric equations to clip the given line.
该算法由Liang和Barsky开发。 它比Cyrus Beck算法和Cohen Sutherland算法更有效，因为它使用更有效的参数方程式裁剪给定的线，因此它比Cyrus Beck算法和Cohen Sutherland算法更有效。
These parametric equations are given as:
这些参数方程式为：
x = x1 + tdx
x = x1 + tdx
y = y1 + tdy, 0 <= t <= 1
y = y1 + tdy，0 <= t <= 1
Where dx = x2 – x1 & dy = y2 – y1
dx = x2 – x1＆dy = y2 – y1
Liang Barsky line clipping algorithm uses 4 inequalities with 2 parameters p & q which are defined in the algorithm below.
Liang Barsky线裁剪算法使用4个不等式以及2个参数p＆q，这些参数在下面的算法中定义。
算法 (Algorithm)
1. Read 2 endpoints of line as p1 (x1, y1) & p2 (x2, y2).
1.将线的2个端点读取为p1(x1，y1)和p2(x2，y2)。
2. Read 2 corners (left-top & right-bottom) of the clipping window as (xwmin, ywmin, xwmax, ywmax).
2.将剪切窗口的2个角(左上角和右下角)读取为(xwmin，ywmin，xwmax，ywmax)。
3. Calculate values of parameters pi and qi for i = 1, 2, 3, 4 such that
3.计算i = 1、2、3、4的参数pi和qi的值，使得
p1 = -dx, q1 = x1 – xwmin
p1 = -dx，q1 = x1 – xwmin
p2 = dx, q2 = xwmax – x1
p2 = dx，q2 = xwmax – x1
p3 = -dy, q3 = y1 – ywmin
p3 = -dy，q3 = y1 – ywmin
p4 = dy, q4 = ywmax – y1
p4 = dy，q4 = ywmax – y1
4. if pi = 0 then line is parallel to ith boundary
4.如果pi = 0，则线平行于第i个边界
if qi < 0 then line is completely outside boundary so discard line
如果qi <0，则线完全在边界之外，因此丢弃线
else, check whether line is horizontal or vertical and then check the line endpoints with the corresponding boundaries.
否则，检查线是水平还是垂直，然后检查具有相应边界的线端点。
5. Initialize t1 & t2 as
5.初始化t1和t2为
t1 = 0 & t2 = 1
t1 = 0＆t2 = 1
6. Calculate values for qi/pi for i = 1, 2, 3, 4.
6.计算i = 1、2、3、4时qi / pi的值。
7. Select values of qi/pi where pi < 0 and assign maximum out of them as t1.
7.在pi <0的情况下选择qi / pi的值，并将其中的最大值分配为t1。
8. Select values of qi/pi where pi > 0 and assign minimum out of them as t2.
8.在pi> 0的情况下选择qi / pi的值，并将其中的最小值指定为t2。
9. if (t1 < t2) { xx1 = x1 + t1dx
9.如果(t1 <t2){xx1 = x1 + t1dx
xx2 = x1 + t2dx
xx2 = x1 + t2dx
yy1 = y1 + t1dy
yy1 = y1 + t1dy
yy2 = y1 + t2dy
yy2 = y1 + t2dy
line (xx1, yy1, xx2, yy2) }
行(xx1，yy1，xx2，yy2)}
10. Stop.
10.停下来。
优点 (Advantages)
1. More efficient than other algorithms as line intersection with boundaries calculations are reduced.
1.与其他算法相比，效率更高，因为与边界计算的线相交减少了。
2. Intersections of line are computed only once.
2.线的交点仅计算一次。
用C和C ++编写Liang Barsky剪线算法程序 (Program for Liang Barsky Line Clipping Algorithm in C and C++)
C程序 (C Program)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
#include<stdio.h>
#include<graphics.h>
#include<math.h>
#include<dos.h>
void main()
{
int i,gd=DETECT,gm;
int x1,y1,x2,y2,xmin,xmax,ymin,ymax,xx1,xx2,yy1,yy2,dx,dy;
float t1,t2,p[4],q[4],temp;
x1=120;
y1=120;
x2=300;
y2=300;
xmin=100;
ymin=100;
xmax=250;
ymax=250;
initgraph(&gd,&gm,"c:\\turboc3\\bgi");
rectangle(xmin,ymin,xmax,ymax);
dx=x2-x1;
dy=y2-y1;
p[0]=-dx;
p[1]=dx;
p[2]=-dy;
p[3]=dy;
q[0]=x1-xmin;
q[1]=xmax-x1;
q[2]=y1-ymin;
q[3]=ymax-y1;
for(i=0;i<4;i++)
{
if(p[i]==0)
{
printf("line is parallel to one of the clipping boundary");
if(q[i]>=0)
{
if(i<2)
{
if(y1<ymin)
{
y1=ymin;
}
if(y2>ymax)
{
y2=ymax;
}
line(x1,y1,x2,y2);
}
if(i>1)
{
if(x1<xmin)
{
x1=xmin;
}
if(x2>xmax)
{
x2=xmax;
}
line(x1,y1,x2,y2);
}
}
}
}
t1=0;
t2=1;
for(i=0;i<4;i++)
{
temp=q[i]/p[i];
if(p[i]<0)
{
if(t1<=temp)
t1=temp;
}
else
{
if(t2>temp)
t2=temp;
}
}
if(t1<t2)
{
xx1 = x1 + t1 * p[1];
xx2 = x1 + t2 * p[1];
yy1 = y1 + t1 * p[3];
yy2 = y1 + t2 * p[3];
line(xx1,yy1,xx2,yy2);
}
delay(5000);
closegraph();
}
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
#include<stdio.h>
#include<graphics.h>
#include<math.h>
#include<dos.h>
void main ( )
{
int i , gd = DETECT , gm ;
int x1 , y1 , x2 , y2 , xmin , xmax , ymin , ymax , xx1 , xx2 , yy1 , yy2 , dx , dy ;
float t1 , t2 , p [ 4 ] , q [ 4 ] , temp ;
x1 = 120 ;
y1 = 120 ;
x2 = 300 ;
y2 = 300 ;
xmin = 100 ;
ymin = 100 ;
xmax = 250 ;
ymax = 250 ;
initgraph ( & gd , & gm , "c:\\turboc3\\bgi" ) ;
rectangle ( xmin , ymin , xmax , ymax ) ;
dx = x2 - x1 ;
dy = y2 - y1 ;
p [ 0 ] = - dx ;
p [ 1 ] = dx ;
p [ 2 ] = - dy ;
p [ 3 ] = dy ;
q [ 0 ] = x1 - xmin ;
q [ 1 ] = xmax - x1 ;
q [ 2 ] = y1 - ymin ;
q [ 3 ] = ymax - y1 ;
for ( i = 0 ; i < 4 ; i ++ )
{
if ( p [ i ] == 0 )
{
printf ( "line is parallel to one of the clipping boundary" ) ;
if ( q [ i ] >= 0 )
{
if ( i < 2 )
{
if ( y1 < ymin )
{
y1 = ymin ;
}
if ( y2 > ymax )
{
y2 = ymax ;
}
line ( x1 , y1 , x2 , y2 ) ;
}
if ( i > 1 )
{
if ( x1 < xmin )
{
x1 = xmin ;
}
if ( x2 > xmax )
{
x2 = xmax ;
}
line ( x1 , y1 , x2 , y2 ) ;
}
}
}
}
t1 = 0 ;
t2 = 1 ;
for ( i = 0 ; i < 4 ; i ++ )
{
temp = q [ i ] / p [ i ] ;
if ( p [ i ] < 0 )
{
if ( t1 <= temp )
t1 = temp ;
}
else
{
if ( t2 > temp )
t2 = temp ;
}
}
if ( t1 < t2 )
{
xx1 = x1 + t1 * p [ 1 ] ;
xx2 = x1 + t2 * p [ 1 ] ;
yy1 = y1 + t1 * p [ 3 ] ;
yy2 = y1 + t2 * p [ 3 ] ;
line ( xx1 , yy1 , xx2 , yy2 ) ;
}
delay ( 5000 ) ;
closegraph ( ) ;
}
|
C ++程序 (C++ Program)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
#include<iostream.h>
#include<graphics.h>
#include<math.h>
#include<dos.h>
void main()
{
int i,gd=DETECT,gm;
int x1,y1,x2,y2,xmin,xmax,ymin,ymax,xx1,xx2,yy1,yy2,dx,dy;
float t1,t2,p[4],q[4],temp;
x1=120;
y1=120;
x2=300;
y2=300;
xmin=100;
ymin=100;
xmax=250;
ymax=250;
initgraph(&gd,&gm,"c:\\turboc3\\bgi");
rectangle(xmin,ymin,xmax,ymax);
dx=x2-x1;
dy=y2-y1;
p[0]=-dx;
p[1]=dx;
p[2]=-dy;
p[3]=dy;
q[0]=x1-xmin;
q[1]=xmax-x1;
q[2]=y1-ymin;
q[3]=ymax-y1;
for(i=0;i<4;i++)
{
if(p[i]==0)
{
cout<<"line is parallel to one of the clipping boundary";
if(q[i]>=0)
{
if(i<2)
{
if(y1<ymin)
{
y1=ymin;
}
if(y2>ymax)
{
y2=ymax;
}
line(x1,y1,x2,y2);
}
if(i>1)
{
if(x1<xmin)
{
x1=xmin;
}
if(x2>xmax)
{
x2=xmax;
}
line(x1,y1,x2,y2);
}
}
}
}
t1=0;
t2=1;
for(i=0;i<4;i++)
{
temp=q[i]/p[i];
if(p[i]<0)
{
if(t1<=temp)
t1=temp;
}
else
{
if(t2>temp)
t2=temp;
}
}
if(t1<t2)
{
xx1 = x1 + t1 * p[1];
xx2 = x1 + t2 * p[1];
yy1 = y1 + t1 * p[3];
yy2 = y1 + t2 * p[3];
line(xx1,yy1,xx2,yy2);
}
delay(5000);
closegraph();
}
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
#include<iostream.h>
#include<graphics.h>
#include<math.h>
#include<dos.h>
void main ( )
{
int i , gd = DETECT , gm ;
int x1 , y1 , x2 , y2 , xmin , xmax , ymin , ymax , xx1 , xx2 , yy1 , yy2 , dx , dy ;
float t1 , t2 , p [ 4 ] , q [ 4 ] , temp ;
x1 = 120 ;
y1 = 120 ;
x2 = 300 ;
y2 = 300 ;
xmin = 100 ;
ymin = 100 ;
xmax = 250 ;
ymax = 250 ;
initgraph ( &gd , &gm , "c:\\turboc3\\bgi" ) ;
rectangle ( xmin , ymin , xmax , ymax ) ;
dx = x2 - x1 ;
dy = y2 - y1 ;
p [ 0 ] = - dx ;
p [ 1 ] = dx ;
p [ 2 ] = - dy ;
p [ 3 ] = dy ;
q [ 0 ] = x1 - xmin ;
q [ 1 ] = xmax - x1 ;
q [ 2 ] = y1 - ymin ;
q [ 3 ] = ymax - y1 ;
for ( i = 0 ; i < 4 ; i ++ )
{
if ( p [ i ] == 0 )
{
cout << "line is parallel to one of the clipping boundary" ;
if ( q [ i ] >= 0 )
{
if ( i < 2 )
{
if ( y1 < ymin )
{
y1 = ymin ;
}
if ( y2 > ymax )
{
y2 = ymax ;
}
line ( x1 , y1 , x2 , y2 ) ;
}
if ( i > 1 )
{
if ( x1 < xmin )
{
x1 = xmin ;
}
if ( x2 > xmax )
{
x2 = xmax ;
}
line ( x1 , y1 , x2 , y2 ) ;
}
}
}
}
t1 = 0 ;
t2 = 1 ;
for ( i = 0 ; i < 4 ; i ++ )
{
temp = q [ i ] / p [ i ] ;
if ( p [ i ] < 0 )
{
if ( t1 <= temp )
t1 = temp ;
}
else
{
if ( t2 > temp )
t2 = temp ;
}
}
if ( t1 < t2 )
{
xx1 = x1 + t1 * p [ 1 ] ;
xx2 = x1 + t2 * p [ 1 ] ;
yy1 = y1 + t1 * p [ 3 ] ;
yy2 = y1 + t2 * p [ 3 ] ;
line ( xx1 , yy1 , xx2 , yy2 ) ;
}
delay ( 5000 ) ;
closegraph ( ) ;
}
|
Output
输出量
Author Bio:
作者简介：
I am Rahul Maheshwari from India currently pursuing engineering degree in Computer Science. I am passionate about programming and loves to code as much as I can and likes to help people to become better in programming.
我是印度的Rahul Maheshwari，目前正在攻读计算机科学的工程学位。 我对编程充满热情，并且热衷于编码，并且喜欢帮助人们在编程方面变得更好。
Connect with him: Facebook | Linkedin
Comment below if you have doubts or found anything incorrect in above liang barsky line clipping algorithm in C and C++.
如果您对以上使用C和C ++的liang barsky线裁剪算法有疑问或发现任何不正确之处，请在下面评论。
翻译自: https://www.thecrazyprogrammer.com/2017/02/liang-barsky-line-clipping-algorithm.html