1、貴州大學實驗報告學院： 計算機科學與信息學院 專業：軟件工程 班級： 102班姓名學號實驗組實驗時間指導教師成績實驗項目名稱實驗五 直線和多邊形的裁剪實驗目的掌握直線段的裁剪算法以及多邊形的裁剪算法實驗要求熟練掌握直線段的裁剪算法以及多邊形的裁剪算法的基本原理，并編寫測試代碼進行實驗。實驗原理Cohen-Sutherland直線剪裁算法以區域編碼為基礎，將窗口及其周圍的，8個方向以4 bit的二進制數進行編碼。右圖所示的編碼方法將窗口及其鄰域分為5個區域： 內域：區域(0000)。 上域：區域(1001, 1000, 1010)。 下域：區域(0101, 0100, 0110)。 左域：區域(

2、1001, 0001, 0101)。 右域：區域(1010, 0010, 0110)。 當線段的兩個端點的編碼的邏輯“與”非零時 ，線段為顯然不可見的，對某線段的兩個端點的區號進行位與運算，可知這兩個端點是否同在視區的上、下、左、右；Cohen-Sutherland直線剪裁算法的算法思想是：對于每條線段P1P2分為三種情況處理。（1）若P1P2完全在窗口內，則顯示該線段P1P2簡稱“取”之。（2）若P1P2明顯在窗口外，則丟棄該線段，簡稱“棄”之。（3）若線段既不滿足“取”的條件，也不滿足“棄”的條件，則在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復上述處理。為快速判斷

3、，采用如下編碼方法：由窗口四條邊所在直線把二維平面分成9個區域(右圖)，每個區域賦予一個四位編碼：CtCbCrCl（上下右左）；直線的端點都按其所處區域賦予相應的區域碼，用來標識出端點相對于裁剪矩形邊界的位置。各位編碼含義：上：if yymax，Ct=1，else, 0;下：if yxmax，Cr=1，else, 0;左：if xxmax，Cl=1，else, 0;對某線段的兩個端點的區號進行位與運算，可知這兩個端點是否同在視區的上、下、左、右； 如果兩端點的編碼均為0000，表示直線在窗口內。 如果兩端點的編碼相與不為0000，表示直線在窗口外。 如果兩端點的編碼不全為0000，但相與為00

4、00，則該直線部分可見，需計算直線與窗口的交點，確定哪一部分可見。裁剪一條線段時，先求出P1P2所在的區號code1,code2。若code1=0,且code2=0，則線段P1P2在窗口內，應取之。若按位與運算code1&code20，則說明兩個端點同在窗口的上方、下方、左方或右方。可判斷線段完全在窗口外，可棄之。否則，按第三種情況處理。求出線段與窗口某邊的交點，在交點處把線段一分為二，其中必有一段在窗口外，可棄之。在對另一段重復上述處理。在實現本算法時，不必把線段與每條窗口邊界依次求交，只要按順序檢測到端點的編碼不為0，才把線段與對應的窗口邊界求交。算法分析：本算法的優點在于簡單，易于實現。

5、用編碼方法可快速判斷線段的完全可見和顯然不可見，他可以簡單的描述為將直線在窗口左邊的部分刪去，按左，右，下，上的順序依次進行，處理之后，剩余部分就是可見的了。在這個算法中求交點是很重要的，他決定了算法的速度。本算法對于其他形狀的窗口是否同樣有效就值得討論了，這也證明了在圖形算法中，沒有幾個是對大多數情況有效的。特別適用二種情形：大窗口場合（線段大多數為完全可見）；窗口特別小場合(線段大多數為完全不可見。光標拾取圖形，光標看作小的裁剪窗口)。多邊形裁剪算法：Sutherland-Hodgema算法算法原理：通過對單一邊或面的裁剪來實現多邊形的裁剪分割處理策略：將多邊形關于矩形窗口的裁剪分解為多邊

6、形關于窗口四邊所在直線的裁剪。一次用窗口的一條邊裁剪多邊形。流水線過程(左上右下)：前邊的結果是后邊的輸入。亦稱逐邊裁剪算法。可見一側PS全部可見輸出點P可見一側PS全部不可見無輸出點可見一側PS離開可見一側輸出點11可見一側PS進入可見一側，輸出點1和點P1算法的每一次輸出（包括中間結果）都是一個多邊形的頂點表，且所有頂點均位于相應窗口裁剪邊或面的可見一側。由于多邊形的每一條邊需要與裁剪邊或面分別進行比較，因此只需要討論單條邊和單個裁剪邊或面之間可能的位置關系。假設S，P為多邊形的兩個相鄰頂點，且S為該邊的起點，P為該邊的終點，則變SP與裁剪邊或面之間只有4種可能的關系。如下圖：由上可見，每

