# include <dos.h> # include <stdio.h> # include <graphics.h> # include <iostream.h> # include <conio.h> # include <math.h> struct Polygon { int x; int y; }; struct edRecord { int YUpper; float XIntersect; float dxperscan; struct edRecord *Next; }; typedef struct edRecord Edge; typedef struct Polygon Nodes; Edge *Active; Edge **Edges; int Cntr=6; Nodes NodesObj[6]={{100,100},{150,150},{150,200},{100,250},{50,200},{50,150}}; void Scanfill(); void InsertEdge(Edge*,Edge*); void BuildEdgeList(int,Nodes*); int YNext(int); void MakeEdgeRec(Nodes,Nodes,int,Edge*); void BulidActiveList(int); void UpdateActiveList(int); void DeleteAfter(Edge*); void ResortActiveList(void); void ResortActiveList(int); //************************************************************************** void main() { int gDriver = DETECT, gMode; int n,xArray[12]; int iCntr,jCntr; initgraph(&gDriver,&gMode,\"c:\\\\tc\\\\bgi\"); for(iCntr=0,jCntr=0;iCntr<12;iCntr+=2,jCntr++) xArray[iCntr] = NodesObj[jCntr].x; for(iCntr=1,jCntr=0;iCntr<12;iCntr+=2,jCntr++) xArray[iCntr] = NodesObj[jCntr].y; drawpoly(6,xArray); line(NodesObj[5].x,NodesObj[5].y,NodesObj[0].x,NodesObj[0].y); //TO CLOSE POLYGON getch(); Scanfill(); getch(); closegraph(); restorecrtmode(); return; } //************************************************************************** void Scanfill() { int iCntr,Scan; //initialize edgelists with dummy nodes Edges=new Edge*[getmaxy()]; for(iCntr=0;iCntr<getmaxy();iCntr++) { Edges[iCntr] = new Edge; Edges[iCntr]->Next = NULL; } //initialize Active edgeList with dummy nodes Active = new Edge; Active->Next = NULL; BuildEdgeList(Cntr,NodesObj); for(Scan=0;Scan<getmaxy();Scan++) { BulidActiveList(Scan); if (Active->Next != NULL) { ResortActiveList(Scan); UpdateActiveList(Scan); ResortActiveList(); } } } //************************************************************************** void InsertEdge(Edge* edgeList,Edge* InitialEdge) { Edge *PEdge,*QEdges; QEdges=edgeList; PEdge=QEdges->Next; while(PEdge!=NULL) if(InitialEdge->XIntersect < PEdge->XIntersect) PEdge=NULL; else { QEdges=PEdge; PEdge=PEdge->Next; } InitialEdge->Next = QEdges->Next; QEdges->Next = InitialEdge; } //************************************************************************** void BuildEdgeList(int Cntr,Nodes* Vertices) { Edge* NewEdge; Nodes Vertex1,Vertex2; int YPrev,iCntr; Vertex1.x=Vertices[Cntr-1].x; Vertex1.y=Vertices[Cntr-1].y; YPrev = Vertices[Cntr-2].y; for(iCntr=0;iCntr<Cntr;iCntr++) { Vertex2.x = Vertices[iCntr].x; Vertex2.y = Vertices[iCntr].y; if(Vertex1.y != Vertex2.y) { NewEdge = new Edge; if(Vertex1.y < Vertex2.y) MakeEdgeRec(Vertex1,Vertex2,YNext(iCntr),NewEdge); else MakeEdgeRec(Vertex2,Vertex1,YPrev,NewEdge); } YPrev = Vertex1.y; Vertex1.x = Vertex2.x; Vertex1.y = Vertex2.y; } } //************************************************************************** void BulidActiveList(int Scan) { Edge *PEdge,*QEdges; PEdge=Edges[Scan]->Next; while(PEdge!=NULL) { QEdges=PEdge->Next; InsertEdge(Active,PEdge); PEdge=QEdges; } } //*************************************************************************** void ResortActiveList(int Scan) { Edge *iEdge,*jEdge; int iCntr; iEdge = Active->Next; while(iEdge!=NULL) { jEdge = iEdge->Next; for(iCntr=iEdge->XIntersect;iCntr<=jEdge->XIntersect-1;iCntr++) putpixel(iCntr,Scan,RED); iEdge=jEdge->Next; } } //*************************************************************************** void UpdateActiveList(int Scan) { Edge *PEdge,*QEdges; QEdges=Active; PEdge=Active->Next; while(PEdge!=NULL) { if(Scan>=PEdge->YUpper) { PEdge=PEdge->Next; DeleteAfter(QEdges); } else { PEdge->XIntersect+=PEdge->dxperscan; QEdges=PEdge; PEdge=PEdge->Next; } } } //*************************************************************************** void ResortActiveList() { Edge *PEdge,*QEdges; PEdge=Active->Next; Active->Next=NULL; while(PEdge!=NULL) { QEdges=PEdge->Next; InsertEdge(Active,PEdge); PEdge=QEdges; } } //*************************************************************************** int YNext(int YCurr) { int jCntr; if(YCurr+1>Cntr) jCntr=1; else jCntr=YCurr+1; while(NodesObj[YCurr].y == NodesObj[jCntr].y) { if(jCntr+1>Cntr) jCntr=1; else jCntr++; } return(NodesObj[jCntr].y); } //*************************************************************************** void DeleteAfter(Edge* QEdges) { Edge* PEdge; PEdge = QEdges->Next; QEdges->Next = PEdge->Next; delete PEdge; } //*************************************************************************** void MakeEdgeRec(Nodes Lower,Nodes Upper,int YComp,Edge* CurrEdge) { CurrEdge->dxperscan = (Upper.x - Lower.x) / (Upper.y - Lower.y); CurrEdge->XIntersect = Lower.x; if(Upper.y < YComp) CurrEdge->YUpper = Upper.y - 1; else CurrEdge->YUpper = Upper.y; InsertEdge(Edges[Lower.y],CurrEdge); }