填充算法

种子填充：

 1 #include <GL/glut.h>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<stack>
 5 using namespace std;
 6 
 7 int v[1000][1000];
 8 
 9 
10 
11 void init()
12 {
13     glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE);                
14     glutInitWindowPosition(100, 100);                          
15     glutInitWindowSize(400, 300);                               
16     glutCreateWindow("种子填充");                           
17 
18     glClearColor(0.0, 0.0, 0.0, 0.0);
19     glMatrixMode(GL_PROJECTION);
20     gluOrtho2D(0, 1000, 0, 1000); 
21 
22     glRectf(-0.5f, -0.5f, 0.5f, 0.5f); 
23     glClear(GL_COLOR_BUFFER_BIT);
24       
25     memset(v,0,sizeof(v));
26 }
27 
28 void setPixel (GLint x,GLint y)               
29 {
30     glBegin(GL_POINTS);
31        glVertex2i(x, y);
32     glEnd();
33 }
34 
35 void dfs(int x,int y)
36 {
37     if (x<350||x>450||y<350||y>450) return ;
38     if (v[x][y]) return ;
39     v[x][y]=1;
40     dfs(x+1,y);
41     dfs(x-1,y);
42     dfs(x,y+1);
43     dfs(x,y-1);
44     setPixel(x,y);
45     
46 }
47 
48 void myDisplay(void)                                             
49 { 
50    glColor3f(1.0, 0.0, 0.0);
51    glBegin(GL_LINE_LOOP);
52        glVertex2f(350,350);
53        glVertex2f(450,350);
54        glVertex2f(450,450);
55        glVertex2f(350,450);
56    glEnd();
57    glFlush();
58    
59    glColor3f(0.0, 1.0, 0.0);
60    dfs(400,400);
61    glFlush(); 
62                                                      
63  }
64 
65  int main(int argc, char *argv[])
66  {
67      glutInit(&argc, argv);
68      init();                                                    
69      glutDisplayFunc(&myDisplay);                                                  
70      glutMainLoop();                                           
71      return 0; 
72  }

View Code

  1 /*************************************************************
  2      pb-????4
  3      ??????
  4 
  5 *************************************************************/
  6 
  7 
  8 #include <GL/glut.h>
  9 #include<cstdio>
 10 #include<cmath>
 11 #include<stack>
 12 using namespace std;
 13 
 14 int x,y,endx,endy,p;
 15 int v[3000][3000];
 16 
 17 struct ST
 18 {
 19     int x,y;
 20 };
 21 ST st[100];
 22 int len=0;
 23 ST f,r;
 24 stack<ST>s;
 25 int yi[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
 26 
 27 void init()
 28 {
 29     glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE);                 //????????,????????,??????
 30     glutInitWindowPosition(100, 100);                            //???????
 31     glutInitWindowSize(400, 300);                                //??????
 32     glutCreateWindow("pb-????4");                            //?????
 33 
 34     glClearColor(0.0, 0.0, 0.0, 0.0);
 35     glMatrixMode(GL_PROJECTION);
 36     gluOrtho2D(-1000, 1000, -1000, 1000); 
 37 
 38     glRectf(-0.5f, -0.5f, 0.5f, 0.5f); 
 39     glClear(GL_COLOR_BUFFER_BIT);
 40     glColor3f(1.0, 0.0, 0.0); 
 41     
 42     
 43     memset(v,0,sizeof(v));
 44     while (!s.empty()) s.pop();
 45 }
 46 
 47 
 48 void setPixel (GLint x,GLint y)               //????,???x,y?nx,ny???????
 49 {
 50     glBegin(GL_POINTS);
 51        glVertex2i(x, y);
 52     glEnd();
 53 }
 54 
 55 //?????
 56 void swap(int &x,int &y)
 57 {
 58     x^=y;
 59     y^=x;
 60     x^=y;
 61 }
 62 
 63 
 64 //?k???,p=1?? 0<k<1; p=2?? k>1; p=3 ?? -1<k<0; p=4?? k<-1;
 65 //?????????0<k<1?
 66 void Spoint()
 67 {
 68    if ((endx-x)*(endy-y)>0)
 69     {
 70         if (abs(endx-x)-abs(endy-y)>=0) p=1;
 71         else 
 72         {
 73             p=2;
 74             swap(x,y);
 75             swap(endx,endy);
 76         }
 77     }
 78     else
 79     {
 80            if (abs(endx-x)-abs(endy-y)>=0) 
 81            {
 82                p=3;
 83                y=-y;
 84                endy=-endy;
 85            }
 86            else 
 87            {
 88                p=4;
 89                x=-x;
 90                endx=-endx;
 91                swap(x,y);
 92                swap(endx,endy);
 93            }
 94     }
 95 }
 96 
 97 
 98 
 99 
