02824523.cpp

数据结构实验课中的所有实验程序

// 02824523.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "windows.h"
#include "GL/gl.h"
#include "GL/glu.h"
#include "GL/glaux.h"
//#include "Edge.h"
//#include "Point.h"
#include "iostream.h"
//#define WINDOW_HEIGHT  500
class Point    //顶点类
{
public:
	int x;
	int y;
	Point();
	void setP(int a, int b);     //给x,y坐标赋值
	int getX();
	int getY();
	void setX(int a);
	void setY(int b);
	Point(int a, int b);
	void operator=(Point m);
};
//顶点类的函数实现
Point::Point(int a, int b)
{
	x=a;
	y=b;
}
Point::Point()
{
	x=y=0;
}


void Point::operator=(Point m)
{
	x=m.x;
	y=m.y;
}
void Point::setP(int a, int b)
{
	x=a;
	y=b;
}
int Point::getX()
{
	return x;
}
int Point::getY()
{
	return y;
}
void Point::setX(int a)
{
	x=a;
}
void Point::setY(int b)
{
	y = b;
}
//边表类
#include "stdio.h"
class Edge  
{
public:
	int yUpper;
	float xLow;
	float dx;
	Edge *next;
	Edge();
};
Edge::Edge()
{
	yUpper=0;
	xLow=0.0;
	dx=0.0;
	next=NULL;}
