基于適應(yīng)性相關(guān)測試和點(diǎn)斜式查表求交的圓形窗口快速裁剪方法

路 通， 蘇 豐， 楊若瑜

（南京大學(xué)計算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗室，江蘇 南京 210093）

裁剪算法是計算機(jī)圖形學(xué)的基礎(chǔ)性方法，速度更快的算法一直是研究者的不斷追求。在經(jīng)典的Cohen-Sutherland線段裁剪算法提出之后又出現(xiàn)了許多好的裁剪方法，它們在本質(zhì)上有兩個共同點(diǎn)：一是盡量避免無效的操作，二是盡量用簡單快捷的加、減等基本操作代替復(fù)雜、耗時的乘、除及開方等操作。例如，Liang-Barsky[1]方法通過正確選擇相對于待裁剪線段的窗口矩形始、終邊來簡化判定；Nicholl–Lee-Nicholl[2]方法通過比較待裁剪線段的斜率和始點(diǎn)到矩形窗口各頂點(diǎn)連線斜率，來確定需求交的窗口邊，以便避免無效的求交操作；Devai[3]方法對 Nicholl–Lee-Nicholl方法作了一定的改進(jìn)；Duvanenko-Robbins-Gyurcsik[4]方法通過優(yōu)化算法、減少冗余比較與浮點(diǎn)數(shù)運(yùn)算等來提高裁剪效率；Wang-Wu-Cai[5]方法通過將待裁剪線段簡單變換，使其始點(diǎn)位于特定區(qū)域，從而明確應(yīng)求交的窗口邊來加速處理；Lu-Wu-Peng[6]提出了基于待裁剪線段位置和方向的排除方法；針對圓形窗口也提出了一些裁剪方法[7-10]。但對于圓形窗口如何在排除性測試和線-圓求交等環(huán)節(jié)避免或減少大量的復(fù)雜操作，仍然是有待進(jìn)一步研究的問題。

圓形窗口對線段的裁剪有眾多應(yīng)用需求，如在智能CAD系統(tǒng)的交互式圖形界面中，需要實(shí)時移動“圓形放大鏡”或“鷹眼”作快速圖元檢查或檢索；在圖形識別與理解等復(fù)雜圖形應(yīng)用系統(tǒng)中，需要快速計算圓與其它各圖元間的精確幾何或拓?fù)浼s束；以及在實(shí)時繪制時需對圖元進(jìn)行消除隱藏線的處理等。在上述系統(tǒng)中，圖元數(shù)量一般比較大、圖元間幾何或拓?fù)潢P(guān)系分析的計算復(fù)雜度較高，且實(shí)時交互與繪制的要求高，因此設(shè)計新的快速圓形窗口裁剪算法顯得尤為重要。

一個好的圓形窗口裁剪方法應(yīng)該盡快、盡多地快速排除完全在圓外的線段；有效地保留完全在圓內(nèi)的線段；對必須與圓求交的線段應(yīng)快速求出交點(diǎn)。本文給出圓形窗口對線段的一種快速裁剪算法。該算法由基于適應(yīng)性切線分隔的圓外線段快速測試方法、基于最小范圍的圓內(nèi)線段測試方法和基于點(diǎn)斜式查表的線段與窗口圓快速求交方法組成?；谶m應(yīng)性切線分隔的圓外線段快速測試方法利用待裁剪線段相對于圓的位置，選擇相關(guān)切線進(jìn)行外側(cè)測試，以決定是否排除該線段；基于最小范圍的圓內(nèi)線段測試方法僅對位于窗口圓包圍盒之內(nèi)的線段實(shí)施包含性測試；基于點(diǎn)斜式查表的直線與圓的快速求交方法利用“從不同半徑圓的坐標(biāo)軸上離原點(diǎn)按半徑比例位置的點(diǎn)出發(fā)的相同斜率的兩條直線，與各自的圓的交點(diǎn)坐標(biāo)也成比例”這樣一個規(guī)律，將二元二次方程組求解改用直線與坐標(biāo)軸的一次特殊求交及查表來實(shí)現(xiàn)。

1 基于切線分隔的圓外線段快速測試規(guī)則

1.1 圓外線段的定義及判定

定義1線段上所有點(diǎn)均在圓外的線段稱為圓外線段。

因為不可能窮盡測試每一個點(diǎn)，所以不能直接按定義1進(jìn)行圓外線段的判定。但由于垂足是圓心到線段所在直線的最近點(diǎn)，只要垂足在圓外就能保證線段為圓外線段。當(dāng)垂足在線段的延長線上時，離垂足近的端點(diǎn)是線段上離圓心最近的點(diǎn)。因此，這兩類圓外線段分別用下列2個條件來判定：

條件1 圓心到線段的距離大于圓的半徑；

條件2 兩端點(diǎn)都在圓外且圓心到線段的垂足在線段延長線上。

由于上述2個條件涉及的二次方程組求解操作過于耗時，其中第1類圓外線段的判定時間為6Tbas+5Tmul+1Tdiv，第 2類的判定時間為 18Tbas+11Tmul+3Tdiv（Tbas、Tmul、Tdiv分別為一次加減、乘法、除法的操作時間）。因此，作為好的裁剪算法必需尋找更快的判定方法。

實(shí)際上，圓外線段還可以這樣定義：

定義2如果存在一條直線，它可將線段和圓分隔在它的兩側(cè)，則該線段為圓外線段。

判定圓是否在某直線一側(cè)的問題實(shí)際上也是圓外線段判定問題。而如果某直線是圓的切線，則“圓在該直線的一側(cè)”自然成立。剩下的只需判定待裁剪線段（的兩個端點(diǎn)）是否在該切線的外側(cè)。

