[OpenGL] 不规则区域的填充算法

不规则区域的填充算法

一、简单递归

利用Dfs实现简单递归填充。
核心代码：

 1 // 简单深度搜索填充 （四连通）
 2 void DfsFill(int x, int y)
 3 {
 4     if (x < 0 || y < 0 || x>23 || y>23)
 5     {
 6         return;
 7     }
 8     if (a[x][y] == 0)
 9     {
10         a[x][y] = 2;
11         DfsFill(x - 1, y);
12         DfsFill(x + 1, y);
13         DfsFill(x, y - 1);
14         DfsFill(x, y + 1);
15     }
16 }

二、扫描线种子填充算法（四连通）

1. 种子点（x,y）入栈。 
2. 栈顶元素（x,y）出栈作为种子点。
3. 从种子点（x,y）开始沿着扫描线向左右两个方向逐个像素进行填充，直到到达边界像素为止。
4. 将上述填充区段的左右端点的横坐标分别记为xleft和xright.
5. 在与当前扫描线相邻的上下两条扫描线的[xleft，xright]范围内进行检查，
看看是否全部为边界像素或已填充像素，若存在着非边界且未填充的像素，那么将该区段的最右端像素作为种子点入栈。

在这里插入图片描述

 1 // 扫描线种子填充算法（四连通）
 2 void ScanFill(int x, int y)
 3 {
 4     if (a[x][y]!=0)
 5     {
 6         return;
 7     }
 8     Pos first(x, y);
 9     s.push(first);
10     while (!s.empty())
11     {
12         int rightX = 0;
13         int leftX = 0;
14         Pos cur = s.top();
15         s.pop();
16         a[cur.x][cur.y] = 2;
17         // 遍历当前行
18         for (int i = 1; i < 24; i++)
19         {
20             if (cur.x + i < 24)
21             {
22                 if (a[cur.x + i][cur.y] == 0)
23                     a[cur.x + i][cur.y] = 2;
24                 else
25                 {
26                     rightX = cur.x + i - 1;
27                     break;
28                 }
29             }
30             else
31             {
32                 rightX = 23;
33             }
34         }
35         for (int i = 1; i < 24; i++)
36         {
37             if (cur.x - i > -1) 
38             {
39                 if (a[cur.x - i][cur.y] == 0)
40                     a[cur.x - i][cur.y] = 2;
41                 else
42                 {
43                     leftX = cur.x - i + 1;
44                     break;
45                 }
46             }
47             else
48             {
49                 leftX = 0;
50             }
51         }
52 
53         cout << leftX <<","<<rightX << endl;
54 
55         // 判断上行
56         int upRightX = -1;
57         for (int i = leftX;i<=rightX;i++)
58         {
59             upRightX = -1;
60             if (a[i][cur.y+1]==0 && cur.y+1<24)
61             {
62                 upRightX = i;
63             }
64             if (upRightX != -1)
65             {
66                 Pos temPos(upRightX, cur.y + 1);
67                 s.push(temPos);
68             }
69         }
70 
71         // 判断下行
72         int downRightX = -1;
73         for (int i = leftX; i <= rightX; i++)
74         {
75             downRightX = -1;
76             if (a[i][cur.y - 1] == 0 && cur.y - 1 >=0)
77             {
78                 downRightX = i;
79             }
80             if (downRightX != -1)
81             {
82                 Pos temPos(downRightX, cur.y - 1);
83                 s.push(temPos);
84             }
85         }
86 
87     }
88 }

