一種更有效的矩形窗口線裁剪算法

洪 燕 洪智化 劉 欣

(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 結束語

該算法借鑒了前人的算法思路，利用了區域編碼算法的區域劃分方式，但對區域的分類和使用卻不一樣;采用了中點分割算法的分割線段的方法，但目的不是為了與矩形邊界求交，而是用于判斷中點最終所在區域，從而確定直線段與矩形的位置關系，以判斷能否對線段進行快速舍棄。通過實驗，證明了該算法的可行性以及它的優勢所在，利用該算法將在很大概率上使得快速舍棄判斷的效率大大提高。

此外，本文只研究和介紹了該算法在矩形窗口線裁剪中的應用，如果再加以改進，該算法還將能應用于任意多變形窗口線裁剪的快速舍棄判斷，筆者將繼續努力對其加以完善，并從事其后續的工作和研究。