Nicholl-Lee-Nicholl二维线段裁剪算法相对于Cohen-Sutherland和Liang-Barsky算法来说，在求交点之前进行了线段端点相对于几个区域的判断，可以确切的知道要求交点的边的信息。
此方法只在二维空间裁剪时使用，C-S和L-B裁剪方法则可应用到三维空间。
![[图形学] 习题8.12 NLN二维线段裁剪算法实现](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9nby9hSFIwY0hNNkx5OXBiV0ZuWlhNeU1ERTFMbU51WW14dlozTXVZMjl0TDJKc2IyY3ZOalV6TmpFeEx6SXdNVGN3Tmk4Mk5UTTJNVEV0TWpBeE56QTJNREV5TWpVNU16SXhPREF0TVRRME5USXdNVEl3T1M1d2JtYz0%3D.jpg?w=700 "[图形学] 习题8.12 NLN二维线段裁剪算法实现")
算法步骤：
1 先使用C-S裁剪算法的区域码判断方法，去除一部分在裁剪区域外面的线段、显示在完全在裁剪区域内的线段。其他不能判断的情况，采用NLN算法进行裁剪。
2 p1和p2若有一点在区域内，必要时交换端点以确保p1在区域内。
分别计算p1到裁剪区域四个顶点斜率m1-m4（从左下端点顺时针的4个顶点），判断线段斜率m与m1-m4的关系，决定计算哪条边与线段的交点。交点值赋给p2.
3 p1和p2有一个点在区域0001（左侧），必要时交换端点以确保p1在0001内。
因为p2在区域内的情况被步骤2覆盖，因此p1为线段与左边界的交点。
分别计算m1-m4，判断线段斜率m与m1-m4的关系，决定计算哪条边与线段的交点。此交点赋值给p2.
4 p1和p2有一个点在区域1001（左上角），必要时交换端点以确保p1在1001内。
同样p2在区域内的情况被步骤2覆盖。
分别计算m1-m4，判断线段斜率m与m1-m4的关系（注意此处需要判断m2与m4的大小，决定计算哪条边与线段的交点）。分别计算p1和p2。
5 对于其他6种情况，分别判断p1和p2的位置，在不同的区域，将线段和裁剪区域旋转相应的角度，重复步骤2-4进行裁剪。裁剪完成后再将线段旋转回原来的位置。
![[图形学] 习题8.12 NLN二维线段裁剪算法实现](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9nby9hSFIwY0hNNkx5OXBiV0ZuWlhNdVkyNWliRzluY3k1amIyMHZUM1YwYkdsdWFXNW5TVzVrYVdOaGRHOXljeTlEYjI1MGNtRmpkR1ZrUW14dlkyc3VaMmxt.jpg?w=700 "[图形学] 习题8.12 NLN二维线段裁剪算法实现")
![[图形学] 习题8.12 NLN二维线段裁剪算法实现](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9nby9hSFIwY0hNNkx5OXBiV0ZuWlhNdVkyNWliRzluY3k1amIyMHZUM1YwYkdsdWFXNW5TVzVrYVdOaGRHOXljeTlGZUhCaGJtUmxaRUpzYjJOclUzUmhjblF1WjJsbQ%3D%3D.jpg?w=700 "[图形学] 习题8.12 NLN二维线段裁剪算法实现")
1 #include <GLUT/GLUT.h>NLN二维线段裁剪算法
2 #include <iostream>
3 #include <math.h>
4 #include "lineNLN.h"
5 #include "linebres.h"
6
7 GLfloat m1, m2, m3, m4;
8
9 const GLint winLeftBitCode = 0x1; // 直接为1也没问题
10 const GLint winRightBitCode = 0x2;
11 const GLint winBottomBitCode = 0x4;
12 const GLint winTopBitCode = 0x8;
13
14 typedef GLfloat Matrix3x3 [3][3];
15 Matrix3x3 matRotate;
16 Matrix3x3 matComposite;
17 const GLdouble pi = 3.14159;
18 GLfloat delta;
19 wcPt2D center;
20
21 inline GLint inside (GLint code)
22 {
23 return GLint (!(code));
24 }
25 inline GLint reject (GLint code1, GLint code2)
26 {
27 return GLint (code1 & code2);
28 }
29 inline GLint accept (GLint code1, GLint code2)
30 {
31 return GLint (!(code1 | code2));
32 }
33
34 GLubyte encode (wcPt2D pt, wcPt2D winMin, wcPt2D winMax)
35 {
36 GLubyte code = 0x00;
37
38 if(pt.getx() < winMin.getx())
39 code = code | winLeftBitCode;
40 if(pt.getx() > winMax.getx())
41 code = code | winRightBitCode;
42 if(pt.gety() < winMin.gety())
43 code = code | winBottomBitCode;
44 if(pt.gety() > winMax.gety())
45 code = code | winTopBitCode;
46
47 return code;
48 }
49
50 void swapPts (wcPt2D * p1, wcPt2D * p2) // TODO 为什么要用指针？
51 {
52 wcPt2D tmp;
53 tmp = * p1; * p1 = * p2; * p2 = tmp;
54 }
55
56 void swapCode (GLubyte * c1, GLubyte * c2)
57 {
58 GLubyte tmp;
59 tmp = * c1; * c1 = * c2; * c2 = tmp;
60 }
61
62 void renewWinVertexes (wcPt2D * winMin, wcPt2D * winMax)
63 {
64 wcPt2D tmp1, tmp2;
65 tmp1.setCoords(fmin(winMin->getx(), winMax->getx()), fmin(winMin->gety(), winMax->gety()));
66 tmp2.setCoords(fmax(winMin->getx(), winMax->getx()), fmax(winMin->gety(), winMax->gety()));
67 * winMin = tmp1;
68 * winMax = tmp2;
69 }
70
71 void matrix3x3SetIdentity (Matrix3x3 matIden3x3)
72 {
73 GLint row, col;
74 for(row = 0; row < 3; row++)
75 {
76 for(col = 0; col < 3; col++)
77 {
78 matIden3x3[row][col] = (row == col);
79 }
80 }
81 }
82
83 void matrix3x3Premultiply (Matrix3x3 m1, Matrix3x3 m2)
84 {
85 GLint row, col;
86 Matrix3x3 matTemp;
87
88 for(row = 0; row < 3; row++)
89 {
90 for(col = 0; col < 3; col++)
91 {
92 matTemp[row][col] = m1[row][0] * m2 [0][col] + m1[row][1] * m2 [1][col] + m1[row][2] * m2 [2][col];
93 }
94 }
95
96 for(row = 0; row < 3; row++)
97 {
98 for(col = 0; col < 3; col++)
99 {
100 m2[row][col] = matTemp[row][col];
101 }
102 }
103 }
104
105 void rotate2D (wcPt2D pivotPt, GLfloat theta)
106 {
107 matrix3x3SetIdentity(matRotate);
108
109 matRotate[0][0] = cos(theta);
110 matRotate[0][1] = -sin(theta);
111 matRotate[0][2] = pivotPt.getx() * (1 - cos(theta)) + pivotPt.gety() * sin(theta);
112 matRotate[1][0] = sin(theta);
113 matRotate[1][1] = cos(theta);
114 matRotate[1][2] = pivotPt.gety() * (1 - cos(theta)) + pivotPt.getx() * sin(theta);
115 }
116
117 void transformVerts2D (wcPt2D * verts)
118 {
119 GLfloat tempx, tempy;
120
121 tempx = matRotate[0][0] * verts->getx() + matRotate[0][1] * verts->gety() + matRotate[0][2];
122 tempy = matRotate[1][0] * verts->getx() + matRotate[1][1] * verts->gety() + matRotate[1][2];
123
124 verts->setCoords(tempx, tempy);
125 }
126
127 void slopeWith4Vertexes (wcPt2D winMin, wcPt2D winMax, wcPt2D p1)
128 {
129 m1 = (p1.gety() - winMin.gety()) / (p1.getx() - winMin.getx());
130 m2 = (p1.gety() - winMax.gety()) / (p1.getx() - winMin.getx());
131 m3 = (p1.gety() - winMax.gety()) / (p1.getx() - winMax.getx());
132 m4 = (p1.gety() - winMin.gety()) / (p1.getx() - winMax.getx());
133
134 // std::cout << "slope : m1 : " << m1 << " m2 : " << m2 << " m3 : " << m3 << " m4 : " << m4 << std::endl;
135 }
136
137 void lineClipNLN (wcPt2D winMin, wcPt2D winMax, wcPt2D p1, wcPt2D p2)
138 {
139 GLubyte code1, code2;
140 GLint plotLine = false, done = false;
141 GLfloat m = 0.0;
142
143 while (!done)
144 {
145 code1 = encode(p1, winMin, winMax);
146 code2 = encode(p2, winMin, winMax);
147 if(accept(code1, code2))
148 {
149 plotLine = true;
150 done = true;
151 }
152 else
153 {
154 if(reject(code1, code2))
155 {
156 std::cout << "1 rejected line!" << std::endl;
157 done = true;
158 }
159 else
160 {
161 // 有一个点在裁剪区域内
162 if(inside(code1) || inside(code2))
163 {
164 plotLine = true;
165 done = true;
166 if(!inside(code1))
167 {
168 swapPts(&p1, &p2);
169 swapCode(&code1, &code2);
170 }
171 wcPt2D topLeft, bottomRight;
172 topLeft.setCoords(winMin.getx(), winMax.gety());
173 bottomRight.setCoords(winMax.getx(), winMin.gety());
174 if(p1.equals(winMin) || p1.equals(winMax) || p1.equals(topLeft) || p1.equals(bottomRight))
175 {
176 p2.setCoords(p1.getx(), p1.gety());
177 }
178 else
179 {
180 slopeWith4Vertexes(winMin, winMax, p1);
181
182 if(p1.getx() != p2.getx())
183 {
184 m = (p2.gety() - p1.gety()) / (p2.getx() - p1.getx());
185
186 if(m <= m1 && m >= m2 && (code2 & winLeftBitCode))
187 {//L
188 p2.setCoords(winMin.getx(), p1.gety() + m * (winMin.getx() - p1.getx()));
189 }
190 else if(m <= m3 && m >= m4 && (code2 & winRightBitCode))
191 {//R
192 p2.setCoords(winMax.getx(), p1.gety() + m * (winMax.getx() - p1.getx()));
193 }
194 else if((m > m3 || m < m2) && (code2 & winTopBitCode))
195 {//T
196 p2.setCoords(p1.getx() + (winMax.gety() - p1.gety())/m, winMax.gety());
197 }
198 else if((m > m1 || m < m4) && (code2 & winBottomBitCode))
199 {//B
200 p2.setCoords(p1.getx() + (winMin.gety() - p1.gety())/m, winMin.gety());
201 }
202 }
203 else
204 {
205 if(p2.gety() > winMax.gety())
206 {
207 p2.setCoords(p2.getx(), winMax.gety());
208 }
209 else
210 {
211 p2.setCoords(p2.getx(), winMin.gety());
212 }
213 }
214 }
215 }
216 else
217 {
218 if(code1 == 0x01 || code2 == 0x01)
219 // 有一个点的区域码是0001，即在裁剪区域正左侧，L的情况在上一个if中包含，这里只会有LT，LR，LB和rejected的情况
220 {
221 if(code1 != 0x01)
222 {
223 swapPts(&p1, &p2);
224 swapCode(&code1, &code2);
225 }
226 slopeWith4Vertexes(winMin, winMax, p1);
227 if(p1.getx() != p2.getx())
228 {
229 m = (p2.gety() - p1.gety()) / (p2.getx() - p1.getx());
230 }
231 if(m < m1 || m > m2)
232 {
233 std::cout << "2 rejected line!" << std::endl;
234 done = true;
235 }
236 else
237 {
238 p1.setCoords(winMin.getx(), p1.gety() + m * (winMin.getx() - p1.getx()));
239 if((m <= m2 && m >= m3) && (code2 & winTopBitCode))
240 {//LT
241 p2.setCoords(p1.getx() + (winMax.gety() - p1.gety())/m, winMax.gety());
242 }
243 else if((m < m3 && m >= m4) && (code2 & winRightBitCode))
244 {//LR
245 p2.setCoords(winMax.getx(), p1.gety() + m * (winMax.getx() - p1.getx()));
246 }
247 else if((m < m4 && m >= m1) && (code2 & winBottomBitCode))
248 {//LB
249 p2.setCoords(p1.getx() + (winMin.gety() - p1.gety())/m, winMin.gety());
250 }
251 plotLine = true;
252 done = true;
253 }
254 }
255 else if(code1 == (winLeftBitCode | winTopBitCode) || code2 == (winLeftBitCode | winTopBitCode))
256 // 有一个点在裁剪区域外左上角的情况，这里的L、T情况已经在第一个if里包含
257 {
258 if(code1 != (winLeftBitCode | winTopBitCode))
259 {
260 swapPts(&p1, &p2);
261 swapCode(&code1, &code2);
262 }
263
264 slopeWith4Vertexes(winMin, winMax, p1);
265 if(p1.getx() != p2.getx())
266 {
267 m = (p2.gety() - p1.gety()) / (p2.getx() - p1.getx());
268 }
269 if(m > m3 || m < m1)
270 {
271 std::cout << "3 rejected line!" << std::endl;
272 done = true;
273 }
274 else
275 {
276 plotLine = true;
277 done = true;
278 if(m <= m3 && m >= m4)
279 {
280 p2.setCoords(winMax.getx(), p1.gety() + m * (winMax.getx() - p1.getx()));
281 if(m2 > m4 && m <= m2)
282 {//LR
283 p1.setCoords(winMin.getx(), p1.gety() + m * (winMin.getx() - p1.getx()));
284 }
285 else
286 {//TR
287 p1.setCoords(p1.getx() + (winMax.gety() - p1.gety())/m, winMax.gety());
288 }
289 }
290 else if(m < m4 && m >= m1)
291 {
292 p2.setCoords(p1.getx() + (winMin.gety() - p1.gety())/m, winMin.gety());
293 if(m2 < m4 && m >= m2)
294 {//TB
295 p1.setCoords(p1.getx() + (winMax.gety() - p1.gety())/m, winMax.gety());
296 }
297 else
298 {//LB
299 p1.setCoords(winMin.getx(), p1.gety() + m * (winMin.getx() - p1.getx()));
300 }
301 }
302 }
303 }
304 else
305 {
306 center.setCoords((winMin.getx() + winMax.getx())/2, (winMin.gety() + winMax.gety())/2);
307
308 if(code1 == (winLeftBitCode | winBottomBitCode) || code2 == (winLeftBitCode | winBottomBitCode))
309 {//LB
310 delta = -pi/2;
311 }
312 else if(code1 == winBottomBitCode || code2 == winBottomBitCode)
313 {//B
314 delta = -pi/2;
315 }
316 else if(code1 == (winBottomBitCode | winRightBitCode) || code2 == (winBottomBitCode | winRightBitCode))
317 {//BR
318 delta = pi;
319 }
320 else if(code1 == winRightBitCode || code2 == winRightBitCode)
321 {//R
322 delta = pi;
323 }
324 else if(code1 == (winRightBitCode | winTopBitCode) || code2 == (winRightBitCode | winTopBitCode))
325 {//TR
326 delta = pi/2;
327 }
328 else if(code1 == winTopBitCode || code2 == winTopBitCode)
329 {//T
330 delta = pi/2;
331 }
332 rotate2D(center, delta);
333 transformVerts2D(&p1);
334 transformVerts2D(&p2);
335 transformVerts2D(&winMin);
336 transformVerts2D(&winMax);
337 renewWinVertexes(&winMin, &winMax);
338 }
339 }
340 }
341 }
342 }
343
344 if(plotLine)
345 {
346 if(delta != 0)
347 {
348 rotate2D(center, -delta);
349 transformVerts2D(&p1);
350 transformVerts2D(&p2);
351 }
352 lineBres(round(p1.getx()), round(p1.gety()), round(p2.getx()), round(p2.gety()));
353 }
354 delta = 0;
355 }
![[图形学] 习题8.12 NLN二维线段裁剪算法实现](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9nby9hSFIwY0hNNkx5OXBiV0ZuWlhNeU1ERTFMbU51WW14dlozTXVZMjl0TDJKc2IyY3ZOalV6TmpFeEx6SXdNVGN3Tmk4Mk5UTTJNVEV0TWpBeE56QTJNREV5TWpRNU1qWTRPRE10TVRBNU1EYzNORFl3TXk1d2JtYz0%3D.jpg?w=700 "[图形学] 习题8.12 NLN二维线段裁剪算法实现")
完整代码路径：https://github.com/p0e0o0p0l0e0/Computer_Graphics/tree/f9a7ad1987586445d780de2461d423af0dd9ba6a