矢量圖形在非自交多邊形中的裁剪算法①

康耀龍,馮麗露,張景安,朱媛媛

1(山西大同大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,大同 037009)

2(山西大同大學(xué) 教育科學(xué)與技術(shù)學(xué)院,大同 037009)

3(山西大同大學(xué) 網(wǎng)絡(luò)信息中心,大同 037009)

在計(jì)算機(jī)輔助設(shè)計(jì)(Computer Aided Design,CAD)軟件中,用戶一般在模型空間繪制圖形,在布局空間打印出圖.由于工程圖需要從不同角度綜合反映工程模型的空間尺寸和幾何關(guān)系,例如主視圖、左側(cè)圖、俯視圖、局部詳圖等[1,2].在打印出圖時(shí),需要輸出模型空間所繪圖形的不同視圖.在CAD軟件的布局空間中,可以將任意閉合區(qū)域作為裁剪邊界(視口)輸出圖形,用戶只關(guān)注視口內(nèi)部的圖形[3–6].當(dāng)批量執(zhí)行矢量圖形的裁剪時(shí),裁剪算法的優(yōu)劣直接影響著工程圖形的生成效率.

1 矢量圖形在非自交多邊形邊界中的裁剪

矢量圖形是使用直線和曲線來(lái)描述的圖形,用戶視窗一般都為多邊形.當(dāng)需要裁剪掉用戶視窗外的圖形時(shí),其本質(zhì)就是直線或圓這兩種圖形和多邊形相交時(shí),裁剪掉多邊形外邊的直線或圓的部分[7].

任意線段和圓,與凸多邊形裁剪邊界相交時(shí)能夠正確裁剪的顯示.圖形在裁剪邊界外的部分不顯示,在裁剪邊界內(nèi)的部分正確顯示,如圖1所示.

圖1 線段、圓與凸多邊形裁剪

任意線段和圓,與凹多邊形裁剪邊界相交并且跨凹多邊形的優(yōu)角時(shí)能夠正確裁剪的顯示.圖形在裁剪邊界外的部分不顯示,在裁剪邊界內(nèi)的部分正確顯示,如圖2所示.

圖2 線段、圓與凹多邊形裁剪

2 矢量圖形在非自交多邊形邊界中裁剪的傳統(tǒng)算法

2.1 線段裁剪非自交多邊形傳統(tǒng)算法思路

線段與多邊形裁剪算法的基本思路是通過(guò)遍歷多邊形的每條邊使其分解為求線段與線段的交點(diǎn),利用直線的一般方程求解時(shí),得到的交點(diǎn)可能是線段與線段的交點(diǎn)也有可能是直線與直線的交點(diǎn)即所求解的交點(diǎn)位于線段的延長(zhǎng)線上,為了避免無(wú)效交點(diǎn)求解過(guò)程中時(shí)間和內(nèi)存的消耗,在求解交點(diǎn)之前進(jìn)行判斷,通過(guò)快速排斥實(shí)驗(yàn)和跨立實(shí)驗(yàn)篩選有交點(diǎn)的線段并求解交點(diǎn),利用列表對(duì)其進(jìn)行存儲(chǔ)[8,9].對(duì)列表中的點(diǎn)進(jìn)行排序,并通過(guò)依次遍歷列表中兩個(gè)點(diǎn),如果中點(diǎn)在多邊形內(nèi)部則進(jìn)行繪制,否則不繪制.

2.2 圓裁剪非自交多邊形傳統(tǒng)算法思路

圓相對(duì)于多邊形裁剪的關(guān)鍵是求出圓和多邊形每條邊的交點(diǎn).首先通過(guò)依次遍歷多邊形的每條邊將其分解為線段與圓的交點(diǎn),為了排除直線斜率的影響采用直線的一般方程與圓的一般方程進(jìn)行求解.在求解過(guò)程中,通過(guò)t的值是否在0和1的范圍內(nèi)進(jìn)行排除,在此范圍內(nèi)所求點(diǎn)即為線段與圓的交點(diǎn),否則交點(diǎn)在線段的延長(zhǎng)線上.在存點(diǎn)的過(guò)程中需要進(jìn)行判斷列表中是否已經(jīng)存在該點(diǎn),如果存在則不存入列表中,否則存入列表中.對(duì)所求交點(diǎn)同樣需要排序,并依次遍歷列表中的每個(gè)點(diǎn),采用判斷圓弧的中點(diǎn)坐標(biāo)是否在多邊內(nèi)部,如果在進(jìn)行繪制,否則不進(jìn)行繪制.