7、一次將多邊形的邊與裁剪邊或面比較后，輸出一個或兩個頂點，也可能無輸出點。如果SP邊完全可見，則輸出P點，不必輸出起點S，因為頂點是按順序處理的，S是作為前一邊的終點輸出的。如果SP邊完全不可見，則無輸出。如果SP邊部分可見，則SP邊可能進入或離開裁剪邊或面的可見一側。 如果SP邊離開裁剪邊或面的可見一側，則輸出SP與裁剪邊或面交點。如果SP邊進入裁剪邊或面的可見一側，則輸出兩點，一個為SP與裁剪邊或面的交點，一個是P點。對于多邊形的第一個頂點，只需判斷其可見性。如果可見，則輸出且作為起點S；否則無輸出，但還是要作為S保存，以便后續點處理。對于最后一條邊PnP1，其處理方法是：標志第一頂點為F，

8、這樣最后一條邊則為PnF，可與其他邊作相同的處理。實現方法：設置二個表：輸入頂點表：用于存放被裁剪多邊形的頂點p1-pm。輸出頂點表：用于存放裁剪過程中及結果的頂點q1-qn。輸入頂點表中各頂點要求按一定順序排列，一般可采用順時針或逆時針方向。相對于裁剪窗口的各條邊界，按頂點表中的順序，逐邊進行裁剪算法分析：對凸多邊形應用本算法可以得到正確的結果，但是對凹多邊形的裁剪將顯示出一條多余的直線。這種情況在裁剪后的多邊形有兩個或者多個分離部分的時候出現。因為只有一個輸出頂點表，所以表中最后一個頂點總是連著第一個頂點。解決這個問題有多種方法，一是把凹多邊形分割成若干個凸多邊形，然后分別處理各個凸多邊形

9、。二是修改本算法，沿著任何一個裁剪窗口邊檢查頂點表，正確的連接頂點對。實驗環境硬件平臺：PC機軟 件：Windows7平臺，eclipse集成開發環境，java編程語言。實驗步驟1. 掌握算法原理；2. 依據算法，編寫源程序并進行調試；3. 對運行結果進行保存與分析；4. 把源程序以文件的形式提交；5. 按格式書寫實驗報告。實驗內容一、直線段裁剪算法的核心代碼為：計算（x,y）點的編碼的方法：private int encode(double x, double y) / 求（x,y）點的編碼int code = 0;if (x XR) / 點位于矩形的右邊code |= RIGHT; / 并

10、上右邊的編碼0010 else if (y YT) / 點位于矩形的上邊code |= TOP; / 并上上邊的編碼1000return code;直線段裁剪的方法：private void lineCut(double x1, double y1, double x2, double y2) / 直線的起點(x1,y1)和終點(x2,y2)double x = 0, y = 0;int code1, code2, code;code1 = this.encode(x1, y1);/ 起點的編碼code2 = this.encode(x2, y2);/ 終點的編碼while (code1 !=

11、 0 | code2 != 0) if (code1 & code2) != 0) / 兩端點的編碼相與不為0，表示直線在窗口外return;if (code1 != 0) code = code1; else code = code2;if (LEFT & code) != 0) / 直線的端點與矩形窗口的左邊編碼相與！=0x = XL;y = y1 + (y2 - y1) * (XL - x1) / (x2 - x1);/ 求直線與矩形窗口的左邊界的交點 else if (RIGHT & code) != 0) / 直線的端點與矩形窗口的右邊編碼相與！=0x = XR;y = y1 + (

12、y2 - y1) * (XR - x1) / (x2 - x1);/ 求直線與矩形窗口的右邊界的交點 else if (BOTTOM & code) != 0) / 直線的端點與矩形窗口的下邊編碼相與！=0y = YB;x = x1 + (x2 - x1) * (YB - y1) / (y2 - y1);/ 求直線與矩形窗口的下邊界的交點 else if (TOP & code) != 0) / 直線的端點與矩形窗口的上邊編碼相與！=0y = YT;x = x1 + (x2 - x1) * (YT - y1) / (y2 - y1);/ 直線的端點與矩形窗口的上/ 邊編碼相與！=0if (co

13、de = code1) x1 = x;y1 = y;code1 = encode(x, y); else x2 = x;y2 = y;code2 = encode(x, y);g.drawLine(int) (x1 + 0.5), (int) (y1 + 0.5), (int) (x2 + 0.5),(int) (y2 + 0.5);二、多邊形裁剪的核心代碼為：通過點集畫直線或者多邊形：private void draw() /通過點集畫直線或者多邊形for (int i = 1; i points.size(); i+) Point p1 = new Point();p1 = points.

