CS直线裁剪算法

#include
#include
#include
using namespace std;
//分别用四个符号常量记录四个边界的编号，相当于C语言中的define宏定义
const unsigned TOP = 8;
const unsigned BOTTOM = 4;
const unsigned RIGHT = 2;
const unsigned LEFT = 1;

static unsigned xl, yb, xr, yt;

//优化后的Bresenham算法，能够处理斜率不存在，斜率为负数，斜率绝对值大于一等情况，并且可以根据需要自动调整两点顺序，具有良好的通用性
//使用只需要输入两点的横纵坐标值即可
void Bresenham(const unsigned& x1, const unsigned& y1, const unsigned& x2, const unsigned& y2)
{
	int dx = x2 - x1, dy = y2 - y1;
	enum MainChangeDirection { x, y };//用一个枚举变量记录直线的主要变化方向（x方向或者y方向）（用枚举变量更加符合语义）
	MainChangeDirection Direction;
	if (abs(dx) >= abs(dy))
		Direction = x;
	else Direction = y;
	if ((Direction == x && x1 > x2) || (Direction == y && y1 > y2))//如果在主要变化方向上的次序相反了，则递归调用自身即可（相当于交换两个点）
	{
		Bresenham(x2, y2, x1, y1);
		return;
	}

	if (dx == 0)//处理斜率不存在的特殊情况
	{
		for (unsigned y = y1; y <= y2; ++y)
		{
			putpixel(x1, y, YELLOW);
		}
		return;
	}

	//对于不同的变化方向以及斜率的正负不同，需要使用不同的数学表达式（自行推导出），也就是需要分情况
	double k = double(dy) / dx;
	if (Direction == x)//处理主要变化方向为x轴的情况
	{
		unsigned x = x1, y = y1;
		if (k >= 0)//主要变化方向为x轴并且斜率大于等于零
		{
			int e = -dx;
			for (; x <= x2; ++x)
			{
				putpixel(x, y, YELLOW);
				e += 2 * dy;
				if (e > 0)
				{
					y++;
					e -= 2 * dx;
				}
			}
		}
		else if (k < 0)//主要变化方向为x轴且斜率小于零
		{
			int e = dx;
			for (; x <= x2; ++x)
			{
				putpixel(x, y, YELLOW);
				e += 2 * dy;
				if (e <= 0)
				{
					y--;
					e += 2 * dx;
				}
			}
		}
	}
	else if (Direction == y)
	{
		unsigned y = y1, x = x1;
		if (k >= 0)//主要变化方向为y轴方向并且斜率大于等于零
		{
			int e = -dy;
			for (; y <= y2; ++y)
			{
				putpixel(x, y, YELLOW);
				e += 2 * dx;
				if (e > 0)
				{
					x++;
					e -= 2 * dy;
				}
			}
		}
		else if (k < 0)//主要变化方向为y轴方向并且斜率小于零
		{
			int e = dy;
			for (; y <= y2; ++y)
			{
				putpixel(x, y, YELLOW);
				e += 2 * dx;
				if (e <= 0)
				{
					x--;
					e += 2 * dy;
				}
			}
		}
	}
	return;
}

unsigned short Region_Coding(const unsigned& x, const unsigned& y)
{
	short coding = 0;
	if (y > yt)
		coding += 8;
	else if (y < yb)
		coding += 4;
	if (x > xr)
		coding += 2;
	else if (x < xl)
		coding += 1;
	return coding;
}

