扫描线方法.c

一个图形学和数据结构作业文档和实现代吗

/**********************************************************************************
          Scan-Line Polygon Fill Algorithm.  Referenced Program Is In 
"Computer Graphics,C Version 2nd Ed" By DONALD HEARN & M.PQULINE BAKER
	                          CopyRights 2002 By LiLi.
**********************************************************************************/
#include "stdlib.h"
#include "graphics.h"
#define MAX 10
#define WINDOW_HEIGHT 480
typedef struct {
		int x;
		int y;
	       }Point;
typedef struct {
		int PolygonNum;
		Point verteces[MAX];
	       }Polygon;
typedef struct tEdge{
		   int yUpper;
		   float xIntersect,dxPerScan;
		   struct tEdge * next;
		   }Edge;
int Color;

main()
{int i;
 Polygon *P;
 void ScanFill(Polygon *);
 printf("Please Enter The Vertex Number Of the Polygon.\n");
 scanf("%d",&P->PolygonNum);
 for(i=0;i<P->PolygonNum;i++)
  {printf("The x Coordinate Of the %d Vertex.\n",i);
   scanf("%d",&P->verteces[i].x);
   printf("The y Coordinate Of the %d Vertex.\n",i);
   scanf("%d",&P->verteces[i].y);
  }
 printf("The Color Of the Plygon Area:\n");
 scanf("%d",&Color);
 P->verteces[i].x=P->verteces[0].x;
 P->verteces[i].y=P->verteces[0].y;
 ScanFill(P);
 getch();
}

/* Insert edge into list in order of increasing xIntersect field
   If the xIntersect is the same then sorting by dxPerScan */
void insertEdge(Edge *list,Edge *edge)
{
  Edge *p,*p1,*q=list;
  p=q->next;
  while(p!=NULL)
   {if(edge->xIntersect<p->xIntersect)
      p=NULL;
    else
      {p1=q;q=p;p=p->next;
      }
   }
   if(q->xIntersect==edge->xIntersect&&q->dxPerScan>edge->dxPerScan)
      {p1->next=edge;edge->next=q;
      }
   else
      {edge->next=q->next;
       q->next=edge;
      }
}
/* For an index, return y-coordinates of nonhorizontal line */
int yNext(int k,int cnt,Point *pts)
{
 int j;
 if((k+1)>(cnt-1))
   j=0;
 else
   j=k+1;
 while(pts[k].y==pts[j].y)
   if((j+1)>(cnt-1))
      j=0;
   else
      j++;
 return(pts[j].y);
}

/* restore lower-y coordinate and inverse slope for each edges. Adjust
   and store upper-y coordinate for edges that are the lower member of
   a monotonically increasing or decreasing pair of edge */
void makeEdgeRec(int x1,int y1,int x2,int y2,int yComp,Edge *edge,Edge *edges[])
{
 edge->dxPerScan=
  (float)(x2-x1)/(y2-y1);
 edge->xIntersect=x1;
 if(y2<yComp)
   edge->yUpper=y2-1;
 else
   edge->yUpper=y2;
 insertEdge(edges[y1],edge);
}

void buildEdgeList(int cnt,Point *pts,Edge *edges[])
{
 Edge *edge;
 int x1,y1,x2,y2;
 int i,yPrev=pts[cnt-2].y;
 x1=pts[cnt-1].x; y1=pts[cnt-1].y;
 for(i=0;i<cnt;i++)
  {x2=pts[i].x;y2=pts[i].y;
   if(y1!=y2)              /* nonhorizontal line */
    {edge=(Edge*)malloc(sizeof(Edge));
     if(y1<y2)              /* up-going edge */
      makeEdgeRec(x1,y1,x2,y2,yNext(i,cnt,pts),edge,edges);
     else                       /* down-going edge */
      makeEdgeRec(x2,y2,x1,y1,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;
  p1=active->next;
  while(p1)
    {p2=p1->next;
     for(i=p1->xIntersect;i<p2->xIntersect;i++)
       putpixel((int)i,WINDOW_HEIGHT-1-scan,Color);
     p1=p2->next;
    }
}

void deleteAfter(Edge *q)
{
  Edge *p=q->next;
  q->next=p->next;
  free(q);
}

/* Delete completed edges, Update 'xIntersect' field for others */
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;
  active->next=NULL;
  while(p)
    {q=p->next;
     insertEdge(active,p);
     p=q;
    }
}

void ScanFill(Polygon *P)
{Edge * edges[WINDOW_HEIGHT],* active;
 int i,scan;
 int gdriver=DETECT,gmode;
 initgraph(&gdriver,&gmode,"");

 for(i=0;i<WINDOW_HEIGHT;i++)
   {edges[i]=(Edge*)malloc(sizeof(Edge));
    edges[i]->next=NULL;
   }
 buildEdgeList(P->PolygonNum,P->verteces,edges);
 active=(Edge*)malloc(sizeof(Edge));
 active->next=NULL;

 for(scan=0;scan<WINDOW_HEIGHT;scan++)
   {buildActiveList(scan,active,edges);
    if(active->next)
      {FillScan(scan,active);
       updateActiveList(scan,active);
       resortActiveList(active);
      }
   }
 getch();
 closegraph();
}