【正文】 92 謝謝大家！ 。 90 裁剪字符串的一種粗略方法 ， 是把一個字符串作為不可分割的整體來處理 ， 用一個字符串框封閉起來 （ 見圖 ）， 檢測這個字符串框上的某一點 、 界線的對角線或者界線本身的可見性 ， 若在窗口內(nèi) ， 就顯示整串字符 ， 否則整串字符就不顯示 。 這當然是一種近似的辦法 ， 然而也能保證一定的精度 ， 且提高了裁剪的效率 。 88 四 、 其它類型圖形裁剪 1． 曲線的裁剪 繪制曲線通常采取用直線段逼近的辦法 ， 所以曲線的剪裁可用線段的剪裁來解決 。 逐邊剪取算法是一個通用的剪取算法 ， 任一多邊形無論是凸多邊形還是凹多邊形均可用這一算法進行剪取。 由于在這一剪取方法中 ， 被裁取多邊形的每一邊是依次處理的 ， 故只需作少許變動 ， 用同一子程序可以處理多邊形的每一邊 。 確定點可見性和求多邊形的邊和窗口邊界交點 ， 可采取前面所述各種方法 。 對于多邊形的最后一條邊 PnP1需要另作處理 。 若不可見 ， 則無輸出 。 86 起點 終點 邊 P4P5完全可見，則輸點 P5 邊 P6P7完全不可見，則無輸出 邊部分可見，則需計算此邊與窗口邊界的交點 87 對于多邊形的第一個頂點 P1只需判斷它是否可見 。 若邊 Pi1Pi部分可見 ， 則此邊可能進入或離開窗口內(nèi)部區(qū)域 ， 若離開可見區(qū) ， 則必須計算并輸出此邊與窗口邊界的交點 。 因為輸出頂點表中的點是依序處理的 ， Pi1作為前一條邊的終點輸出 。 由于在剪取過程中 ， 實際是多邊形的每一邊與窗口的一邊界進行比較 ， 從而確定它們的位置關(guān)系 。 依次用第三 、 第四條邊界重復進行裁剪 ， 形成了最后裁剪出來的多邊形 ， 整個裁剪過程結(jié)束 84 （ a） 裁剪前圖形 （ b） 以 AB邊裁剪 （ c） 以 BC邊裁剪剪圖形 （ d） 以 CD邊裁剪剪圖形 （ e） 以 DA邊裁剪 先用窗口的第一條邊界對要裁剪的多邊形進行裁剪，去掉窗口外的圖形，保留窗口內(nèi)的圖形 再用窗口的第二條邊界對要裁剪的多邊形進行裁剪，去掉窗口外的圖形，保留窗口內(nèi)的圖形 85 逐邊裁剪法實質(zhì)是用窗口四條邊分別對多邊形一邊進行剪取 。 現(xiàn)討論窗口為矩形的裁剪 ， 先用窗口的第一條邊界對要裁剪的多邊形進行裁剪 ， 去掉窗口外的圖形 ， 保留窗口內(nèi)的圖形 ， 形成一個新的多邊形 。 這種算法采用了分割處理 、 逐邊裁剪的方法 。 82 一個完整的多邊形被裁剪成兩個獨立的多邊形 一個凹多邊形被裁剪成幾個小多邊形 多邊形 G經(jīng)矩形窗口裁剪后出現(xiàn) G1和G2兩個多邊形 83 多邊形剪裁原理 多邊形裁剪方法很多 ， 例如逐邊裁剪法 ， 雙邊裁剪法， 分區(qū)編碼裁剪法等 ， 這里僅介紹逐邊裁剪法 。 由于這兩個問題使得我們不能簡單地應(yīng)用直線段裁剪方法 。 其一是一個完整的封閉多邊形經(jīng)裁剪后一般不再是封閉的 ， 需要用窗口邊界適當部分來封閉它 。 如圖所示 ， 用一個矩形窗口去裁剪多邊形將會遇到各種不同情況 。 81 三 、 多邊形裁剪 概述 前面我們討論了直線段剪裁 ， 多邊形裁剪是以線段裁剪為基礎(chǔ) ， 但又不同于線段的裁剪 。 這種結(jié)果表明：被裁剪的線段要么完全處于窗口之外而被排除掉；要么能在窗口內(nèi)得到一個距對應(yīng)端點最遠的可見點 ， 這個可見點可能是原直線段的一個端點 ， 也可能是線段在被不斷地中點再分過程中 ， 最終得到的剛好和窗口邊框相重的那個中點 。這樣 ， 位于窗口內(nèi)可見段的兩個可見端點就確定了 。 分割直線段P1P2于中點 Pm 線段 PmP2被完全排斥在窗口之外 ,以線段 P1Pm作為新的 P1P2再取中點 線段 PmP2沒有被完全排斥在窗口之外 ,以線段 PmP2作為新的 P1P2再取中點 80 這個過程確定了距離 P1點最遠的可見點 。 反之 ， 則以線段 PmP2為新的線段P1P2（ 如圖的線段 c） 從算法的第一步重新開始執(zhí)行 。 79 （ 3） 分割直線段 P1P2于中點 Pm（ 這是為了估計離 P1點最遠的可見點 ,把它簡單地取作中點 ） 。 如果是 ， 則 P2點就是離 P1點最遠的可見點 ， 過程結(jié)束 （ 圖中的線段 a） 。 如果是 ， 過程結(jié)束且無輸出線段 （ 如圖中的線段 b） ； 否則繼續(xù)執(zhí)行下一步 。 下面 ， 我們以找出直線段 P1P2上離 P1點最遠的可見點為例 ， 來對中點再分裁減算法加以說明 。 （ 1） 基本思想 中點分割算法基本思想是：分別尋找直線段兩個端點各自對應(yīng)最遠的可見點 ， 只要該線段能在窗口內(nèi)留下一個可見段 ， 那么這個最遠的可見點只有兩種選擇：要么是直線段一個相應(yīng)端點；要么是在不斷中點再分過程中產(chǎn)生的某個子段的中點 。 設(shè)直線的兩端點坐標為 P1 （ x1， y1） 和 P2 （ x2， y2） 如圖所示 ， 直線與窗口四條邊線的交點坐標 ， 可分別由下列公式確定： （ 利用相似直角三角形比例關(guān)系 ） 左交點 : 右交點 : 111212 )( yxWxxyyyWxxlxl??????111212 )( yxWxxyyyWxxrxr??????74 下交點： 上交點： 111212 )( xyWyyxxxWyybyb??????111212 )( xyWyyxxxWyytyb??????75 4. 矢量裁剪法 (略 ) 76 5． 中點分割裁剪法 上面介紹兩種方法都要計算直線段與窗口邊界交點 ， 這不可避免地要進行大量乘除運算 ， 勢必會降低程序執(zhí)行效率 。 應(yīng)該指出的是 ， 分割線段是從 C點還是 D點開始 ， 這是難以確定的 ， 因此只能隨機的 ， 但是最后結(jié)果是相同的。 這樣可以逐段地舍棄位于窗口外的線段 ， 保留剩在窗口內(nèi)的線段 。 此檢查判斷直線在窗口外 ， 應(yīng)全部舍棄 。 Wxl ≤(x 1,x2) ≤ Wxr Wyb ≤(y 1,y2)≤ Wyt 則兩端點代碼 C1＝ C2＝ 0 表示均在窗口內(nèi) ， 應(yīng)全部保留 71 ② 當兩個端點在窗口邊線外的同側(cè)位置 ， 則它們的四位代碼中 ， 有一相同位 ， 同時為 “ 1” ， 顯然兩個端點代碼的邏輯乘不等于零 。 70 由編碼規(guī)則可知 ， 若線段兩端點編碼均為零 ， 則兩點均在窗口內(nèi) ， 線段完全可見 。 下面我們介紹幾種直線剪裁法 69 3． 編碼裁剪法 （ 1） 編碼規(guī)則 這一方法是由庫恩和薩瑟蘭德 （ Cohen和 Sutherland）提出的 ， 該方法是把包含窗口的平面區(qū)域沿窗口的四條邊線分成九個區(qū)域 . 每個區(qū)域用一個四位代碼來表示 ， 代碼中每一位分別是 0或 1， 是按照窗口邊線來確定的 ， 下面給出編碼規(guī)則 ， 其中 最右邊的位是第一位 ， 依次第 二 、 三 、 四位 。 直線段完全被排斥在窗口的邊框之外 直線段完全被包含在窗口之內(nèi) 直線段和窗口的一條邊框相交，使得該直線段被相交點分成兩截，其中的一個截段落在窗口之內(nèi)，而另一個截段留在窗口之外 直線段貫穿整個窗口，這樣，直線段就與窗口的兩條邊框相交，使得原直線段被分成三個截段，其中只能有一個截段落在窗口內(nèi)，而另外的兩段都處于窗口之外， 68 歸納以上四種情況，可以得出這樣一個結(jié)論： 對于任意一條直線段，它要么被完全排斥在窗口之外，如上述的情況（ 1）；要么在窗口內(nèi)留下一個可見段，并且只能有一個可見段 ,如上所述的情況（ 2）、（ 3）和（4）。直線段是組成一切其它圖形的基礎(chǔ) 。 這樣的裁剪過程所在時間就會過長 ， 不經(jīng)濟 。 如圖所示 : Wxl ≤ xW ≤ Wxr Wyb ≤ yW ≤ Wyt 滿足上述兩個不等式的點即在窗口內(nèi) ， 屬于可見的點 ， 應(yīng)該保留；反之 ， 則該點不可見 ， 應(yīng)予舍棄 。 裁剪算法中最基本的情況是點的裁剪。 66 三、 直線段裁剪 點的剪裁 裁剪的過程就是對窗口內(nèi)每個圖形元素都得劃分一下可見部分和不可見部分 。先進行平移變換將窗口左下角坐標移到用戶坐標原點，接著進行比例變換，使窗口中各點比例變換到設(shè)備坐標系（屏幕）中，最后再作平移交換，使原點移到視圖左下角。 62 如圖所示 ， 設(shè)在用戶坐標系下定義的窗口為：左下角點坐標 （ Wxl， Wyb） ， 右上角點坐標 （ Wxr， Wyt） ； 在設(shè)備坐標系中定義的視區(qū)為：左下角點坐標 （ Vxl， Vyb） ， 右上角點坐標 （ Vxr ， Vyt） 。 同時用戶圖形區(qū)還可分為各個子區(qū) ， 以滿足用戶顯示多層窗口的需要 。 下圖表示窗口與視圖關(guān)系 。 視圖區(qū)可用來顯示某一窗口內(nèi)圖形 。 窗口區(qū)，用左下角和右上角來定義 60 視圖區(qū)：簡稱視圖 （ Viewport） ， 是在屏幕上定義的一個小于或等于屏幕區(qū)域一個矩形塊 。我們可用該矩形的左下角和右上角兩點坐標來定義其大小和位置 。 此坐標系擁有的區(qū) 域在理論上是無限的 ， 在使用時我們可以把它 當作是一個有限的矩形區(qū) ， 即用戶域 。 此時 ， 窗口外那部分被裁剪掉 。都有一部分在窗口外 。、 F39。的一部分 ， 而直線段 E39。F39。 所以裁剪的目的是顯示可見點和可見部分 ， 刪除視區(qū)外的部分 。由于顯示屏幕的尺寸及其分辨率限制，這樣復雜的圖形往往不能全部顯示出來，即使將它們采用比例變換后全部顯示在同一屏幕上，也只能表現(xiàn)一個大致輪廓，并且圖形擁擠不清。 裁剪就是將指定窗口作為圖形邊界 ， 從一幅大的畫面中抽取所需的具體信息， 以顯示某一局部畫面或視圖 。 56 二維圖像裁剪 一、概述 定義 為了描述圖形對象 ， 我們必須存儲它的全部信息 ，