02824523wanglili.cpp

来自「数据结构实验课中的所有实验程序」· C++ 代码 · 共 353 行

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

#include "stdafx.h"
#include <iostream.h>
#include <windows.h>
#include <gl/gl.h>
#include <gl/glaux.h>
#include <gl/glu.h>

#define SCREEN_WIDTH   500


inline void DrawPoint(int x, int y)         //画点函数
{
	::glBegin(GL_POINTS);
		::glVertex2d(x, y);
	::glEnd();
}

void CALLBACK Reshape(GLsizei w, GLsizei h)
{
	::glViewport(0, 0, w, h);
	::glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
    if (w <= h) 
		gluOrtho2D (0.0, SCREEN_WIDTH, 0.0, SCREEN_WIDTH*(GLfloat)h/(GLfloat)w);
    else 
		gluOrtho2D (0.0, (GLfloat)SCREEN_WIDTH*(GLfloat)w/(GLfloat)h, 0.0, SCREEN_WIDTH);
    
	glMatrixMode(GL_MODELVIEW);
	return;
}


void Init()
{
	::auxInitDisplayMode(AUX_RGBA|AUX_SINGLE);     //RGB单缓存模式
	::auxInitPosition(0, 0, 500, 500);//窗口的左上角位置(x,y)及窗口大小
	::auxInitWindow("Scan algithmic");

	::glShadeModel(GL_FLAT);
	::glClearColor(0.0, 0.0, 0.0, 0.0);
}

//-----------------------------------
//Here, please define your own data structure for edge Table, Active Edge Table, Edge

//struct Original_Edge:Define to receive Original Edge information
struct Original_Edge                  //初始边信息
{
	int x1,y1;
	int x2,y2;
};


//*************接收初始边信息并存入初始边数组******************
void BuildArea(const int n,Original_Edge o_edge[])
{
	
	for(int i=0;i<n;i++)
	{
		cout<<"please input vertex"<<i<<"'s coordinate"<<endl<<"x: ";
		if(i==0)                            
		{
			cin>>o_edge[i].x1;
			o_edge[n-1].x2=o_edge[i].x1;
			cout<<"y: ";
			cin>>o_edge[i].y1;
			o_edge[n-1].y2=o_edge[i].y1;
		}
		else
		{
			cin>>o_edge[i-1].x2;
			o_edge[i].x1=o_edge[i-1].x2;
			cout<<"y: ";
			cin>>o_edge[i-1].y2;
			o_edge[i].y1=o_edge[i-1].y2;
		}
	}
}

//struct Edge:Define to store edge information prepared for scan_conversion
struct Edge
{
	float x_current;
	int y_max;
	float x_incrs;//Inverse of the edge slope
	Edge *next;
};

//////////////////////////////////////////
Edge *edge[SCREEN_WIDTH];//store information of edges sorted by their top y_value
int n;//number of totle edges of polygon
Original_Edge o_edge[15];//store polygon edges,but it's edges should less then 15.
/////////////////////////////////////////

//function Insert_Edge: Define to Insert primary-worked Edges(from Original_edge o_edge[] to
// Edge_table *edge[] via Edge p[])
void Insert_Edge(int q,int index[],Edge p[],Edge *edge[])  //q处理后的(非水平边)数目,index边序号，边数组，边表
{
	while(q>0)
	{
		int id=index[q-1];
		Edge *p1;
		Edge *p2;
		p1=p2=edge[id];
		if(p1==NULL) edge[id]=&p[q-1];
		else
		{
			while(p1!=NULL)
			{
				p2=p1;
				p1=p1->next;
			}
		p2->next=&p[q-1];
		}
		q--;
	}//end of while
}



