李清艷 傅自鋼

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

關(guān)鍵詞：非自交多邊形；裁剪；算法；海量矢量圖形

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

圖形的裁剪是計(jì)算機(jī)圖形學(xué)中許多重要問題的基礎(chǔ)，裁剪的應(yīng)用有：從定義的場(chǎng)景中抽取出用于觀察的部分；在三維視圖中標(biāo)識(shí)出可見面；允許選擇圖形的一部分來進(jìn)行拷貝，移動(dòng)或刪除等繪圖操作。裁剪對(duì)象可以是二維的點(diǎn)，線段或者是封閉的多邊形，也可以是三維的多面體。在二維圖像裁剪中，線段裁剪是最基本的內(nèi)容，很多適用于二維線段裁剪的算法通過擴(kuò)展同樣都可以用來處理多邊形的裁剪。因此選擇二維圖形裁剪作為研究課題在圖形裁剪領(lǐng)域有重要的意義。

1 算法描述

1.1利用快速排斥試驗(yàn)算法判斷線段與多邊形的關(guān)系

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

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

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

1.2跨立試驗(yàn)算法研究

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

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

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

當(dāng)[P1-Q1×Q2-Q1=0]時(shí)，說明和[Q2-Q1]共線，由快速排斥試驗(yàn)分析得知[P1]一定在線段[Q1Q2]上，同理[Q2-Q1×P2-Q1=0]，說明 P2 一定在線段[Q1Q2]上，判斷[P1P2]跨立[Q1Q2]的依據(jù)是

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

判段跨立[P1P2]的依據(jù)是

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

圖1 跨立試驗(yàn)算法研究圖

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

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

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

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

（2）

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

2 軟件測(cè)試與應(yīng)用分析

圖2 裁剪前后對(duì)比

圖3 百萬級(jí)矢量圖形正確裁剪顯示

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

3 結(jié)論

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

參考文獻(xiàn)：

[1] 劉勇奎，劉桂英.一般多邊形窗口的線裁剪[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，1993，5（4）：269-274.

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

[3] 劉勇奎，顏葉，石教英.一個(gè)有效的多邊形窗口的線裁剪算法[J].計(jì)算機(jī)學(xué)報(bào)，1999，22（11）：209-214.

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