void CS_LineClip(const unsigned& x1, const unsigned& y1, const unsigned& x2, const unsigned& y2)
{
	unsigned p1, p2;
	//通过区域码函数分别求出两个点的区域码
	p1 = Region_Coding(x1, y1);
	p2 = Region_Coding(x2, y2);

	//第一种情况：两点的区域码均在窗口内部，则直接画出该直线即可
	if (p1 == 0 && p2 == 0)
	{
		Bresenham(x1, y1, x2, y2);
		return;
	}
	//第二种情况，两点的区域码均不在窗口内部，则不绘制任何直线
	else if ((p1 & p2) != 0)
	{
		return;
	}
	//第三种情况：即排除之前两种情况后的剩余情况，此时进行分类讨论
	else
	{
		//首先处理斜率不存在的特殊情况，该情况下可以直接画出线
		if ((x1 == x2 && y1 <= yb && y2 >= yt) || (x1 == x2 && y1 >= yt && y2 <= yb))
		{
			Bresenham(x1, yb, x2, yt);
			return;
		}
		//求出直线的斜率。

注意：此处一定要用到类型转换！否则求出的斜率很可能存在异常
		double k = (double(y2) - double(y1)) / (double(x2) - double(x1));
		if ((p1 & LEFT) != 0)//由于已经使得两点的横坐标升序排列，因此如果左边点在左边界的左边的话，则求出直线与左边界的交点，以交点代替第一个点递归执行函数
		{
			unsigned New_y1 = unsigned(k * (xl - x1) + y1 + 0.5);
			CS_LineClip(xl, New_y1, x2, y2);
			return;
		}
		if ((p2 & RIGHT) != 0)//运行到此处时直线左端点一定在左边界上或左边界的右边，此时对右端点进行类似检查：如果右端点在右边界的右边，则取直线与右边界的交点。


		{
			unsigned New_y2 = unsigned(k * (xr - x1) + y1 + 0.5);
			CS_LineClip(x1, y1, xr, New_y2);
			return;
		}
		//剩下的情况中只包含两点横坐标均在左右边界之间，但是纵坐标不在上下边界内的情况，需要分斜率正负进行讨论
		if (k >= 0)
		{
			if ((p2 & TOP) != 0)//斜率为正且右边的点在上边界以上时，求出直线与上边界的交点来代替上点，递归调用自身即可
			{
				unsigned New_x2 = unsigned(x1 + (yt - y1) / k + 0.5);
				CS_LineClip(x1, y1, New_x2, yt);
				return;
			}
			if ((p1 & BOTTOM) != 0)//斜率为正且左边的点在下边界以下时，求出直线与下边界的交点来代替下点，递归调用自身
			{
				unsigned New_x1 = unsigned(x1 + (yb - y1) / k + 0.5);
				CS_LineClip(New_x1, yb, x2, y2);
				return;
			}
		}
		if (k < 0)//斜率小于零的情况进行类似讨论即可
		{
			if ((p1 & TOP) != 0)
			{
				unsigned New_x1 = unsigned(x1 + (yt - y1) / k + 0.5);
				CS_LineClip(New_x1, yt, x2, y2);
				return;
			}
			if ((p2 & BOTTOM) != 0)
			{
				unsigned New_x2 = unsigned(x1 + (yb - y1) / k + 0.5);
				CS_LineClip(x1, y1, New_x2, yb);
				return;
			}
		}
	}
}

int main(void)
{
	int x1, y1, x2, y2;
	cout << "请分别输入原始直线两端点的横纵坐标：";
	cin >> x1 >> y1 >> x2 >> y2;
	cout << "请分别输入裁剪窗口左下角和右上角的横纵坐标：";
	cin >> xl >> yb >> xr >> yt;
	cout << "原始直线和裁剪窗口如下图所示：(按任意键查看，查看后按任意键裁剪）";
	_getch();
	initgraph(800, 640);
	Bresenham(x1, y1, x2, y2);//通过之前学过的Bresenham方法进行画线 *** 作
	rectangle(xl, yt, xr, yb);
	_getch();
	closegraph();
	initgraph(800, 640);
	CS_LineClip(x1, y1, x2, y2);
	rectangle(xl, yt, xr, yb);
	_getch();
	closegraph();
	return 0;
}

备注：①graphics.h包需要自行百度免费下载 ②代码中的Bresenham画线算法可以用任意画直线的函数代替，对结果不产生影响。