完整代码：

  1 #include <cmath>
  2 #include <stack>
  3 #include "gl/glut.h"
  4 #include "iostream"
  5 using namespace std;
  6 
  7 #define PI 3.14
  8 
  9 struct Pos
 10 {
 11     int x;
 12     int y;
 13     Pos(int mx, int my) :x(mx), y(my) {};
 14     Pos() :x(0), y(0) {};
 15 };
 16 
 17 stack<Pos> s;
 18 int a[24][24] = { 0 };
 19 
 20 void init(void)
 21 {
 22     glClearColor(1.0, 1.0, 1.0, 1.0);
 23     glMatrixMode(GL_PROJECTION);//设置投影矩阵
 24     gluOrtho2D(0.0, 600.0, 0.0, 600.0);//二维视景区域
 25     glPointSize(12.0f);
 26 }
 27 // 画棋子
 28 void Drawtri(int x,int y,int color)
 29 {
 30     double n = 200;//分段数
 31     float R = 10;//半径
 32     int i;
 33     if (color == 1)
 34     {
 35         glColor3f(1.0, 0.0, 0.0);
 36     }
 37     else if (color == 2)
 38     {
 39         glColor3f(0.0, 1.0, 0.0);
 40     }
 41     glBegin(GL_POLYGON);
 42     glVertex2f(x, y);
 43     for (i = 0; i <= n; i++)
 44         glVertex2f(R*cos(2 * PI / n * i)+x, R*sin(2 * PI / n * i)+y);
 45     glEnd();
 46     glPopMatrix();
 47 }
 48 
 49 // 绘制格线
 50 void playMap()
 51 {
 52     glColor3f(0.0, 0.0, 0.0);
 53     glBegin(GL_LINES);
 54     for (int i = 0; i < 600; i += 25)
 55     {
 56         glVertex2f(i, 0);
 57         glVertex2f(i, 600);
 58     }
 59     for (int j = 0; j < 600; j += 25)
 60     {
 61         glVertex2f(0, j);
 62         glVertex2f(600, j);
 63     }
 64     glEnd();
 65     for (int k = 0; k < 24; k++)
 66     {
 67         for (int l = 0; l < 24; l++)
 68         {
 69             if (a[k][l] == 1)
 70             {
 71                 Drawtri(k * 25 + 12, l * 25 + 12,1);
 72             }
 73             else if (a[k][l] == 2)
 74             {
 75                 Drawtri(k * 25 + 12, l * 25 + 12, 2);
 76             }
 77         }
 78     }
 79 }
 80 
 81 // 简单深度搜索填充 （四连通）
 82 void DfsFill(int x, int y)
 83 {
 84     if (x < 0 || y < 0 || x>23 || y>23)
 85     {
 86         return;
 87     }
 88     if (a[x][y] == 0)
 89     {
 90         a[x][y] = 2;
 91         DfsFill(x - 1, y);
 92         DfsFill(x + 1, y);
 93         DfsFill(x, y - 1);
 94         DfsFill(x, y + 1);
 95     }
 96 }
 97 
 98 // 扫描线种子填充算法（四连通）
 99 void ScanFill(int x, int y)
100 {
101     if (a[x][y]!=0)
102     {
103         return;
104     }
105     Pos first(x, y);
106     s.push(first);
107     while (!s.empty())
108     {
109         int rightX = 0;
110         int leftX = 0;
111         Pos cur = s.top();
112         s.pop();
113         a[cur.x][cur.y] = 2;
114         // 遍历当前行
115         for (int i = 1; i < 24; i++)
116         {
117             if (cur.x + i < 24)
118             {
119                 if (a[cur.x + i][cur.y] == 0)
120                     a[cur.x + i][cur.y] = 2;
121                 else
122                 {
123                     rightX = cur.x + i - 1;
124                     break;
125                 }
126             }
127             else
128             {
129                 rightX = 23;
130             }
131         }
132         for (int i = 1; i < 24; i++)
133         {
134             if (cur.x - i > -1) 
135             {
136                 if (a[cur.x - i][cur.y] == 0)
137                     a[cur.x - i][cur.y] = 2;
138                 else
139                 {
140                     leftX = cur.x - i + 1;
141                     break;
142                 }
143             }
144             else
145             {
146                 leftX = 0;
147             }
148         }
149 
150         cout << leftX <<","<<rightX << endl;
151 
152         // 判断上行
153         int upRightX = -1;
154         for (int i = leftX;i<=rightX;i++)
155         {
156             upRightX = -1;
157             if (a[i][cur.y+1]==0 && cur.y+1<24)
158             {
159                 upRightX = i;
160             }
161             if (upRightX != -1)
162             {
163                 Pos temPos(upRightX, cur.y + 1);
164                 s.push(temPos);
165             }
166         }
167 
168         // 判断下行
169         int downRightX = -1;
170         for (int i = leftX; i <= rightX; i++)
171         {
172             downRightX = -1;
173             if (a[i][cur.y - 1] == 0 && cur.y - 1 >=0)
174             {
175                 downRightX = i;
176             }
177             if (downRightX != -1)
178             {
179                 Pos temPos(downRightX, cur.y - 1);
180                 s.push(temPos);
181             }
182         }
183 
184     }
185 }
186 
187 void displayFcn(void)
188 {
189     glClear(GL_COLOR_BUFFER_BIT);
190     playMap();
191     glFlush();
192 }
193 
194 
195 void mouse(GLint button, GLint action, GLint x, GLint y)
196 {
197     int curX, curY;
198     if (button == GLUT_LEFT_BUTTON && action == GLUT_DOWN)
199     {
200         curX = x / 25;
201         curY = (600 - y) / 25;
202         a[curX][curY] = 1;
203         glutPostRedisplay();//重绘窗口
204     }
205     if (button == GLUT_RIGHT_BUTTON && action == GLUT_DOWN)
206     {
207         curX = x / 25;
208         curY = (600 - y) / 25;
209         ScanFill(curX, curY);
210         
211         glutPostRedisplay();//重绘窗口
212     }
213 }
214 
215 
216 void main(int argc, char** argv)
217 {
218     glutInit(&argc, argv);
219     glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
220     glutInitWindowPosition(300, 100);
221     glutInitWindowSize(600, 600);
222     glutCreateWindow("mouse");
223 
224     init();
225     glutDisplayFunc(displayFcn);
226 
227     glutMouseFunc(mouse);
228 
229     glutMainLoop();
230 
231 }