張英男

(俄羅斯國(guó)立（古布金）石油天然氣大學(xué)地質(zhì)與地球物理系,俄羅斯莫斯科,119991）

?

線段與圓在任意多邊形邊界中的裁剪算法設(shè)計(jì)及實(shí)現(xiàn)

張英男

(俄羅斯國(guó)立（古布金）石油天然氣大學(xué)地質(zhì)與地球物理系,俄羅斯莫斯科,119991）

摘要：設(shè)計(jì)并優(yōu)化了線段與圓關(guān)于任意多邊形邊界（包括凸多邊形及凹多邊形邊界）的裁剪算法。求出每一條邊界與所要裁剪的線段和圓的交點(diǎn)并排序，利用交點(diǎn)將裁剪對(duì)象分割成線段、圓弧，通過(guò)計(jì)算線段和圓弧的中點(diǎn)并判斷其與邊界的位置關(guān)系來(lái)完成對(duì)圖形的裁剪。文中給出了算法具體描述，通過(guò)對(duì)算法復(fù)雜度的分析，該算法的效率與以往的一些經(jīng)典算法相比有了較大提高。

關(guān)鍵詞：裁剪算法；任意多邊行邊界；線段裁剪；圓裁剪

0　引言

在計(jì)算機(jī)處理圖形時(shí)，往往需要在較大的圖形中選取我們所關(guān)注的部分置于一個(gè)窗口中，比如電子地圖中地圖的放大處理，這時(shí)候就需要我們確定圖形的哪些部分落在窗口內(nèi)而哪些部分落在窗口外，在計(jì)算機(jī)圖形學(xué)中這個(gè)處理過(guò)程叫做裁剪。

計(jì)算機(jī)圖形學(xué)作為計(jì)算機(jī)科學(xué)一門重要的分支，近年來(lái)已經(jīng)發(fā)展的較為完備。而對(duì)于圖形裁剪算法的探討，許多專家學(xué)者也都撰寫(xiě)了專門的文章或書(shū)籍。這其中討論的熱點(diǎn)多是在矩形邊界中對(duì)線段、圓或多邊形的裁剪，而任意多邊形區(qū)域的裁剪算法則討論的很少。對(duì)于任意的多邊形區(qū)域，由于其不確定性，圖形裁剪的難度有所提高，一些經(jīng)典的算法對(duì)于特殊的區(qū)域（如：凹多邊形）可能就不再適用。而這種不規(guī)則邊界裁剪在CAD中應(yīng)用的頻率較高，提高裁剪效率可以使軟件的性能得到大幅的提高。

文中給出了對(duì)于非自交多邊形邊界的線段與圓的裁剪算法，并與已有的一些算法的復(fù)雜度做了比較。

1　算法的描述

1.1算法的設(shè)計(jì)思想

核心思想：

對(duì)于要裁剪的線段或圓求出它與邊界各邊的交點(diǎn)，將交點(diǎn)與端點(diǎn)（端點(diǎn)僅對(duì)線段）按某一坐標(biāo)（圓按弧度）的順序排序，每次取出兩點(diǎn)計(jì)算出所夾短線段或圓弧的中點(diǎn)，若判斷中點(diǎn)在邊界（邊界區(qū)域已提前涂色，查表即可）內(nèi)，則保留該部分，否則丟棄。

1.2算法的具體說(shuō)明

1.2.1線段裁剪

首先我們要計(jì)算線段與多邊形邊界各邊的交點(diǎn)，這里被裁剪線段與邊界的線段我們以兩端點(diǎn)坐標(biāo)的形式獲得，例如我們知道了被裁線段的端點(diǎn)多邊形某條邊界的端點(diǎn)，我們可以得到兩條線段所在的直線方程：

其中

dlt≠0時(shí)交點(diǎn)坐標(biāo)：

當(dāng)

迭代求出線段與邊界的所有交點(diǎn)，并與端點(diǎn)一起排序，如圖1中按橫坐標(biāo)排序?yàn)閙、o、p、q、l，分別求出線段mo、op、

pq、ql、ln的中點(diǎn)，可知應(yīng)將線段op、ql保留，得到裁剪結(jié)果。

線段裁剪的主要代碼實(shí)現(xiàn)：

1.2.2圓裁剪

同線段裁剪，我們要先求出圓與各邊界的交點(diǎn)，這里圓我們以圓心坐標(biāo)和半徑長(zhǎng)度的形式獲得，線段以端點(diǎn)的形式獲得。為了方便計(jì)算先坐標(biāo)平移，把圓心作為原點(diǎn)，例如我們知道了多邊形某條邊界的端點(diǎn)，被裁剪圓圓心O(xo,yo)，半徑r

點(diǎn)

為了求圓弧的中點(diǎn)以及繪制圓弧我們還要求出各交點(diǎn)的弧度。設(shè)兩交點(diǎn)的弧度分別為res1、res2，當(dāng)時(shí)，如果，res1= π/ 2，如果，res1 = 3 / 2*π

同理可求出res2

迭代求出圓與邊界的所有交點(diǎn)及其弧度，并將交點(diǎn)按照弧度大小排序，如圖2中交點(diǎn)按弧度大小排序c、b、a、d，分別求出弧cb、ba、ad、dc中點(diǎn)的弧度，則弧中點(diǎn)的直角坐標(biāo)為。特別地，求dc弧中點(diǎn)弧度時(shí)需要對(duì)c點(diǎn)弧度作2π的補(bǔ)償。根據(jù)中點(diǎn)的位置可知，保留弧cb、ad，得到裁剪結(jié)果。

圓裁剪的主要代碼實(shí)現(xiàn)：

圖1

圖2

1.2.3判斷點(diǎn)在邊界內(nèi)

先在位圖內(nèi)把邊界填充完成，這里為了方便使用的GDI的填充。填充之后取得位圖，需要的時(shí)候查表判斷像素就可以了。比如判斷p(x,y)是否在邊界內(nèi)，將邊界內(nèi)像素賦值為1，邊界外的像素賦值為0。具體函數(shù)可定義為:

isPointIn(const Point &p)

2　復(fù)雜度分析與比較

對(duì)于求交點(diǎn)，假設(shè)有m個(gè)被裁剪的對(duì)象（線段、圓），裁剪邊界為n邊形，每個(gè)裁剪對(duì)象對(duì)邊界的每個(gè)邊求交點(diǎn)的時(shí)間復(fù)雜度為O（m*n）。

對(duì)于求中點(diǎn)，線段與n邊形最多有個(gè)n-1交點(diǎn)，圓與n邊形最多有2n個(gè)交點(diǎn)，順次取兩點(diǎn)求中點(diǎn)時(shí)間復(fù)雜度為O(n)。

對(duì)于判斷中點(diǎn)的位置，我們放在了求中點(diǎn)的迭代中，且判斷的方法為先涂色后查表時(shí)間復(fù)雜度僅為O（1）。傳統(tǒng)的叉積判別法僅適用于凸多邊形邊界，且需要判斷該點(diǎn)與每一個(gè)頂點(diǎn)的相鄰的連線叉積符號(hào)相同，時(shí)間復(fù)雜度為O(n)并且單步的叉積運(yùn)算較為復(fù)雜。文獻(xiàn)[9] 中的射線法可用于任意多邊形但需要利用過(guò)該點(diǎn)的射線與多邊形的每一條邊求交點(diǎn)，根據(jù)交點(diǎn)的個(gè)數(shù)判斷點(diǎn)的位置，時(shí)間復(fù)雜度為O(n)，且單步的求交過(guò)程復(fù)雜。

文獻(xiàn)[10] 中介紹了類似的圓裁剪方法，文中利用參數(shù)方程計(jì)算交點(diǎn)和中點(diǎn)的時(shí)間復(fù)雜度與本文相同，在判定中點(diǎn)位置時(shí)采用了射線法，因此總體的效率比本文的算法要低。

3　結(jié)束語(yǔ)

介紹了線段與圓關(guān)于任意多邊形窗口的裁剪算法，分別對(duì)線段、圓與邊界的求交及裁剪給出了具體的描述及代碼實(shí)現(xiàn)。通過(guò)求解交點(diǎn)將圖形分割，再通過(guò)對(duì)中點(diǎn)與邊界關(guān)系的判斷完成對(duì)圖形的裁剪。采用了一種簡(jiǎn)單的方法判定點(diǎn)是否在多邊形邊界內(nèi)，經(jīng)過(guò)對(duì)算法時(shí)間復(fù)雜度的計(jì)算可以發(fā)現(xiàn)其效率比經(jīng)典算法有了較大提高。

參考文獻(xiàn)

[1] 陸國(guó)棟 張樹(shù)友 譚建榮 黃長(zhǎng)林.工程計(jì)算機(jī)圖形學(xué).科學(xué)出版社，2004

[2] 孫家廣,胡事民.計(jì)算機(jī)圖形學(xué)基礎(chǔ)教程[M] .北京:清華大學(xué)出版社,2005.

[3] 孫家廣.計(jì)算機(jī)圖形學(xué)[M] .北京:清華大學(xué)出版社,1998.

[4] WU X,Rokne J.Double- Step incremental generation of lines and circles[J] . Computer Vision, Graphics,and Image Processing,1987,37(3):331-334.

[5] Liang Y D,Brasky B A.A New Concept and Method for Line Clipping[J] .ACM Transactions on Graphics,1984,3(1):1-22.

[6] Nicholl T M,Lee D T,Nicholl R A.An Efficient New Algorithm for 2D Line Clipping:Its development and analysis[J] . Computer Graphics,1987,21(4): 253-262.

[7] 韓明峰.基于一般多邊形窗口的線裁剪[J] .微機(jī)發(fā)展(現(xiàn)更名:計(jì)算機(jī)技術(shù)與發(fā)展),1999,9(2):49-50.

[8] 范延軍,孫燮華.一種基于幾何關(guān)系編碼的高效凸多邊形線裁剪算法[J] .計(jì)算機(jī)應(yīng)用與軟件,2007,24(2):148-150.

[9] 苗春葆. 點(diǎn)與多邊形關(guān)系的射線法. 電腦編程技巧與維護(hù)，2008.3

[10] 杭后俊,孫麗萍. 任意多邊形窗口的圓裁剪算法. 計(jì)算機(jī)技術(shù)與發(fā)展,第19卷 第5期2009年5月

The Design and Implementation of the Line and Circle Clipping Algorithms against the Arbitrary Polygon Boundary

Zhang Yingnan
(Geology and geophysics oil and gas，F(xiàn)ederal State Budgetary Educational Institution of Higher Education ?Gubkin Russian State University of Oil and Gas (National Research University)? ,The Russian Federation，Moscow, 119991)

Abstract：The line and circle clipping algorithms against the arbitrary polygon boundary,including convex polygon boundary and concave polygon boundary,are designed and optimized in this paper.The intersection points between each boundary and line or circle that needs to be clipped are calculated and sorted,and then these intersection points are used to divide the clipping object into line segments or circular arcs. The graphic is clipped by calculating middle points of these line segments or circular arcs and deciding their positional relation to the boundary. Both algorithms are described in detail in this paper.Through the analysis of the complexity of the two algorithms, it can be seen that the efficiency of both algorithms has been improved a lot compared with other classical algorithms.

Keywords：Clipping Algorithm;Arbitrary Polygon Boundary;Line Clipping;Circle Clipping

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)識(shí)碼：A

作者簡(jiǎn)介

張英男（1990年10月出生），男，山東東營(yíng)人，俄羅斯國(guó)立石油天然氣大學(xué)留學(xué)生，在讀碩士，研究方向：石油地質(zhì)勘探、計(jì)算機(jī)圖形學(xué)。