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

洪 燕 洪智化 劉 欣

(1、江西陶瓷工藝美術(shù)職業(yè)技術(shù)學(xué)院，江西 景德鎮(zhèn) 333001;2、浙江大學(xué)機械與能源工程學(xué)院，浙江 杭州 310027)

0 引言

在窗口的線裁剪中，對于直線段與多邊形(或矩形)窗口沒有相交的情形可以快速舍棄，不必進行求交運算，從而提高裁剪效率，因此，窗口線裁剪的快速舍棄判斷是十分有意義的。對于有些情形，快速舍棄判斷是十分簡單的，但有些情況卻不然，以矩形窗口線裁剪為例，如圖1所示。

圖1 0矩形窗口線裁剪

像圖1中的線段a，顯然與矩形窗口沒有相交，可以快速舍棄，不必進行求交運算，因為線段兩端點均位于矩形窗口的同一側(cè)，這一點通過比較線段兩端點的坐標(biāo)值和矩形窗口上下左右坐標(biāo)的大小即可做出判斷，十分容易。但對于線段b，線段兩端點位于矩形窗口的不同側(cè)，與矩形窗口也沒有相交，也可進行快速舍棄，但判斷并不容易。而本文，特針對這種情形提出了一種十分有效的判斷算法。

1 中點區(qū)域法

1.1 算法介紹

本算法結(jié)合了傳統(tǒng)的區(qū)域編碼算法和中點算法的思路，通過判斷線段中點最終所在區(qū)域來判斷線段是否與矩形相交。

首先，將矩形四條邊延伸，劃分出“井”字形區(qū)域，取矩形外部的兩個方向上的對角區(qū)域為I1和I2，矩形內(nèi)部區(qū)域為II(包括矩形的邊界和四個頂點)，如圖2所示。

圖2 矩形所確定的“井”字形區(qū)域

圖3 k＞0時線段中點的區(qū)域判斷

當(dāng)直線段的斜率k＞0時，取被判斷線段AB的中點為M1，如圖3所示，可知點A、點M1完全位于矩形的同一側(cè)，即圖1中的線段a的情形，于是AM1段可以不用考慮。然后繼續(xù)取線段BM1的中點M2，同樣可知點B、點M2也完全位于矩形的同一側(cè)，于是再取線段M1M2的中點M3，此時點M3落在矩形的對角區(qū)域I1內(nèi)，便可以判斷線段AB與矩形不相交，可以快速舍棄。而對于線段CD，其中點N1落在矩形的內(nèi)部區(qū)域Ⅱ內(nèi)，此時便可以判斷線段CD與矩形相交，需要進行裁剪求交運算。

而對于斜率k＜0的情況，區(qū)別只是將I1區(qū)域換成I2區(qū)域，其他判斷方法及步驟均一樣，如圖4所示。取被判斷線段EF的中點為P1，可知點E、點P1完全位于矩形的同一側(cè)，即圖1中的線段a的情形，于是EP1段可以不用考慮。然后繼續(xù)取線段FP1的中點P2，同樣可知點F、點P2也完全位于矩形的同一側(cè)，于是再取線段P1P2的中點P3，此時點P3落在矩形的對角區(qū)域I2內(nèi)，便可以判斷線段EF與矩形不相交，可以快速舍棄。而對于線段GH，其中點Q1落在矩形的內(nèi)部區(qū)域II內(nèi)，此時便可以判斷線段GH與矩形相交，需要進行裁剪求交運算。

圖4 k＜0時線段中點的區(qū)域判斷

需要說明的是:本文在此省略掉對線段兩端點均落在矩形內(nèi)、線段一端點落在矩形內(nèi)以及線段兩端點落在矩形外的同一側(cè)和線段斜率等于0等情況的判斷，因為這些判斷都比較容易實現(xiàn)，本文只對圖1中b、c兩種情況做出判斷，即判斷出線段能夠快速舍棄或者是會與矩形相交。具體到普遍情況的程序算法步驟如圖5所示。

圖5 程序判斷流程圖

1.2 編程實驗

中點區(qū)域法耗時的主要部分是中點的計算，因此計算中點次數(shù)的多少是決定該算法效率高低的關(guān)鍵因素。為客觀地檢驗和評價該算法的性能，特設(shè)計如下實驗:在坐標(biāo)為(－1000，1000)的正方區(qū)域內(nèi)隨機生成1000萬條本文所討論的情形的線段，即線段兩端點位于矩形的不同側(cè)，然后與以原點(0，0)為中心、邊長為100的一正方形進行裁減判斷。實驗的輸出數(shù)據(jù)為:做每次判斷所需要計算中點的次數(shù)，并由此來評價該算法的效率和優(yōu)劣。

1.3 實驗結(jié)果及算法優(yōu)缺點分析

上述實驗在VC++中編譯完成，結(jié)果如圖6所示。

圖6 程序?qū)嶒灲Y(jié)果

由試驗數(shù)據(jù)可以看出，只需做1次到3次運算的概率接近75%，只需做1次運算的概率接近40%，而目前的一些快速舍棄判斷算法都至少需要做3次除法運算，雖然本算法有大于3次運算的情況，但從概率上說，本算法還是大大提高了裁減前快速舍棄判斷的效率。況且，本算法的運算均為除2運算，可以利用硬件由加法和位移實現(xiàn)，因此實際效率會有極大的提高。

2 結(jié)束語

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

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