因此，上述兩個判別條件可以合并成1個：

條件如果兩端點(diǎn)都在圓的某一切線的外側(cè)，則該線段完全在圓外。

1.2 基于切線外側(cè)測試的圓外線段排除規(guī)則

為了便于敘述，本文設(shè)線段兩端點(diǎn)為P1(x1,y1),P2(x2,y2)，約定坐標(biāo)原點(diǎn)在裁剪窗口圓的圓心。

1.2.1 基于水平或垂直切線外側(cè)測試的規(guī)則

垂直或水平切線的外側(cè)測試是最簡單的操作，每邊僅需進(jìn)行2次坐標(biāo)比較，且可排除的線段在所有待裁剪線段中占有較大比例。有下列圓外線段排除規(guī)則：

規(guī)則1如果x1>=R∧x2>=R，則可排除該線段，（圖 1-a）。

規(guī)則2如果x1<=-R∧x2<=-R，則可排除該線段（圖1-b）。

規(guī)則3如果y1>= R∧y2>= R，則可排除該線段（圖1-c）。

規(guī)則4如果y1<=-R∧y2<=-R，則可排除該線段（圖1-d）。

圖1 基于切線分隔的圓外線段排除

1.2.2 基于斜率為±1的切線外側(cè)測試的規(guī)則

斜率為±1的切線外側(cè)排除測試也是較簡單的操作，且可排除的情況也占有很大比例。設(shè)a=(21/2)*R，（此值對一個窗口圓只需計算一次，由所有待裁剪線段共享，故可視為常數(shù)），有下列圓外線段排除規(guī)則：

規(guī)則 5如果(x1-a)≥-y1∧(x2-a)≥-y2，則可排除該線段（圖1-e）。

規(guī)則 6如果(x1+a)≤-y1∧(x2+a)≤-y2，則可排除該線段（圖1-f）。

規(guī)則 7如果(x1+a)≤y1∧(x2+a)≤y2，則可排除該線段（圖1-g）。

規(guī)則 8如果(x1-a)≥y1∧(x2-a)≥y2，則可排除該線段（圖1-h）。

1.2.3 基于斜率為±0.5的切線外側(cè)測試的規(guī)則

設(shè)b=(51/2)R，與“a”一樣可視為窗口常數(shù)。針對斜率為±0.5的切線，可有如下規(guī)則：

規(guī)則 9如果(x1-b)≥-2y1∧(x2-b)≥-2y2，則可排除該線段（圖1-i）。

規(guī)則 10如果(x1+b)≤-2y1∧(x2+b)≤-2y2，則可排除該線段（圖1-j）。

規(guī)則 11如果 (x1+b)≤2y1∧(x2+b)≤2y2，則可排除該線段（圖1-k）。

規(guī)則 12如果 (x1-b)≥2y1∧(x2-b)≥2y2，則可排除該線段（圖1-l）。

1.2.4 基于斜率為±2的切線外側(cè)測試的規(guī)則

常數(shù)b與上同，針對斜率為±2的切線，則可有如下規(guī)則：

規(guī)則 13如果 2x1≥-(y1-b)∧2x2≥-(y2-b)，則可排除該線段（圖1-m）。

規(guī)則 14如果 2x1≤-(y1+b)∧2x2≤-(y2+b)，則可排除該線段（圖1-n）。

規(guī)則 15如果 2x1≤(y1-b)∧2x2≤(y2-b)，則可排除該線段（圖1-o）。

規(guī)則 16如果 2x1≥(y1+b)∧2x2≥(y2+b)，則可排除該線段（圖1-p）。

1.2.5 基于與線段斜率平行的切線外側(cè)測試的規(guī)則

對線段所在直線與圓不相交的圓外線段，還可用與之平行的兩條切線來排除。設(shè)線段斜率為t，則與其平行的兩條切線與Y軸交點(diǎn)的y坐標(biāo)分別為±R*(1+t2)1/2；因此，如果線段與Y軸交點(diǎn)不在上述兩點(diǎn)連線之內(nèi)，則可排除。為了避免“無窮大”，分兩種情況：

規(guī)則 17如果|x2-x1|<|y2-y1|，t=(x2-x1)/(y2-y1)，當(dāng) xinter=x1-t*y1滿足(xinter2≥R2*(1+t2))時，則可排除該線段（圖1-q）；

規(guī)則 18如果|x2-x1|≥|y2-y1|，t=(y2-y1)/(x2-x1)，當(dāng) yinter=y1-t*x1滿足(yinter2≥R2*(1+t2))時，則可排除該線段；

1.2.6 基于線段近圓端點(diǎn)到圓心連線與圓的交點(diǎn)處切線外側(cè)測試的規(guī)則

對于兩端點(diǎn)都在圓外、且都在圓心到該線段垂線一側(cè)的圓外線段，其所在直線可能與圓相交，也可能不相交。這一類圓外線段可如下判定：設(shè)始點(diǎn)為近圓端點(diǎn)，在始點(diǎn)到圓心連線與圓的交點(diǎn)處作切線，再過始點(diǎn)作平行于該切線的直線，如果終點(diǎn)在該直線外側(cè)，必定也在與其平行的切線外側(cè)，則線段在圓外。

始點(diǎn)到圓心連線的斜率為-(x1/y1)，過始點(diǎn)且平行于始點(diǎn)到圓心連線與圓的交點(diǎn)處切線的直線方程為(x-x1)x1+(y-y1)y1=0，終點(diǎn)在其外側(cè)的判別式為 x1x2+y1y2-x12-y12≥0。始點(diǎn)和終點(diǎn)對調(diào)的情況類似。