14、get(i);int x1 = (int) p1.getX();int y1 = (int) p1.getY();Point p2 = new Point();p2 = points.get(i - 1);int x2 = (int) p2.getX();int y2 = (int) p2.getY();g.drawLine(x1, y1, x2, y2);多邊形的裁剪函數：private Point cutPicture(Point point, Point edge) / 剪裁函數，參數為（點集，邊）Point intersectPoint = new Point20;/存放交點的集合fo

15、r (int j = 0; j 20; j+) intersectPointj = new Point();Point s = new Point();Point p = new Point();Point t = new Point();int i = 0;int length = point.length;s = pointlength - 1;for (int j = 0; j length; j+) p = pointj;if (inside(p, edge) / sp在窗口內，情況1if (inside(s, edge) intersectPointi = p;i += 1; els

16、e / s在窗口外，情況4t = intersect(s, p, edge);intersectPointi = t;i += 1;intersectPointi = p;i += 1; else if (inside(s, edge) / s在窗口內，p在窗口外，情況3t = intersect(s, p, edge);intersectPointi = t;i += 1;/ 情況2沒有輸出s = p;List tempList = new ArrayList();for (int k = 0; k i; k+) if (intersectPointk != null) Point pt =

17、 intersectPointk;tempList.add(pt);Point temp = new PointtempList.size();for (int j = 0; j tempList.size(); j+) tempj = new Point();tempj = tempList.get(j);intersectPoint = temp;return intersectPoint;判斷點是否在裁剪邊的可見側：private boolean inside(Point point, Point edge) /判斷點是否在裁剪邊的可見側/ 裁剪邊為窗口下邊if (edge0.y = e

18、dge1.y) & (edge0.x = edge0.y) return true;/ 裁剪邊為窗口上邊if (edge0.y = edge1.y) & (edge0.x edge1.x) if (point.y = edge0.y) return true;/ 裁剪邊為窗口右邊if (edge0.x = edge1.x) & (edge0.y edge1.y) if (point.x edge1.y) if (point.x = edge0.x) return true;return false;直線段與窗口邊界求交：private Point intersect(Point s, Poin

19、t p, Point edge) /直線段與窗口邊界求交，并返回交點Point t = new Point();if (edge0.y = edge1.y) / 水平裁剪邊t.y = edge0.y;t.x = s.x + (edge0.y - s.y) * (p.x - s.x) / (p.y - s.y); else if (edge0.x = edge1.x) / 垂直裁剪邊t.x = edge0.x;t.y = s.y + (edge0.x - s.x) * (p.y - s.y) / (p.x - s.x);return t;鼠標的監聽類（內部類）：class MouseMonito

20、r extends MouseAdapter /通過鼠標的單擊獲取點，并畫出直線或者多邊形public void mouseClicked(MouseEvent e) points.add(e.getPoint();if (points.size() 1) draw();鍵盤的監聽類（內部類）：class KeyMonitor extends KeyAdapter / 鍵盤控制public void keyPressed(KeyEvent e) switch (e.getKeyCode() case KeyEvent.VK_R:/ 清空畫布和點集panel.repaint();points.r

21、emoveAll(points);break;case KeyEvent.VK_W:/對裁剪窗口的處理g.setColor(Color.RED);g.drawRect(XL, YB, XR - XL, YT - YB);/存放裁剪窗口的邊top = new Point2;/ 存放裁剪窗口的上邊top0 = new Point(XL, YB);top1 = new Point(XR, YB);right = new Point2;/存放裁剪窗口的右邊right0 = new Point(XR, YB);right1 = new Point(XR, YT);bottom = new Point2;

22、/存放裁剪窗口的下邊bottom0 = new Point(XR, YT);bottom1 = new Point(XL, YT);left = new Point2;/存放裁剪窗口的左邊left0 = new Point(XL, YT);left1 = new Point(XL, YB);break;case KeyEvent.VK_A:/對直線段進行裁剪g.setColor(Color.GREEN);Point p1 = points.get(0);Point p2 = points.get(1);lineCut(p1.getX(), p1.getY(), p2.getX(), p2.ge

23、tY();break;case KeyEvent.VK_B:/對多邊形進行裁剪source = new Pointpoints.size();/得到多邊形的點for (int i = 0; i points.size(); i+) sourcei = points.get(i);g.setColor(Color.GREEN);wT = cutPicture(source, top);/得到多邊形與裁剪窗口上邊的交點wR = cutPicture(wT, right);/得到多邊形與裁剪窗口右邊的交點wB = cutPicture(wR, bottom);/得到多邊形與裁剪窗口下邊的交點wL = cutPicture(wB, left);/得到多邊形與裁剪窗口左邊的交點int length = wL.length;/ 得到剪裁后的頂點集合,并畫出圖形for (int j = 0; j