C/C++实现图形学扫描线填充算法

在上图形学课的时候，学习了扫描线填充算法。不过在完成实验的时候在真正理解了该算法，在此记录一下，如果有表达上的错误，欢迎指正！

扫描线填充算法通过在与图形相交的第（1，2）、（3，4）... 边之间划线不断不断填充图形。因此，在扫描时就需要确定什么时候与图形的某条边相交、划线的时候x的范围是多少以及划线时是从哪个交点画至另一个交点。

结构体如下所示：

为了节省存储的空间，边表项也使用链表结构，将图形中ymin值相同的边链接在同一个边表项后，这样在扫描的时候方便添加。

具体的流程如下：

一、初始化活动边表

1. 统计并初始化表项

2. 将每条边分别链接在表项后

二、 绘制与填充

1. 取出当前与扫描线相交的边

① 取出ymin 大于当前扫描线的y值的边

② 删除ymax 小于等于当前扫描线的边（①②过程可以排除掉与扫描线平行的边）

2. 将取出的边按照左右顺序排序（根据边的最低点的坐标与直线的斜率判断）

3. 划线并直接在原结构上修改边的x值（因为是在一个函数内，修改保存的值仅限于函数内，并不影响main函数中的值）

具体的代码如下所示，使用的库是EasyX（可以在http://www.easyx.cn/下载）：

