谁有多边形的截剪算法的实现代码？分不够再加。

Question

谁有多边形的截剪算法的实现代码？要求能处理凹多边形。分不够再加。

Answer 1

看看 计算机图形学 孙家广 的那本书2，关于裁剪算法的说明
此程序是对Cohen-Sutherland编码裁剪算法的演示。在图形学中，图形裁剪是其一项重要的内容。裁剪的目的就是把落在用户定义的窗口外的部分图形裁剪掉，从而为图像识别和图像处理提供清晰的对象。
图形裁剪的关键技术是对直线段和平面多边形的裁剪，因为任何图形都可以用多面体逼近，每一个面可视为一个多边形，而多边形的裁剪归结于直线的裁剪。因此直线段的裁剪算法的优劣对图形的裁剪速度的影响较大。Cohen—Sutherland编码裁剪算法的优点在于用区域检查的办法有效地识别可直接接受或直接舍弃的线段，只有不属于这两种情况的线段才算线段与窗口边线的交点，并作相应的取舍处理。
Cohen—Sutherland算法是将一平面区域分成九个子区域，每个子区域给一个4位二进制编码，如图所示，其意义是：XL，XR，YB，YT为窗口的四边界线。规定YT上方的第1位为1，YB下方的第2位为1，XL左边的第4位为1，XR右边的第3位为1，其余为0，显然当线段两端点的编码全为0时，则线段全在窗口内，直接接受。如果线段两端的4位编码进行位运算-逻辑与，结果非0，则线段全在窗口之外，舍弃。否则再进行分割，即找出线段与窗口的一个边界线的交点，对交点也进行四位编码，并对线段的分段分别进行检查或接受，或舍弃，或再次分割。重复这一过程，直到完成[2]。如图，线段AB，只接受CD段，其余全部舍弃。  
图 2-1
首先确定四条边界的值：
RegionPoint数组存储了矩形框的两个端点的横，纵坐标值。取出x轴中的大者作为XR，小者作为XL；y轴中的大者作为YT，小者作为YB。则四条边框确定出来。
void  Input()
{
if(RegionPoint[0].x>RegionPoint[1].x)
{
XR=RegionPoint[0].x;
XL=RegionPoint[1].x;
}
else{
XR=RegionPoint[1].x;
XL=RegionPoint[0].x;
}
//setup the limit of coordinate of x     if(RegionPoint[0].y>RegionPoint[1].y)
{
YT=RegionPoint[0].y;
YB=RegionPoint[1].y;
}
else{
YT=RegionPoint[1].y;
YB=RegionPoint[0].y;
}
//setup the limit of coordinate of y
}
encode程序段是判断线段端点在那个编码区域，其中
#define LEFT   1
#define RIGHT  2
#define BOTTOM 4
#define TOP    8
定义是为了让点与边界进行逻辑与计算而定义的。
int encode(float x,float y,int* code)
{
int c;
c=0;
if(x<XL)
c=c|LEFT;
else if(x>XR)
c=c|RIGHT;
if(y<YB)
c=c|BOTTOM;
else if(y>YT)
c=c|TOP;
*code=c;
return 1;
}算法的大意是：对于每条直线段分为三种情况处理。1，若两个端点完全在窗口内，则显示该线段。2，若明显在窗口外，则丢弃该线段。3，若线段不满足上述条件，则求出线段与边框的交点。
int CLip(float x1,float y1,float x2,float y2)
//float x1,y1,x2,y2,XL,XR,YB,YT;
//*(x1,y1)与(x2,y2)是线段端点坐标，其他四个参数分别定义窗口的左，右，上，下边界
{
float x,y;
int code1,code2,code;
encode(x1,y1,&code1);
encode(x2,y2,&code2);
while(code1!=0||code2!=0)
{
if((code1&code2)!=0)      //不过裁剪区域
return 0;
code=code1;
if(code1==0)
code=code2;
if((LEFT&code)!=0)        //线段与左边界的交点
{
x=XL;
y=y1+(y2-y1)*(XL-x1)/(x2-x1);
}
else if((RIGHT&code)!=0)  //线段与右边界的交点
{
x=XR;
y=y1+(y2-y1)*(XR-x1)/(x2-x1);
}
else if((BOTTOM&code)!=0)  //线段与下边界的交点
{
y=YB;
x=x1+(x2-x1)*(YB-y1)/(y2-y1);
}
else if((TOP&code)!=0)      //线段与上边界的交点
{
y=YT;
x=x1+(x2-x1)*(YT-y1)/(y2-y1);
}
if(code==code1)
{
x1=x;
y1=y;
encode(x,y,&code1);
}
else
{
x2=x;
y2=y;
encode(x,y,&code2);
}
}
return 1;
}

Answer 2

多谢 wqs6(竹山)，可是我要完成的任务不是显示多边形，我是要将某一区域划分成n*n块，而这一区域内有许多的多边形，要求将这些多边形分割后存入相应的块中。

Answer 3

太好了，卡门！你的算法或许对我有帮助，请给我发一份。launch20012◎163.com

Answer 4

其实就是GIS中的拓扑和overlay原理。

Answer 5

carman2003(卡门) ,那我也要一份看看[email protected]多谢！

Answer 6

[email protected]
我也想看看，拜托了