扫描线填充算法--有效边表填充算法

代码：

draw.cpp

//using OpenGL

#include "opengl.h"

#include

#include

#include

#include

#define PN 6

int

point[N][2]={{40,5},{75,40},{60,70},{35,50},{25,80},{5,30 }};

//AE

struct AE{

AE(float _x,float _dx,int

_ymax){x=_x;dx=_dx;ymax=_ymax;}

float x;

float dx;

int ymax;

void operator++(int){

x+=dx;

}

};

//AET

//which eage is on the right

bool fill_comp(const AE& ae1,const AE& ae2){

if(ae1.x

return true;

}

if(ae1.x==ae2.x&&ae1.dx

return true;

}

return false;

}

void fillline(int y,int x1,int x2){

for(int i=x1;i<=x2;i++) drawpoint(i,y);

flush();

}

void fill(){

//make k=(x2-x1)/(y2-y1)

float k[PN]={0.0};for(int

i=0;i!=PN;i++){k[i]=((float)(point[(i+1)%PN][0]-point[i][ 0])/(float)(point[(i+1)%PN][1]-point[i][1]));}

//find min and max with selection sort.

int min=point[0][1],max=min;for(int

i=0;i!=PN;i++){if(point[i][1]>max){max=point[i][1];};;if( point[i][1]

//make scanning line list

std::vector*ET =new std::vector[max-min+1];

//make ET

//

for(int i =0; i

//get ymin, ymax

int yminn=point[i][1]

(i+1)%PN;

int ymaxn=point[i][1]>=point[(i+1)%PN][1]? i :

(i+1)%PN;

AE *tmp =new

AE(point[yminn][0],k[i],point[ymaxn][1]);

//insert node

ET[point[yminn][1]-min].push_back(*tmp);

}

//init AET

std::vector AET;

for(int i=0;i!=max-min+1;i++){

//insert node from ET to AET

for(int ii=0;ii!=ET[i].size();ii++){

//sort with selection sort.

AET.insert(std::upper_bound(AET.begin(),

AET.end(),ET[i][ii],fill_comp),ET[i][ii]);

}

//delete y=ymax,"下闭上开"

for(int

ii=0;ii!=AET.size();){if(i+min==AET[ii].ymax)

{AET.erase(AET.begin()+ii);}else{ii++;}}

//draw

{

bool flag=false;

for(int ii=0;ii!=AET.size();ii++){

if(flag)

fillline(i+min,(int)(AET[ii-1].x+0.5),(int)(AET[ii].x+0.5 ));

//if(flag)

std::cout<

flag=!flag;

}}

for(int ii=0;ii!=AET.size();ii++){AET[ii]++;} }

delete[](ET);

}

void draw(){

drawgrid(0.8,0.8,0.8);

setcolor(1,0.5,0.5);

fill();

draweage(point,PN);

}

int main(int n,char*avg[]){

init(n,avg,"L2");

reinit(draw);

loop();

return0;

}

opengl.h

#include

#define N 100

#define GRIDSIZE 5

int size=N*GRIDSIZE;

void init(int argc,char** argv,char*title){

//init openGL

size = N * GRIDSIZE;

glutInit(&argc, argv);

glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE);

glutInitWindowPosition(10,10);