1. #include "graphics.h"
2. #include "stdio.h"
3. #include "conio.h"
4. #include <stdlib.h>
5. #include <math.h>
6. #include <cmath>
7. #include <iostream>
8.  
9. using namespace std;
10. #define MAX_VOL 20
11. //多边形的边的数据结构
12. typedef struct Edge
13. {
14. int y_max, y_min; //该有向边的y坐标的最大值与最小值
15. double x, deltax; //该有向边的x的最小值以及x的变化的量（1/斜率）
16. struct Edge* next; //指向下一条边的指针
17.  
18. }Edge;
19. //活动边表表项
20. typedef struct TableItem
21. {
22. int curr_y; //该表项的y坐标值 ymin
23. Edge *firstNode; //该表项的首个节点，如果没有，NULL
24. struct TableItem *next; //指向下一个活动边表表项的指针
25. }TableItem;
26. //活动边表结构体
27. typedef struct Table
28. {
29. TableItem *itemHeader; //活动边表的表项header
30. int item_count; //活动边表表项的个数
31. }ET;
32.  
33. class Point
34. {
35. private:
36. int x1, x2, y1, y2;
37. public:
38. Point(int x1, int y1, int x2, int y2)
39. {
40. this->x1 = x1;
41. this->x2 = x2;
42. this->y1 = y1;
43. this->y2 = y2;
44. }
45. //返回两个点之中的ymax
46. int YMax()
47. {
48. return (y1 > y2 ? y1 : y2);
49. }
50. //返回ymin
51. int YMin()
52. {
53. return (y1 < y2 ? y1 : y2);
54. }
55. //返回ymin 端点的x 值
56. int x()
57. {
58. return (y1 < y2 ? x1 : x2);
59. }
60. //返回直线的斜率,按照传入的参数的顺序
61. double KOfLine()
62. {
63. return ((y2 - y1)*1.0 / (x2 - x1));
64. }
65.  
66. };
67.  
68. class Solution
69. {
70. public:
71. //根据多边形初始化活动表
72. //参数 T 活动边表
73. //参数edges 用于初始化的边数组
74. //参数 edge_num 用于初始化的边的个数
75. void Init(ET &T, Edge *edges, int edge_num)
76. {
77. //初始化活动边表结构体
78. T.item_count = 0;
79. T.itemHeader = NULL;
80. int ymins[20]; //存储ymin ,决定活动边表的个数以及表项的内容
81.  
82. T.item_count = TableItemCount(edges, edge_num, ymins);
83. T.itemHeader = (TableItem*)malloc(sizeof(TableItem));
84. T.itemHeader->curr_y = ymins[0];
85. T.itemHeader->firstNode = NULL;
86. T.itemHeader->next = NULL;
87. TableItem *p = T.itemHeader; //指向头结点
88. for (int i = 1; i<T.item_count; ++i)
89. {
90. //依次创建活动边表的各个表项，并连接在一起
91. TableItem *e = (TableItem*)malloc(sizeof(TableItem));
92. e->curr_y = ymins[i];
93. e->firstNode = NULL;
94. e->next = NULL;
95. p->next = e;
96. p = e;
97. }
98.  
99. //按照用于初始化的边数组初始化活动边表
100. p = T.itemHeader;
101. for (int j = 0; j < edge_num; ++j) {
102. this->AppendNode(T, edges[j].y_min, edges[j]);
103. }
104. //方法结束
105. ////////测试区////////////
106. //cout << "遍历表项。。。。。" << endl;
107. //p = T.itemHeader;
108. //while (p != NULL) {
109. // cout << "当前表项y : " << p->curr_y << endl;
110. // Edge *ele = p->firstNode;
111. // while (ele != NULL) {
112. // cout << "表项中的边： x = " << ele->x << " y_min = " << ele->y_min << " y_max = " << ele->y_max <<
113. // "deltax = " << ele->deltax << endl;
114. // ele = ele->next;
115. // }
116.  
117. // p = p->next;
118. //}
119. ////////测试删除结点////////
120. //p = T.itemHeader;
121. //int yMax = 0;
122. //while (yMax < 24) {
123. // p = T.itemHeader;
124. // cout << "-------------------------------" << endl;
125. // cout << "当前y max :" << yMax << endl;
126. // this->DeleteNode(T, yMax);
127. // while (p != NULL) {
128. // cout << "当前表项y : " << p->curr_y << endl;
129. // Edge *ele = p->firstNode;
130. // while (ele != NULL) {
131. // cout << "表项中的边： x = " << ele->x << " y_min = " << ele->y_min << " y_max = " << ele->y_max <<
132. // "deltax = " << ele->deltax << endl;
133. // ele = ele->next;
134. // }
135. // p = p->next;
136. // }
137. // yMax++;
138. //}
139.  
140. /////////////////////////
141.  
142. }
143.  
144. //用于根据边数组计算需要多少个表项
145. //表项的个数取决于边的ymin的个数
146. //返回值 ymin 数组
147. //返回 item_num 表项的个数
148. int TableItemCount(Edge *edges, int edge_num, int* ymins)
149. {
150. int count = 0;
151. for (int i = 0; i<edge_num; ++i)
152. {
153. if (!isInArray(ymins, edges[i].y_min, count))
154. {
155. ymins[count++] = edges[i].y_min;
156. }
157. }
158. //将ymin 升序排序
159. for (int j = 0; j<count - 1; ++j)
160. {
161. for (int k = j + 1; k<count; ++k)
162. {
163. if (ymins[k] < ymins[j])
164. {
165. int tmp = ymins[k];
166. ymins[k] = ymins[j];
167. ymins[j] = tmp;
168. }
169. }
170. }
171. return count;
172.  
173. }
174. //判断一个整数是否在整数数组中
175. bool isInArray(int *array, int e, int array_length)
176. {
177. for (int i = 0; i<array_length; ++i)
178. {
179. if (array[i] == e)
180. {
181. return true;
182. }
183. }
184. return false;
185. }
186.  
187. //传入edges数组，初始化，返回Edge 结构体数组
188. //因为需要是封闭图形，所以，在边数组中，最后的点的坐标设为起始点的坐标，传入的edge_num 不变
189. Edge* InitEdges(int *edges, int edge_num)
190. {
191. Edge *newEdges = (Edge*)malloc(sizeof(Edge)*edge_num);
192. int j = 0;
193. for (int i = 0; i<edge_num; ++i)
194. {
195. Point point(edges[2 * i], edges[2 * i + 1], edges[2 * (i + 1)], edges[2 * (i + 1) + 1]);
196. Edge *newEdge = (Edge*)malloc(sizeof(Edge));
197. newEdge->x = (double)point.x();
198. newEdge->y_max = point.YMax();
199. newEdge->y_min = point.YMin();
200. newEdge->deltax = 1.0 / point.KOfLine(); // 斜率分之一
201. newEdge->next = NULL;
202. newEdges[j++] = *(newEdge);
203. }
204. return newEdges;
205. }
206. //删除所有的小于ymax 的节点
207. //参数 curr_ymax 当前扫描线的y值
208. void DeleteNode(ET &T, int curr_ymax)
209. {
210. TableItem *p = T.itemHeader; //指向表项的指针
211. while (p != NULL) {
212. Edge *item = p->firstNode; //指向表项的邻接链表的指针
213. Edge *itempre = p->firstNode; //指向前一个边结点的指针
214. while (item != NULL) {
215. if (item->y_max <= curr_ymax) { //删除该结点
216. T.item_count--; //当前活动边表中的边的个数-1
217. //判断该结点是否是该链表的头结点
218. if (item == p->firstNode) {
219. p->firstNode = (Edge*)malloc(sizeof(Edge));
220. p->firstNode = item->next;
221. free(item); //释放该结点
222. item = p->firstNode; //重新指向firstnode结点
223. itempre = p->firstNode;
224. }
225. else {
226. itempre->next = item->next; //修改前一个结点的next的值
227. free(item); //删除该指针
228. item = itempre->next; //继续向后遍历
229. }
230. }//if (item->y_max < curr_ymax)
231. else {
232. itempre = item;
233. item = item->next;
234. }
235. }//while (item != NULL)
236. p = p->next;
237. }//while (p != NULL)
238.  
239. }
240.  
241. //将指定y值的节点添加到该表项, 该方法插入的顺序取决于调用该方法传入参数的顺序
242. //该方法将新节点插入到对应表项的邻接链表的末尾
243. void AppendNode(ET &T, int place_y, Edge &e)
244. {
245. ////////测试区//////////
246. //cout << "In Append , place_y = " << place_y << " e.ymin = " << e.y_min << endl;
247. //cout << "item count" << T.item_count << endl;
248.  
249. ///////////////////////
250. TableItem *p = T.itemHeader; //指向活动边表的头结点
251. //将边e插入到对应的表项
252. //之后在该表项中按照x的大小确定插入的位置
253. for (int i = 0; i < T.item_count; ++i) {
254. if (p->curr_y == e.y_min)
255. break;
256. p = p->next;
257. }
258. //将边插入到该表项的邻接链表中
259. Edge *egp = p->firstNode; //egp 指向该表项的首个邻接节点
260. if (egp == NULL) { //如果该表项还没有节点，直接插入
261. egp = (Edge*)malloc(sizeof(Edge));
262. *(egp) = e;
263. egp->next = NULL;
264. p->firstNode = egp;
265. }
266. else {
267. Edge *pre = egp;
268. while (egp != NULL) {
269. pre = egp;
270. egp = egp->next;
271. }
272. Edge *newedge = (Edge*)malloc(sizeof(Edge));
273. *(newedge) = e;
274. pre->next = newedge;
275. newedge->next = NULL;
276. }
277.  
278. }
279.  
280. //绘图的方法
281. void Draw(ET T) {
282. //首先取出ymin 值小于当前扫描线y 的边
283. //按照顺序配对
284. int curr_y = 0, curr_edge_num = 0, curr_gy = graphy(curr_y); //图形坐标的扫描线的y坐标
285. Edge *currEdges = (Edge*)malloc(sizeof(Edge) * 20); //用于存放指针的数组
286. //将每条边的记录的x 化为图形上的坐标
287. TableItem *p = T.itemHeader;
288. while (p != NULL) {
289. Edge *q = p->firstNode;
290. while (q != NULL) {
291. q->x = graphx(q->x);
292. q = q->next;
293. }
294. p = p->next;
295. }
296.  
297. for (; curr_y < 30; curr_gy--, curr_y = realy(curr_gy)) {
298. this->DeleteNode(T, curr_y); //删除当前扫描过的边（ymax 小于 curr_y）
299. currEdges = this->GetCurrEdges(T, curr_y, curr_edge_num); //获取当前与扫描线相交的边
300. //对获取到的边进行排序、配对
301. for (int i = 0; i < curr_edge_num - 1; ++i) {
302. for (int j = i + 1; j < curr_edge_num; ++j) {
303. if (this->IsRightTo(currEdges[i], currEdges[j])) {
304. Edge tmp = currEdges[i];
305. currEdges[i] = currEdges[j];
306. currEdges[j] = tmp;
307. }
308. }
309.  
310. }
311.  
312. ////
313. // getchar();
314. // cout << "------------------------------" << endl;
315.  
316. setcolor(BLUE);
317. for (int j = 0; j < curr_edge_num / 2; ++j) {
318.  
319. ///
320.  
321. // cout << "line :" << (int)currEdges[2 * j].x << " , " << curr_y << "----->" << (int)currEdges[2 * j + 1].x << " , " << curr_y <<
322. // " edge_num = " << curr_edge_num << endl;
323.  
324. line((int)currEdges[2 * j].x, curr_gy, (int)currEdges[2 * j + 1].x, curr_gy);
325. Edge *curr_edge1 = this->GetThisEdge(T, currEdges[2 * j].x, currEdges[2 * j].y_min,
326. currEdges[2 * j].y_max); //获取当前边的指针，修改x值，保存修改
327. curr_edge1->x += curr_edge1->deltax;
328. Edge *curr_edge2 = this->GetThisEdge(T, currEdges[2 * j + 1].x, currEdges[2 * j + 1].y_min,
329. currEdges[2 * j + 1].y_max);
330. curr_edge2->x += curr_edge2->deltax;
331.  
332. //line((int)currEdges[2 * j].x, curr_gy, (int)currEdges[2 * j + 1].x, curr_gy); //在两条直线之间划线
333. //currEdges[2 * j].x += currEdges[2 * j].deltax;
334. //currEdges[2 * j + 1].x += currEdges[2 * j + 1].deltax; //更新x 的坐标值
335. }
336.  
337. //////////测试模拟输出划线///////////////
338. /*cout << "------------------------------------------" << endl;
339. cout << "curr_y = " << curr_y << endl;
340. cout << "当前扫描的边的个数 = " << curr_edge_num << endl;
341. for (int i = 0; i < curr_edge_num / 2; ++i) {
342. cout << "draw line bwtwen :" << endl;
343. cout << "直线1 x = " << currEdges[2 * i].x << " ymin = " << currEdges[2 * i].y_min <<
344. " ymax = " << currEdges[2 * i].y_max << endl;
345. cout << "直线2 x = " << currEdges[2 * i + 1].x << " ymin = " << currEdges[2 * i + 1].y_min <<
346. " ymax = " << currEdges[2 * i + 1].y_max << endl;
347.  
348. }*/
349.  
350. ////////////////////////////////////
351. //在1,2 3,4 ... 边之间划线
352. //TODO 坐标转换以及划线
353.  
354. }
355.  
356. ///////测试区/////////////////
357. //cout << "-------------------------------------" << endl;
358. //cout << "当前取出的边。。。。。。。。。。" << endl;
359. //cout << "curr_edge_num = " << curr_edge_num << endl;
360. //for (int i = 0; i < curr_edge_num; ++i) {
361. // cout << "x = " << currEdges[i].x << " y_min = " << currEdges[i].y_min << " y_max = " << currEdges[i].y_max << endl;
362. //}
363.  
364. ////////////////////////////////
365.  
366. }
367.  
368. //返回某个边的指针
369. //可通过此指针修改原结构体中边的x的值
370. Edge* GetThisEdge(ET T, double x, int y_min, int y_max) {
371. TableItem *p = T.itemHeader;
372. while (p != NULL) {
373. Edge *q = p->firstNode;
374. while (q != NULL) {
375. if ((q->x == x) && (q->y_max == y_max) && (q->y_min == y_min)) {
376. return q;
377. }
378. q = q->next;
379. }
380. p = p->next;
381. }
382.  
383. return NULL;
384. }
385.  
386. //用于坐标转换的函数
387. double graphx(double x) {
388. return x * 10 + 100;
389. }
390.  
391. double realx(double gx) {
392. return (gx - 100)*1.0 / 10;
393. }
394.  
395. int graphy(int y) {
396. return 400 - y * 10;
397. }
398.  
399. int realy(int gy) {
400. return (400 - gy) / 10;
401. }
402.  
403. //绘制坐标系
404. void DrawCoordinate(int edges[], int edge_num) {
405. line(100, 100, 100, 400);
406. line(100, 400, 400, 400);
407. outtextxy(85, 95, "y↑");
408. outtextxy(400, 393, "→x");
409.  
410. for (int i = 0; i < 30; ++i) {
411. if (i % 2 != 0)
412. continue;
413. //TODO 字符转换
414. outtextxy(i * 10 + 100, 390, "|");
415. char *text = (char*)malloc(sizeof(char) * 10);
416. itoa(i,text,10);
417. outtextxy(i * 10 + 100, 410, text);
418. free(text);
419. }
420.  
421. for (int j = 0; j < 30; ++j) {
422. if (j % 2 != 0)
423. continue;
424. outtextxy(100, 400 - j * 10, "_");
425. char *str = (char*)malloc(sizeof(char)*10);
426. itoa(j,str,10);
427. outtextxy(100, 400 - j * 10,str);
428. free(str);
429. }
430.  
431. //绘制原多边形
432. for (int k = 0; k < edge_num; ++k) {
433. setcolor(YELLOW);
434. int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
435. x1 = edges[2 * k] * 10 + 100;
436. y1 = 400 - edges[2 * k + 1] * 10;
437. x2 = edges[2 * (k + 1)] * 10 + 100;
438. y2 = 400 - edges[2 * (k + 1) + 1] * 10;
439. line(x1, y1, x2, y2);
440. }
441.  
442. }
443.  
444. //获取当前的涉及的扫描线的边
445. //即取出当前ymin 小于curr_y的边
446. //通过参数返回取出的边的个数
447. Edge* GetCurrEdges(ET T, int curr_y, int &edge_num) {
448. Edge *currEdges = (Edge*)malloc(sizeof(Edge) * 20); //分配最大容量
449. int i = 0;
450. TableItem *p = T.itemHeader;
451. while (p != NULL) {
452. Edge *q = p->firstNode;
453. while (q != NULL) {
454. if (q->y_min <= curr_y) { //等于号很重要，否则会在图形中出现空白区
455. currEdges[i++] = *q; //将当前边的值取出（不改变原活动表）
456. }
457. q = q->next;
458. }
459. p = p->next;
460. }
461. edge_num = i; //保存取出的边的个数
462. return currEdges;
463. }
464.  
465. //判断edge1 是否在edge2 的右边的方法
466. bool IsRightTo(Edge edge1, Edge edge2) {
467. if (edge1.x > edge2.x) //如果edge1最低点的x坐标小于edge2的最低点的x的坐标，则edge1在edge2的右边
468. return true;
469. else {
470. if (edge1.x < edge2.x)
471. return false;
472. double x_max1 = (edge1.y_max - (edge1.y_min - 1.0 / edge1.deltax*edge1.x))*edge1.deltax;
473. double x_max2 = (edge2.y_max - (edge2.y_min - 1.0 / edge2.deltax*edge2.x))*edge2.deltax;
474. if (x_max1 > x_max2)
475. return true;
476. }
477. return false;
478. }
479.  
480. };
481.  
482. int main()
483. {
484. //TODO 测试活动边表初始化
485. Solution solution;
486. int edges[] = { 4,18,14,14,26,22,26,10,14,2,4,6,4,18 };
487. Edge* newEdges = solution.InitEdges(edges, 6);
488. ET T;
489. solution.Init(T, newEdges, 6); //初始化活动边表
490.  
491. initgraph(800, 800, SHOWCONSOLE);
492. solution.DrawCoordinate(edges, 6);
493. solution.Draw(T);
494. getchar();
495. closegraph();
496. return 0;
497. }

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

原文链接：https://blog.csdn.net/qq_36573282/article/details/78633319