【正文】 棟 )Barsky 算法 算法的基本思想： 從 A、 B和 P1三點中找出最靠近 P2 的點 ( P1)， 從 C、 D和 P2三點中找 出最靠近 P1的點 (C )， 則 P1C 就是 P1P2 線段上的可見部分 。 將被裁剪的線段 P1P2 表示成參數(shù)方程形式 ： x＝ x1＋ △ xt 其中 △ x＝ x2－ x1 y＝ y1＋ △ yt △ y＝ y2－ y1 x y xL xR yB yT P1 P2 A B C D ( 0 ≤ t ≤ 1 ) 另外 ， 把窗口的四條邊分成二類： 始邊 和 終邊 。 △ x＞＝ 0， x＝ xL為始邊 ， x＝ xR為終邊 。 △ y＞＝ 0， y＝ yB為始邊 ， y＝ yT為終邊 。 反之 ， △ x＜ 0， x＝ xR為始邊 ， x＝ xL為終邊 。 △ y＜ 0， y＝ yT為始邊 ， y＝ yB為終邊 。 求出 P1P2和二條始邊的交點的參數(shù) t1′ 和 t1″ 令 t1＝ max (t1′ ， t1″ ， 0) 則 t1 即為 A、 B、 P1三點中最靠近 P2的點的參數(shù) 。 求出 P1P2和二條終邊的交點的參數(shù) t2′ 和 t2″ 令 t2＝ min (t2′ ， t2″ ， 1) 則 t2 即為 C、 D、 P2三點中最靠近 P1的點的參數(shù) 。 當 t2＞ t1時 ， 方程 (1)中參數(shù) t∈[t 1,t2]的線段就是 P1P2的可見部分 。 當 t2 t1時 ， 整個線段為不可見 。 x y xL xR yB yT P1 P2 A B C D 二 . 字符裁剪方法 1. 字符的表示方法 點陣字符 ——每個字符用一個位圖 (掩膜 ) 來表示，其大小由位圖的尺寸來確定，如 7 9， 9 16， 16 24 等。 1 1 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 P在字庫的表示 P的顯示結果 矢量字符 —— 選一個正方形 網(wǎng)格 ，作為字符的 局部坐標 空間，網(wǎng)格的大小可選 16 16， 32 32， 64 64等。每個字符由構成它的 筆畫 組成，每個筆畫又由其兩端確定。每個 端點 保存它的 坐標值 及 連線標志 。 x y o p1 p2 p3 p4 p5 p6 63 63 字符的編碼 x1 y1 0 x2 y2 1 x3 y3 0 x4 y4 1 x5 y5 0 x6 y6 1 － 1 0表示不連線 1表示連線 字符結束標志 特點 ：除用直線段表示筆畫外，還可采用二次三次曲線段。 對矢量字符的變換是對其端點進行圖形的幾何變換。 2. 字符的裁剪 簡單裁剪方法： 用點陣字符的掩膜或矢量字符的網(wǎng)格大小作為字符的包 圍框，若該包圍框在窗口內(nèi)，則顯示字符；否則，不予顯示。 精確裁剪方法： 對于點陣字符，判斷組成其筆畫的每個像素點是否位于 窗口內(nèi)。 對于矢量字符，對組成其筆畫的每條線段進行裁剪。 三. 多邊形的裁剪 平面多邊形是由若干直線段圍成的平面封閉圖形， 因此裁剪后的結果仍應是一個多邊形，即是封閉的圖形，而且仍應保持原多邊形各邊的連接順序。 對于多邊形的裁剪要著重考慮下列問題：如何把多邊形落在窗口邊界上的交點正確地、按序連接成裁剪后的多邊形，其中包括決定窗口邊界及拐角點地取舍。 1． SutherlandHodgman(SH)算法 該算法的出發(fā)點是把一個解決復雜問題的全過程分 解為幾個簡單過程。其中的每個簡單過程僅僅是完成一 個單邊裁剪，所以每一個簡單過程都是類似的重復，這 樣就使復雜問題的解決方法最終得到簡化。 思路 ：將多邊形的各邊先相對于窗口的某一條邊界進行裁剪，然后將裁剪結果再用另一條邊界進行裁剪，如此重復多次，便可得到最終結果。 實現(xiàn)方法 ： ① 設置二個表 輸入頂點表 (向量 )—用于存放被裁剪多邊形的頂點 p1pm。 輸出頂點表 (線性鏈表 )—用于存放裁剪過程中及結果的頂 點 q1qn。 ② 輸入頂點表中各頂點要求按一定順序排列 ， 一般可采用順時 針或逆時針方向 。 ③ 相對于裁剪窗口的各條邊界 ， 按頂點表中的順序 ， 逐邊進行 裁剪 。 具體操作 ： 讀入頂點 Pi， 除第一個頂點外 ， 要檢查每一個 Pi 和前一頂 點 Pi1是否位于窗口邊界的同一側 ， 若不在同一側 ， 則需計算出交點送輸出頂點表 。 Pi 若位于邊界線的可見一側 ， 則 Pi 送輸出頂點表 Pi 若位于邊界線的不可見一側 ， 則將其舍棄 。 最后一個頂點還要與 第一個頂點 一起進行同樣的檢查 。 p1 p2 p3 p4 p5 q1 q2 q3 q4 p1 p3 p4 p5 q1 q2 p3 p4 p5 q5 q6 q7 q8 q1 q2 p3 q7 q8 q5 q6 q4 q3 裁剪前： 裁剪后： 輸入頂點表： p1p2p3p4p5 輸入頂點表 : 不變 輸出頂點表： 空 輸出頂點表 : q3q1q2p3q7q8q5q6q4 算法特點 ： ∵ 算法中相對于各窗口邊界的裁剪過程相同，且每次都是相對于前一次的結果進行處理。 ∴ 可采用 遞歸 算法，可不保留中間多邊形的頂點，而節(jié)省數(shù)據(jù)的存儲量，但遞歸會影響速度 。 q3 q4 q1 q2 p3 p4 q5 q6 q3 q4 q1 q2 p3 SH算法流程圖 單邊裁剪 開 始 Pi是第一點？ SPi與 e相交？ 計算并輸出交點 K S Pi Pi位于 e的可見側？ 輸出 Pi 輸入頂點 Pi Pi是最后一點？ PiF與 e相交？ 計算并輸出交點 K 結 束 F Pi Y N Y N N Y Y N Y N 2． WeilerAtherton（ WA）算法 WA算法可以用一個有內(nèi)孔的凹多邊形去裁剪另一個也有內(nèi)孔的凹多邊形 。 被裁剪的多邊形 ——主多邊形 裁剪區(qū)域 ——裁剪多邊形 思路 ：主多邊形和裁剪多邊形均用它們的頂點表來定義 。 各多邊形的外部邊界取順時針方向 ， 而其內(nèi)部邊界或孔取逆時針方向 。 主多邊形和裁剪多邊形的邊界若相交 ， 交點 必定 成對 地出現(xiàn) ， 其中一個交點為主多邊形邊進入裁剪多邊形內(nèi)部時的交點（ 稱進點 ） ， 另一個交點則為離開時的交點 （ 稱出點 ） 。 這兩類交點分別用 進點表 和 出點表 來存放 。 算法 ： 分別建立主多邊形和裁剪多邊形的頂點表 求出主多邊形與裁剪多邊形的交點 （ 進點和出點 ） 并分別建立進點表和出點表 將交點加入各頂點表中 if 進點表為空 then finish 1 取一進點作為始點 2 跟蹤主多邊形頂點表 ， 直至發(fā)現(xiàn)下一交點 ， 復制這一段主多邊形頂點到內(nèi)表中 根據(jù)交點處指針 ， 轉到裁剪多邊形頂點表中的相應位置跟蹤裁剪多邊形頂點表 ， 直至發(fā)現(xiàn)下一交點 ， 復制這一段裁剪多邊形頂點到內(nèi)表中 。 if 該交點不是起始點 then 2 if 進點表中還有未遍歷到的交點 then 1 3 finish c1 c2 c3 c4 s1 s2 s3 s4 s5 s6 s7 I1 I2 I3 I4 I5 I6 I7 I8 裁剪多邊形 主多邊形 主多邊形 裁剪多邊形 頂點表 頂點表 s1 c1 I1 I8 I2 I1 s2 c2 I3 I2 s3 I3 I4 c3 s4 I4 I5 I5 I6 c4 s5 I6 I7 I7 s6 c1 I8 s7 s1 起點 本 章 小 結 1。圖形和數(shù)字之間的聯(lián)系是通過坐標建立起來的。圖形的幾何 變換實質(zhì)上就是圖形的坐標變換。因此，圖形變換必須在設 定的 坐標系 中進行。 2。為了用 矩陣的形式來描述 圖形變換，采用了 齊次坐標 表示。 3。要熟悉 二維和三維變換矩陣 中各個部分的作用，對于復雜的 圖形變換，需要通過若干個變換 矩陣的級聯(lián) 才能實現(xiàn)。 4。 二維線段的裁剪 是實現(xiàn)圖形裁剪的基本技術，要熟悉各種裁 剪方法的基本思路。 5。由于多邊形繪制時的特殊要求，所以多邊形的裁剪要用專門 的方法來實現(xiàn)。 SH算法和 WA算法各有特色，可分別用于不 同的情況。