www.pudn.com > glGraph.rar > glPolygon.cpp
// glPolygon.cpp: implementation of the glPolygon class.
//
//////////////////////////////////////////////////////////////////////
#include "glPolygon.h"
#include "gl/glut.h"
#include "math.h"
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
glPolygon::glPolygon()
{
type = POLYGON;
tail = head = 0;
num = 0;
ET = 0;
ymin = 60000;
ymax = -60000;
AEL = 0;
}
glPolygon::~glPolygon()
{
}
void glPolygon::AddPoint(float x, float y,double width,double height)
{
point* p = new point;//创建一新节点
p->nod[0] = (x-width/2);
p->nod[1] = ((int)(height/2)-y);
p->m_next = 0;
num++;
if(head == 0)//如果为第一节点
{
tail = head = p;//加入链手
if(p->nod[1] < ymin)
ymin = p->nod[1];//保留新的y的最小值
if(p->nod[1] > ymax)
ymax = p->nod[1];//保留新的y的最大值
return;
}
else
{//其它节点
tail->m_next = p;//加入链尾
}
if(IsAble() == 0)//判断是否为自交多边形
{
tail->m_next = 0;
delete p;//如果不是删除刚节点
num--;
}
else
tail = tail->m_next;//如果是确定链尾
if(p->nod[1] < ymin)
{
// DeleteET();
ymin = p->nod[1];//保留新的y的最小值
// CreatET();//重建边分类表
}
if(p->nod[1] > ymax)
{
// DeleteET();
ymax = p->nod[1];//保留新的y的最大值
// CreatET();//重建边分类表
}
}
void glPolygon::Draw()
{
point* p = head;
glColor3fv(color);
glLineWidth(scale);
glBegin(GL_LINE_LOOP);
while(p)//画多边形的各边
{
glVertex2fv(p->nod);
p = p->m_next;
}
glEnd();
Fill();
}
int glPolygon::IsAble()
{//判断是否为自交多边形
return 1;
int flag = 0;//标志向量的乘积是否大于0
point* p1;
point* p2;
point* p3;
float x1[2];//记录一向量
float x2[2];//记录一向量
if(num < 3)
return 1;
p1 = head->m_next->m_next;
p2 = head->m_next;
p3 = head;
while(p1)
{
//确定两向量
x1[0] = p2->nod[0] - p3->nod[0];
x1[1] = p2->nod[1] - p3->nod[1];
x2[0] = p1->nod[0] - p2->nod[0];
x2[1] = p1->nod[1] - p2->nod[1];
if(flag == 0)
{//如果是第一个向量则修改flag
if(x1[0]*x2[1]-x1[1]*x2[0] > 0)
{
flag = 1;//大于0，置1
}
else
{
flag = -1;//小于0，置-1
}
}
if(x1[0]*x2[1]-x1[1]*x2[0] > 0)
{
if(flag == -1)//在当前大于0的乘积下，如果之前小于0
return 0;//返回0
}
if(x1[0]*x2[1]-x1[1]*x2[0] < 0)
{
if(flag == 1)//在当前小于0的乘积下，如果之前大于0
return 0;//返回0
}
p1 = p1->m_next;
p2 = p2->m_next;
p3 = p3->m_next;
}
p1 = head;//判断从最后点到开始点的向量
//确定两向量
x1[0] = p2->nod[0] - p3->nod[0];
x1[1] = p2->nod[1] - p3->nod[1];
x2[0] = p1->nod[0] - p2->nod[0];
x2[1] = p1->nod[1] - p2->nod[1];
if(x1[0]*x2[1]-x1[1]*x2[0] > 0)
{
if(flag == -1)//在当前大于0的乘积下，如果之前小于0
return 0;//返回0
}
if(x1[0]*x2[1]-x1[1]*x2[0] < 0)
{
if(flag == 1)//在当前小于0的乘积下，如果之前大于0
return 0;//返回0
}
p1 = p1->m_next;
p2 = head;
p3 = p3->m_next;
//确定两向量
x1[0] = p2->nod[0] - p3->nod[0];
x1[1] = p2->nod[1] - p3->nod[1];
x2[0] = p1->nod[0] - p2->nod[0];
x2[1] = p1->nod[1] - p2->nod[1];
if(x1[0]*x2[1]-x1[1]*x2[0] > 0)
{
if(flag == -1)//在当前大于0的乘积下，如果之前小于0
return 0;//返回0
}
if(x1[0]*x2[1]-x1[1]*x2[0] < 0)
{
if(flag == 1)//在当前小于0的乘积下，如果之前大于0
return 0;//返回0
}
return 1;
}
void glPolygon::CreatET()
{
int a = ymax-ymin+1;
ET = new struct EDGE[a];
for(int i = 0;inextEdge = 0;//将分类表各项置空
point* p1;//指向当前分析边的首点
point* p2;//指向当前分析边的末点
float x1,x2,y1,y2;//用于保存当前分析边两个点的横竖坐标
p1 = head;//获得第一条边的一点
p2 = head->m_next;//获得第一条边的另一点
while(p2)
{
//保存当前分析边两个点的横竖坐标
y1 = p1->nod[1];
x1 = p1->nod[0];
y2 = p2->nod[1];
x2 = p2->nod[0];
if(y1 < y2)
{
EDGE* e = new EDGE;
e->ymax = y2;
e->x = x1;
e->deltax = (x1-x2)/(y1-y2);
e->nextEdge = 0;
a = y1 - ymin;
InsertEdgeToET(a,e);
}
if(y1 > y2)
{
EDGE* e = new EDGE;
e->ymax = y1;
e->x = x2;
e->deltax = (x1-x2)/(y1-y2);
e->nextEdge = 0;
a = y2 - ymin;
InsertEdgeToET(a,e);
}
p1 = p1->m_next;//获得下一条边的一点
p2 = p2->m_next;//获得下一条边的另一点
}
if(num == 2)//只有一条边直接返回
return;
//处理末点到首点的边
p2 = head;
y1 = p1->nod[1];
y2 = p2->nod[1];
x1 = p1->nod[0];
x2 = p2->nod[0];
if(y1 < y2)
{
EDGE* e = new EDGE;
e->ymax = y2;
e->x = x1;
e->deltax = (x1-x2)/(y1-y2);
e->nextEdge = 0;
a = y1 - ymin;
InsertEdgeToET(a,e);
}
if(y1 > y2)
{
EDGE* e = new EDGE;
e->ymax = y1;
e->x = x2;
e->deltax = (x1-x2)/(y1-y2);
e->nextEdge = 0;
a = y2 - ymin;
InsertEdgeToET(a,e);
}
}
point* glPolygon::GetPrePointForY(float y)
{//通过给定y值，返回找到节点的上一point
point* p1;
point* p2;
p2 = head;
p1 = head->m_next;
if(head->nod[1] == y)//第一节点的y为所求，则返回末节点
return tail;
while(p1)
{
if(p1->nod[1] == y)
return p2;
p2 = p2->m_next;
p1 = p1->m_next;
}
return 0;
}
point* glPolygon::GetNextPointForY(float y)
{//通过给定y值，返回找到节点的下一point
point* p1;
point* p2;
p2 = head->m_next;
p1 = head;
while(p2)
{
if(p1->nod[1] == y)
return p2;
p2 = p2->m_next;
p1 = p1->m_next;
}
if(p1->nod[1] == y)//末点的y为所求，则返回头节点
return head;
return 0;
}
point* glPolygon::GetPointForY(float y)
{
return 0;
}
void glPolygon::InsertEdgeToET(int kind, EDGE *e)
{
EDGE* et1;//一临时辅助指针
EDGE* et2;//一临时辅助指针
if((ET + kind)->nextEdge == 0)//如果当前类的边没有，则直接插入分类表
{
(ET + kind)->nextEdge = e;
return;
}
else
{//如果已经有当前类的边，进行以下处理
et1 = (ET+kind)->nextEdge;//获得此类的第一条边
et2 = (ET+kind);//获得此类链首
while(et1)
{
if(et1->x > e->x)
{//如果新边的x小于当前边ex1的x，则插入当前位
et2->nextEdge = e;
e->nextEdge = et1;
return;
}
if(et1->x == e->x)
{
if(et1->deltax > e->deltax)
{//如果新边的x==当前边ex1的x 且新边的deltax于当前边ex1的deltax，则插入
et2->nextEdge = e;
e->nextEdge = et1;
return;
}
else//否则
{//插入到下一位置
et1 = et1->nextEdge;
et2 = et2->nextEdge;
et2->nextEdge = e;
e->nextEdge = et1;
return;
}
}
et1 = et1->nextEdge;
et2 = et2->nextEdge;
}
if(et1 == 0)
et2->nextEdge = e;
}
}
void glPolygon::DeleteET()
{//释放当前分类表空间
if(ET == 0)
return;
/* EDGE* t1;
EDGE* t2;
for(int j = 0;jnextEdge;
while(t2)
{
t1 = t2;
t2 = t2->nextEdge;
delete t1;
}
}*/
delete [] ET;//释放表
}
void glPolygon::Fill()
{//扫描线填充多边性
AEL = 0;
DeleteET();
CreatET();//重建边分类表
float x1;//填充时存放x的临时值
float x2;//填充时存放x的临时值
EDGE* e;
EDGE* e1;
glBegin(GL_LINES);
if((ET+0)->nextEdge != 0)
{//初始AEL表
InsetEdgeToAEL(0);
}
for(int y = 0;y<=ymax-ymin;y++)
{//扫描填充
e1 = e = AEL;
while(e)
{
glVertex2f(e->x,ymin+y);
e->x += e->deltax;//x = x+deltax
if(e->ymax == ymin+y)
{//如果y值大于ymax值，则将当前边从AEL中移出
if(e == AEL)
{
AEL = AEL->nextEdge;
delete e;
e1 = e = AEL;
continue;
}
e1->nextEdge = e->nextEdge;
delete e;
e = e1->nextEdge;
continue;
}
e1 = e;
e = e->nextEdge;
}
if((ET+y)->nextEdge != 0 && y != 0)
{//如果有新点，则将边插入AEL表
InsetEdgeToAEL(y);
}
}
glEnd();
}
void glPolygon::InsetEdgeToAEL(int y)
{//将分类表中的边移到活化边表中
EDGE* e;
EDGE* et;
EDGE* e1;
EDGE* e2;
e = et = (ET+y)->nextEdge;//取出边链
(ET+y)->nextEdge = 0;//当前类置空
if(AEL == 0)
{
AEL = e;
return;
}
while(e)
{
e1 = AEL;
e2 = AEL->nextEdge;
while(e2)
{
if(e1->x > et->x)
{//AEL的第一条边的x大于插入边的x
e = e->nextEdge;//插入的队列指针后移
et->nextEdge = AEL;//将插入边插入到AEL队首
AEL = et;
break;
}
if(e2->x > e->x)
{
e = e->nextEdge;//插入的队列指针后移
e1->nextEdge = et;
et->nextEdge = e2;
break;
}
e1 = e1->nextEdge;
e2 = e2->nextEdge;
}
if(e2 == 0)
{
e1->nextEdge = e;//将插入边插入到AEL队尾
e = e->nextEdge;//插入的队列指针后移
et->nextEdge = 0;
}
et = e;
}
}
void glPolygon::DeleteLastPoint()
{
point* p;
p = head;
if(head == tail)
{
delete head;
head = 0;
return;
}
while(p)
{
if(p->m_next == tail)
break;
p = p->m_next;
}
if(p == 0)
return;
tail = p;
p = p->m_next;
tail->m_next = 0;
delete p;
}