100 void setpoint(int x0,int y0)
101 {
102     if (p==1)  
103     {
104         v[x0+1001][y0+1001]=1;
105     //    setPixel(x0,y0);
106     }
107     if (p==2)  
108     {
109         
110         v[y0+1001][x0+1001]=1;
111     //    setPixel(y0,x0);
112     }
113     if (p==3)  
114     {
115     
116         v[x0+1001][-y0+1001]=1;
117     //    setPixel(x0,-y0);
118     }
119     if (p==4)  
120     {
121     
122         v[-y0+1001][x0+1001]=1;
123     //    setPixel(-y0,x0);
124     }
125 }
126 
127 //Bresenham???
128 void myDisplay(void)                                             
129 { 
130     x=st[len-2].x;
131     y=st[len-2].y;
132     int i;
133     for (i=0;i<len-1;i++)
134     {
135         endx=st[i].x;
136         endy=st[i].y;
137         Spoint();
138         int dx=abs(x-endx),dy=abs(y-endy);
139         int d=2*dy-dx;
140         int tdy=2*dy,tdx=2*(dy-dx);
141         
142         if (x>endx)
143         {
144            swap(x,endx);
145            swap(y,endy);
146         }
147         x-=40;
148         v[x+1001][y+1001]=1;
149         
150         while (x<endx+40)
151         {
152             x++;
153             if (d<0)
154             {
155                 d+=tdy;
156             }
157             else
158             {
159               y++;
160              d+=tdx;
161             }
162           setpoint(x,y);
163          
164         }
165         x=st[i].x;
166         y=st[i].y;
167     }
168  glFlush();
169     f.x=0;
170     f.y=0;
171     s.push(f);
172 
173     while (!s.empty())
174     {
175         r=s.top();
176         s.pop();
177         setPixel(r.x,r.y);
178         for (i=0;i<4;i++)
179         {
180             f.x=r.x+yi[i][0];
181             f.y=r.y+yi[i][1];
182             if (f.x<=-1000||f.x>=1000) continue;
183             if (f.y<=-1000||f.y>=1000) continue;
184             if (v[f.x+1001][f.y+1001]) continue;
185             v[f.x+1001][f.y+1001]=1;
186             s.push(f);
187         }
188     }
189      glFlush();
190                                                      
191  }
192 
193 
194 
195  int main(int argc, char *argv[])
196  {
197      glutInit(&argc, argv);
198 
199      printf("请输入多边形顶点坐标，坐标（0，0）必须在多边形内：
");
200      while (~scanf("%d%d",&st[len].x,&st[len++].y));
201 
202      init();                                                     //?????
203      glutDisplayFunc(&myDisplay);                                //????                    
204      glutMainLoop();                                             //????
205      return 0; 
206  }

View Code

扫描线填充：

  1 #include <GL/glut.h>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<stack>
  5 #include<algorithm>
  6 #include<iostream>
  7 using namespace std;
  8 
  9 int x,y,endx,endy,p;
 10 int v[3000][3000];
 11 
 12 struct ST
 13 {
 14     int x,y;
 15 };
 16 ST st[100];
 17 ST str[100000];
 18 int len=0,k=0;
 19 ST f,r;
 20 stack<ST>s;
 21 bool com(ST a,ST b)
 22 {
 23     if (a.y==b.y) return a.x<b.x;
 24     return a.y<b.y;
 25 }
 26 
 27 void init()
 28 {
 29     glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE);                 //????????,????????,??????
 30     glutInitWindowPosition(100, 100);                            //???????
 31     glutInitWindowSize(400, 300);                                //??????
 32     glutCreateWindow("pb-????4");                            //?????
 33 
 34     glClearColor(0.0, 0.0, 0.0, 0.0);
 35     glMatrixMode(GL_PROJECTION);
 36     gluOrtho2D(-1000, 1000, -1000, 1000); 
 37 
 38     glRectf(-0.5f, -0.5f, 0.5f, 0.5f); 
 39     glClear(GL_COLOR_BUFFER_BIT);
 40     glColor3f(1.0, 0.0, 0.0); 
 41     
 42     
 43     memset(v,0,sizeof(v));
 44     while (!s.empty()) s.pop();
 45 }
 46 
 47 
 48 void setPixel (GLint x,GLint y,GLint nx,GLint ny)               //????,???x,y?nx,ny???????
 49 {
 50     glBegin(GL_LINES);
 51        glVertex2i(x, y);
 52        glVertex2i(nx,ny);
 53     glEnd();
 54 }
 55 
 56 //?????
 57 void swap(int &x,int &y)
 58 {
 59     x^=y;
 60     y^=x;
 61     x^=y;
 62 }
 63 
 64 
 65 //?k???,p=1?? 0<k<1; p=2?? k>1; p=3 ?? -1<k<0; p=4?? k<-1;
 66 //?????????0<k<1?
 67 void Spoint()
 68 {
 69    if ((endx-x)*(endy-y)>0)
 70     {
 71         if (abs(endx-x)-abs(endy-y)>=0) p=1;
 72         else 
 73         {
 74             p=2;
 75             swap(x,y);
 76             swap(endx,endy);
 77         }
 78     }
 79     else
 80     {
 81            if (abs(endx-x)-abs(endy-y)>=0) 
 82            {
 83                p=3;
 84                y=-y;
 85                endy=-endy;
 86            }
 87            else 
 88            {
 89                p=4;
 90                x=-x;
 91                endx=-endx;
 92                swap(x,y);
 93                swap(endx,endy);
 94            }
 95     }
 96 }
 97 
 98 
 99 
