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

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

1(山西大同大學 數學與計算機科學學院,大同 037009)

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

3(山西大同大學 網絡信息中心,大同 037009)

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 改進算法的思路

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

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

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

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

(2) 圓中交點求解冗余

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

3.1.2 重用對象

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

3.1.3 多線程控制

分別對直線裁剪、圓裁剪增加多線程.從直線、圓裁剪數量的一半進行劃分,分別使用兩個線程同時進行裁剪繪制.同時避免公用對象Graphics2D g2的混合使用.

3.2 線段裁剪非自交多邊形改進算法

裁剪算法的描述如下:

Step 1.用intnPoints變量存儲多邊形的頂點數量,利用兩個一維整型數組分別存儲點的x,y坐標,實現二維數組的功能,并且設置標志量flag1、flag2為true.

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

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

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

Step 5.判斷所獲取的兩條線段是否有交點,如果無交點轉Step 11; 如果有交點轉Step 6.

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

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

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

Step 9.對列表中的點進行排序.

Step 10.依次遍歷列表中的點,判斷兩點的中點坐標是否在多邊形內部,如果在則進行繪制; 否則不進行處理.

Step 11.結束.

3.3 圓裁剪非自交多邊形改進算法

對于中點坐標的求解采用Arc2D中弧線的類直接求中點坐標.

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

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

圓的方程為:

圖3 線段與圓求交點

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

P1P2的參數方程為:

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

其中,

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

以圓心為原點,以圓心左右兩邊區(qū)分所有交點,按照順時針方向進行排序.設圓心坐標為p(x0,y0),其他點坐標為(x,y),由于可執(zhí)行程序已經進行坐標點的轉換,所以使得原點為框體右上角的頂點,向下為y值增大方向分為2種情況:

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

設Q1,Q2,…,Qk是多邊形與被裁減圓的所有交點,并且進行順時針方向排序.對兩相鄰的交點Qi,之間的圓弧是否繪制,可采用中點檢測法(圓弧存在方向,即順時針方向).

根據Java中Arc2D的弧線類,通過Qi,Qi+1確定需要繪制的弧線參數,通過類中方法,返回兩個點的夾角,并再次通過一個弧線類的對象,設置起始點和夾角來確定弧線的中點坐標M3;

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

② 若M3在窗口內,圓弧QiQi+1被保留.

4 系統(tǒng)仿真實驗及分析

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

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

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

(2) 單個圓裁剪

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

圖4 對一個單圓的裁剪

(3) 百萬級數量的線段和圓裁剪

為測試算法的通用性,選取不同隨機斜率下的線段和區(qū)域內不同隨機原點不等半徑下的圓進行凹多邊形裁剪.對百萬級數量的線段和圓進行裁剪,以進一步驗證裁剪算法的正確性.裁剪前圖形顯示如圖5所示,藍色表示區(qū)域內不同原點、不等半徑下的圓,綠色表示不同斜率下的線段.

圖5 裁剪前圖形

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

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

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

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

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

(4) 實驗結果分析

實驗對1000 124個圖形進行裁剪,有991 520個圖形與邊界相交(交點數),有5670個圖形在邊界內部,有2934個圖形在邊界外部.裁剪后線段顯示均在凹多邊形內部,裁剪后圓在裁剪邊界外的部分不顯示,在裁剪邊界內的部分正確顯示.

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

5 總結

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