C语言 Sutherland Hodgman 多边形裁剪算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7715040/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Sutherland Hodgman polygon clipping Algorithm
提问by sriram
Sutherland hodgeman polygon clipping algorithm is where we are interested in clipping or getting only some particular part of the given polygon. I know the concept of clipping and I saw the following code on the web :
Sutherland hodgeman 多边形裁剪算法是我们对裁剪或仅获取给定多边形的某些特定部分感兴趣的地方。我知道裁剪的概念，我在网上看到了以下代码：
#include <stdio.h>
#include <graphics.h>
#include <conio.h>
#include <math.h>
#include <process.h>
#define TRUE 1
#define FALSE 0
typedef unsigned int outcode;
outcode CompOutCode(float x,float y);
enum { TOP = 0x1,
BOTTOM = 0x2,
RIGHT = 0x4,
LEFT = 0x8
};
float xmin,xmax,ymin,ymax;
void clip(float x0,float y0,float x1,float y1)
{
outcode outcode0,outcode1,outcodeOut;
int accept = FALSE,done = FALSE;
outcode0 = CompOutCode(x0,y0);
outcode1 = CompOutCode(x1,y1);
do
{
if(!(outcode0|outcode1))
{
accept = TRUE;
done = TRUE;
}
else
if(outcode0 & outcode1)
done = TRUE;
else
{
float x,y;
outcodeOut = outcode0?outcode0:outcode1;
if(outcodeOut & TOP)
{
x = x0+(x1-x0)*(ymax-y0)/(y1-y0);
y = ymax;
}
else if(outcodeOut & BOTTOM)
{
x = x0+(x1-x0)*(ymin-y0)/(y1-y0);
y = ymin;
}
else if(outcodeOut & RIGHT)
{
y = y0+(y1-y0)*(xmax-x0)/(x1-x0);
x = xmax;
}
else
{
y = y0+(y1-y0)*(xmin-x0)/(x1-x0);
x = xmin;
}
if(outcodeOut==outcode0)
{
x0 = x;
y0 = y;
outcode0 = CompOutCode(x0,y0);
}
else
{
x1 = x;
y1 = y;
outcode1 = CompOutCode(x1,y1);
}
}
}while(done==FALSE);
if(accept)
line(x0,y0,x1,y1);
outtextxy(150,20,"POLYGON AFTER CLIPPING");
rectangle(xmin,ymin,xmax,ymax);
}
outcode CompOutCode(float x,float y)
{
outcode code = 0;
if(y>ymax)
code|=TOP;
else if(y<ymin)
code|=BOTTOM;
if(x>xmax)
code|=RIGHT;
else if(x<xmin)
code|=LEFT;
return code;
}
void main( )
{
float x1,y1,x2,y2;
/* request auto detection */
int gdriver = DETECT, gmode, n,poly[14],i;
clrscr( );
printf("Enter the no of sides of polygon:");
scanf("%d",&n);
printf("\nEnter the coordinates of polygon\n");
for(i=0;i<2*n;i++)
{
scanf("%d",&poly[i]);
}
poly[2*n]=poly[0];
poly[2*n+1]=poly[1];
printf("Enter the rectangular coordinates of clipping window\n");
scanf("%f%f%f%f",&xmin,&ymin,&xmax,&ymax);
/* initialize graphics and local variables */
initgraph(&gdriver, &gmode, "c:\tc\bgi");
outtextxy(150,20,"POLYGON BEFORE CLIPPING");
drawpoly(n+1,poly);
rectangle(xmin,ymin,xmax,ymax);
getch( );
cleardevice( );
for(i=0;i<n;i++)
clip(poly[2*i],poly[(2*i)+1],poly[(2*i)+2],poly[(2*i)+3]);
getch( );
restorecrtmode( );
}
The coding was well written and I have the real problem of understanding the clipfunction defined in the code. Since I'm a novice in C, I couldn't able to figure it out, can anyone explain the algorithm involved in the clipfunction?
编码写得很好，我在理解clip代码中定义的函数方面遇到了真正的问题。由于我是 C 的新手，我无法弄清楚，谁能解释一下函数中涉及的算法clip？
回答by Christian Rau
The algorithm you present is not the Sutherland-Hodgman-Algorithm for clipping against an arbitrary polygon, but the Cohen-Sutherland-Algorithm for clipping against a rectangular viewport. The code snippet seems to be taken directly from the corresponding Wikipedia article. That article explains the algorithm and it also explains the code sample step by step, as their version contains many helpful comments. The major idea is to classify the location of the line endpoints with respect to the viewport using a 4-bit code, which makes the actual clipping implementable based on simple bitwise operations.
您提供的算法不是用于裁剪任意多边形的 Sutherland-Hodgman-Algorithm，而是用于裁剪矩形视口的 Cohen-Sutherland-Algorithm。代码片段似乎直接取自相应的维基百科文章。那篇文章解释了算法，还逐步解释了代码示例，因为它们的版本包含许多有用的注释。主要思想是使用 4 位代码对线端点相对于视口的位置进行分类，这使得基于简单的按位运算实现实际裁剪。
Assuming you understand the basic programming constructs (like loops, if, ...), basic arithmetics and the basic workings of the algorithm (maybe with the help of Wikipedia), then the key to understanding the code sample is to keep in mind that the C operators |and &realize bitwise operations.
假设您了解基本的编程结构（如循环、if、...）、基本算术和算法的基本工作原理（可能在 Wikipedia 的帮助下），那么理解代码示例的关键是要记住C 运算符|并&实现按位运算。
If you are really looking for the Sutherland-Hodgman-Algorithm to clip against an arbitrary polygon, then completely forget about this code sample. The source you got it from either wrongly attributes this to the Sutherland-Hodgman-Algorithm or you misinterpreted it due to the fact that both algorithms are attributed to Ivan Sutherland, but these are fundamentally different algorithms.
如果你真的在寻找 Sutherland-Hodgman-Algorithm 来裁剪任意多边形，那么完全忘记这个代码示例。您获得它的来源要么错误地将其归因于 Sutherland-Hodgman-Algorithm，要么您误解了它，因为这两种算法都归因于 Ivan Sutherland，但它们是根本不同的算法。
