李清艷 傅自鋼

摘要：該文介紹和研究海量矢量圖形在非自交多邊形邊界中的裁剪顯示圖形。程序采用快速排斥試驗，跨立試驗等算法實時高效地計算矢量圖形與非矩形且非自交的凸多邊形及凹多邊形區(qū)域的交點，判斷圖形的哪些部分在多邊形邊界內部，哪些部分在多邊形邊界外部，同時能正確顯示位于多邊形邊界內部的圖形部分，不顯示位于多邊形邊界外部的圖形部分。最終實現當有百萬級的line和circle需要裁剪顯示時，統(tǒng)計的完成裁剪顯示的時間不超過10s，存儲器占用不超過100MB 的效果。

關鍵詞：非自交多邊形；裁剪；算法；海量矢量圖形

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2015）31-0168-02

Mass Vector Graphics in a Non-Self-Intersections Clipping in the Polygon Boundary Display

LI Qing- yan， FU Zi-gang

（Hunan Agricultural University Information Institute of Science and Technology， Changsha 410128， China）

Abstract ：This article describes and research mass vector graphics in a non-self-intersections polygon boundary clipping in the display graphics. Using of the quick test procedures， straddling the exclusion pilot algorithms such as effective， real-time computing vector graphics and non-rectangular and non-cross the convex hull polygon regions， and the intersection of the judgment which parts of the graphics in the polygon boundary in which parts of the inside of the polygon boundary and at the same time to display correctly on the polygon boundary in the graphical part of the internal， do not display on the outside of the polygon boundary Graphical sections. The final realization of the millions of when a line to be cropped and circle displayed， the completion of the statistics displayed in the crop time should not exceed 10s， memory utilization not to exceed 100MB.

Key words：Non-self-intersections ； polygon ； clipping ； Algorithm，Mass vector graphics

圖形的裁剪是計算機圖形學中許多重要問題的基礎，裁剪的應用有：從定義的場景中抽取出用于觀察的部分；在三維視圖中標識出可見面；允許選擇圖形的一部分來進行拷貝，移動或刪除等繪圖操作。裁剪對象可以是二維的點，線段或者是封閉的多邊形，也可以是三維的多面體。在二維圖像裁剪中，線段裁剪是最基本的內容，很多適用于二維線段裁剪的算法通過擴展同樣都可以用來處理多邊形的裁剪。因此選擇二維圖形裁剪作為研究課題在圖形裁剪領域有重要的意義。

1 算法描述

1.1利用快速排斥試驗算法判斷線段與多邊形的關系

假設多邊形的頂點為[Pi]的n次方，[i=0]，其中[Pi]=[Pix，Piy]，[P0=Pn]，裁剪線段為[L]，它的兩個端點分別為A和B。用[Ax，Ay]，[Bx，By]分別表示A和B點的x，y坐標。用快速排斥試驗的方法判斷是否完全不可見，即判斷A和B是否落在多邊形[P0，P1，…，Pn]包圍盒的同一側，記為公式（1）

[Xmin=minPix0≤i≤nYmin=minPiy0≤i≤n][Xmax=maxPix0≤i≤nYmax=maxPiy0≤i≤n] （1）

