计算机图形学：多边形裁剪算法-Sutherland—Hodgman算法

 

/*
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)//裁剪边界：左、上、右、下
{
	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;
}