洪 燕 洪智化 劉 欣

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

0 引言

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

圖1 0矩形窗口線裁剪

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

1 中點(diǎn)區(qū)域法

1.1 算法介紹

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

首先，將矩形四條邊延伸，劃分出“井”字形區(qū)域，取矩形外部的兩個(gè)方向上的對(duì)角區(qū)域?yàn)镮1和I2，矩形內(nèi)部區(qū)域?yàn)镮I(包括矩形的邊界和四個(gè)頂點(diǎn))，如圖2所示。

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

圖3 k＞0時(shí)線段中點(diǎn)的區(qū)域判斷

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

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

圖4 k＜0時(shí)線段中點(diǎn)的區(qū)域判斷

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

圖5 程序判斷流程圖

1.2 編程實(shí)驗(yàn)

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

1.3 實(shí)驗(yàn)結(jié)果及算法優(yōu)缺點(diǎn)分析

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

圖6 程序?qū)嶒?yàn)結(jié)果

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

2 結(jié)束語

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

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