今天yogurt想要和大家分享一个大家在玩电脑时经常会用到的一个功能“窗口裁剪”的C语言编程实现方法~~相信用过QQ截屏或者其他截屏软件的盆友都知道截屏就是对一个图形或者图案用一个矩形框或者圆形框框起来，只保留框内的内容，而框外的内容自动舍去。那么它是怎么实现的呢？今天就让美丽可爱善良机智的yogurt来告诉你这个神奇的东东吧！

===================================yogurt小课堂开课啦===================================

首先讲一下程序中用到的算法--Cohen-Sutherland端点编码算法。我们的每一个点在存储时除了要存储它的xy坐标，还要存储一个编码key，编码key由四个0/1的数字组成，0表示在窗口某边内，1表示在窗口某边外，如key=0101,表示该点在窗口左边界和下边界之外，如下图：

然后对待截取的直线，进行判断，若直线在窗口内（直线两端点的key都是0000）则简取，若直线两端点都在窗口外的同一侧（两个端点的key有同一位都是1）则简弃，对于其他情况（直线穿过窗口、直线未穿过窗口但是跨越三个界域）则进行较为复杂的判断，但是每次判断之前必须确保第一个点p1在窗口外，以便计算交点。得到交点之后用交点替代p1，继续重复进行待截取直线的判断，直到可以简取或者简弃为止。

至于复杂多边形的裁剪，我们要考虑到由p1到p2是由外-->内，or由外-->外，or由内-->内，or由内-->外四种情况，每种情况对于点的处理是不同的。（以下是yogurt自己想到的算法，恩，就叫它“标记数判断法”吧O(∩_∩)O~）

我们用a来进行特殊判断，当多边形某条边由内-->外时，记a为1。若是外-->外，就将a++，且判断若a==3，则证明该点的相邻两条边都在窗口外面（都是外-->外），则该点是舍去的且没有替代此点位置的点,将a重新置为2（代表这条线是外-->外，方便下一条线进行判断）。若是外-->内，判断若a==1，证明上一条边正好是从内-->外，则相对于被裁剪多边形来说，窗口内增加一个端点，然后把a置为0。如下图：

====================================好，同学们，下课啦===================================

接下来是Yogurt的个人炫技时间(*^__^*) 嘻嘻……

