基于圖形內(nèi)角的兩個(gè)任意多邊形的交并差算法.pdf

1、在圖形系統(tǒng)中，平面多邊形布爾運(yùn)算是最為基礎(chǔ)的運(yùn)算之一，在CAD和幾何實(shí)體造型中有著廣泛的應(yīng)用，在計(jì)算幾何學(xué)、計(jì)算機(jī)圖形學(xué)、地理信息系統(tǒng)、地質(zhì)災(zāi)害預(yù)測(cè)評(píng)估及土木工程領(lǐng)域都有涉及。現(xiàn)有的布爾運(yùn)算在一般的情況下可以快速地得出正確結(jié)果，但如遇到奇異情況，則會(huì)產(chǎn)生錯(cuò)誤?，F(xiàn)有的算法對(duì)奇異情況的探討較少，因此，本文從圖形內(nèi)角的角度來解決布爾運(yùn)算當(dāng)中所遇到奇異現(xiàn)象，對(duì)高效的、魯棒性高的多邊形布爾運(yùn)算算法進(jìn)行了探討和研究。 本文首先闡述了多邊形布

2、爾運(yùn)算的研究意義、基本幾何、相關(guān)概念、數(shù)據(jù)結(jié)構(gòu)和已有算法，并著重?cái)⑹隽伺c本文密切相關(guān)的交點(diǎn)遍歷算法。然后對(duì)多邊形布爾運(yùn)算中的奇異情況進(jìn)行了分析，采用了一種用圖形內(nèi)角概念分析奇異的思路，并在原有的交點(diǎn)遍歷算法框架基礎(chǔ)上給出一種全局化的奇異處理算法框架。這個(gè)算法框架包括三個(gè)部分：交點(diǎn)求取、交點(diǎn)遍歷和布爾運(yùn)算之后形成的新的圖形內(nèi)角，論文提出了解決交點(diǎn)處問題新的算法，使整個(gè)框架可以解決各種奇異現(xiàn)象。 本文同時(shí)處理了無交點(diǎn)環(huán)。該算法使用圖