int number;             //顶点个数
Point point[8];         //保存顶点的数组
//Here, please define your own data structure for edge Table, Active Edge Table, Edge
int yNext(int k, int cnt, Point *pts)//寻找下一条非平行线的纵坐标值
{
	int j;
	if((k+1)>(cnt-1))//当前顶点为最后一个顶点，则下一个顶点为第0个顶点
		j=0;
	else 
		j=k+1;//当前顶点不是最后一个顶点，下一个顶点为数组下标加一
	while(pts[k].getY() == pts[j].getY())//扫描线扫过平行顶点，需分情况找到当前顶点下下个顶点
		if((j+1)>(cnt-1))
			j=0;
		else
			j++;	
	return (pts[j].getY());//返回下一个顶点的y值
}
void insertEdge(Edge *list, Edge *edge)// 把边插入边表
{
	Edge *p = NULL;
	Edge *q = list;
	p=q->next;
	while(p!=NULL)//按x值非递减顺序增加边表
	{
		if(edge->xLow < p->xLow) //要插入的边的x较大不应该在当前插入		
			p=NULL;		
		else //要插入的边的x较小应该在当前插入
		{
			q=p;
			p=p->next;
		}
	}
	edge->next = q->next;
	q->next=edge;
}
void makeEdgeRec(Point lower, Point upper, int yComp, Edge *edge, Edge *edges[])  //取最小的y坐标，并且取斜率倒数。
{
	edge->dx=(float)(upper.getX()-lower.getX())/(upper.getY()-lower.getY());
	edge->xLow = lower.getX();
	if(upper.getY()<yComp)//奇点，应该把这点当作两个点而分开，所以把y的最大值减一，向下移动 	
		edge->yUpper = upper.getY()-1;	
	else
		edge->yUpper = upper.getY();//不是奇点，不需改变y值
	insertEdge(edges[lower.getY()],edge);
}
void buildEdgeList(int cnt, Point* pts, Edge* edges[])      //建立边表
{
	Edge *edge;
	Point v1, v2;
	int i, yPrev = pts[cnt-2].getY();//当前顶点的前一个顶点的y值，在当前顶点不是奇点时使用该参数
	v1=pts[cnt-1];
	for(i =0; i<cnt; i++)
	{
		v2 = pts[i];
		if(v1.getY()!=v2.getY())           
		{
			edge = new Edge();
			if(v1.getY()<v2.getY())//当前顶点不是奇点，建立边表时使用下一个顶点的y值即yNext
				makeEdgeRec(v1, v2, yNext(i, cnt, pts), edge, edges);
			else
				makeEdgeRec(v2, v1, yPrev, edge, edges);//当前顶点是奇点
		}
		yPrev = v1.getY();
		v1=v2;
	}
}
void buildActiveList(int scan, Edge* active, Edge* edges[]) //建立活化边表
{
	Edge *p, *q;
	p = edges[scan]->next;//查找当前扫描线对应的y桶
	while(p)//y桶不空
	{
		q = p->next;//找到最后一个边结点，插入
		insertEdge(active, p);
		p=q;
	}
}
void deleteAfter(Edge *q)  //删除不需要的边表
{
	Edge *p=q->next;
	q->next=p->next;
	delete(p);
}
void update(int scan, Edge *active)//更新活化边表
{
	Edge *q = active;
	Edge *p = active->next;
	while(p)
	{
		if(scan>=p->yUpper)//扫描线超过边的最大y值，此条边的节点应该删掉
		{
			p=p->next;
			deleteAfter(q);
		}
		else//扫描线未超过边的最大y值，相应的x值增加
		{
			p->xLow = p->xLow+p->dx;
			q=p;
			p=p->next;
		}
	}
}
void resort(Edge* active)  //保存新的活化边表
{
	Edge *q, *p = active->next;
	active->next=NULL;
	while(p)
	{
		q = p->next;
		insertEdge(active, p);//把更新后的边表重新插入边表中保存
		p=q;
	}
}
void DrawPoint(int i,int j)//画点函数
{
	glColor3f(0.0f, 1.0f, 0.0f);//绿色
	glBegin(GL_POINTS);
	glVertex2i(i,j);
    glFlush();
}
void input()//输入顶点个数和各点坐标
{    
	int x,y;
	cout<<"输入顶点个数(3-8):";
    cin>>number;
    if(3<=number&&number<=8)
	{
		for(int i=0;i<number;i++)
		{
	   	  cout<<"分别输入顶点横纵坐标值";
		  cin>>x;
		  point[i].setX(x);		  
		  cin>>y;
		  point[i].setY(y);
		}
	   	}
	else 
	{
		cout<<"输入错误"<<endl;
		return ;
	}
}
void Init(void)
{
	glShadeModel (GL_FLAT);
    glClearColor (0.0, 0.1f, 0.3f, 0.0);
}
void CALLBACK display(void)
{
	int i, scan;
	glPointSize(2);
   //use the function "DrawPoint"defined above to display
   glClear(GL_COLOR_BUFFER_BIT);
	Edge *edges[200];//边表
	Edge *active;
	Point *points = point;
	for(i=0; i<100; i++)	
		edges[i] = new Edge();//初始化边表为空
	buildEdgeList(number, points, edges); //通过顶点数组建立边表
	active = new Edge();//初始化活化表	
	for(scan=0; scan<200; scan++)
	{
		buildActiveList(scan, active, edges);//建立活化表
		if(active->next)//活化表不为空
		{
			Edge *p1, *p2;
        	    int i;

          	p1=active->next;
          	while(p1)
			{
	         	p2=p1->next;	        
	        	for(i = (int)p1->xLow; i<(int)p2->xLow; i++)			         	
					DrawPoint((int)i, scan);//画出图形内部的点				
	        	p1=p2->next;//活化表的下一条边表
			}
			update(scan, active);//更新活化表
			resort(active);//保存更新后的活化表
		}
	}

// your scan conversion result here
	glFlush();
	auxSwapBuffers();
}
void CALLBACK Reshape(GLsizei w, GLsizei h)
{
	glViewport(0, 0, w, h);
	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	if (w <= h) 
	    gluOrtho2D (0.0, 100.0, 0.0, 100.0*(GLfloat)h/(GLfloat)w);
    else 
	    gluOrtho2D (0.0, 100.0*(GLfloat)w/(GLfloat)h, 0.0, 100.0);
	glMatrixMode(GL_MODELVIEW);
	glLoadIdentity();
}
int main(int argc, char** argv)
{   
   
	// implement your scan conversion algorithm here!
    input();  //输入顶点数组		
    auxInitDisplayMode (AUX_DOUBLE | AUX_RGBA);
    auxInitPosition (0, 0, 500, 500);
    auxInitWindow ("扫描转换");
    Init();
    auxReshapeFunc (Reshape);
    auxMainLoop(display);//
	return 1;
}