首先我们看看简单的线段在窗口内的裁剪，上代码：

  1 // caijian.cpp : 定义控制台应用程序的入口点。
  2 //
  4 #include "stdafx.h"
  5 #include"Graph.h"
  7 typedef struct Key
  9     int d3;
 10     int d2;
 11     int d1;
 12     int d0;
 13 }key;
 15 typedef struct Point
 16 {
 17     int x;
 18     int y;
 19     key c;
 20 }point;
 22 key code(point p, int xw1, int xwr, int ywb, int ywt);
 23 point asso(point p1, point p2,int xw1, int xwr, int ywb, int ywt);
 24 void drawline(point p1, point p2);
 26 int _tmain(int argc, _TCHAR* argv[])
 27 {
 28     point p1, p2;
 29     int xmin , xmax , ymin , ymax ;
 31     //printf("Please enter point one:");
 32     //scanf("%d,%d", &p1.x, &p1.y);
 34     //printf("Please enter point two:");
 35     //scanf("%d,%d", &p2.x, &p2.y);
 36     //
 37     //printf("Please enter the four boundary(xmin,xmax,ymin,ymax):");
 38     //scanf("%d,%d,%d,%d", &xmin, &xmax, &ymin, &ymax);
 41     /*测试数据*/
 42     p1.x = 3;
 43     p1.y = 10;
 44     p2.x = 100;
 45     p2.y = 120;
 46     xmin = 50;
 47     xmax = 150;
 48     ymin = 0;
 49     ymax = 180;
 52     setPenColor(RED);
 53     drawline(p1, p2);
 55     int x0 = int((xmin + xmax) / 2);
 56     int y0 = int((ymin + ymax) / 2);
 57     drawRectangle(x0,y0,xmax-xmin,ymax-ymin);
 59     p1.c = code(p1, xmin, xmax, ymin, ymax);
 60     p2.c = code(p2, xmin, xmax, ymin, ymax);
 62     while (1)
 63     {
 64         if (((p1.c.d0 | p2.c.d0 )== 0) && ((p1.c.d1 | p2.c.d1) == 0)&& ((p1.c.d2 | p2.c.d2) == 0 )&&( (p1.c.d3 | p2.c.d3) == 0)) //简取
 65             break;
 66         else if ((p1.c.d0 & p2.c.d0 == 1) || (p1.c.d1 & p2.c.d1 == 1 )|| (p1.c.d2 & p2.c.d2 == 1) || (p1.c.d3 & p2.c.d3 == 1 )) //简弃
 67             return 0;
 68         else
 69         {
 70             //确保p1在窗口外
 71             if ((p1.c.d0 == 0) && (p1.c.d1 == 0) && (p1.c.d2 == 0) && (p1.c.d3 == 0))  //若p1在窗口内
 72             {
 73                 point p3;
 74                 p3 = p1;
 75                 p1 = p2;
 76                 p2 = p3;
 77             }
 79             point s = asso(p1, p2, xmin, xmax, ymin, ymax);  //s为直线段p1p2与窗口的交点
 80             p1 = s;
 81         }
 82     }
 84     setPenColor(GREEN);
 85     drawline(p1, p2);
 86     return 0;
 87 }
 89 key code(point p, int xmin, int xmax, int ymin, int ymax)
 90 {
 91     if (p.x < xmin)
 92         p.c.d0 = 1;
 93     else
 94         p.c.d0 = 0;
 96     if (p.x>xmax)
 97         p.c.d1 = 1;
 98     else
 99         p.c.d1 = 0;
101     if (p.y < ymin)
102         p.c.d2 = 1;
103     else
104         p.c.d2 = 0;
106     if (p.y>ymax)
107         p.c.d3 = 1;
108     else
109         p.c.d3 = 0;
111     return p.c;
112 }
114 point asso(point p1, point p2, int xmin, int xmax, int ymin, int ymax)
115 {
116     double k = (p2.y - p1.y)*1.0 / (p2.x - p1.x);
118     point s;
120     if (p1.c.d0 == 1)//p1在左侧
121     {
122         s.x = xmin;
123         s.y = p1.y + k*(xmin - p1.x);
125         if (s.y > ymax)//s应该在矩形上边界
126         {
127             s.y = ymax;
128             s.x = p1.x + (ymax - p1.y) / k;
129         }
130         else if (s.y < ymin)//s应该在矩形下边界
131         {
132             s.y = ymin;
133             s.x = p1.x + (ymin - p1.y) / k;
134         }
135     }
136     else  if (p1.c.d1 == 1)//p1在右侧
137     {
138         s.x = xmax;
139         s.y = p1.y + k*(xmax - p1.x);
141         if (s.y > ymax)//s应该在矩形上边界
142         {
143             s.y = ymax;
144             s.x = p1.x + (ymax - p1.y) / k;
145         }
146         else if (s.y < ymin)//s应该在矩形下边界
147         {
148             s.y = ymin;
149             s.x = p1.x + (ymin - p1.y) / k;
150         }
151     }
152     else if (p1.c.d2 == 1)//p1在正下侧
153     {
154         s.y = ymin;
155         s.x = p1.x + (ymin - p1.y) / k;
156     }
157     else//p1在正上方
158     {
159         s.y = ymax;
160         s.x = p1.x + (ymax - p1.y) / k;
161     }
162     s.c = code(s, xmin, xmax, ymin, ymax);
164     return s;
165 }
167 void drawline(point p1, point p2)
168 {
169     moveTo(p1.x, p1.y);
170     lineTo(p2.x, p2.y);
171 }

结果如图，为了验证裁剪算法的正确性，我不仅画了模拟窗口，还将待裁剪的线段也画了出来，可看到该线段的红色部分是被裁剪掉的，不在窗口内显示，而黑色部分就是在窗口内显示的部分啦~~

