【正文】 C D G J A， B算交點 C不算 ， D算 I不算 ， H算 G， F不算 Y 25 掃描線算法 ? 算法實現(xiàn) － 數(shù)據(jù)結(jié)構(gòu) （ 1）邊的分類表 ET （ Edge Table）（又稱新邊表） ?按照邊的下端點 y 坐標，對非水平邊進行分類的鏈表 ?下端點 y 坐標值等于 i 的邊屬于第 i類 ?作用：避免盲目求交 26 掃描線算法 ET定義 ?每條掃描線，對應(yīng)一個鏈表 ?鏈表中每個結(jié)點的結(jié)構(gòu) typedef struct {int ymax。 //多邊形頂點數(shù)組 Point vertexces[MAX] } Polygon。x = xmax。 }/*end of FillRectangle() */ (xmin, ymin) (xmax, ymax) 6 掃描轉(zhuǎn)換矩形 ? 問題 ? 矩形是簡單的多邊形，那么為什么要單獨處理矩形？ ?比一般多邊形可簡化計算 ?應(yīng)用非常多，如窗口系統(tǒng) ? 共享邊界如何處理？ ?原則：左閉右開，下閉上開 屬于誰？ 7 掃描 轉(zhuǎn)換 多邊形 ? 多邊形的表示方法 ? 頂點表示 頂點序列 P0P1P2… Pn ? 點陣表示 ? 掃描轉(zhuǎn)換多邊形：將頂點表示形式轉(zhuǎn)換成點陣表示形式 ? 三種方法： 逐點判斷法；掃描線算法；邊緣填充法 ? 多邊形分類（只考慮：簡單多邊形，即多邊形邊不自相交） ? 凸多邊形 (convex)：內(nèi)角小于 180度 ? 凹多邊形 (concave)：存在內(nèi)角大于 180度 8 掃描 轉(zhuǎn)換 多邊形 如何識別多邊形的凸凹性 方法 1：觀察多邊形邊的延長線是否劃分頂點在兩側(cè) 方法 2：向量的叉積 每條邊建立一個向量，測試相鄰邊的叉積 z坐標的正負 （ 1）如果叉積同號，那么是凸多邊形 （ 2）如果叉積不同號，那么是凹多邊形 (E1 E2 )z 0 (E2 E3 )z 0 (E3 E4 )z 0 (E4 E5 )z 0 (E5 E6 )z 0 (E6 E1 )z 0 9 掃描 轉(zhuǎn)換 多邊形 向量叉積（ Cross Product of Two Vector） kjikjiba)()()(xyyxzxxzyzzyzyxzyxbababababababbbaaa????????當 a與 b為二維向量時， a b 矢量中 x， y 分量為 0 10 逐點判斷法 ? 基本原理 ? 判斷繪圖窗口內(nèi)的像素是否位于多邊形內(nèi)，若是，則用指定顏色繪制該像素 ? 問題 ? 如何判斷點在多邊形的內(nèi)外關(guān)系？ ?射線法 ?累計角度法 * ?編碼法 * P1 P2 (xmin, ymin) (xmax, ymax) 11 逐點判斷法 ? 算法 ? 假設(shè)判斷點是否在多邊形內(nèi)的函數(shù)為 IsInside（） void FillPolygon(Polygon *P, int polygonColor) { int x,y。 y = rectymax。 for(y = rectymin。 x++) SetPixel(x, y, color)。y++) for(x = xmin。 }/*end of FillPolygonPbyP() */ define MAX 100 typedef struct { // 多邊形頂點個數(shù) int PolygonNum。 檢查兩相鄰邊在掃描線的哪一側(cè)。 }Edge。 }Edge。 Edge *nextEdge。 i=m。 FloodFill4(x,y+1,oldColor,newColor)。 } }/*end of FloodFill4() */ 51 種子填充法 ① FloodFill4(x, y+1, oldColor, newColor)。 52 （ 2）邊界表示的 4連通區(qū)域 種子填充法 void BoundaryFill4(int x, int y, int oldColor, int newColor) {//oldColor邊界像素顏色 int color。 (color != newColor)) { SetPixel(x, y, newColor)。 BoundaryFill4(x+1,y,oldColor,newColor)。 ? (4)像素圖填充：以像素對應(yīng)的像素圖單元的顏色值顯示該像素。 glBegin(GL_TRIANGLES)。 glVertex2iv(p4)。 GL_TRIANGLE_STRIP GL_TRIANGLES GL_TRIANGLE_FAN p1 p1 p1 64 ? 菜單函數(shù) ? int glutCreateMenu(void (*func)(int value))。 ? 例： OpenGL相關(guān)函數(shù) void MenuInit() { int sub_menu1 = glutCreateMenu(objectMenu)。 glutAddSubMenu(圖形 ,sub_menu1)。 else if (id==12) GraphicsType = 12?？蛇x值： GL_FRONT、 GL_BACK和GL_FRONT_AND_BACK ? displayMode： GL_FILL和 GL_LINE OpenGL相關(guān)函數(shù) void display (void) { glClearColor (, , , )。 glColor3f(,0,0)。 glVertex2f(,)。 glClear (GL_COLOR_BUFFER_BIT)。 glVertex2f(,)。 glVertex2f(,)。 glFlush()。 glEnableClientState(GL_VERTEX_ARRAY)。 glFlush ( )。 bitShape中的元素值為 0或 1，當為 1時，用設(shè)定的顏色繪制對應(yīng)的像素，否則對應(yīng)像素不受影響 ? 位圖的存儲模式：字節(jié) ? glPixelStorei ( GL_UNPACK_ALIGNMENT, 1 ) 。 glBitmap (8, 12, , , , , rasters)。 glColor3f (, , )。 } rasters 73 OpenGL相關(guān)函數(shù) ? 繪制字符 ? OpenGL基本庫：位圖方法，需要自己創(chuàng)建字庫 ? GLUT工具包：位圖和輪廓字體 ? 位圖字符函數(shù)： glutBitmapCharacter(font, character) ? font:指定字型，常量（如 GLUT_BITMAP_8_BY_13） ? Character：字符的 ASCII碼值 ? 輪廓字符函數(shù)： glutStrokeCharacter(font, character) ? font:指定字型，常量（如 GLUT_STROKE_ROMAN） ? Character：字符的 ASCII碼值 ? 位圖和輪廓字符比較 ? 前者速度快，后者放大縮小不變形 74 OpenGL相關(guān)函數(shù) 程序 void display() { glColor3f (, , )。 glutBitmapCharacter (GLUT_BITMAP_TIMES_ROMAN_10,66)。glScalef(,1)。 glScalef(,1)。 （ a）寫出邊的分類表 （ b）說明掃描線 y＝ 6， 7， 8， 9和 10時，哪些邊是活