規(guī)則 19如果則可排除該線段（圖1-r）。

規(guī)則 20 如果 x1x2+y1y2≥x22+y22≥R2，則可排除該線段。

2 適應(yīng)性排除與保留算法

上述規(guī)則中的每一條均有自己的覆蓋范圍，并需數(shù)量不等的操作。雖然按一定順序使用這些規(guī)則能將所有圓外線段判定出來，但整體效率可能不是最高。高效的方法必須做到：

1）對有希望判定為圓外的線段，盡量選擇針對性的、操作簡單的少量規(guī)則來測試；

2）對可能是圓內(nèi)的線段才進(jìn)行包含性測試；

3）對與圓相交的線段，盡早肯定，避免做無效的排除性測試操作。

本文的適應(yīng)性圓外線段排除與圓內(nèi)線段保留算法按以下幾點(diǎn)進(jìn)行。

2.1 第1階段：適應(yīng)線段始點(diǎn)位置的垂直/水平切線排除測試

圖2給出了使用圓的水平、垂直切線將線段定義范圍各分成3個垂直“片”和水平“片”、交叉分成9個“區(qū)”的方式。規(guī)則1～4中的每條只有在 2個條件都滿足情況下才能確定圓外線段，只要第1個條件不滿足，就沒有必要測試第2個條件。因此，本文在逐步判定始點(diǎn)所在的“片”位置的過程中，選擇適應(yīng)的規(guī)則來判定圓外線段，以便避免盲目測試造成的時間浪費(fèi)。例如，一旦測試確定始點(diǎn)在“x1≥R片”，就選擇規(guī)則1，如滿足則判定線段為圓外線段并結(jié)束第1階段測試；如不滿足，也不再對是否滿足x1≤-R進(jìn)行測試，而是接下來對始點(diǎn)的y1坐標(biāo)測試。如果始點(diǎn)在“y1≥R片”，就選擇規(guī)則 3，如規(guī)則3滿足則判定線段為圓外線段并結(jié)束第1階段測試；如不滿足，也結(jié)束第1階段測試，因為此時已明確始點(diǎn)在3區(qū)而終點(diǎn)只可能在4、5、7或8區(qū)。

在上述適應(yīng)線段始點(diǎn)位置的垂直/水平切線測試方法中，8種可成功判定一條圓外線段的情況中最少花費(fèi)2次、最多6次、平均4.25次比較操作時間(4.25Tbas)；而9種可確定第1階段無法排除待測線段的情況中則最少花費(fèi)4次、最多6次，平均4.56次比較操作時間(4.56Tbas)。

2.2 第1階段的后處理-分析余下的待測線段終點(diǎn)的區(qū)域位置

線段兩端點(diǎn)相對于圓的位置是進(jìn)一步在第2階段中選擇相適應(yīng)規(guī)則的主要依據(jù)。對于不能在第一階段被判定為圓外的線段而言，其始點(diǎn)所在區(qū)域已確定，終點(diǎn)的可能范圍也已清楚。比如，當(dāng)始點(diǎn)在1區(qū)時，終點(diǎn)只能位于5、6、8、9區(qū)之一。因此，稍加處理（平均時間為 2.57Tbas）即可獲得線段終點(diǎn)的區(qū)域位置。

2.3 第2階段：適應(yīng)兩端點(diǎn)位置組合的斜切線排

除測試和最小范圍的圓內(nèi)線段保留測試

第2階段中，由于線段始、終點(diǎn)的區(qū)域位置已明確，可根據(jù)位置組合先選擇規(guī)則5 ～8中適合的一條規(guī)則測試，必要時再選擇規(guī)則 9 ～16中適合的一條規(guī)則測試。例如，兩端點(diǎn)位置分別在1區(qū)和6區(qū)時，絕對不會滿足規(guī)則6 ～8中任一條，因而只需使用規(guī)則5。按兩端點(diǎn)位置組合分別有如下處理：

1）“兩端點(diǎn)”為2-8或4-6，線段與圓相交，直接進(jìn)入求交處理①（端點(diǎn)組合不計方向，如“2-8”包括從2到8和從8到2）；

2）“兩端點(diǎn)”都在5區(qū)，圓面積占5區(qū)的78.53%，即始、終點(diǎn)在圓內(nèi)的概率各為78.53%，線段是圓內(nèi)線段的概率為61.67%。本文僅在這個“最小的范圍”中進(jìn)行圓內(nèi)線段測試，有助于提高整體效率。設(shè)則可分下列情況處理：

（1）如果(d1≤R2)&(d2≤R2)，則線段為圓內(nèi)，加以保留(圖3-e)；

（2）如果((d1R2))∨((d1>R2)&(d2< R2))，則線段與圓相交，進(jìn)入求交處理①(圖3-f )；

（3）其它情況下：

① 如果兩端點(diǎn)在不同象限，則線段與圓相交，進(jìn)入求交處理① (圖3-g)；

② 如果兩端點(diǎn)在同一象限，則按象限選擇使用相關(guān)規(guī)則：第一象限使用規(guī)則5；第2象限使用規(guī)則7；第3象限使用規(guī)則6；第4象限使用規(guī)則8。若滿足，是圓外線段(圖3-h)；如所用規(guī)則中兩個條件均不滿足，則當(dāng)兩端點(diǎn)在所在象限平分線（如第1象限的x=y）兩側(cè)時可確定線段與圓相交，進(jìn)入求交處理①；在平分線同側(cè)時、以及如兩個條件中只有一個滿足時，還可能是圓外線段，需進(jìn)入第3階段②繼續(xù)測試；

