一种更有效的矩形窗口线裁剪算法

洪 燕 洪智化 刘 欣

(1、江西陶瓷工艺美术职业技术学院，江西 景德镇 333001;2、浙江大学机械与能源工程学院，浙江 杭州 310027)

0 引言

在窗口的线裁剪中，对于直线段与多边形(或矩形)窗口没有相交的情形可以快速舍弃，不必进行求交运算，从而提高裁剪效率，因此，窗口线裁剪的快速舍弃判断是十分有意义的。对于有些情形，快速舍弃判断是十分简单的，但有些情况却不然，以矩形窗口线裁剪为例，如图1所示。

图1 0矩形窗口线裁剪

像图1中的线段a，显然与矩形窗口没有相交，可以快速舍弃，不必进行求交运算，因为线段两端点均位于矩形窗口的同一侧，这一点通过比较线段两端点的坐标值和矩形窗口上下左右坐标的大小即可做出判断，十分容易。但对于线段b，线段两端点位于矩形窗口的不同侧，与矩形窗口也没有相交，也可进行快速舍弃，但判断并不容易。而本文，特针对这种情形提出了一种十分有效的判断算法。

1 中点区域法

1.1 算法介绍

本算法结合了传统的区域编码算法和中点算法的思路，通过判断线段中点最终所在区域来判断线段是否与矩形相交。

首先，将矩形四条边延伸，划分出“井”字形区域，取矩形外部的两个方向上的对角区域为I1和I2，矩形内部区域为II(包括矩形的边界和四个顶点)，如图2所示。

图2 矩形所确定的“井”字形区域

图3 k＞0时线段中点的区域判断

当直线段的斜率k＞0时，取被判断线段AB的中点为M1，如图3所示，可知点A、点M1完全位于矩形的同一侧，即图1中的线段a的情形，于是AM1段可以不用考虑。然后继续取线段BM1的中点M2，同样可知点B、点M2也完全位于矩形的同一侧，于是再取线段M1M2的中点M3，此时点M3落在矩形的对角区域I1内，便可以判断线段AB与矩形不相交，可以快速舍弃。而对于线段CD，其中点N1落在矩形的内部区域Ⅱ内，此时便可以判断线段CD与矩形相交，需要进行裁剪求交运算。

而对于斜率k＜0的情况，区别只是将I1区域换成I2区域，其他判断方法及步骤均一样，如图4所示。取被判断线段EF的中点为P1，可知点E、点P1完全位于矩形的同一侧，即图1中的线段a的情形，于是EP1段可以不用考虑。然后继续取线段FP1的中点P2，同样可知点F、点P2也完全位于矩形的同一侧，于是再取线段P1P2的中点P3，此时点P3落在矩形的对角区域I2内，便可以判断线段EF与矩形不相交，可以快速舍弃。而对于线段GH，其中点Q1落在矩形的内部区域II内，此时便可以判断线段GH与矩形相交，需要进行裁剪求交运算。

图4 k＜0时线段中点的区域判断

需要说明的是:本文在此省略掉对线段两端点均落在矩形内、线段一端点落在矩形内以及线段两端点落在矩形外的同一侧和线段斜率等于0等情况的判断，因为这些判断都比较容易实现，本文只对图1中b、c两种情况做出判断，即判断出线段能够快速舍弃或者是会与矩形相交。具体到普遍情况的程序算法步骤如图5所示。

图5 程序判断流程图

1.2 编程实验

中点区域法耗时的主要部分是中点的计算，因此计算中点次数的多少是决定该算法效率高低的关键因素。为客观地检验和评价该算法的性能，特设计如下实验:在坐标为(－1000，1000)的正方区域内随机生成1000万条本文所讨论的情形的线段，即线段两端点位于矩形的不同侧，然后与以原点(0，0)为中心、边长为100的一正方形进行裁减判断。实验的输出数据为:做每次判断所需要计算中点的次数，并由此来评价该算法的效率和优劣。

1.3 实验结果及算法优缺点分析

上述实验在VC++中编译完成，结果如图6所示。

图6 程序实验结果

由试验数据可以看出，只需做1次到3次运算的概率接近75%，只需做1次运算的概率接近40%，而目前的一些快速舍弃判断算法都至少需要做3次除法运算，虽然本算法有大于3次运算的情况，但从概率上说，本算法还是大大提高了裁减前快速舍弃判断的效率。况且，本算法的运算均为除2运算，可以利用硬件由加法和位移实现，因此实际效率会有极大的提高。

2 结束语

该算法借鉴了前人的算法思路，利用了区域编码算法的区域划分方式，但对区域的分类和使用却不一样;采用了中点分割算法的分割线段的方法，但目的不是为了与矩形边界求交，而是用于判断中点最终所在区域，从而确定直线段与矩形的位置关系，以判断能否对线段进行快速舍弃。通过实验，证明了该算法的可行性以及它的优势所在，利用该算法将在很大概率上使得快速舍弃判断的效率大大提高。

此外，本文只研究和介绍了该算法在矩形窗口线裁剪中的应用，如果再加以改进，该算法还将能应用于任意多变形窗口线裁剪的快速舍弃判断，笔者将继续努力对其加以完善，并从事其后续的工作和研究。