【正文】 出直線與窗口邊線的交點 ， 將直線分段后繼續(xù)進行檢查判斷 。 這樣可以逐段地舍棄位于窗口外的線段 ， 保留剩在窗口內(nèi)的線段 。 72 如圖所示 ， 用編碼裁剪算法對 P1P2線段裁剪 ， 可以在C點分割 ， 對 P2C， CP1進行判別 ， 舍棄 P2C， 再分割 CP1于 D點 ， 對 CD， DP1作判別 ， 舍棄 CD， 而 DP1全部位于窗口內(nèi) ，算法即告結(jié)束 。 應(yīng)該指出的是 ， 分割線段是從 C點還是 D點開始 ， 這是難以確定的 ， 因此只能隨機的 ， 但是最后結(jié)果是相同的。 73 （ 3） 交點的求法 下面介紹交點的求法 。 設(shè)直線的兩端點坐標為 P1 （ x1， y1） 和 P2 （ x2， y2） 如圖所示 ， 直線與窗口四條邊線的交點坐標 ， 可分別由下列公式確定： （ 利用相似直角三角形比例關(guān)系 ） 左交點 : 右交點 : 111212 )( yxWxxyyyWxxlxl??????111212 )( yxWxxyyyWxxrxr??????74 下交點： 上交點： 111212 )( xyWyyxxxWyybyb??????111212 )( xyWyyxxxWyytyb??????75 4. 矢量裁剪法 (略 ) 76 5． 中點分割裁剪法 上面介紹兩種方法都要計算直線段與窗口邊界交點 ， 這不可避免地要進行大量乘除運算 ， 勢必會降低程序執(zhí)行效率 。 而中點分割裁剪卻只需用到加法和除 2運算 ， 而除2在計算機中可以簡單地用右移一位來完成 ， 從而提高算法的效率 。 （ 1） 基本思想 中點分割算法基本思想是：分別尋找直線段兩個端點各自對應(yīng)最遠的可見點 ， 只要該線段能在窗口內(nèi)留下一個可見段 ， 那么這個最遠的可見點只有兩種選擇：要么是直線段一個相應(yīng)端點；要么是在不斷中點再分過程中產(chǎn)生的某個子段的中點 。 77 圖中直線段 e說明 ， 該線段處于窗口內(nèi)的可見段部分是線段 S1S2, S1和 S2是可見段的兩個端點 ， 其中 S2是距原線段端點 P1最遠的可見點；同樣 ， S1是距原線段端點 P2最遠的可見點 。 下面 ， 我們以找出直線段 P1P2上離 P1點最遠的可見點為例 ， 來對中點再分裁減算法加以說明 。 78 算法步驟如下： （ l） 檢驗直線段 P1P2是否完全被排斥在窗口之外 。 如果是 ， 過程結(jié)束且無輸出線段 （ 如圖中的線段 b） ； 否則繼續(xù)執(zhí)行下一步 。 （ 2） 檢驗點 P2是否可見 。 如果是 ， 則 P2點就是離 P1點最遠的可見點 ， 過程結(jié)束 （ 圖中的線段 a） 。 如果 P2點是不可見的 （ 如圖中的線段 c或線段 d） ， 那么繼續(xù)執(zhí)行下一步 。 79 （ 3） 分割直線段 P1P2于中點 Pm（ 這是為了估計離 P1點最遠的可見點 ,把它簡單地取作中點 ） 。 如果線段 PmP2被完全排斥在窗口之外 ， 那么原估計還不足 （ 如圖 中的線段 d） ， 便以線段 P1Pm作為新的 P1P2線段從算法的第一步重新開始執(zhí)行 。 反之 ， 則以線段 PmP2為新的線段P1P2（ 如圖的線段 c） 從算法的第一步重新開始執(zhí)行 。 反復(fù)執(zhí)行上述三步，直至找到離 P1點最遠的可見點為止。 分割直線段P1P2于中點 Pm 線段 PmP2被完全排斥在窗口之外 ,以線段 P1Pm作為新的 P1P2再取中點 線段 PmP2沒有被完全排斥在窗口之外 ,以線段 PmP2作為新的 P1P2再取中點 80 這個過程確定了距離 P1點最遠的可見點 。 然后對調(diào)該線段的兩個端點 ， 以線段 P2P1為新的 P1P2線段 ， 重新開始實施該算法過程 ， 就可以確定出距離 P2點最遠的可見點 。這樣 ， 位于窗口內(nèi)可見段的兩個可見端點就確定了 。 從這個算法中我們可以看到 ， 整個裁剪過程總是在執(zhí)行第一步或第二步時結(jié)束 。 這種結(jié)果表明：被裁剪的線段要么完全處于窗口之外而被排除掉；要么能在窗口內(nèi)得到一個距對應(yīng)端點最遠的可見點 ， 這個可見點可能是原直線段的一個端點 ， 也可能是線段在被不斷地中點再分過程中 ， 最終得到的剛好和窗口邊框相重的那個中點 。 這里要注意的是：在判斷中點和窗口邊框相重時 ， 一般不需要坐標值一定相等 ， 也不大可能 ， 只要在精度許可前提下 ， 給出一個誤差允許范圍 。 81 三 、 多邊形裁剪 概述 前面我們討論了直線段剪裁 ， 多邊形裁剪是以線段裁剪為基礎(chǔ) ， 但又不同于線段的裁剪 。 多邊形裁剪要比一條線段裁剪復(fù)雜得多 。 如圖所示 ， 用一個矩形窗口去裁剪多邊形將會遇到各種不同情況 。 裁剪多邊形要解決兩個問題 。 其一是一個完整的封閉多邊形經(jīng)裁剪后一般不再是封閉的 ， 需要用窗口邊界適當部分來封閉它 。 其二是矩形窗口的四個角點在裁剪中是否要與其它交點連線 。 由于這兩個問題使得我們不能簡單地應(yīng)用直線段裁剪方法 。 而需要去研究適合多邊形裁剪特點的算法 。 82 一個完整的多邊形被裁剪成兩個獨立的多邊形 一個凹多邊形被裁剪成幾個小多邊形 多邊形 G經(jīng)矩形窗口裁剪后出現(xiàn) G1和G2兩個多邊形 83 多邊形剪裁原理 多邊形裁剪方法很多 ， 例如逐邊裁剪法 ， 雙邊裁剪法， 分區(qū)編碼裁剪法等 ， 這里僅介紹逐邊裁剪法 。 逐邊裁剪法是薩瑟蘭德 （ ） 和霍德曼（ Hodglhan） 在 1974年提出的 。 這種算法采用了分割處理 、 逐邊裁剪的方法 。 算法的依據(jù)是：簡單地通過對單一邊或面的裁剪實現(xiàn)對多邊形的裁剪 。 現(xiàn)討論窗口為矩形的裁剪 ， 先用窗口的第一條邊界對要裁剪的多邊形進行裁剪 ， 去掉窗口外的圖形 ， 保留窗口內(nèi)的圖形 ， 形成一個新的多邊形 。然后 ， 再用第二條邊界對這個新的多邊形進行裁剪 ， 再次生成一個新的多邊形 。 依次用第三 、 第四條邊界重復(fù)進行裁剪 ， 形成了最后裁剪出來的多邊形 ， 整個裁剪過程結(jié)束 84 （ a） 裁剪前圖形 （ b） 以 AB邊裁剪 （ c） 以 BC邊裁剪剪圖形 （ d） 以 CD邊裁剪剪圖形 （ e） 以 DA邊裁剪 先用窗口的第一條邊界對要裁剪的多邊形進行裁剪，去掉窗口外的圖形，保留窗口內(nèi)的圖形 再用窗口的第二條邊界對要裁剪的多邊形進行裁剪，去掉窗口外的圖形，保留窗口內(nèi)的圖形 85 逐邊裁剪法實質(zhì)是用窗口四條邊分別對多邊形一邊進行剪取 。 剪取后結(jié)果是輸出一個多邊形的頂點表 。 由于在剪取過程中 ， 實際是多邊形的每一邊與窗口的一邊界進行比較 ， 從而確定它們的位置關(guān)系 。 假定取多邊形頂點表中的某一點 Pi作為一邊的終點 ，表中位于前面的一點 Pi1作為該邊的起點 ,則邊 Pi－ 1 Pi被窗口的一邊界剪取后輸出一個或兩個頂點 ， 或者不輸出頂點 ， 若邊 Pi1 Pi完全可見 ， 則輸點 Pi， 需要注意的是這里不必再輸出邊的起點 Pi1。 因為輸出頂點表中的點是依序處理的 ， Pi1作為前一條邊的終點輸出 。 若邊 Pi1 Pi完全不可見 ， 則無輸出 。 若邊 Pi1Pi部分可見 ， 則此邊可能進入或離開窗口內(nèi)部區(qū)域 ， 若離開可見區(qū) ， 則必須計算并輸出此邊與窗口邊界的交點 。 若進入可見區(qū) ， 同樣需要計算并輸出這一邊與窗口邊界的交點 ， 由于此時邊的終點 Pi可見 ， 故應(yīng)輸出點 Pi。 86 起點 終點 邊 P4P5完全可見，則輸點 P5 邊 P6P7完全不可見，則無輸出 邊部分可見，則需計算此邊與窗口邊界的交點 87 對于多邊形的第一個頂點 P1只需判斷它是否可見 。 若可見 ， 則輸出并作為起點 P1。 若不可見 ， 則無輸出 。 但仍需作為點 P1保存 ， 以便對其它邊進行處理 。 對于多邊形的最后一條邊 PnP1需要另作處理 。 這時需將頂點表中第一點記為 F， 于是最后一邊變?yōu)?PnF， 這樣就可同其它邊一樣進行處理 。 確定點可見性和求多邊形的邊和窗口邊界交點 ， 可采取前面所述各種方法 。 例如編碼裁剪法 。 由于在這一剪取方法中 ， 被裁取多邊形的每一邊是依次處理的 ， 故只需作少許變動 ， 用同一子程序可以處理多邊形的每一邊 。 需要注意的是最后一個頂點需要作特殊處理 。 逐邊剪取算法是一個通用的剪取算法 ， 任一多邊形無論是凸多邊形還是凹多邊形均可用這一算法進行剪取。 這一算法簡單 ， 易于程序?qū)崿F(xiàn) ， 但計算量較大 ， 需要比較大的存貯區(qū)來存放剪取過程中待剪取的多邊形 。 88 四 、 其它類型圖形裁剪 1． 曲線的裁剪 繪制曲線通常采取用直線段逼近的辦法 ， 所以曲線的剪裁可用線段的剪裁來解決 。 由于逼近時總是將線段取得很短 ， 所以 ， 為了節(jié)省計算時間 ， 可以免去計算剪裁的交點 ， 只要線段端點中至少有一個在窗外 ， 就將該線段略去不畫 ， 達到剪裁的結(jié)果 。 這當然是一種近似的辦法 ， 然而也能保證一定的精度 ， 且提高了裁剪的效率 。 89 2. 字符裁剪 把每個字符看作是不可分割的整體 ， 對每一個字符串就可用逐字裁剪的方法 ， 把每個字符用一矩形 （ 字符框 ） 包圍起來 （ 見圖 ） ， 然后檢測該字符框中的某一點（ 如頂點或中心點 ） 的可見性 ， 把該點與窗口進行比較， 如果在窗口內(nèi) ， 就顯示該字符 ， 否則就舍棄不顯示 ，另外也可以用整個字符框的界線或其對角線與窗口進行比較 ， 當字符框或?qū)蔷€完全在窗口內(nèi)時才顯示該字符， 不過用字符框頂點或用字符框界線 （ 或?qū)蔷€ ） 裁剪的兩種方法 ， 只有當窗口邊與字符框界線平行時才等效， 否則必須以字符框界進行裁剪 。 90 裁剪字符串的一種粗略方法 ， 是把一個字符串作為不可分割的整體來處理 ， 用一個字符串框封閉起來 （ 見圖 ）， 檢測這個字符串框上的某一點 、 界線的對角線或者界線本身的可見性 ， 若在窗口內(nèi) ， 就顯示整串字符 ， 否則整串字符就不顯示 。 91 習(xí)題 作業(yè)題： p163 第 11 1 18。 92 謝謝大家！