圓與橢圓對多邊形裁剪算法研究.pdf

1、裁剪是計(jì)算機(jī)圖形學(xué)中的一個(gè)重要技術(shù)。裁剪有多種類型，其中，二維多邊形裁剪是目前裁剪研究的主要課題。矩形(或多邊形)對多邊形裁剪已有許多經(jīng)典的算法。由于沒有完全避免求解一元二次方程或開方運(yùn)算，圓和橢圓對多邊形裁剪效率較低。 本文對圓和橢圓對多邊形裁剪進(jìn)行深入研究，設(shè)計(jì)出快速可行的算法。圓對多邊形裁剪是研究的重點(diǎn)，做到完全避免求解一元二次方程和開方運(yùn)算。 應(yīng)用區(qū)域編碼技術(shù)將完全可見或顯然完全不可見的多邊形判別出來。對于既不是

2、完全可見也不是顯然完全不可見的多邊形，需要用圓對多邊形各邊進(jìn)行裁剪。主要通過區(qū)域編碼技術(shù)并借助于距離平方判別法判別出圓和多邊形各邊的位置關(guān)系；采用中點(diǎn)分割算法求圓和多邊形邊的近似交點(diǎn)；通過交點(diǎn)和位于圓內(nèi)的多邊形頂點(diǎn)逆時(shí)針順序的鄰接關(guān)系，確定裁剪結(jié)果的直線邊界；通過對交點(diǎn)的排序和配對，確定裁剪結(jié)果的曲線邊界。 圓是一種特殊的橢圓，橢圓不具有圓的所有特性。圓對多邊形裁剪算法不能簡單地移植到橢圓對多邊形裁剪上，找出圓對多邊形裁剪算法中