3）只有1個端點(diǎn)在5區(qū)，由于在5區(qū)的端點(diǎn)在圓內(nèi)的概率為78.53%，如果確定在圓內(nèi)，則線段與圓相交，不必再進(jìn)行圓外測試。因此，先對在5區(qū)的端點(diǎn)進(jìn)行圓的包含性測試比較有利。設(shè)在5區(qū)的端點(diǎn)號為i，d= xi2+yi2，則可分別處理如下：

（1）如果d

（2）如果d=R2，該端點(diǎn)在圓上，則按其所在象限號(Ⅰ、Ⅱ、Ⅲ、或Ⅳ)與另一端點(diǎn)所在區(qū)域的組合選擇處理如下：

① “Ⅰ-3”、“Ⅱ-1”、“Ⅲ-7”、“Ⅳ-9”時，線段為圓外線段，可排除；

② “Ⅰ-1”、“Ⅰ-2”、“Ⅰ-6”、“Ⅰ-9”、“Ⅱ-2”、“Ⅱ-3”、“Ⅱ-4”、“Ⅱ-7”、“Ⅲ-1”、“Ⅲ-4”、“Ⅲ-8”、“Ⅲ-9”時，還可能是圓外線段，進(jìn)入第3階段3）；

③ 其他組合時，線段與圓相交，進(jìn)入求交處理① (圖3-m)；

（3）如果 d >R2，該端點(diǎn)在圓外，則按其所在象限號與另一端點(diǎn)所在區(qū)域的組合選擇處理如下：

① “Ⅰ-3”、“Ⅱ-1”、“Ⅲ-7”、“Ⅳ-9”時，線段為圓外線段，可排除(圖3-j)；

② “Ⅰ-1”、“Ⅰ-2”、“Ⅰ-6”、“Ⅰ-9” 時，使用規(guī)則 5；“Ⅱ-2”、“Ⅱ-3”、“Ⅱ-4”、“Ⅱ-7”時，使用規(guī)則 7；“Ⅲ-1”、“Ⅲ-4”、“Ⅲ-8”、“Ⅲ-9”時，使用規(guī)則 6；“Ⅳ-3”、“Ⅳ-6”、“Ⅳ-7”、“Ⅳ-8”時，使用規(guī)則8；若滿足，是圓外線段(圖3-k)；如所用規(guī)則中兩個條件均不滿足，則當(dāng)兩端點(diǎn)在所在象限平分線（如第1象限的x=y）兩側(cè)時可確定線段與圓相交（圖3-l），進(jìn)入求交處理①；在平分線同側(cè)時、以及如兩個條件中只有一個滿足，則還可能是圓外線段，進(jìn)入第3階段③；

③ 其他組合時，線段與圓相交，進(jìn)入求交處理① (圖3-m)；

4）“兩端點(diǎn)”為 1-6、2-6、或 2-9，使用規(guī)則5；“兩端點(diǎn)”為1-8、4-8、或4-9，使用規(guī)則6；“兩端點(diǎn)”為4-2、4-3、或7-2，使用規(guī)則7；“兩端點(diǎn)”為7-6、8-6、或8-3，使用規(guī)則8；按測試結(jié)果分別處理：

（1）若兩個條件都滿足，則線段是圓外線段(圖3-a)；

（2）若兩個條件都不滿足，則線段與圓相交，進(jìn)入求交處理① (圖3-b)；

（3）若兩個條件中只有一個滿足，線段還可能是圓外線段而需繼續(xù)使用規(guī)則9 ～16中的一條測試。比如，當(dāng)使用規(guī)則5時兩個條件中只有一個滿足時，如滿足條件的端點(diǎn)在右邊時，再使用規(guī)則9；當(dāng)滿足條件的端點(diǎn)在左邊時，再使用規(guī)則13。然后再按測試結(jié)果分別處理如下：

① 若兩個條件都滿足，則線段是圓外線段(圖3-c)；

② 若兩個條件都不滿足，則線段與圓相交，進(jìn)入求交處理①(圖3-d)；

③ 若兩個條件中只有一個滿足，線段還可能是圓外線段，需進(jìn)入第3階段①；

5）“兩端點(diǎn)”為 1-9時，先使用規(guī)則 5，按測試結(jié)果分別處理：

（1）若兩個條件都滿足，則線段是圓外線段；

（2）若兩個條件中只有一個滿足，則按滿足條件的端點(diǎn)在右邊時再使用規(guī)則9，在左邊時使用規(guī)則13，然后再按測試結(jié)果分別處理：

① 若兩個條件都滿足，則線段是圓外線段；

② 若兩個條件都不滿足，則線段與圓相交，進(jìn)入求交處理①；

③ 若兩個條件中只有一個滿足，線段還可能是圓外線段，需進(jìn)入第3階段①

（3）若兩個條件都不滿足，再使用規(guī)則6；按測試結(jié)果分別處理：

① 若兩個條件都滿足，則線段是圓外線段；

② 若兩個條件都不滿足，則線段與圓相交，進(jìn)入求交處理①；

③ 若兩個條件中只有一個滿足，則按滿足條件的端點(diǎn)在右邊時再使用規(guī)則14，在左邊時使用規(guī)則10，然后再按測試結(jié)果分別處理：

a) 若兩個條件都滿足，則線段是圓外線段；

b) 若兩個條件都不滿足，則線段與圓相交，進(jìn)入求交處理①；

