扫描线填充.zip

#include<iostream> #include<gl/glut.h> #include<algorithm rel='nofollow' onclick='return false;'> #include<vector> #include<stack> #include<queue> using namespace std; int maxn = 9999; struct point{ float x, y; point(){} point(int xx, int yy) :x(xx), y(yy) {} }; vector<point> vertice; typedef struct XET{ float x; float dx; float ymax; XET* next; }AET, NET;//AET 活性边表； NET新边表 void draw_a_point(int x, int y){ glBegin(GL_POINTS); glColor3f(1, 0, 0); glVertex2f(x, y); glEnd(); glFlush(); } void PolyScan(){ vertice.push_back(point(200, 200)); vertice.push_back(point(300, 200)); vertice.push_back(point(350, 350)); vertice.push_back(point(250, 450)); vertice.push_back(point(150, 400)); vertice.push_back(point(100, 300)); vertice.push_back(point(200, 200)); //得到最高点的y坐标 int Max_Y = 0; for (int i = 0; i < vertice.size(); i++) if (vertice[i].y > Max_Y) Max_Y = vertice[i].y; //初始化AET表 AET* pAET = new AET; pAET->next = NULL; //初始化NET表 NET* pNET[800]; for (int i = 0; i <= Max_Y; i++){ pNET[i] = new NET; pNET[i]->next = NULL;; } //扫描并且建立NET表 int len = vertice.size(); for (int i = 0; i <= Max_Y; i++){ for (int j = 0; j < len; j++){ if (i == vertice[j].y){ //如果一个点和前一个点有一条边相连，则该点和后面一个点也相连 if (vertice[(j - 1 + len) % len].y > vertice[j].y){ NET* p = new NET; p->x = vertice[j].x; p->ymax = vertice[(j - 1 + len) % len].y; float DX = vertice[(j - 1 + len) % len].x - vertice[j].x; float DY = vertice[(j - 1 + len) % len].y - vertice[j].y; p->dx = DX / DY; p->next = pNET[i]->next; pNET[i]->next = p; } if (vertice[(j + 1) % len].y > vertice[j].y){ NET* p = new NET; p->x = vertice[j].x; p->ymax = vertice[(j + 1) % len].y; float DX = vertice[(j + 1) % len].x - vertice[j].x; float DY = vertice[(j + 1) % len].y - vertice[j].y; p->dx = DX / DY;//dx为直线斜率的倒数 p->next = pNET[i]->next; pNET[i]->next = p; } } } } //建立并且更新活性边表AET for (int i = 0; i <= Max_Y; i++){ //计算新的交点 更新AET NET* p = pAET->next; while (p){ p->x = p->x + p->dx; p = p->next; } //排序 AET* tq = pAET; p = pAET->next; tq->next = NULL; while (p != NULL){ while (tq->next != NULL && tq->next->x <= p->x) tq = tq->next; //把这一段小的整体向前移动 NET* t = p->next; p->next = tq->next; tq->next = p; p = t; tq = pAET; } AET* q = pAET; p = q->next; while (p){ if (p->ymax == i){ q->next = p->next; delete p; p = q->next; } else{ q = q->next; p = q->next; } } //将NET中的新点用插入法插入AET，按x递增的顺序排列 p = pNET[i]->next; q = pAET; while (p){ while (q->next != NULL && p->x >= q->next->x) q = q->next; NET* t = p->next; p->next = q->next; q->next = p; p = t; q = pAET; } //配对后填充颜色 p = pAET->next; while (p != NULL && p->next != NULL) { for (float j = p->x; j <= p->next->x; j++){ draw_a_point(j, i); } p = p->next->next;//考虑端点情况 } } glFlush(); } void display(){ glClear(GL_COLOR_BUFFER_BIT); glColor3f(0.0, 0.4, 0.2); glPointSize(1); glBegin(GL_POINTS); PolyScan(); glEnd(); glFlush(); } int main(int argc, char* argv[]){ glutInit(&argc, argv); glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB); glutInitWindowPosition(100, 50); glutInitWindowSize(800, 500); glutCreateWindow("扫描线填充"); glMatrixMode(GL_PROJECTION); glLoadIdentity(); gluOrtho2D(0, 800, 0, 500); glClearColor(1, 1, 1, 1); glClear(GL_COLOR_BUFFER_BIT); glutDisplayFunc(&display); glutMainLoop(); return 0; }