//Function Build_Edge:Define to build edge table
//Including dealing with the odd points(if is not extremum point Its y_max-1)
void Build_Edge(const int n,Original_Edge o_edge[],Edge *edge[])
{
	Edge *p=new Edge[n];
	int q=0;
	int *id=new int[n];//id:use to decide the location of the edge in Edge_table
	for(int k=0;k<n;k++)
	{
		if(o_edge[k].y1==o_edge[k].y2) continue;//Horizon edges should not insert into edge_table
		else 
		{ 
		//x_incrs:refer to the x_value on current edge increase when y_value add 1(scan upper line)
			p[q].x_incrs=((float)o_edge[k].x2-o_edge[k].x1)/(o_edge[k].y2-o_edge[k].y1);
			p[q].next=NULL;//initialization pointer next
		}
		if(k==0)
		{
			if((o_edge[k].y1-o_edge[k].y2)*(o_edge[k].y1-o_edge[n-1].y2)<0)//非奇点
			{
				p[q].y_max=(o_edge[k].y1>o_edge[k].y2?o_edge[k].y1:o_edge[k].y2)-1;
				p[q].x_current=float(o_edge[k].y1<o_edge[k].y2?o_edge[k].x1:o_edge[k].x2);
				id[q]=o_edge[k].y1<o_edge[k].y2?o_edge[k].y1:o_edge[k].y2;
			}
			else
			{
				p[q].y_max=(o_edge[k].y1>o_edge[k].y2?o_edge[k].y1:o_edge[k].y2);
				p[q].x_current=float(o_edge[k].y1<o_edge[k].y2?o_edge[k].x1:o_edge[k].x2);
				id[q]=o_edge[k].y1<o_edge[k].y2?o_edge[k].y1:o_edge[k].y2;
			}
		}
		else
		{
			if((o_edge[k].y1-o_edge[k-1].y1)*(o_edge[k].y1-o_edge[k].y2)<0)//非奇点
			{
				if(o_edge[k].y1>o_edge[k].y2)//current edge ymax-1
				{
					p[q].y_max=(o_edge[k].y1>o_edge[k].y2?o_edge[k].y1:o_edge[k].y2)-1;//将高点的Y值减1
					p[q].x_current=float(o_edge[k].y1<o_edge[k].y2?o_edge[k].x1:o_edge[k].x2);//记录低点的x值
					id[q]=o_edge[k].y1<o_edge[k].y2?o_edge[k].y1:o_edge[k].y2;//将该边信息记录到该边最低点经过扫描线的Y桶 
				}
				else//last edge ymax-1
				{
					p[q-1].y_max=p[q-1].y_max-1;
					p[q].y_max=(o_edge[k].y1>o_edge[k].y2?o_edge[k].y1:o_edge[k].y2);
					p[q].x_current=float(o_edge[k].y1<o_edge[k].y2?o_edge[k].x1:o_edge[k].x2);
					id[q]=o_edge[k].y1<o_edge[k].y2?o_edge[k].y1:o_edge[k].y2;
				}
			}
			else//对奇点的处理，坐标值不做改变
			{
				p[q].y_max=(o_edge[k].y1>o_edge[k].y2?o_edge[k].y1:o_edge[k].y2);
				p[q].x_current=float(o_edge[k].y1<o_edge[k].y2?o_edge[k].x1:o_edge[k].x2);
				id[q]=o_edge[k].y1<o_edge[k].y2?o_edge[k].y1:o_edge[k].y2;
			}
		}
	q++;
	}
	Insert_Edge(q,id,p,edge);
}
void Scan_Fill(Edge *edge[])
{
	Edge *ael=NULL;//初始化活化边表指针;
	for(int scan=0;scan<SCREEN_WIDTH;scan++)//scan from bottom to top
	{
		Edge *po,*pl;//point to Old Active edge list for sorting,*po2
		Edge *pn1,*pn2;//point to New Active edge list for sorting
		Edge *pe=edge[scan];//point to edge to get information

		if(pe!=NULL)
		{
			pl=po=ael;
			while(po!=NULL)
			{
				pl=po;
				po=po->next;
			};
			if(pl==NULL)     //如果原来活化边表为空，就将边表中值直接赋给当前活化边
				ael=pe;
			else
				pl->next=pe;//将新边加到活化边表尾
		}

		//以下为更新活化边表，对表中边进行排序
		Edge *newlist=new Edge;
		newlist=NULL;
		po=ael;
		while(po!=NULL)
		{
			Edge *listNode=new Edge;
			listNode->next=NULL;
			listNode->x_current=po->x_current;
			listNode->x_incrs=po->x_incrs;
			listNode->y_max=po->y_max;
			if(newlist==NULL)
				newlist=listNode;
			else                      //begin
			{
				pn1=pn2=newlist;
				while(pn1!=NULL)
				{
					if(pn1->x_current<listNode->x_current)
					{
						pn2=pn1;
						pn1=pn1->next;
					}
					else break;
				}
				if(pn1==NULL)//插入到表尾
				{
					pn2->next=listNode;
				}
				else if(pn1!=newlist)//不是活化边表头的情况
				{
						listNode->next=pn1;
						pn2->next=listNode;
				}
				else                 //插入到表头部
				{
						listNode->next=pn1;
						newlist=listNode;
				}
			}                  //end 
			po=po->next;
		};                    //结束更新活化边表
		ael=newlist;

		// 开始扫描填充
		pn1=pn2=ael;
		if(pn1!=NULL)
		while(pn2->next!=NULL)
		{
			pn2=pn2->next;
			int x1,x2;
			x1=int(pn1->x_current+0.5);
			x2=int(pn2->x_current+0.5);
			for(int pix=x1;pix<x2;pix++)
			{
				DrawPoint(pix,scan);
			}
			pn1->x_current=pn1->x_current+pn1->x_incrs;
			pn2->x_current=pn2->x_current+pn2->x_incrs;
			if(pn2->next!=NULL)
			{
				pn1=pn2->next;   //指向紧跟的两条边
				pn2=pn1;
			}
		};

		//如果该边最高端点小于当前扫描线 将之删除
		pn1=pn2=ael;
		while(pn1!=NULL)
		{
			Edge *temp;
			if(pn1->y_max==scan)
			{
				if(pn1==ael) {temp=ael; ael=pn1->next; }       //删除活化边表头
				else {temp=pn1;pn2->next=pn1->next;}           //删除中间的边
				pn1=pn1->next;
				delete temp;
			}
			else
			{
				pn2=pn1;
				pn1=pn1->next;
			}
		};//删除操作结束
	}//end of active__for
}


