一種任意多邊形的裁剪算法.pdf

1、線段裁剪和多邊形裁剪作為圖形裁剪中最基礎(chǔ)、最常用的操作之一,其算法始終是計算機圖形學研究的熱點。近年來,隨著遙感繪圖、CAD輔助設計、圖象識別處理技術(shù)的發(fā)展,圖形裁剪算法從最初在二維平面上線和圖形的裁剪擴展到三維空間里體和場的裁剪,國內(nèi)外相繼提出不少行之有效的算法,但越來越復雜的圖形和計算也對算法的速度和適用性提出了越來越高的要求。因此,不斷簡化算法的實現(xiàn)過程,完善細節(jié)處理,滿足大量任意多邊形的裁剪也就成了當今算法研究的焦點之一。

2、>　　 本文首先對目前國外經(jīng)典線段裁剪和多邊形裁剪算法作了概述,介紹了Cohen-Sutherland裁剪算法、直線段的中點分割裁剪算法、Liang-barsky算法、Sutherland-Hodgman算法,Weiler-Atherton算法的基本思路,也描述了國內(nèi)在相關(guān)領(lǐng)域提出的一些典型算法,如劉勇奎、蔡志杰等人在Weiler-Atherton算法基礎(chǔ)上提出的改進算法。
　　 接著,本文對現(xiàn)有算法的適用性進行了比較,重點分

3、析了Weiler-Atherton算法。在此基礎(chǔ)上,通過對多邊形按照指定頂點順序正向和逆向遍歷,查找出全部最小多邊形,再通過位置判斷來得出最終裁剪結(jié)果多邊形的算法進行了描述。隨后,以偽代碼和流程圖的形式,進一步說明了該算法的結(jié)構(gòu)。
　　 最后,根據(jù)算法特征,顯然較適用于地質(zhì)構(gòu)圖和地圖比較算法。本文以地層結(jié)果圖的繪制為例,用折線和多邊形裁剪的算法,推斷了地層逐條裁剪構(gòu)圖的過程,證明了該算法在處理此類運算時,算法計算量較小,時間較快