1、貴州大學(xué)實(shí)驗(yàn)報(bào)告學(xué)院： 計(jì)算機(jī)科學(xué)與信息學(xué)院 專業(yè)：軟件工程 班級(jí)： 102班姓名學(xué)號(hào)實(shí)驗(yàn)組實(shí)驗(yàn)時(shí)間指導(dǎo)教師成績(jī)實(shí)驗(yàn)項(xiàng)目名稱實(shí)驗(yàn)五 直線和多邊形的裁剪實(shí)驗(yàn)?zāi)康恼莆罩本€段的裁剪算法以及多邊形的裁剪算法實(shí)驗(yàn)要求熟練掌握直線段的裁剪算法以及多邊形的裁剪算法的基本原理，并編寫(xiě)測(cè)試代碼進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)原理Cohen-Sutherland直線剪裁算法以區(qū)域編碼為基礎(chǔ)，將窗口及其周圍的，8個(gè)方向以4 bit的二進(jìn)制數(shù)進(jìn)行編碼。右圖所示的編碼方法將窗口及其鄰域分為5個(gè)區(qū)域： 內(nèi)域：區(qū)域(0000)。 上域：區(qū)域(1001, 1000, 1010)。 下域：區(qū)域(0101, 0100, 0110)。 左域：區(qū)域(

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

3、，采用如下編碼方法：由窗口四條邊所在直線把二維平面分成9個(gè)區(qū)域(右圖)，每個(gè)區(qū)域賦予一個(gè)四位編碼：CtCbCrCl（上下右左）；直線的端點(diǎn)都按其所處區(qū)域賦予相應(yīng)的區(qū)域碼，用來(lái)標(biāo)識(shí)出端點(diǎn)相對(duì)于裁剪矩形邊界的位置。各位編碼含義：上：if y>ymax，Ct=1，else, 0;下：if y<ymax，Cb=1，else, 0；右：if x>xmax，Cr=1，else, 0;左：if x<xmax，Cl=1，else, 0;對(duì)某線段的兩個(gè)端點(diǎn)的區(qū)號(hào)進(jìn)行位與運(yùn)算，可知這兩個(gè)端點(diǎn)是否同在視區(qū)的上、下、左、右； 如果兩端點(diǎn)的編碼均為0000，表示直線在窗口內(nèi)。 如果兩端點(diǎn)的編碼相

4、與不為0000，表示直線在窗口外。 如果兩端點(diǎn)的編碼不全為0000，但相與為0000，則該直線部分可見(jiàn)，需計(jì)算直線與窗口的交點(diǎn)，確定哪一部分可見(jiàn)。裁剪一條線段時(shí)，先求出P1P2所在的區(qū)號(hào)code1,code2。若code1=0,且code2=0，則線段P1P2在窗口內(nèi)，應(yīng)取之。若按位與運(yùn)算code1&code20，則說(shuō)明兩個(gè)端點(diǎn)同在窗口的上方、下方、左方或右方。可判斷線段完全在窗口外，可棄之。否則，按第三種情況處理。求出線段與窗口某邊的交點(diǎn)，在交點(diǎn)處把線段一分為二，其中必有一段在窗口外，可棄之。在對(duì)另一段重復(fù)上述處理。在實(shí)現(xiàn)本算法時(shí)，不必把線段與每條窗口邊界依次求交，只要按順序檢測(cè)到端

5、點(diǎn)的編碼不為0，才把線段與對(duì)應(yīng)的窗口邊界求交。算法分析：本算法的優(yōu)點(diǎn)在于簡(jiǎn)單，易于實(shí)現(xiàn)。用編碼方法可快速判斷線段的完全可見(jiàn)和顯然不可見(jiàn)，他可以簡(jiǎn)單的描述為將直線在窗口左邊的部分刪去，按左，右，下，上的順序依次進(jìn)行，處理之后，剩余部分就是可見(jiàn)的了。在這個(gè)算法中求交點(diǎn)是很重要的，他決定了算法的速度。本算法對(duì)于其他形狀的窗口是否同樣有效就值得討論了，這也證明了在圖形算法中，沒(méi)有幾個(gè)是對(duì)大多數(shù)情況有效的。特別適用二種情形：大窗口場(chǎng)合（線段大多數(shù)為完全可見(jiàn)）；窗口特別小場(chǎng)合(線段大多數(shù)為完全不可見(jiàn)。光標(biāo)拾取圖形，光標(biāo)看作小的裁剪窗口)。多邊形裁剪算法：Sutherland-Hodgema算法算法原理：通

6、過(guò)對(duì)單一邊或面的裁剪來(lái)實(shí)現(xiàn)多邊形的裁剪分割處理策略：將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪。一次用窗口的一條邊裁剪多邊形。流水線過(guò)程(左上右下)：前邊的結(jié)果是后邊的輸入。亦稱逐邊裁剪算法。可見(jiàn)一側(cè)PS全部可見(jiàn)輸出點(diǎn)P可見(jiàn)一側(cè)PS全部不可見(jiàn)無(wú)輸出點(diǎn)可見(jiàn)一側(cè)PS離開(kāi)可見(jiàn)一側(cè)輸出點(diǎn)11可見(jiàn)一側(cè)PS進(jìn)入可見(jiàn)一側(cè)，輸出點(diǎn)1和點(diǎn)P1算法的每一次輸出（包括中間結(jié)果）都是一個(gè)多邊形的頂點(diǎn)表，且所有頂點(diǎn)均位于相應(yīng)窗口裁剪邊或面的可見(jiàn)一側(cè)。由于多邊形的每一條邊需要與裁剪邊或面分別進(jìn)行比較，因此只需要討論單條邊和單個(gè)裁剪邊或面之間可能的位置關(guān)系。假設(shè)S，P為多邊形的兩個(gè)相鄰頂點(diǎn)，且S為該邊

7、的起點(diǎn)，P為該邊的終點(diǎn)，則變SP與裁剪邊或面之間只有4種可能的關(guān)系。如下圖：由上可見(jiàn)，每一次將多邊形的邊與裁剪邊或面比較后，輸出一個(gè)或兩個(gè)頂點(diǎn)，也可能無(wú)輸出點(diǎn)。如果SP邊完全可見(jiàn)，則輸出P點(diǎn)，不必輸出起點(diǎn)S，因?yàn)轫旤c(diǎn)是按順序處理的，S是作為前一邊的終點(diǎn)輸出的。如果SP邊完全不可見(jiàn)，則無(wú)輸出。如果SP邊部分可見(jiàn)，則SP邊可能進(jìn)入或離開(kāi)裁剪邊或面的可見(jiàn)一側(cè)。 如果SP邊離開(kāi)裁剪邊或面的可見(jiàn)一側(cè)，則輸出SP與裁剪邊或面交點(diǎn)。如果SP邊進(jìn)入裁剪邊或面的可見(jiàn)一側(cè)，則輸出兩點(diǎn)，一個(gè)為SP與裁剪邊或面的交點(diǎn)，一個(gè)是P點(diǎn)。對(duì)于多邊形的第一個(gè)頂點(diǎn)，只需判斷其可見(jiàn)性。如果可見(jiàn)，則輸出且作為起點(diǎn)S；否則無(wú)輸出，但還