3 矢量圖形在非自交多邊形邊界中裁剪的改進(jìn)算法

3.1 改進(jìn)算法的思路

3.1.1 降低循環(huán)中冗余計(jì)算

在循環(huán)過(guò)程中如果使用j

(1) 直線中交點(diǎn)求解冗余

先判斷直線與多邊形的邊是否有交點(diǎn),當(dāng)存在交點(diǎn)的情況再對(duì)要裁剪的線段求解方程所需要的變量,如斜率和偏移量; 否則,不進(jìn)行計(jì)算,直接跳出本次循環(huán).

(2) 圓中交點(diǎn)求解冗余

在傳統(tǒng)的圓的求解交點(diǎn)算法中對(duì)多邊形某條邊線段變量A、B、C等的求解會(huì)在每一次的循環(huán)中進(jìn)行求解即使圓與線段無(wú)交點(diǎn)的情況下也會(huì)冗余進(jìn)行[12].解決方法:將這些變量的求解放到d(圓心到線段的距離)<=R(半徑)的判斷當(dāng)中,減少了當(dāng)不存在交點(diǎn)的情況的求解,減少時(shí)間消耗.

3.1.2 重用對(duì)象

在傳統(tǒng)算法中,對(duì)于需要裁剪的每一條線段的端點(diǎn)記錄都在每次循環(huán)時(shí)進(jìn)行重新新建,需要不斷的在堆內(nèi)存中開辟引用空間,浪費(fèi)時(shí)間還浪費(fèi)內(nèi)存的消耗.改進(jìn)算法定義一個(gè)函數(shù)的局部變量,開辟兩個(gè)Point點(diǎn)堆內(nèi)存空間,利用set和get方法對(duì)兩個(gè)Point對(duì)象進(jìn)行重新設(shè)置,以減少內(nèi)存和時(shí)間的消耗.

3.1.3 多線程控制

分別對(duì)直線裁剪、圓裁剪增加多線程.從直線、圓裁剪數(shù)量的一半進(jìn)行劃分,分別使用兩個(gè)線程同時(shí)進(jìn)行裁剪繪制.同時(shí)避免公用對(duì)象Graphics2D g2的混合使用.

3.2 線段裁剪非自交多邊形改進(jìn)算法

裁剪算法的描述如下:

Step 1.用intnPoints變量存儲(chǔ)多邊形的頂點(diǎn)數(shù)量,利用兩個(gè)一維整型數(shù)組分別存儲(chǔ)點(diǎn)的x,y坐標(biāo),實(shí)現(xiàn)二維數(shù)組的功能,并且設(shè)置標(biāo)志量flag1、flag2為true.

Step 2.獲取一條線段,判斷斜率是否存在,如果不存在設(shè)置標(biāo)志量flag2=false; 如果存在求解線段的斜率k2和b2.

Step 3.依次遍歷多邊形的每條邊,在每一次循環(huán)之前都將上一次用于存儲(chǔ)線段和多邊形的交點(diǎn)以及在多邊形內(nèi)部線段的頂點(diǎn)的列表plist清空,并且獲取當(dāng)前線段的坐標(biāo)封裝在類Line的對(duì)象line中.

Step 4.判斷斜率是否存在,如果不存在設(shè)置標(biāo)志量flag1=false; 如果存在求解該線段的k1,b1.

Step 5.判斷所獲取的兩條線段是否有交點(diǎn),如果無(wú)交點(diǎn)轉(zhuǎn)Step 11; 如果有交點(diǎn)轉(zhuǎn)Step 6.

Step 6.如果 (!flag1&&!flag2)或 (k1==k2&&flag1&&flag2)跳出本次循環(huán),轉(zhuǎn)Step 3; 否則求解交點(diǎn)坐標(biāo).

Step 7.當(dāng)所求交點(diǎn)坐標(biāo)中不含有該點(diǎn),則將交點(diǎn)存儲(chǔ)在列表中,否則不作處理,轉(zhuǎn)Step 3進(jìn)行下輪循環(huán),直到多邊形的每條邊都被遍歷完轉(zhuǎn)Step 8.