c) 若兩個條件中只有一個滿足，線段還可能是圓外線段，進(jìn)入第3階段①。

6）“兩端點(diǎn)”為3-7時，參照1-9方法類似地處理。

在本階段處理中，不同的“兩端點(diǎn)”組合對應(yīng)的程序分支花費(fèi)不同的時間。最少的是2-8和4-6組合，直接進(jìn)入求交處理，花費(fèi)時間為0；兩端點(diǎn)中都不在 5區(qū)時，使用規(guī)則 5 ～8之一花費(fèi)4Tbas，若還需使用相應(yīng)的規(guī)則 9 ～16之一，則在利用已有計算結(jié)果的前提下，再花 4Tbas，平均6Tbas。5-5組合測試是否為圓內(nèi)線段花費(fèi)時間為4Tbas+4Tmul。按各種組合的線段數(shù)平均分布的假設(shè)（實(shí)際上5-5和5-X組合概率會較?。?，再加上按端點(diǎn)區(qū)域的程序分支時間(2Tbas)，每條線段在本階段的平均處理時間為8.55Tbas+0.73Tmul。

圖3 按兩端點(diǎn)的區(qū)域位置選擇測試規(guī)則

2.4 第3階段：適應(yīng)線段方向及位置的切線排除測試

進(jìn)入第3階段處理的有3種情況：① 可按線段“斜率”選用規(guī)則17或18中的一條測試，如滿足則為圓外線段；如不滿足則進(jìn)入求交處理；② 比較d1和d2可明確哪個是近圓端點(diǎn)，然后用規(guī)則19和20之一測試，滿足即確定為圓外線段，不滿足時再用規(guī)則17或18中的一條測試；③ 在5區(qū)的端點(diǎn)是近圓端點(diǎn)，先用規(guī)則19、20中對應(yīng)的一條測試，不滿足時再用規(guī)則17或18中的一條測試。最終還不能排除時，該線段一定與圓相交，進(jìn)入求交處理②。

對于情況②，x12+y12或x22+y22已在第2階段中求得，且均符合“≥R2”。將 d1和 d2比較及使用規(guī)則19或20之一共需時間3Tbas+2Tmul。對于情況③，作為近圓端點(diǎn)的在5區(qū)的點(diǎn)坐標(biāo)已求得“x2+y2”，且符合“≥R2”。因此，按“情況①線段數(shù)=4*（情況②+情況③）線段數(shù)”的假設(shè)，第3階段每條線段平均處理時間為 6.75Tbas+4Tmul+0.8Tdev。

3 基于點(diǎn)斜式查表的線段與窗口圓的快速求交方法

3.1 直線和圓的點(diǎn)斜式查表求交原理

圖4中兩個半徑不同的圓在各自坐標(biāo)系定義，兩條線段的斜率相同，它們分別與兩個圓的Y軸相交，且交點(diǎn)各自的y坐標(biāo)與兩圓半徑成比例。只要其中一條線段與相關(guān)圓的交點(diǎn)坐標(biāo)已知，就可按半徑比例計算出另一線段與其相關(guān)圓的交點(diǎn)坐標(biāo)?；诖死?，可給出如下定理：

定理 從不同半徑圓的對應(yīng)坐標(biāo)軸上離原點(diǎn)按半徑成比例位置的點(diǎn)出發(fā)的斜率相同的兩條直線，與各自的圓相交時的交點(diǎn)坐標(biāo)也按半徑成比例。

如果左邊是一個半徑固定的規(guī)范化圓，事先將其坐標(biāo)軸上每一點(diǎn)引出各種不同斜率的直線與圓的交點(diǎn)坐標(biāo)計算好并制備一張兩維的線-圓交點(diǎn)表（針對保證直線與圓有交點(diǎn)的坐標(biāo)軸點(diǎn)和斜率的組合），則對右邊任意半徑的圓和直線的求交處理，可通過將直線與其坐標(biāo)軸的交點(diǎn)坐標(biāo)比例變換到規(guī)范化圓的坐標(biāo)系中，從線-圓交點(diǎn)表中查獲直線與規(guī)范化圓的交點(diǎn)坐標(biāo)，并逆比例變換回原來坐標(biāo)系中來獲得直線和圓的交點(diǎn)。這樣，線段與圓的求交工作避免了求解二元二次方程組的工作，減少了計算時間。

3.2 線-圓交點(diǎn)表的組織

令規(guī)范化圓的半徑為 256，針對斜率從 0、1/256、2/256、…、255/256共256種，Y坐標(biāo)軸上 y =0、1、2、…、362 共 363 個點(diǎn)是斜率小于等于1且與規(guī)范化圓相交的直線和Y軸交點(diǎn)坐標(biāo)最大值），建立一張二維的線-圓交點(diǎn)表2；針對斜率為1，Y坐標(biāo)軸上y =0、1、2、…、362共363個點(diǎn)，再建立一張一維的線-圓交點(diǎn)表1。兩張表的表項內(nèi)容一致，包含4個數(shù)據(jù)：這 4個數(shù)據(jù)分別為規(guī)范化圓和相應(yīng)直線的2個交點(diǎn)的坐標(biāo)。表1在斜率為1時使用ynor=0、1、2、…、362查詢；表2使用ynor=0、1、2、…、362之一和與斜率為0、1/256、2/256、…、255/256對應(yīng)的tnor=0、1、2、…、255之一來查詢。

在字節(jié)編址條件下，設(shè)4個交點(diǎn)坐標(biāo)均為2字節(jié)整數(shù)，則表1通過 Left_Shift3bits(ynor)即可形成訪問 8字節(jié)表項內(nèi)容的邏輯地址；而Left_Shift11bits(ynor)+Left_Shift3bits(tnor)則形成了表2的8字節(jié)表項的邏輯地址，因而查表速度很快。