8、是要作為S保存，以便后續(xù)點(diǎn)處理。對(duì)于最后一條邊PnP1，其處理方法是：標(biāo)志第一頂點(diǎn)為F，這樣最后一條邊則為PnF，可與其他邊作相同的處理。實(shí)現(xiàn)方法：設(shè)置二個(gè)表：輸入頂點(diǎn)表：用于存放被裁剪多邊形的頂點(diǎn)p1-pm。輸出頂點(diǎn)表：用于存放裁剪過(guò)程中及結(jié)果的頂點(diǎn)q1-qn。輸入頂點(diǎn)表中各頂點(diǎn)要求按一定順序排列，一般可采用順時(shí)針或逆時(shí)針?lè)较颉Ｏ鄬?duì)于裁剪窗口的各條邊界，按頂點(diǎn)表中的順序，逐邊進(jìn)行裁剪算法分析：對(duì)凸多邊形應(yīng)用本算法可以得到正確的結(jié)果，但是對(duì)凹多邊形的裁剪將顯示出一條多余的直線。這種情況在裁剪后的多邊形有兩個(gè)或者多個(gè)分離部分的時(shí)候出現(xiàn)。因?yàn)橹挥幸粋€(gè)輸出頂點(diǎn)表，所以表中最后一個(gè)頂點(diǎn)總是連著第一個(gè)頂