Step 8.分別判斷線段的兩個(gè)端點(diǎn)是否在多邊形內(nèi)部,如果在則存入列表中,不再不作處理,轉(zhuǎn)Step 2直到所有的線段都被求解完轉(zhuǎn)Step 9.

Step 9.對(duì)列表中的點(diǎn)進(jìn)行排序.

Step 10.依次遍歷列表中的點(diǎn),判斷兩點(diǎn)的中點(diǎn)坐標(biāo)是否在多邊形內(nèi)部,如果在則進(jìn)行繪制; 否則不進(jìn)行處理.

Step 11.結(jié)束.

3.3 圓裁剪非自交多邊形改進(jìn)算法

對(duì)于中點(diǎn)坐標(biāo)的求解采用Arc2D中弧線的類直接求中點(diǎn)坐標(biāo).

(1) 多邊形某條邊(線段)與圓求交點(diǎn)的算法思路

已知線段P1P2,端點(diǎn)坐標(biāo)為P1(x1,y1),P2(x2,y2),如圖3所示.則其方程為:

圓的方程為:

圖3 線段與圓求交點(diǎn)

由求點(diǎn)到直線的距離方法radiusTolines,可得到圓心(x0,y0)到P1P2的距離d.若d>r,則表明線段與圓沒(méi)有交點(diǎn),否則,討論交點(diǎn)求法.

P1P2的參數(shù)方程為:

將(3)代入(2)中,化簡(jiǎn)整理得:

其中,

(2) 圓與多邊形交點(diǎn)的排序算法

以圓心為原點(diǎn),以圓心左右兩邊區(qū)分所有交點(diǎn),按照順時(shí)針?lè)较蜻M(jìn)行排序.設(shè)圓心坐標(biāo)為p(x0,y0),其他點(diǎn)坐標(biāo)為(x,y),由于可執(zhí)行程序已經(jīng)進(jìn)行坐標(biāo)點(diǎn)的轉(zhuǎn)換,所以使得原點(diǎn)為框體右上角的頂點(diǎn),向下為y值增大方向分為2種情況:

(3) 判斷圓弧是否裁剪的算法

設(shè)Q1,Q2,…,Qk是多邊形與被裁減圓的所有交點(diǎn),并且進(jìn)行順時(shí)針?lè)较蚺判?對(duì)兩相鄰的交點(diǎn)Qi,之間的圓弧是否繪制,可采用中點(diǎn)檢測(cè)法(圓弧存在方向,即順時(shí)針?lè)较?.

根據(jù)Java中Arc2D的弧線類,通過(guò)Qi,Qi+1確定需要繪制的弧線參數(shù),通過(guò)類中方法,返回兩個(gè)點(diǎn)的夾角,并再次通過(guò)一個(gè)弧線類的對(duì)象,設(shè)置起始點(diǎn)和夾角來(lái)確定弧線的中點(diǎn)坐標(biāo)M3;

① 若M3在窗口外,圓弧QiQi+1被裁剪.

② 若M3在窗口內(nèi),圓弧QiQi+1被保留.

4 系統(tǒng)仿真實(shí)驗(yàn)及分析

為了更進(jìn)一步驗(yàn)證“矢量圖形在非自交多邊形邊界中裁剪的算法”正確性和算法的執(zhí)行效率、內(nèi)存消耗等問(wèn)題,模擬CAD軟件的布局空間中不同視口輸出圖形的顯示方式,選取對(duì)單個(gè)圓的凹多邊形裁剪和對(duì)百萬(wàn)級(jí)數(shù)量的直線、圓的凹多邊形裁剪.

(1) 系統(tǒng)仿真實(shí)驗(yàn)環(huán)境

系統(tǒng)仿真實(shí)驗(yàn)環(huán)境為3.2 GHz CPU,4 GB內(nèi)存,1 TB硬盤,64位的Windows 7操作系統(tǒng).實(shí)驗(yàn)由一個(gè)可執(zhí)行程序,通過(guò)讀取XML文件生成裁剪邊界和被裁剪的圖形,并且統(tǒng)計(jì)有多少個(gè)圖形與邊界相交(交點(diǎn)數(shù)),有多少個(gè)圖形在邊界內(nèi)部,有多少個(gè)圖形在邊界外部.

(2) 單個(gè)圓裁剪