將各種對應(yīng)不同的點(diǎn)-斜率組合的直線與圓的交點(diǎn)事先計算并存入表中相應(yīng)位置。這2張線-圓交點(diǎn)表即可供任意圓中線-圓求交時使用。

3.3 基于點(diǎn)斜式查表的線段與窗口圓的快速求交

進(jìn)入求交處理的線段肯定與圓有交點(diǎn)。其中，從“進(jìn)入求交處理②”進(jìn)入的線段已經(jīng)過規(guī)則17或18的測試(但失敗)。因此，(t,yinter)或(t,xinter)已求出；為了在求交時可直接使用上述數(shù)據(jù)，以便節(jié)省時間，在不改變實(shí)質(zhì)的前提下，將規(guī)則17或18修改為：

圓外線段排除規(guī)則 17：如果|x2-x1|<|y2-y1|，計算 t=Left_Shift8bits(x2-x1)/(y2-y1)，當(dāng) d= Left_Shift8bits(x1)-t*y1滿足 d2≥R2*(2562+t2)時，可排除；

圓外線段排除規(guī)則18：如果|x2-x1|≥|y2-y1|，計算 t=Left_Shift8bits(y2-y1)/(x2-x1)，當(dāng) d=Left_滿足時，可排除；

修改后的規(guī)則使用時雖然比原來多做2次左移8位的操作，但從而可避免實(shí)數(shù)除法和乘法，全部用整數(shù)運(yùn)算，其時間反而節(jié)省。

如果對從“進(jìn)入求交處理①”進(jìn)入的線段補(bǔ)求規(guī)則17或18中的(t,d)，則基于點(diǎn)斜式查表的線段與窗口圓的快速求交可由下列步驟接著完成：

1）求 tnor：tnor=|t|；（|t|即 t的絕對值）；

2）求 ynor：ynor=|d|/R；（整數(shù)除法）；

3）查表：如果tnor=256，使用ynor查表1；否則，使用 ynor和 tnor查表 2；獲 xi1nor、yi1nor、xi2nor、yi2nor；

4）規(guī)范化逆變換：xi1=Right_Shift8bits

5）生成原坐標(biāo)系坐標(biāo)：由于利用了圓的對稱性，正、負(fù)斜率及交點(diǎn)在坐標(biāo)軸負(fù)半軸上等各情況都按圖5中指定方式變換后，按線段所在直線斜率在[0-1]范圍、及與Y軸正半軸有交點(diǎn)的情況查表，因此，所得直線與圓的交點(diǎn)必須按表1所示進(jìn)行逆變換，將規(guī)范化逆變換所得坐標(biāo)(xi,yi)還原到原坐標(biāo)系中的坐標(biāo)(xo,yo)。

圖5 線段斜率及其和坐標(biāo)軸交點(diǎn)位置的各種不同組合時使用“點(diǎn)斜式查表求交”前的變換

（除第1個外，實(shí)線為原線段，虛線為查表所用線段）

表1 生成原坐標(biāo)系坐標(biāo)的變換方法

有效性檢查：如果|x2-x1|≥|y2-y1|，將Po1(xo1,yo1)、Po2(xo2,yo2)、P1、P2從左往右排序；如果|x2-x1|<|y2-y1|，將 Po1(xo1,yo1)、Po2(xo2,yo2)、P1、P2從下往上排序。中間兩點(diǎn)之間的線段為裁剪結(jié)果。

上述查表求交處理平均需要時間12Tbas+4Tmul+1Tdiv；對從第2階段“進(jìn)入求交處理①”進(jìn)入的線段補(bǔ)求(t,d )的時間可與第 3階段處理時間抵消，故不計入。

4 裁剪算法分析和實(shí)驗

4.1 線段隨機(jī)分布實(shí)驗

算法效率的高低除了與算法中涉及的操作類型和次數(shù)有關(guān)外，還與待裁剪線段的隨機(jī)分布位置有關(guān)。表2給出了本文方法對在中心位于坐標(biāo)原點(diǎn)、邊長為 1440的正方形范圍內(nèi)隨機(jī)生成的100000條線段，用圓心位于坐標(biāo)原點(diǎn)的5種半徑的窗口圓進(jìn)行裁剪處理的情況分類統(tǒng)計。

表2 100,000條隨機(jī)線段在幾個不同大小的圓形窗口時的處理分類實(shí)驗數(shù)據(jù)

4.2 算法效率對比分析

由于參考文獻(xiàn)[7]用圓形窗口對拋物線裁剪，在對線段裁剪的參考文獻(xiàn)中，參考文獻(xiàn)[10]的方法比[8-9]的方法均好，因此本文方法僅和文獻(xiàn)[10]的方法進(jìn)行比較。先從算法上對比，再給出實(shí)驗比較。算法上的對比有助于對實(shí)驗數(shù)據(jù)差別的理解。

文獻(xiàn)[10]在排除圓外線段方面采用三重編碼，即3個階段；本文與此類似，也分3個階段。

1）第1階段測試

在第 1階段，文獻(xiàn)[10]使用了Cohen-Sutherland編碼算法，通過將兩端點(diǎn)與窗口圓的正則外切正方形的4條邊所在直線進(jìn)行比較，計算待測線段2端點(diǎn)的2組第1類4位區(qū)域編碼，然后將兩組區(qū)域碼進(jìn)行“與”操作，若結(jié)果非全“零”，線段可排除；而本文在判定始點(diǎn)位置過程中按始點(diǎn)位置選擇垂直、水平切線中適應(yīng)的有關(guān)切線進(jìn)行比較，一旦確認(rèn)兩端點(diǎn)同在某條切線外側(cè)，即可排除線段。

