任意多邊形的裁剪算法及其在土建工程中的應(yīng)用.pdf

1、裁剪算法是計(jì)算機(jī)圖形學(xué)中的基本算法，也是其它諸多重要問題的基礎(chǔ)。經(jīng)過了近半個(gè)世紀(jì)的討論和探索，一些線裁剪算法越來越完善，尤以矩形窗口的線裁剪方法最為突出，但一般多邊形窗口的線裁剪算法并不是十分理想，而多邊形窗口的多邊形裁剪算法還沒有受到廣泛的關(guān)注。但后兩者在圖形學(xué)以及工程實(shí)際的應(yīng)用中具有更為重大的現(xiàn)實(shí)意義。尤其是目前還沒有文獻(xiàn)提到帶圓弧邊的多邊形的多邊形裁剪問題。而這類問題又是土建工程三維可視化預(yù)算軟件開發(fā)中最為基礎(chǔ)的問題。 因

2、此，本文首先基于VisualC++6.0語言、采用OpenGL圖形庫，開發(fā)了一個(gè)小型矢量圖形系統(tǒng)，為后續(xù)算法的設(shè)計(jì)、調(diào)試和應(yīng)用提供了圖形平臺(tái)。 接著，設(shè)計(jì)了一個(gè)任意多邊形窗口的多邊形裁剪算法。該算法不僅適用于一般意義上的凸多邊形和凹多邊形，而且還適用于帶圓弧邊的組合多邊形以及有空洞的多邊形(本文稱之為廣義多邊形)。其次，在算法的設(shè)計(jì)中采用了包圍盒技術(shù)、計(jì)算幾何的跨立法、射線法等技術(shù)，大大簡化了計(jì)算過程。再者，VisualC++支

3、持的CArray類，以及CObList類的數(shù)據(jù)結(jié)構(gòu)(單鏈表)的采用，大幅度地減少了內(nèi)存開銷，節(jié)約了存儲(chǔ)空間。符號(hào)函數(shù)的引入，有效地控制了誤差傳遞，確保了計(jì)算精度。最后，針對(duì)MFC(MicrosoftFoundationClassLibrary)提供的庫函數(shù)的不足，編寫了一個(gè)判斷點(diǎn)與廣義多邊形位置關(guān)系的新函數(shù)，有效地消除了由此產(chǎn)生的致命性錯(cuò)誤。最終實(shí)現(xiàn)了一個(gè)幾何適應(yīng)性強(qiáng)，時(shí)間和空間復(fù)雜度低的算法。 最后，將新算法應(yīng)用于土建工程三維