用Sutherland-Hodgman算法实现裁剪任意凸多边形

一、 实验目的。
用Sutherland-Hodgman算法实现裁剪任意凸多边形
二、 实验工具
VC6.0
三、 实验步骤
思想：每次用窗口的一条边界以及其延长线来裁剪多边形。
裁剪得到的多边形的顶点由两部分组成：
落在可见一侧的原多边形顶点；多边形的边与裁剪窗口边界的交点
根据多边形每一边与窗口边所形成的位置关系，沿着多边形依次处理顶点会遇到四种情况：
（1）第一点 S 在不可见侧面，而第二点 P 在可见侧。处理方法：交点 I 和点 P 均被加入到输出顶点表中。
（2）S 和 P 都在可见侧。处理方法：P 被加入到输出顶点表中
（3）S 在可见侧，而 P 在不可见侧。处理方法：交点 I 被加入到输出顶点表中
（4）如果 S 和 P 都在不可见侧。处理方法：输出顶点表中不增加任何顶点

在窗口的一条裁剪边界处理完所有顶点后，其输出顶点表将用窗口的下一条边界继续裁剪。

3.建立一个工程文件，将思路转化为c编程语言，进行编译。
代码如下：

在这里插入代码片
``

第一次代码：
#include <windows.h>
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include<iostream>
#include<graphics.h>
#include<math.h>
using namespace std;
void CMyClip_A View::ClipedgeL (CPoint polypoint[], CPointclipwindow[], UINT polyum){
long xl, xr,yt, yb;
UINT i;
xl=clipwindow[0].x;
xr=clipwindow[0].x;
yt=clipwindow[0].y;
yb=clipwindow[0].y;
for(i=1;i<=4;i+t){
	if(xl>clipwindow[il.x)
	xl=clipwindow[i]·x;
	if(xc<clipwindow[i].x)
		xr=clipindow[i].x;
	if(yb>clipwindow[i]. y)
		yb=clipwindow[i].y;
	if(yt<clipwindow[i].y)
		yt=clipwindow[i]. y;
}

CPoint B[Polygon_Num],C[Polygon_Num];
UINT m_nA,m_nB;,
int x,y;
long teml, tem2:
m_nA=polynum://记载原始多边形顶点顶点个数
m_nB-0://记载新生成多边形顶点顶点个数
for(i=0;i<m_nA;i++){
	if (polypoint[i]. x<x1 && polypoint[i+1]. x<xl){ //判断多边形两个端点都在外部，不做处理
		continue;//如果是这种情况，就继续对下-条多边形边作判断//
				 }
  if(polypoint[i]. x>=xl && polypoint[i+l].x>=xl) //两端点都在内部，保留。因为每个保留的点在数组中只出现一次,且下一次判断时第二个端点一定要的//
  {
	  B[m_nB].x = polypoint[i].x;
	  B[m_nB].y =polypoint[i].y;
      m_nB=m_nB+1;
	  continue;
  }
  if(polypoint[i].x<xl && polypoint[i+1].x>=xl){//两端点在外部，终点在内部，求交点，终点送入临时数组//
	x=xl;
	tem1=(xl-polypoint[i].x);
	//tem2= (xl- xl)*dy/dxtyl:
	//y/x=dy/dx------>y=x*dy/dx
	tem2=tem1* (polypoint[i+l].y -polypoint[i].y)// (polypoint[i+1]. x- -polypoint[i]. x) +polypoint[i].y;
	y=tem2;
	B[m_nB].x =x;
	B[m_nB].y =y;
	m_nB=m_nB+1;
	continue;
  }

if(polypoint[i].x>=xl && polypoint[i+l]. x<xl)//起点在内部，终点在外,求交点，然后起点,交点送入临时数组
{
//保留内部点
	B[m_nB].x -=polypoint[i].x ;
	B[m_nB].y =polypoint[i].y;
	m_nB=m_nB+l://保留交点
	x=xl;
	tem1=(xl-polypoint[i].x);
	tem2=tem1*(polypoint[i+1].y-polypoint[i].y/ polypoint[i+1].x-polypoint[i].x)+polypoint[i].y;
	y=tem2;
	B[m_ nB].x=x;
	B[m_ nB].y=y;
	m_nB=m_ nB+1;
	continue;
}
//把第一 个点的数据拷贝到最后,形成裁剪后的多边形

if(i=m_ nA){
	B[m_ nB]=B[0];
}
m_ nA=0;
for(i=0;i<m_ nB;i++）{
	if(B[i].y<yb &&B[i+1].y<yb){
	continue;
	}//下一条边
if(B[il.y>=yb&& B[i+l].y>=yb) //p1,p2 都在yb下方
{
	C[m_nA].x =B[i].x;
	C[m_nA].y =B[i].y;
	m_ nA++;
	continue ;
}
it(B[i].y<yb && B[i+1].y>=yb)//P1在下,P2在上,留交点,外一>内
{
	y=yb;
	teml=yb- B[i].y;
	//tem2=x1+ (yb-y1)*dx/dy
	tem2=tem1*(B[i+1]. x-B[i]. x)/(B[i+1].y-B[i].y) + B[i].x;
	x=tem2;
	C[m_nA].x =x;
	C[m_nA].y =y;
	m_ nA++;
	continue;
}
if(B[i].y)=yb && B[i+1]. y<yb){
//p1在上方,P2在下方,留P1和交点,内-外
//save pl
	C[m_nA].x=B[i].x;
	C[m_ nA]. y=B[i].y:
	m_ nA++;
	y=yb;
	teml=yb-B[i].y;
	tem2-teml*(B[i+1].x-B[i]. x)/(B[i+1].y-B[i]. y)+B[i].x;
	x=tem2;
	C[m_nA].x =x;
	C[m_nA].y =y;
	continue;
	}
}
//形成第二次裁剪多边形
if(i==m_nB){
	C[m_nA]=C[0];
}
由于感觉思路非常混乱，编译也有错误，就重新写代码。
----------------------------------------------------------------------------------------------------------------------
第二次代码：
#include <windows.h>
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include<iostream>
#include<graphics.h>
#include<math.h>
using namespace std;

/*
1、顶点Pi在内侧，前一顶点Pi-1也在内侧，则将Pi纳入新的顶点序列；
2、顶点Pi在内侧，前一顶点Pi-1在外侧，则先求交点Q，再将Q、Pi依次纳入新的顶点序列；
3、顶点Pi在外侧，前一顶点Pi-1在内侧，则先求交点Q，再将Q纳入新的顶点序列；
4、顶点Pi与前一顶点Pi-1均在外侧，则顶点序列中不增加新的顶点。
*/
 
/*
函数定义在CPolygon类中；
数组pt存放原多边形的顶点；
n为多边形的顶点个数，第一个顶点和最后一个顶点相同，因此实际多边形的顶点个数为n-1。
*/
void CPolygon::SutherlandHodgman(double wxl, double wyt, double wxr, double wyb)//裁剪边界：左、上、右、下（xmin、ymin、xmax、ymax）
{
	CP2 B[100], C[100];   //定义两个临时数组，用于每次裁剪后新生成的多边形顶点
	UINT m_nA, m_nB;
	int x, y;
	long tem1, tem2;
	int i;
 
	//原始多边形顶点个数
	//原始多边形顶点数组的第一个顶点和最后一个顶点相同，因此实际顶点个数为n-1
	m_nA = n-1;    
	m_nB = 0;      //新生成多边形顶点个数
	
	//左边界---------------------------------------------
	for (i = 0; i < m_nA; i++) {
		if (pt[i].x < wxl&&pt[i + 1].x < wxl) { //多边形两个顶点都在外部
			continue;
		}
		else if (pt[i].x >= wxl && pt[i + 1].x >= wxl) { //多边形两个顶点都在内部，保留第一个点
			/*
			    因为每个保留的点在数组中只出现一次，且下一次判断时第二个端点一定会要取到
			因此只保留两个点中的第一个
			*/
			B[m_nB].x = pt[i].x;
			B[m_nB].y = pt[i].y;
			m_nB++;
		}
		else if (pt[i].x < wxl && pt[i + 1].x >= wxl) { //两个端点起点在外部，终点在内部
			//求交点，然后交点送入临时数组
			x = wxl; 
			y = (wxl - pt[i].x) * (pt[i + 1].y - pt[i].y) / (pt[i + 1].x - pt[i].x) + pt[i].y;//y = x*dy/dx+y0
			
			B[m_nB].x = x;
			B[m_nB].y = y;
			m_nB++;
		}
		else if (pt[i].x >= wxl && pt[i + 1].x < wxl) { //两个端点起点在内部，终点在外部
			//求交点，起点和交点送入临时数组
 
			//保留起点
			B[m_nB].x = pt[i].x;
			B[m_nB].y = pt[i].y;
			m_nB++;
 
			//保留交点
			x = wxl;
			y = (wxl - pt[i].x) * (pt[i + 1].y - pt[i].y) / (pt[i + 1].x - pt[i].x) + pt[i].y;
 
			B[m_nB].x = x;
			B[m_nB].y = y;
			m_nB++;
		}
	}
 
	//把第一个点的数据拷贝到最后，形成第一次裁剪后的多边形
	if (i == m_nA) {
		B[m_nB] = B[0];
	}
	
 
	//上边界-------------------
	m_nA = 0;
	for (i = 0; i < m_nB; i++) {
		if (B[i].y < wyt&&B[i + 1].y < wyt) {  //两个都在边界上方（外部）
			continue;
		}
		else if (B[i].y >= wyt && B[i + 1].y >= wyt) { //都在上边界下方，保留起点
			C[m_nA].x = B[i].x;
			C[m_nA].y = B[i].y;
			m_nA++;
		}
		else if (B[i].y < wyt && B[i + 1].y >= wyt) { //起点在上，终点在下，保留交点
			y = wyt;
			x = (wyt - B[i].y) * (B[i + 1].x - B[i].x) / (B[i + 1].y - B[i].y) + B[i].x;//x = y*dx/dy+x0;
 
			C[m_nA].x = x;
			C[m_nA].y = y;
			m_nA++;
		}
		else if (B[i].y >= wyt && B[i + 1].y < wyt) {////起点在下，终点在上，保留起点、交点
			//保留起点
			C[m_nA].x = B[i].x;
			C[m_nA].y = B[i].y;
			m_nA++;
 
			//保留交点
			y = wyt;
			x = (wyt - B[i].y) * (B[i + 1].x - B[i].x) / (B[i + 1].y - B[i].y) + B[i].x;
 
			C[m_nA].x = x;
			C[m_nA].y = y;
			m_nA++;
		}
	}
	//形成第二次裁剪多边形
	if (i == m_nB) {
		C[m_nA] = C[0];
	}
 
	//右边界----------------------------------------------
	m_nB = 0;
	for (i = 0; i < m_nA; i++) {
		if (C[i].x > wxr && C[i + 1].x > wxr) {  //都在右边界右方
			continue;
		}
		else if (C[i].x <= wxr && C[i + 1].x <= wxr) {//都在右边界左方，保留起点
			B[m_nB].x = C[i].x;
			B[m_nB].y = C[i].y;
			m_nB++;
		}
		else if (C[i].x > wxr && C[i + 1].x <= wxr) { //起点在右方，终点在左方，保留交点
			x = wxr;
			y = C[i].y - (C[i].x - wxr) * (C[i + 1].y - C[i].y) / (C[i + 1].x - C[i].x);//y = y0-x*dy/dx;
 
			B[m_nB].x = x;
			B[m_nB].y = y;
			m_nB++;
		}
		else if (C[i].x <= wxr && C[i + 1].x > wxr) { //起点在左方，终点在右方，保留起点、交点
			//保留起点
			B[m_nB].x = C[i].x;
			B[m_nB].y = C[i].y;
			m_nB++;
 
			//保留交点
			x = wxr;
			y = C[i].y - (C[i].x - wxr) * (C[i + 1].y - C[i].y) / (C[i + 1].x - C[i].x);
			
			B[m_nB].x = x;
			B[m_nB].y = y;
			m_nB++;
		}
	}
	//三次裁剪后的新多边形
	if (i == m_nA) {
		B[m_nB] = B[0];
	}
 
	//下边界---------------------------------
	m_nA = 0;
	for (i = 0; i < m_nB; i++) {
		if (B[i].y > wyb && B[i + 1].y > wyb) {  //都在下边界下方
			continue;
		}
		else if (B[i].y <= wyb && B[i + 1].y <= wyb) { //都在下边界上方，保留起点
			C[m_nA].x = B[i].x;
			C[m_nA].y = B[i].y;
			m_nA++;
		}
		else if (B[i].y > wyb && B[i + 1].y <= wyb) { //起点在下方，终点在上方，保留交点
			y = wyb;
			x = B[i].x - (B[i].y - wyb) * (B[i + 1].x - B[i].x) / (B[i + 1].y - B[i].y);//x = x0-y*dx/dy;
 
			C[m_nA].x = x;
			C[m_nA].y = y;
			m_nA++;
		}
		else if (B[i].y <= wyb && B[i + 1].y > wyb) { //起点在上方，终点在下方，保留起点、交点
			//保留起点
			C[m_nA].x = B[i].x;
			C[m_nA].y = B[i].y;
			m_nA++;
 
			//保留交点
			y = wyb;
			x = B[i].x - (B[i].y - wyb) * (B[i + 1].x - B[i].x) / (B[i + 1].y - B[i].y);
 
			C[m_nA].x = x;
			C[m_nA].y = y;
			m_nA++;
		}
	}
	//形成裁剪后的多边形
	if (i == m_nB) {
		C[m_nA] = C[0];
	}
 
	//把新多边形顶点放回原多边形顶点数组
	pt = new CP2[m_nA+1];
	for (int i = 0; i <= m_nA; i++) {
		pt[i].x = C[i].x;
		pt[i].y = C[i].y;
	}
	n = m_nA+1;
}
四、	实验结果
编译错误，无法完成实验。



**-------------哦豁**
**真的，无语**