#include<stdio.h>
#include<graphics.h>
#include<conio.h>
#define YMAX 480
 typedef struct tEdge
{
    int yUpper,yLower;
    float xIntersect,dxPerScan;
    struct tEdge *next;
    struct tEdge *active;
}Edge;
void insertEdge (Edge *list,Edge *edge)  //将结点插入边表
{
    Edge *p,*q=list;
    p=q->next;

    while (p!=NULL)
    {
        if(edge->xIntersect<p->xIntersect)
            p=NULL;
        else
        {
            q=p;
            p=p->next;
        }
}
    edge->next=q->next;
    q->next=edge;
}
int yNext (int k,int count,int * y) //求奇异点
{
    int j;
    if((k+1)>(count-1))
        j=0;
    else
        j=k+1;
    while(y[k]==y[j])
        if((j+1)>(count-1))
            j=0;
        else
            j++;
        return(y[j]);
}
void makeEdgeRecord(int xLower,int yLower,int xUpper,int yUpper,int yComp,Edge *edge,Edge *edges[])
//生成边表结点，并插入到边表中
{
    edge->dxPerScan=(float)(xUpper-xLower)/(yUpper-yLower);
    edge->yUpper=yUpper;
    if(yLower>yComp)
    {
        edge->yLower=yLower+1;
        edge->xIntersect=xLower+edge->dxPerScan;
    }
    else
        edge->xIntersect=(float)xLower;
    insertEdge(edges[yLower],edge);
}

void buildEdgeList(int count,int *x,int *y,Edge *edges[])   //创建边表的主体函数
{
    Edge *edge;
    int x1,y1,x2,y2;
    int i,yPrev=y[count-2];
    x1=x[count-1];y1=y[count-1];
    for(i=0;i<count;i++)
    {
        x2=x[i];y2=y[i];
        if(y1!=y2)
        {
            edge=(Edge *)malloc(sizeof(Edge));
            if(y1<y2)
                makeEdgeRecord(x2,y2,x1,y1,yNext(i,count,y),edge,edges);
            else
                makeEdgeRecord(x1,y1,x2,y2,yPrev,edge,edges);
        }
        yPrev=y1;
        x1=x2;
        y1=y2;
    }
}
void buildActiveList(int scan,Edge *active,Edge *edges[]) //建立活动边表的主体函数
{
    Edge *p,*q;
    p=edges[scan]->next;
    while(p)
    {
        q=p->next;
        insertEdge(active,p);
        p=q;
    }
}
void fillScan(int scan,Edge *active) //填充当前扫描线
{
    Edge  *p1,*p2;
    int i,PolygonColor=255;
     p1=active->next;
    while(p1);
    {
        p2=p1->next;
        for(i=(int)p1->xIntersect;i<p2->xIntersect;i++)
            putpixel(i,scan,PolygonColor);
        p1=p2->next;
    }
}
void deleteAfter(Edge *q) //删除已经处理过的边
{
    Edge *p=q->next;
    q->next=p->next;
    free(p);
}
void updateActiveList(int scan,Edge *active) //更新活化链表
{
    Edge *q=active,*p=active->next;
    while (p)
        if(scan>=p->yUpper)
        {
            p=p->next;
            deleteAfter(q);
        }
        else
        {
            p->xIntersect=p->xIntersect+p->dxPerScan;
            q=p;
            p=p->next;
        }
}
void resortActiveList(Edge *active) //活化链表排序
{
    Edge *q, *p=active->next;
    while(p)
    {
        q=p->next;
        insertEdge(active,p);
        p=q;
    }
}
void scanFillPolygon(int count,int *x,int *y) //多边形扫描转换
{   
    Edge *edges[YMAX],*active;
    int i,scan;
    //扫描线的边界
    for(i=0;i<YMAX;i++)
    {
        edges[i]=(Edge *)malloc(sizeof(Edge));//申请空间
        edges[i]->next=NULL;
    }
    buildEdgeList(count,x,y,edges);
    active=(Edge *)malloc(sizeof(Edge));
    active->next=NULL;

    //初始化边表
    for(scan=0;scan<YMAX;scan++)
    {
        buildActiveList(scan,active,edges);
        if (active->next)
        {
            fillScan(scan,active);
            updateActiveList(scan,active);
            resortActiveList(active);
        }
    }
    free(active);
}
void main( )
{
    int x=(48,125,20,350);
    int y=(56,90,138,368);
    int count=sizeof(x)/sizeof(y);
    int gdriver=DETECT,gmode;
   initgraph(&gdriver,&gmode," ");
   void scanFillPolygon(int count,int *x,int *y);
   getch();
   closegraph();
}