一種基於交點排序的多邊形裁剪的方法
2023-09-22 02:34:45 1
專利名稱：一種基於交點排序的多邊形裁剪的方法
技術領域：
本發明涉及計算機圖形學中多邊形裁剪的技術領域，尤其涉及一種基於交點排序的多邊形裁剪的方法。
背景技術：
裁剪是圖形學中的基本操作。經典的多邊形裁剪算法，如Sutherland-Hodgeman 算法、梁-Barsky算法等要求裁剪多邊形為矩形，而在實際應用中，裁剪多邊形和實體多邊形可能均為一般多邊形，並包含內環。Wfeiler算法、Vatti算法以及Greiner-Hormarm算法可以在一定的時間內處理一般多邊形的裁剪，其中，Weiler算法使用的是樹形數據結構， Vatti和Greiner-Hormarm算法使用的是雙線性鍊表數據結構，劉永奎等對上述三種算法進行改進後，提出了一種新的多邊形裁剪算法(劉氏算法)，對原有的數據結構進行了一定的優化，提高了裁剪效率。但是，該算法的交點採用雙指針結構，將交點插入到實體多邊形和裁剪多邊形頂點鍊表使得參與求交的邊的數量因為多邊形頂點個數的增加而增加，造成算法的冗餘，當多邊形交點數目不斷增多時，重複的求交計算對算法效率的影響比較明顯。
發明內容
本發明的目的是克服現有技術的不足，提供一種基於交點排序的多邊形裁剪的方法。基於交點排序的多邊形裁剪的方法的步驟如下1)根據裁剪邊和被裁剪邊四個節點的相對位置，判斷兩條線段是否相交，並對交點的進出性情況進行分析；2)取裁剪多邊形的邊依次對實體多邊形的邊界進行求交，根據每一條裁剪邊上交點的順序、進出性，判斷該裁剪邊的終點是否組成結果多邊形，將組成結果多邊形的裁剪多邊形頂點插入到交點鍊表，形成一個由進點和出點組成的點對；3)根據交點的進出性，以及所記錄的實體多邊形的終點序號，設置所有交點的指針指向，並將組成結果多邊形的實體多邊形頂點插入到交點鍊表，完成交點的第二次排序；4)遍歷結果多邊形頂點鍊表，根據指針指向輸出結果多邊形。所述的步驟1)包括(1)將平面上坐標為xm，yco的點Ctl，到坐標為ycl的C1的線段Ctl C1和由坐標為&。，Yso的點&到坐標為A1, Y51的點S1所組成的線段& S1的直線方程寫成
權利要求
1.一種基於交點排序的多邊形裁剪的方法，其特徵在於它的步驟如下1)根據裁剪邊和被裁剪邊四個節點的相對位置，判斷兩條線段是否相交，並對交點的進出性情況進行分析；2)取裁剪多邊形的邊依次對實體多邊形的邊界進行求交，根據每一條裁剪邊上交點的順序、進出性，判斷該裁剪邊的終點是否組成結果多邊形，將組成結果多邊形的裁剪多邊形頂點插入到交點鍊表，形成一個由進點和出點組成的點對；3)根據交點的進出性，以及所記錄的實體多邊形的終點序號，設置所有交點的指針指向，並將組成結果多邊形的實體多邊形頂點插入到交點鍊表，完成交點的第二次排序；4)遍歷結果多邊形頂點鍊表，根據指針指向輸出結果多邊形。
2.根據權利要求1所述的一種基於交點排序的多邊形裁剪的方法，其特徵在於所述的步驟1)包括(1)將平面上坐標為^1Jai的點Ctl，到坐標為A^yaWC1的線段Ctl C1和由坐標為&。， Ys0的點&到坐標為A1, Y51的點S1所組成的線段& S1的直線方程寫成JC0C1 \Ax + By + C = 0I^0 :A'x + B'y + C' =0^ = J^Sl ~ J^so~ xSO _ xSl(1)其中令C — -^51^50 ~~ -^50^51Δ =ABJci—J^co -^co _ xClA'B'~ Xso ^1SO 「「 xSl則當2^ = ^Cl "^co B = Xco _ xCl、C — -^Cl^CO ~~ IcoJ^ciΔ Φ 0時，兩直線的交點坐標為 Jx = (BC'-BC)/A \y = (A'C-AC')/A(2)記裁剪多邊形的一條邊的兩個頂點為=Ctl C1，線段方向為Ctl^C1 ；實體多邊形當前被處理的邊的頂點為&和S1，線段方向為& — S1,由式(1)，其所在的直線方程為 [fc(x,y) = Ax + By + C = 0 \fs(x,y) = Ax + B'y + C'=0 點Sp S1相對於直線Ctl C1的位置表示為>0 直線右側的點fc(xs,ys)·=0 直線上的點<0 直線左側的點
3.根據權利要求1所述的一種基於交點排序的多邊形裁剪的方法，其特徵在於所述的步驟2、包括(1)對於實體多邊形和裁剪多邊形的交點，如果沿著裁剪多邊形的邊由交點進入實體多邊形，這一類交點稱為進點，反之，如果沿著裁剪多邊形由交點離開實體多邊形，則這類交點為出點；(2)採用單線性鍊表來表示多邊形，鍊表中的每一個節點按序存儲著多邊形的一個頂點，多邊形頂點和交點的數據結構如下Vertex = {χ, y !Coordinates ；Next :Pointer ；PartNum :Number}； Intersection = {χ, y !Coordinates ；Next :Pointer ；VertexID Number ；Inters Boolean ；Used :Boolean}Vertex用於存儲裁剪多邊形和實體多邊形的頂點，其中，x，y表示點的坐標，Next用於指向多邊形中以當前頂點為始點的邊的終點，PartNum記錄頂點所在多邊形環的序號， htersection用於存儲實體多邊形和裁剪多邊形的交點，其中x，y用於表示點的坐標， Next用於指向該交點在結果多邊形中的下一個頂點，VertexID記錄該交點所在實體多邊形邊的終點在實體多邊形鍊表中的序號，Inters表示交點的進出性，^ed用於最後輸出結果多邊形時標記交點是否已經輸出過。(3)將多邊形的求交運算、交點的進出性判斷以及將裁減多邊形頂點插入到交點鍊表合成一步同時進行，根據交點的進出性，將每一條裁剪邊上的所有交點按照裁剪邊的方向排序後插入交點鍊表，如果最後一個交點為進點，則當前裁剪邊的終點位於實體多邊形內， 若無交點，則與前一頂點的內外關係一致，將該頂點作為進點按序插入到交點鍊表中。
4.根據權利要求1所述的一種基於交點排序的多邊形裁剪的方法，其特徵在於所述的步驟幻包括對於每一個進點，直接將其指針指向鍊表中下一個交點；對於出點，如果存在與該出點具有相同終點信息的進點，且位於出點的前方，則將該出點的指針指向該進點；反之，將出點所在實體多邊形邊的終點作為出點插入到交點鍊表，並將出點指針指向該頂點。
全文摘要
本發明公開了一種基於交點排序的多邊形裁剪方法。它的步驟如下1)根據裁剪被裁剪邊四個節點的相對位置，判斷線段是否相交，對交點的進出性進行分析；2)取裁剪多邊形的邊依次對實體多邊形進行求交，根據每一條裁剪邊上交點的順序、進出性，判斷裁剪邊的終點是否組成結果多邊形，將組成結果多邊形的裁剪多邊形頂點插入到交點鍊表，形成一個由進點和出點組成的點對；3)根據交點的進出性，以及所記錄的實體多邊形的終點序號，設置所有交點的指針指向，並將組成結果多邊形的實體多邊形頂點插入到交點鍊表，完成交點的第二次排序；4)遍歷結果頂點鍊表，根據指針指向輸出結果多邊形。本發明在計算機圖形學領域具有重要的實際應用價值。
文檔編號G06T11/00GK102360507SQ20111031839
公開日2012年2月22日 申請日期2011年10月19日 優先權日2011年10月19日
發明者何榕健, 劉仁義, 張豐, 彭傑, 杜震洪 申請人:浙江大學