若[Ax]和[Bx和[Bx>Xmax]，或和[By>Ymax]，則為完全不可見線段且與多邊形沒有交點。若用快速排斥試驗不能確定是否可見，則[Xmax=maxPix0≤i≤n；]繼續(xù)進行運算。若判斷出被裁剪線段是否完全不可見，則求出被裁剪線段與多邊形窗口邊界的真實交點。對求出的所有真實交點和被裁剪線段的端點同時排序，根據排序的結果將被裁剪線段分成若干條子線段，然后選擇線段的一個端點判斷該端點是否在多邊形內。若在多邊形之內，表明奇數點到偶數點間的線段在多邊形內且顯示，偶數點到奇數點間的線段不顯示。若該端點在多邊形之外，表明奇數點到偶數點間的線段不在多邊形內且不顯示。

1.2跨立試驗算法研究

設以線段[P1P2]為對角線的矩形為R，設以線段[Q1Q2]為對角線的矩形為T.若兩線段相交，則兩線段必然相互跨立對方。若跨立，則矢量[P1-Q1]和[P2-Q1]位于矢量[Q2-Q1]的兩側，得出：

[P1-Q1×Q2-Q1×P2-Q1×Q2-Q1<0]，將其改寫成：

[P1-Q1×Q2-Q1×Q2-Q1P2-Q1>0]

當[P1-Q1×Q2-Q1=0]時，說明和[Q2-Q1]共線，由快速排斥試驗分析得知[P1]一定在線段[Q1Q2]上，同理[Q2-Q1×P2-Q1=0]，說明 P2 一定在線段[Q1Q2]上，判斷[P1P2]跨立[Q1Q2]的依據是

[P1-Q1×Q2-Q1×Q2-Q1×P2-Q1≥0]

判段跨立[P1P2]的依據是

[Q1-P1×P2-P1×P2-P1×Q2-P1≥0]，具體情況如圖1所示：

圖1 跨立試驗算法研究圖

1.2.1 特殊情況處理的一致性方法

對相交的線段求交時裁剪線段通過多邊形的頂點，若兩個相臨邊在被裁剪線段的同側，即不為交點，若在裁剪線段的異側則記為交點。若相交的線段求交時裁剪線段與多邊形的邊重合則做頂點的凹凸性判斷，即在兩線段重合部分的兩端點中，若端點是多邊形凸頂點，則將該頂點記為交點，若是多邊形凹頂點，則該頂點不記為交點。若被裁剪線段的端點在多邊形窗口的邊上而不在頂點上，將端點記為交點，若該端點在多邊形頂點上，則將該端點及其上的所有交點按橫坐標從小到大排序來討論左端點在多邊形頂點是否記為交點的情況。

1.3任意多邊形裁剪圓的算法研究

求出多邊形與圓的交點，記錄公共點包括交點與切點的位置與數量，根據多邊形與圓的公共點數量對圓進行分類，對“有無公共點圓”進行裁剪。設線段端點[P1（x1，y1）][P2（x2，y2）]得到線段所在直線的方程[ax+by+c=0]，圓心[P0x0，y0]）和半徑r得到圓的方程，由點到圓的距離公式算出圓心到線段的距離d。假設圓與線段有兩個公共點，將線段P1P2寫成參數方程形式。x與y是公共點坐標信息，t為參數用來判斷直線與圓公共點是否不在線段范圍內。按公式（2）判定出多邊形與圓的關系。

（2）

綜上分析，若d>r則多邊形與圓沒有公共點，將兩個公共點對象的t置為不合法。若d<=r則通過圓方程與線段參數方程求解公共點坐標與參數，將t合法的公共點對象記錄為多邊形與圓的公共點。對于d=r的情況視為有兩個相同的公共點輸出。

2 軟件測試與應用分析

圖2 裁剪前后對比

圖3 百萬級矢量圖形正確裁剪顯示

任意line和circle，與多邊形裁剪邊界相交時正確裁剪顯示：a）是裁剪前圖級的line和circle需要裁剪顯示時正確的顯示圖形顯示；b）是裁剪后裁剪前圖級的line和circle需要裁剪顯示時正確的顯示圖形顯示。

3 結論

本文解決了海量矢量圖形如何在非自交多邊形邊界中的裁剪顯示問題，通過采用快速排斥試驗，跨立試驗等算法實時高效地計算海量矢量圖形與任意多邊形區(qū)域的交點，正確顯示位于多邊形邊界內部的圖形部分，在實現基本功能的基礎上，最終實現當有百萬級的line和circle需要裁剪顯示時，統(tǒng)計的完成裁剪顯示的時間不超過10s，存儲器占用不超過100MB，提升了時間和空間效率。

參考文獻：

[1] 劉勇奎，劉桂英.一般多邊形窗口的線裁剪[J].計算機輔助設計與圖形學學報，1993，5（4）：269-274.

[2] 汪灝泓，吳銳迅，蔡志杰.一種幾何變換的高效的線裁剪新算法[J].軟件學報，1998，9（10）：728-733.

[3] 劉勇奎，顏葉，石教英.一個有效的多邊形窗口的線裁剪算法[J].計算機學報，1999，22（11）：209-214.

[4] Cyms M，Beck J.Generalized two—dimensional clipping[J].Computer and Graphics，1978，3（1）：23-28.