線段與圓在任意多邊形邊界中的裁剪算法設計及實現

張英男

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

?

線段與圓在任意多邊形邊界中的裁剪算法設計及實現

張英男

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

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

關鍵詞：裁剪算法；任意多邊行邊界；線段裁剪；圓裁剪

0　引言

在計算機處理圖形時，往往需要在較大的圖形中選取我們所關注的部分置于一個窗口中，比如電子地圖中地圖的放大處理，這時候就需要我們確定圖形的哪些部分落在窗口內而哪些部分落在窗口外，在計算機圖形學中這個處理過程叫做裁剪。

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

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

1　算法的描述

1.1算法的設計思想

核心思想：

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

1.2算法的具體說明

1.2.1線段裁剪

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

其中

dlt≠0時交點坐標：

當

迭代求出線段與邊界的所有交點，并與端點一起排序，如圖1中按橫坐標排序為m、o、p、q、l，分別求出線段mo、op、

pq、ql、ln的中點，可知應將線段op、ql保留，得到裁剪結果。

線段裁剪的主要代碼實現：

1.2.2圓裁剪

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

點

為了求圓弧的中點以及繪制圓弧我們還要求出各交點的弧度。設兩交點的弧度分別為res1、res2，當時，如果，res1= π/ 2，如果，res1 = 3 / 2*π

同理可求出res2

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

圓裁剪的主要代碼實現：

圖1

圖2

1.2.3判斷點在邊界內

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

isPointIn(const Point &p)

2　復雜度分析與比較

對于求交點，假設有m個被裁剪的對象（線段、圓），裁剪邊界為n邊形，每個裁剪對象對邊界的每個邊求交點的時間復雜度為O（m*n）。

對于求中點，線段與n邊形最多有個n-1交點，圓與n邊形最多有2n個交點，順次取兩點求中點時間復雜度為O(n)。

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

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

3　結束語

介紹了線段與圓關于任意多邊形窗口的裁剪算法，分別對線段、圓與邊界的求交及裁剪給出了具體的描述及代碼實現。通過求解交點將圖形分割，再通過對中點與邊界關系的判斷完成對圖形的裁剪。采用了一種簡單的方法判定點是否在多邊形邊界內，經過對算法時間復雜度的計算可以發現其效率比經典算法有了較大提高。

參考文獻

[1] 陸國棟 張樹友 譚建榮 黃長林.工程計算機圖形學.科學出版社，2004

[2] 孫家廣,胡事民.計算機圖形學基礎教程[M] .北京:清華大學出版社,2005.

[3] 孫家廣.計算機圖形學[M] .北京:清華大學出版社,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] .微機發展(現更名:計算機技術與發展),1999,9(2):49-50.

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

[9] 苗春葆. 點與多邊形關系的射線法. 電腦編程技巧與維護，2008.3

[10] 杭后俊,孫麗萍. 任意多邊形窗口的圓裁剪算法. 計算機技術與發展,第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，Federal 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

中圖分類號：TP393

文獻標識碼：A

作者簡介

張英男（1990年10月出生），男，山東東營人，俄羅斯國立石油天然氣大學留學生，在讀碩士，研究方向：石油地質勘探、計算機圖形學。