文獻(xiàn)[10]必須在對兩端點(diǎn)區(qū)域編碼生成并操作后才得到能否排除的結(jié)論，每一位編碼的平均生成時間為2.5 Tbas，加上編碼初始化及“與”操作，不管能否排除，每一條線段的平均處理時間為 12Tbas；而本文成功判定一條圓外線段時不必記錄其位置，將失敗判定時記錄始點(diǎn)位置及繼續(xù)判定終點(diǎn)位置時間考慮在內(nèi)，按表2所出排除率計算，本文第1階段對每條線段的平均處理時間是(9.24*34%+4.25*66%=)5.95Tbas。

2）第2階段測試

第1階段未能排除的線段必須進(jìn)行第2階段測試。在第 2階段，文獻(xiàn)[10] 使用旋轉(zhuǎn) 45°的Cohen-Sutherland算法，通過將兩端點(diǎn)與窗口圓的45°外切正方形的4條邊所在直線進(jìn)行比較，計算待測線段兩端點(diǎn)的第 2類兩組 4位區(qū)域編碼，然后將兩組區(qū)域碼進(jìn)行“與”操作，若結(jié)果非全“零”，線段可排除。不管能否排除，每一條線段的平均處理時間為 18Tbas；而本文方法與其不同點(diǎn)有：

（1）根據(jù)兩端點(diǎn)在水平、垂直切線所劃分的區(qū)域碼組合選擇不同的操作；有些組合直接進(jìn)入求交處理；需與±45°斜切線中比較的僅與其中合適的一條進(jìn)行比較，然后作出“線段在圓外”、“線段與圓相交”、或“再測試”的結(jié)論；

（2）“再測試”時根據(jù)兩端測試結(jié)果進(jìn)一步選用斜率為±2、±0.5切線中的相關(guān)的一條再測試，可排除更多的圓外線段（按表2數(shù)據(jù)，多排除全部線段中的5.78%）；

（3）對兩端點(diǎn)均在圓的包圍盒之內(nèi)時進(jìn)行是否為圓內(nèi)線段的判定；

（4）對眾多與圓相交的線段（按表 2，多達(dá)全部線段中的7.79%）及時判定，跳過第3階段，直接進(jìn)入求交處理。本文方法在第2端點(diǎn)的平均處理時間是8.55Tbas+0.73Tmul。

3）第3階段測試

如果前2個階段不能肯定線段為圓外線段，則必須進(jìn)行第3階段測試。按表2數(shù)據(jù)，本文方法下進(jìn)入第 3階段的線段數(shù)為全部線段中的9.24%，而文獻(xiàn)[10]為22.85%。

在第3階段，文獻(xiàn)[10]通過計算廣義距離編碼及某些后續(xù)操作后判定線段是否在圓外。每一端點(diǎn)的廣義距離編碼通過兩次乘除、兩次加減法獲得。對兩端點(diǎn)都在圓心到線段的垂線所在直線同一側(cè)的圓外線段共需判定時間為13Tbas+7Tmul；對兩端點(diǎn)在圓心到線段的垂線所在直線兩側(cè)的圓外線段共需判定時間為18Tbas+8Tmul+1Tdiv；兩類平均15.5Tbas+7.5Tmul+0.5Tdiv。

本文在第3階段對每條線段的平均處理判定時間為6.75Tbas+4Tmul+0.8Tdev。

4）圓內(nèi)線段的判定

如果線段兩個端點(diǎn)都在圓內(nèi)，則線段為圓內(nèi)線段。文獻(xiàn)[10]和本文都使用端點(diǎn)與圓心距離的平方與半徑平方相比來確定端點(diǎn)是否在圓內(nèi)。但是文獻(xiàn)[10]在第3階段才測試圓內(nèi)線段，而本文在第2階段就測試圓內(nèi)線段，且僅當(dāng)兩端點(diǎn)都在5區(qū)時才測試，成功率高。因此，圓內(nèi)線段被成功判定時，在兩種方法下所花費(fèi)的實(shí)際總時間差別很大。

5）線段和窗口圓的求交

文獻(xiàn)[10]在第3階段已計算廣義距離等參數(shù)的基礎(chǔ)上，再經(jīng) 2次減法運(yùn)算計算出方程At2+2Bt+C=0的3個系數(shù)，求解出參數(shù)t后再計算線段和窗口圓的交點(diǎn)坐標(biāo)，合計花費(fèi)17Tbas+6Tmul+1Tdiv+1Tsqrt，其中，Tsqtr為一次“開方”時間。

本文利用第 3階段己計算“交點(diǎn)”和“斜率”的基礎(chǔ)上，通過查表法計算兩個交點(diǎn)的坐標(biāo)，共需 15Tbas+4Tmul+1Tdiv。本文方法節(jié)省了 2次加減法、2次乘法和1次特別耗時的“開方”運(yùn)算時間。

6）整體效率

由于2種方法均包括3個排除處理階段和一個求交處理，每條線段的平均處理時間與各階段處理的線段數(shù)、處理時間有關(guān)，即

