直线裁剪算法研究

《直线裁剪算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、直线裁剪算法研究华北电力人学课程论文论文题冃课程名称11K1学生姓名：张振兴号：111909020134成绩：1111专业班级：软件学直线裁剪算法研究摘要：直线裁剪是计算机图形学中的一个重要技术，在对常见的直经线裁剪的算法分析的基础上，针対Cohen-Sutherland算法和Liang-Barsky算法进彳亍了分析研究。并対两种算法了计算直线与窗口边界的交点吋，进行了有效有比较。关键词：裁剪；算法；Cohen-Sutherland；Liang—Barsky；引言直线是图形系统中使用最多的一个基木元素。所以对丁直线段的裁

2、剪算法是被研究最深入的一类算法，目前在矩形窗口的直线裁剪算法中，出现了许多有效的算法。其中比校著名的有:Cohen-Sutherland算法、中点分割算法、Liang-Barsky算法、Sobkow-Pospisil-Yang算法，及Nichol1-Lee-Ncholl算法等。1、直线裁剪的基木原理图1所示的为直线与窗口边界Z间对能出现的几种关系。对以通过检査直线的两个端点是否在窗口之内确定如何对此玄线裁剪。如果一肓线的两个端点均在窗口边界之内（如图1中P5到P6的直线），则此直线应保留。如果一条直线的一个端点在窗口外（

3、如P9）另一个点在窗口内（如P10）,则应从直线与边界的交点（P9处裁明掉边界之外的线段。如果直线的两个端点均在边界外，则可分为两种情况：一种情况是该直线全部在窗口之外；另一种情况是直线穿过两个窗口边界。图中从P3到P4的直线属于前一种情况，应全部裁剪掉；从P7到P8的直线属丁•后一种情况，应保留P7到P8的线段，其余部分均裁剪掉。图1玄线相对干窗口边界的栽剪直线裁剪算法应首先确定哪些直线全部保留或全部裁剪，剩下的即为部分裁剪的直线。对于部分裁剪的百线则首先要求出这些直线与窗口边界的交点，把从交点开始在边界外的部分裁剪掉

4、。一个复杂的画而中可能包含有儿T•条直线，为了提高算法效率，加快裁剪速度，应当采用计算量较小的算法求直线与窗口边界的交点。2、两种垂要的算法10011000101000010000窗口00100101010001102、1cohcn—Sutherland直线裁剪算法Cohen-Sutherland算法的人意是：对于每条线段P1P2,分为3种情况处理。①若P1P2完全在窗口内，则显示该线段P1P2,简称“取”之。②若P1P2明显在窗口外，则丢弃该线段，简称“弃”Z。③若线段既不满足“収”的条件，也不满足“弃”的条件，则把线

5、段分为两段。其中一段完全在窗口外，可弃之。然后对另一•段重复上述处理。1.区域码及其建立Cohen-Sutherland直线裁剪算法的核心是把所有直线的端点均分配一个表示其相对位置的4位二进制代码。此代码称为区域码。区域码按照端点与窗口边界的相对位置编码，即区域码的4位分别代表端点位丁•窗口的上、下、左、右。区域码从右到左的各位所代表的坐标区如下所示：位坐标区上下右左上述各位中某位为1,则表示点位于此坐标区。窗口周围各坐标区的区域码如图2所示。由图2可见，位于窗中内的点，其区域码应为0000,位于窗口左下方的点，其区域码

6、应为0101,其余类推。区域码各位的值可以通过对端点坐标（x,y）与窗口边界的比较求得。如果x

7、都建立了区域码Z后，就对按区域码判断直线在窗口Z内或窗口Z外。这可分为如下几种情况：①若-•直线的两个端点的区域码均为0000则此直线在窗口边界Z内，应子保留。②若一直线的两个端点的区域码的同一位同时为1,则此直线全部在窗口边界Z外，应子裁剪。例如，若一直线的一个端点的区域码为1001,另一个端点的区域码为0101,贝IJ此两端点的区域码的第一位均为1,说明此两端点均在窗口边界Z左，因此，直线在窗口边界之外，应了裁剪。可川将玄线两个端点的区域码进行与操作的方法，判断玄线是否在窗口之外，若与操作的结果为oooo则两端点的区

8、域码任何位均不同时为1,此直线不一怎被裁剪。③以上两种情况之外的直线，有町能穿过窗口，也有可能不穿过窗口，如图87所示。图屮所示的两条直线都不符合情况②的要求，但一条直线(P1P2)穿过窗口，另一直线(P3P4)不守过窗口。对■这类直线可以进行如下处理：取窗口外的一个端点与窗口边界比较以确定可排除直线的哪一部分，然后