9、點(diǎn)。解決這個(gè)問(wèn)題有多種方法，一是把凹多邊形分割成若干個(gè)凸多邊形，然后分別處理各個(gè)凸多邊形。二是修改本算法，沿著任何一個(gè)裁剪窗口邊檢查頂點(diǎn)表，正確的連接頂點(diǎn)對(duì)。實(shí)驗(yàn)環(huán)境硬件平臺(tái)：PC機(jī)軟 件：Windows7平臺(tái)，eclipse集成開(kāi)發(fā)環(huán)境，java編程語(yǔ)言。實(shí)驗(yàn)步驟1. 掌握算法原理；2. 依據(jù)算法，編寫(xiě)源程序并進(jìn)行調(diào)試；3. 對(duì)運(yùn)行結(jié)果進(jìn)行保存與分析；4. 把源程序以文件的形式提交；5. 按格式書(shū)寫(xiě)實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)內(nèi)容一、直線段裁剪算法的核心代碼為：計(jì)算（x,y）點(diǎn)的編碼的方法：private int encode(double x, double y) / 求（x,y）點(diǎn)的編碼int cod

10、e = 0;if (x < XL) / 點(diǎn)位于矩形的左邊code |= LEFT; / 并上左邊的編碼0001 else if (x > XR) / 點(diǎn)位于矩形的右邊code |= RIGHT; / 并上右邊的編碼0010 else if (y < YB) / 點(diǎn)位于矩形的下邊code |= BOTTOM; / 并上下邊的編碼0100 else if (y > YT) / 點(diǎn)位于矩形的上邊code |= TOP; / 并上上邊的編碼1000return code;直線段裁剪的方法：private void lineCut(double x1, double y1, do

11、uble x2, double y2) / 直線的起點(diǎn)(x1,y1)和終點(diǎn)(x2,y2)double x = 0, y = 0;int code1, code2, code;code1 = this.encode(x1, y1);/ 起點(diǎn)的編碼code2 = this.encode(x2, y2);/ 終點(diǎn)的編碼while (code1 != 0 | code2 != 0) if (code1 & code2) != 0) / 兩端點(diǎn)的編碼相與不為0，表示直線在窗口外return;if (code1 != 0) code = code1; else code = code2;if (L

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

13、= x1 + (x2 - x1) * (YB - y1) / (y2 - y1);/ 求直線與矩形窗口的下邊界的交點(diǎn) else if (TOP & code) != 0) / 直線的端點(diǎn)與矩形窗口的上邊編碼相與！=0y = YT;x = x1 + (x2 - x1) * (YT - y1) / (y2 - y1);/ 直線的端點(diǎn)與矩形窗口的上/ 邊編碼相與！=0if (code = code1) x1 = x;y1 = y;code1 = encode(x, y); else x2 = x;y2 = y;code2 = encode(x, y);g.drawLine(int) (x1

14、+ 0.5), (int) (y1 + 0.5), (int) (x2 + 0.5),(int) (y2 + 0.5);二、多邊形裁剪的核心代碼為：通過(guò)點(diǎn)集畫(huà)直線或者多邊形：private void draw() /通過(guò)點(diǎn)集畫(huà)直線或者多邊形for (int i = 1; i < points.size(); i+) Point p1 = new Point();p1 = points.get(i);int x1 = (int) p1.getX();int y1 = (int) p1.getY();Point p2 = new Point();p2 = points.get(i - 1);