對(duì)單圓的凹多邊形裁剪的執(zhí)行結(jié)果、算法執(zhí)行效率和內(nèi)存消耗如圖4所示,裁剪后圓在多邊形邊界外的部分不顯示,在多邊形邊界內(nèi)的部分正確顯示,單一數(shù)據(jù)驗(yàn)證算法的正確性.

圖4 對(duì)一個(gè)單圓的裁剪

(3) 百萬(wàn)級(jí)數(shù)量的線段和圓裁剪

為測(cè)試算法的通用性,選取不同隨機(jī)斜率下的線段和區(qū)域內(nèi)不同隨機(jī)原點(diǎn)不等半徑下的圓進(jìn)行凹多邊形裁剪.對(duì)百萬(wàn)級(jí)數(shù)量的線段和圓進(jìn)行裁剪,以進(jìn)一步驗(yàn)證裁剪算法的正確性.裁剪前圖形顯示如圖5所示,藍(lán)色表示區(qū)域內(nèi)不同原點(diǎn)、不等半徑下的圓,綠色表示不同斜率下的線段.

圖5 裁剪前圖形

在執(zhí)行裁剪操作后,統(tǒng)計(jì)完成裁剪顯示后時(shí)間和內(nèi)存達(dá)到非功能性需求的結(jié)果.使用傳統(tǒng)裁剪算法的運(yùn)行內(nèi)存和時(shí)間消耗,如圖6、圖7所示.使用改進(jìn)后裁剪算法的運(yùn)行內(nèi)存和時(shí)間消耗,如圖8、圖9所示.

圖6 傳統(tǒng)裁剪算法的執(zhí)行內(nèi)存消耗

圖7 傳統(tǒng)裁剪算法的執(zhí)行時(shí)間消耗

圖8 改進(jìn)后裁剪算法的執(zhí)行內(nèi)存消耗

圖9 改進(jìn)后裁剪算法的執(zhí)行時(shí)間消耗

(4) 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)對(duì)1000 124個(gè)圖形進(jìn)行裁剪,有991 520個(gè)圖形與邊界相交(交點(diǎn)數(shù)),有5670個(gè)圖形在邊界內(nèi)部,有2934個(gè)圖形在邊界外部.裁剪后線段顯示均在凹多邊形內(nèi)部,裁剪后圓在裁剪邊界外的部分不顯示,在裁剪邊界內(nèi)的部分正確顯示.

實(shí)驗(yàn)結(jié)果顯示傳統(tǒng)裁剪算法的執(zhí)行時(shí)間為12.791 s;運(yùn)行過(guò)程中,內(nèi)存隨計(jì)算機(jī)運(yùn)行狀態(tài)有所變化,我們?nèi)?nèi)存中堆的使用峰值為93 898 576個(gè)字節(jié).采用改進(jìn)后裁剪算法的執(zhí)行時(shí)間為4.641 s,遠(yuǎn)小于12.791 s,在算法的執(zhí)行時(shí)間上大大縮短了,內(nèi)存中堆的使用峰值為76 156 576個(gè)字節(jié),所占空間明顯降低.

5 總結(jié)

本文針對(duì)傳統(tǒng)計(jì)算機(jī)圖形學(xué)中的矢量圖形裁剪算法進(jìn)行改進(jìn),通過(guò)實(shí)時(shí)高效地計(jì)算矢量圖形(line、circle)與非矩形的且非自交的多邊形的交點(diǎn),通過(guò)對(duì)交點(diǎn)的排序與分析,判斷圖形與多邊形邊界的內(nèi)、外部關(guān)系,從而決定其裁剪后的圖形顯示結(jié)果.改進(jìn)算法主要圍繞降低循環(huán)中冗余計(jì)算、重用對(duì)象、多線程控制等方面進(jìn)行改進(jìn).改進(jìn)后的算法在程序執(zhí)行時(shí)間和內(nèi)存消耗方面均優(yōu)于傳統(tǒng)的矢量圖裁剪算法.此算法的實(shí)現(xiàn)為提高工程圖形的生成效率提供了一種新的方法.但本算法只是模擬CAD軟件的布局空間中不同視口輸出圖形的顯示方式來(lái)仿真實(shí)驗(yàn),還需要進(jìn)一步嵌入到具體的應(yīng)用軟件中來(lái)驗(yàn)證其算法的執(zhí)行效率和內(nèi)存消耗問(wèn)題.