100 
101 void setpoint(int x0,int y0)
102 {
103     if (p==1)  
104     {
105         str[k].x=x0;
106         str[k++].y=y0;
107     }
108     if (p==2)  
109     {
110         str[k].x=y0;
111         str[k++].y=x0;
112     }
113     if (p==3)  
114     {
115           str[k].x=x0;
116           str[k++].y=-y0;
117     }
118     if (p==4)  
119     {
120 
121           str[k].x=-y0;
122           str[k++].y=x0;
123     }
124 }
125 
126 //Bresenham???
127 void myDisplay(void)                                             
128 { 
129     x=st[len-2].x;
130     y=st[len-2].y;
131     int i;
132     for (i=0;i<len-1;i++)
133     {
134         endx=st[i].x;
135         endy=st[i].y;
136         Spoint();
137         int dx=abs(x-endx),dy=abs(y-endy);
138         int d=2*dy-dx;
139         int tdy=2*dy,tdx=2*(dy-dx);
140         
141         if (x>endx)
142         {
143            swap(x,endx);
144            swap(y,endy);
145         }
146         v[x+1001][y+1001]=1;
147         str[k].x=x;
148         str[k++].y=y;
149         while (x<endx)
150         {
151             x++;
152             if (d<0)
153             {
154                 d+=tdy;
155             }
156             else
157             {
158               y++;
159              d+=tdx;
160             }
161           setpoint(x,y);
162          
163         }
164         x=st[i].x;
165         y=st[i].y;
166     }
167 
168     sort(str,str+k,com);
169 
170     for (i=0;i<k-1;i++)
171     {
172         if (str[i].y==str[i+1].y&&str[i].x!=str[i+1].x-1)
173         {
174              setPixel(str[i].x,str[i].y,str[i+1].x,str[i+1].y);
175              i++;
176         }
177     }
178     
179      glFlush();
180                                                      
181  }
182 
183 
184 
185  int main(int argc, char *argv[])
186  {
187      glutInit(&argc, argv);
188      while (~scanf("%d%d",&st[len].x,&st[len++].y));
189 
190      init();                                                    
191      glutDisplayFunc(&myDisplay);                                                
192      glutMainLoop();                                            
193      return 0; 
194  }

View Code