其中，Ni為每階段處理的線段數(shù)，Ti為每階段花費(fèi)的平均處理時間，T整體為每條線段平均處理時間。圖6給出了兩種方法前兩個階段用來排除圓外線段的切線集合。兩種方法在第 1、4兩個階段處理的線段數(shù)完全相同，而表2中“規(guī)則9 ～16排除的圓外線段數(shù)”、“保留的圓內(nèi)線段數(shù)”及 4類“進(jìn)入求交①的線段數(shù)”在文獻(xiàn)[11]中必須在第3階段完成排除，“2-8、4-6組合（進(jìn)入求交①）的線段數(shù)”跳過第2、3兩個階段，另外3項線段跳過第3階段進(jìn)入求交處理。每一階段中本文方法均比文獻(xiàn)[10]的方法明顯快，特別是第2階段和求交階段，因而整體效率本文會明顯高。

圖6 文獻(xiàn)[11]方法(左)和本文方法(右)分隔切線集合

4.3 算法效率對比實(shí)驗

表3給出了相應(yīng)的2種方法在幾個不同大小的圓形窗口下對100,000條隨機(jī)線段的處理時間及比較，使用的計算機(jī) CPU為 intel Pentium 43.00Ghz，內(nèi)存1GB。隨著窗口圓半徑的增大，本文方法的效率比文獻(xiàn)[10]越來越高，4.1節(jié)的實(shí)驗分類數(shù)據(jù)和4.2節(jié)的分析給出了其中的原因。

表3 兩種方法在幾個不同大小的圓形窗口下對100,000條隨機(jī)線段的處理時間對比實(shí)驗數(shù)據(jù)

本文方法應(yīng)用于建筑智能CAD[11-12]、圖形識別與理解[13-14]等系統(tǒng)中。在上述系統(tǒng)中，由于涉及的圖元數(shù)量多、圖元間幾何關(guān)系分析和圖形語義理解算法較為復(fù)雜、計算量大，而系統(tǒng)對實(shí)時交互響應(yīng)性能要求較高（如快速圖元檢索與定位、幾何約束查詢、通過鷹眼的交互式全圖遍歷等），采用包括AutoCAD等在內(nèi)的現(xiàn)有圖形軟件提供的裁剪算法并不滿足上述要求。應(yīng)用結(jié)果表明，采用本文所提出的快速圓形窗口裁剪算法，效率成倍提高。

由于本算法中多層次處理思想的引入，算法實(shí)現(xiàn)時的簡潔性、與底層圖形軟硬件接口的銜接需在進(jìn)一步工作中加以優(yōu)化。

5 結(jié) 束 語

本文為窗口圓定義了16條固定位置切線、6條隨機(jī)切線及2條隨機(jī)切線的平行線作為圓外線段的分隔線。根據(jù)端點(diǎn)位置選擇適應(yīng)的分隔切線，可快速確認(rèn)圓外線段、盡早肯定與圓相交的線段，提高了排除性測試效率；基于最小范圍的圓內(nèi)線段測試提高了包含性測試效率；基于點(diǎn)斜式查表的線段與窗口圓快速求交方法避免了復(fù)雜的開方操作；由于盡可能地選擇適應(yīng)的、操作簡單的、覆蓋率高的測試方法，盡可能避免或減少了復(fù)雜耗時的操作和無效的計算，保證了本文算法具有較高的效率。

進(jìn)一步的研究可包括圓形窗口對多邊形的裁剪、橢圓窗口對直線段的裁剪或多邊形的裁剪等。

[1] Liang Y D,Barsky B A. A new concept and method for line clipping [J]. ACM Transactions on Graphics,1984,3(1): 1-22.

[2] Nicholl T M,Lee D T,Nicholl R A. An effiecient new algorithm for 2-D line clipping: its development and analysis [J]. SIGGRAPH,1987,21(4): 253-292.

[3] Duvanenko V J,Robbins W E,Gyurcsik R S. Simple and efficient 2D and 3D span clipping algorithms [J].Computers and Graphics,1993,17(1): 39-54.

[4] Devai F. An analysis technique and an algorithm for line clipping [C]//Proc of the IEEE Symposium on Information Visualization,1998: 157-165.

[5] Wang H,Wu R,Cai S. A new algorithm for two-dimensional line clipping via geometric transformation [J]. Journal of Computer Science and Technology,1998,13(5): 410-416.

[6] Lu G,Wu X,Peng Q. An efficient line clipping algorithm based on adaptive line rejection [J].Computers & Graphics,2002,3(26): 409-415.

[7] Wu Q,Huang X,Han Y. A clipping algorithm for parabola segments against circular windows [J].Computers & Graphics,2006,30(4): 540-560.

[8] 沈慶云,周來水,周儒榮. 一種圓形窗口裁剪的新方法[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,1997,9(6):538-542.

[9] 姚涵珍,宋 鵬,張國安. 圓形窗口裁剪算法的研究與實(shí)踐[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,1992,(4): 14-20.

[10] 陸國棟,邢軍偉,譚建榮. 基于多重編碼技術(shù)的圓形窗口線裁剪算法[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2002,14(12): 1133-1137.

[11] 雷 璐,蘇 豐,蔡士杰. 建筑構(gòu)件參數(shù)化建模語言 PCML的設(shè)計與應(yīng)用[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2006,18(5): 687-693.

[12] 楊華飛,楊若瑜,路 通,等. 計算機(jī)輔助建筑結(jié)構(gòu)算量技術(shù)與軟件[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2007,19(6): 748-756.

[13] Lu T,Tai C L,Su F,et al. A new recognition model for electronic architectural drawings [J].Computer-Aided Design,2005,37(10): 1053-1069.

[14] Lu T,Tai C L,Yang H,et al. A novel knowledge-based system for interpreting complex engineering drawings:theory,representation and implementation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31(8): 1444-1457.