//-----------------------------------


void CALLBACK Display()
{
	::glColor3f(1.0, 0.0, 0.0);
//-----------------------------------
// use the function "DrawPoint"defined above to display
// your scan conversion result here
////draw polygon
	glColor3f(1.0f,0.0f,0.0f);
	Scan_Fill(edge);
	
/*	glLineWidth(3.0f);
	glColor3f(0.0f,1.0f,0.0f);
	glBegin(GL_LINE_LOOP);
	for(int i=0;i<n;i++)
	{
		glVertex2i(o_edge[i].x1,o_edge[i].y1);
	}
	glEnd();*/
//-----------------------------------
	::glFlush();
	return;
}


void main(int argc, char **argv)
{
	//-------------------------------------------
	// implement your scan conversion algorithm here!
	cout<<"======welcome to test lily's programe========="<<endl;
	cout<<"please input the amount of your edges:";
	cin>>n;
	while(n<3) { cerr<<endl<<"the edges are not enough to build a polygon,please reput:"; cin>>n;}
	BuildArea(n,o_edge);
	/*for(int j=0;j<n;j++)
		cout<<"p: "<<o_edge[j].x1<<o_edge[j].y1<<o_edge[j].x2<<o_edge[j].y2<<endl;*/
	for(int i=0;i<SCREEN_WIDTH;i++)
		edge[i]=NULL;
	Build_Edge(n,o_edge,edge);
	/*for(int k=0;k<SCREEN_WIDTH;k++)
	{
		Edge *p=edge[k];
		while(p!=NULL)
		{
			cout<<"e:"<<p->x_current<<' '<<p->y_max<<' '<<p->x_incrs<<endl;
			p=p->next;
		}
	}
	*/
	Scan_Fill(edge);
//-------------------------------------------
	Init();
	::auxReshapeFunc(Reshape);
	::auxMainLoop(Display);
	return;
}