15、int x2 = (int) p2.getX();int y2 = (int) p2.getY();g.drawLine(x1, y1, x2, y2);多邊形的裁剪函數(shù)：private Point cutPicture(Point point, Point edge) / 剪裁函數(shù)，參數(shù)為（點(diǎn)集，邊）Point intersectPoint = new Point20;/存放交點(diǎn)的集合for (int j = 0; j < 20; j+) intersectPointj = new Point();Point s = new Point();Point p = new Point();

16、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在窗口內(nèi)，情況1if (inside(s, edge) intersectPointi = p;i += 1; else / s在窗口外，情況4t = intersect(s, p, edge);intersectPointi = t;i += 1;intersectPointi = p;i += 1;

17、 else if (inside(s, edge) / s在窗口內(nèi)，p在窗口外，情況3t = intersect(s, p, edge);intersectPointi = t;i += 1;/ 情況2沒(méi)有輸出s = p;List<Point> tempList = new ArrayList<Point>();for (int k = 0; k < i; k+) if (intersectPointk != null) Point pt = intersectPointk;tempList.add(pt);Point temp = new PointtempLi

18、st.size();for (int j = 0; j < tempList.size(); j+) tempj = new Point();tempj = tempList.get(j);intersectPoint = temp;return intersectPoint;判斷點(diǎn)是否在裁剪邊的可見(jiàn)側(cè)：private boolean inside(Point point, Point edge) /判斷點(diǎn)是否在裁剪邊的可見(jiàn)側(cè)/ 裁剪邊為窗口下邊if (edge0.y = edge1.y) && (edge0.x < edge1.x) if (point.y >

19、;= 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 <= edge0.x) return true;/ 裁剪邊為窗口左邊if (edge0.x = edge1.x) && (edge0.y > edge1.

20、y) if (point.x >= edge0.x) return true;return false;直線段與窗口邊界求交：private Point intersect(Point s, Point p, Point edge) /直線段與窗口邊界求交，并返回交點(diǎn)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 =

21、 edge0.x;t.y = s.y + (edge0.x - s.x) * (p.y - s.y) / (p.x - s.x);return t;鼠標(biāo)的監(jiān)聽(tīng)類（內(nèi)部類）：class MouseMonitor extends MouseAdapter /通過(guò)鼠標(biāo)的單擊獲取點(diǎn)，并畫(huà)出直線或者多邊形public void mouseClicked(MouseEvent e) points.add(e.getPoint();if (points.size() > 1) draw();鍵盤(pán)的監(jiān)聽(tīng)類（內(nèi)部類）：class KeyMonitor extends KeyAdapter / 鍵盤(pán)控制pu

22、blic void keyPressed(KeyEvent e) switch (e.getKeyCode() case KeyEvent.VK_R:/ 清空畫(huà)布和點(diǎn)集panel.repaint();points.removeAll(points);break;case KeyEvent.VK_W:/對(duì)裁剪窗口的處理g.setColor(Color.RED);g.drawRect(XL, YB, XR - XL, YT - YB);/存放裁剪窗口的邊top = new Point2;/ 存放裁剪窗口的上邊top0 = new Point(XL, YB);top1 = new Point(XR,

23、 YB);right = new Point2;/存放裁剪窗口的右邊right0 = new Point(XR, YB);right1 = new Point(XR, YT);bottom = new Point2;/存放裁剪窗口的下邊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:/對(duì)直線段進(jìn)行裁剪g.setColor(C

24、olor.GREEN);Point p1 = points.get(0);Point p2 = points.get(1);lineCut(p1.getX(), p1.getY(), p2.getX(), p2.getY();break;case KeyEvent.VK_B:/對(duì)多邊形進(jìn)行裁剪source = new Pointpoints.size();/得到多邊形的點(diǎn)for (int i = 0; i < points.size(); i+) sourcei = points.get(i);g.setColor(Color.GREEN);wT = cutPicture(source, top);/得到多邊形與裁剪窗口上邊的交點(diǎn)wR = cutPicture(wT, right);/得到多邊形與裁剪窗口右邊的交點(diǎn)wB = cutPicture(wR, bottom);/得到多邊形與裁剪窗口下邊的交點(diǎn)wL = cutPicture(wB, left);/得到多邊形與裁剪窗口左邊的交點(diǎn)int length = wL.