多邊形裁剪算法PPT學習教案

1、會計學1多邊形裁剪算法多邊形裁剪算法第1頁/共40頁(xL,yB )(xR,yT )第2頁/共40頁第3頁/共40頁第4頁/共40頁第5頁/共40頁第6頁/共40頁100100010101100000000100101000100110ABCD第7頁/共40頁第8頁/共40頁一旦給定所有的線段端點的區(qū)域碼，就可以快速判斷哪條直線完全在剪取窗口內(nèi)，哪條直線完全在窗口外。所以得到一個規(guī)律：第9頁/共40頁100110001010000100000010010101000110P1P2P3P4第10頁/共40頁第11頁/共40頁第12頁/共40頁P0P1PmAB第13頁/共40頁P0P1PmAB第1

2、4頁/共40頁第15頁/共40頁第16頁/共40頁 設要裁剪的線段是P0P1。 P0P1和窗口邊界交于A,B,C,D四點，見圖。算法的基本思想是從A,B和P0三點中找出最靠近的P1點，圖中要找的點是P0。從C,D和P1中找出最靠近P0的點。圖中要找的點是C點。那么P0C就是P0P1線段上的可見部分。第17頁/共40頁為始邊。為終邊，若為終邊。為始邊，若為始邊。為終邊，若為終邊。為始邊，若TBTBRLRLyyyyyyyyyyxxxxxxxxxx0000第18頁/共40頁n若tu tl,則可見線段區(qū)間tl, tut0t1t2t301第19頁/共40頁EFAB第20頁/共40頁EFAB第21頁/共4

3、0頁第22頁/共40頁第23頁/共40頁2）一個凹多邊形可能被裁剪成幾個小的多邊形，如何確定這些小多邊形的邊界？第24頁/共40頁亦稱亦稱逐邊裁剪算法逐邊裁剪算法第25頁/共40頁可見一側(cè)可見一側(cè)可見一側(cè)可見一側(cè)SpSSSppp(1)(2)(3)(4)第26頁/共40頁可見一側(cè)可見一側(cè)可見一側(cè)可見一側(cè)SpSSSppp(1)(2)(3)(4)第27頁/共40頁SP與裁剪線相交 求SP與裁剪線的交點I輸出IP位于可見一側(cè)輸出頂點PYNYN 處理線段SP過程子框圖開始第一個頂點 S第一個頂點 F頂點輸入完畢輸入頂點P處理線段SPF P處理線段SP結(jié)束YN逐邊裁剪法算法框圖P S第28頁/共40頁第29頁/共40頁第30頁/共40頁思考：l如何推廣到任意凸多邊形l裁剪窗口？第31頁/共40頁第32頁/共40頁裁剪結(jié)果區(qū)域的邊界由A的部分邊界和B的部分邊界兩部分構(gòu)成，并且在交點處邊界發(fā)生交替，即由A的邊界轉(zhuǎn)至B的邊界，或由B的邊界轉(zhuǎn)至A的邊界 BA第33頁/共40頁第34頁/共40頁1）建頂點表；2）求交點；3）裁剪 1、建立主多邊形和裁剪多邊的頂點表2、求主多邊形和裁剪多邊形的交點，并將這些交點按順序插入兩多邊形的頂點表中。在兩多邊表形頂點表中的相同交點間建立雙向指針 。3、裁剪: 如果存在沒有被