然后你说yogurt这个也太简单了吧！有本事来个复杂的！yogurt傲娇脸，好嘞！客官，我给您上一道大菜！(拭目以待哦~~mua~~)

  1 // 多边形裁剪.cpp : 定义控制台应用程序的入口点。
  2 //
  4 #include "stdafx.h"
  5 #include"Graph.h"
  6 #define MAX_NUM 14
  8 typedef struct Key
 10     int d3;
 11     int d2;
 12     int d1;
 13     int d0;
 14 }key;
 16 typedef struct Vertex
 17 {
 18     int x, y, table;
 19     key code;
 20 }vertex;
 22 typedef struct Graph
 23 {
 24     vertex ver[MAX_NUM+1];
 25     int vexnum;
 26 }graph;//存储的是图形边界点（封闭凸图形）
 28 typedef struct WINDOW
 29 {
 30     int xmin;
 31     int xmax;
 32     int ymin;
 33     int ymax;
 34 }window;
 36 graph readgraphics(char * filename);
 37 void Tocode(vertex *point , window C);
 38 void Totable(vertex *point, window C);   //在可视域范围内为1，否则为0.
 39 graph clip(graph G,window C);
 40 vertex newver(vertex a, vertex b, window C);  
 41 void draw(graph G);
 43 int _tmain(int argc, _TCHAR* argv[])
 44 {
 45     char filename[20] = "Graph.txt";
 46     graph G=readgraphics(filename);
 48     setPenColor(GREEN);
 49     draw(G);
 51     window C;
 52     /*printf("Please enter the four boundary(xmian,xmax,ymin,ymax):");
 53     scanf("%d,%d,%d,%d",&C.xmin,&C.xmax,&C.ymin,&C.ymax);*/
 55     C.xmin = -180;
 56     C.xmax = 180;
 57     C.ymin = -230;
 58     C.ymax = 220;
 60     for (int i = 1; i <= G.vexnum; i++)
 61     {
 62         Tocode(&(G.ver[i]), C);
 63         Totable(&(G.ver[i]), C);
 64     }
 66     setPenColor(RED);
 67     int x0 = int((C.xmin + C.xmax) / 2);
 68     int y0 = int((C.ymin + C.ymax) / 2);
 69     drawRectangle(x0, y0, C.xmax - C.xmin, C.ymax - C.ymin);
 71     graph newG=clip(G,C);
 73     draw(newG);
 75     return 0;
 76 }
 78 graph readgraphics(char * filename)
 79 {
 80     graph G;
 81     FILE * fp = fopen(filename, "r");
 82     if (fp)
 83     {
 84         fscanf(fp, "%d", &G.vexnum);
 86         for (int i = 1; i <= G.vexnum; i++)
 87         {
 88             fscanf(fp,"%d,%d", &G.ver[i].x, &G.ver[i].y);
 89         }
 90     }fclose(fp);
 92     return G;
 93 }
 95 void Tocode(vertex *point, window C)
 96 {
 98     if (point->x < C.xmin)
 99         point->code.d0 = 1;
100     else
101         point->code.d0 = 0;
103     if (point->x>C.xmax)
104         point->code.d1 = 1;
105     else
106         point->code.d1 = 0;
108     if (point->y < C.ymin)
109         point->code.d2 = 1;
110     else
111         point->code.d2 = 0;
113     if (point->y>C.ymax)
114         point->code.d3 = 1;
115     else
116         point->code.d3 = 0;
118 }
120 graph clip(graph G,window C)
121 {
122     graph newG;
123     newG.vexnum = G.vexnum;
125     vertex ver;
127     int a = 0, b = 0;
129     for (int i = 1; i <= G.vexnum - 1; i++)  //从第一个顶点-->下一个顶点，直到第num-1个顶点到第num个顶点为止
130     {
131         if ((G.ver[i].table == 0) && (G.ver[i + 1].table == 1))  //从外到内
132         {
133             if (a == 1) //上次进行的是从内到外，这次外到内，newG相对于G来说增加一个点
134             {
135                 b -= 1;
136                 newG.vexnum++;
137             }
139             a = 0;//将a清零
141             ver = newver(G.ver[i], G.ver[i + 1], C);
142             newG.ver[i + 1 - b] = G.ver[i + 1];
143             newG.ver[i - b] = ver;
144         }
145         else if ((G.ver[i].table == 1) && (G.ver[i + 1].table == 1))  //从内到内
146         {
147             newG.ver[i + 1 - b] = G.ver[i + 1];
148             newG.ver[i - b] = G.ver[i];
149         }
150         else if ((G.ver[i].table == 1) && (G.ver[i + 1].table == 0))  //从内到外
151         {
152             a += 1;
153             ver = newver(G.ver[i], G.ver[i + 1], C);
154             newG.ver[i - b] = G.ver[i];
155             newG.ver[i + 1 - b] = ver;
156         }
157         else  //从外到外
158         {
159             //进入时a为2证明上一次就是从外到外
160             a += 1;
162             if (a == 3)  //与该点相邻的左右两点都在外，则newG相对于G来说没有该点(也没有该点的替换点)
163             {
164                 b += 1;
165                 a = 2;//将a重新置为1
166                 newG.vexnum--;
167             }
168         }
169     }
170     //处理从最后一个点到第一个点
171     if ((G.ver[G.vexnum].table == 0) && (G.ver[1].table == 1))   //从外到内
172     {
173         ver = newver(G.ver[G.vexnum], G.ver[1], C);
174         newG.ver[G.vexnum + 1 - b] = ver;
175         newG.vexnum++;
176     }
177     else if ((G.ver[G.vexnum].table == 1) && (G.ver[1].table == 1))  //从内到内
178         ;
179     else if ((G.ver[G.vexnum].table == 1) && (G.ver[1].table == 0))  //从内到外，多一个点
180     {
181         ver = newver(G.ver[G.vexnum], G.ver[1], C);
182         newG.ver[G.vexnum + 1 - b] = ver;
183         newG.vexnum++;
184     }
185     else  //从外到外
186         ;
188     return newG;
189 }
191 void Totable(vertex *point,window C)  
192 {
193     if ((point->x < C.xmin) || (point->x>C.xmax) || (point->y<C.ymin) || (point->y>C.ymax)) //在窗口外
194         point->table = 0;
195     else
196         point->table = 1;
198     return ;
199 } 
201 vertex newver(vertex p1, vertex p2, window C)
202 {
203     //确保p1在窗口外
204     if ((p1.code.d0 == 0) && (p1.code.d1 == 0) && (p1.code.d2 == 0) && (p1.code.d3 == 0))  //若p1在窗口内
205     {
206         vertex p3;
207         p3 = p1;
208         p1 = p2;
209         p2 = p3;
210     }
212     double k = (p2.y - p1.y)*1.0 / (p2.x - p1.x);
214     vertex s;
216     if (p1.code.d0 == 1)//p1在左侧
217     {
218         s.x = C.xmin;
219         s.y = p1.y + k*(C.xmin - p1.x);
221         if (s.y > C.ymax)//s应该在矩形上边界
222         {
223             s.y = C.ymax;
224             s.x = p1.x + (C.ymax - p1.y) / k;
225         }
226         else if (s.y < C.ymin)//s应该在矩形下边界
227         {
228             s.y = C.ymin;
229             s.x = p1.x + (C.ymin - p1.y) / k;
230         }
231     }
232     else  if (p1.code.d1 == 1)//p1在右侧
233     {
234         s.x = C.xmax;
235         s.y = p1.y + k*(C.xmax - p1.x);
237         if (s.y > C.ymax)//s应该在矩形上边界
238         {
239             s.y = C.ymax;
240             s.x = p1.x + (C.ymax - p1.y) / k;
241         }
242         else if (s.y < C.ymin)//s应该在矩形下边界
243         {
244             s.y = C.ymin;
245             s.x = p1.x + (C.ymin - p1.y) / k;
246         }
247     }
248     else if (p1.code.d2 == 1)//p1在正下侧
249     {
250         s.y = C.ymin;
251         s.x = p1.x + (C.ymin - p1.y) / k;
252     }
253     else//p1在正上方
254     {
255         s.y = C.ymax;
256         s.x = p1.x + (C.ymax - p1.y) / k;
257     }
258     Tocode(&s, C);
259     Totable(&s, C);
261     return s;
262 }
264 void draw(graph G)
265 {
266     moveTo(G.ver[1].x, G.ver[1].y);
268     for(int i=2;i<=G.vexnum;i++)
269     {
270         lineTo(G.ver[i].x,G.ver[i].y);
271     }
273     lineTo(G.ver[1].x,G.ver[1].y);
275     return;
276 }

接下来就是见证奇迹的时刻啦！duang~~duang~~duang~~

同样，为了验证算法的正确性，我设计的图案（虽然很丑！）包含了所有增加端点数的可能性，在结果里不仅画了模拟窗口，还画出了待裁剪的原图以及裁剪后在窗口内的图案，图中绿色部分是被窗口裁剪掉的，不会在窗口内显示。

好啦，今天就讲到这里啦~~咱们下次再见哦，( ^_^ )/~~拜拜