Anybody know of a library that handles arbitrary polygon filling? I

have only found them for lines, triangles, circles etc. and I really

donâ€™t want to write my own.

Thanks

p

Anybody know of a library that handles arbitrary polygon filling? I

have only found them for lines, triangles, circles etc. and I really

donâ€™t want to write my own.

Thanks

p

well, each polygon can be broken into a series of triangles. Software

implementations of 3d engines do it this way so id be fairly confident

saying that is the most efficient way to do it. You might consider doing

that (:

other than thatâ€¦no i dont :P> ----- Original Message -----

From: pchans@wm.edu ()

To:

Sent: Saturday, September 21, 2002 7:53 PM

Subject: [SDL] polygon fillingAnybody know of a library that handles arbitrary polygon filling? I

have only found them for lines, triangles, circles etc. and I really

donâ€™t want to write my own.Thanks

p

SDL mailing list

SDL at libsdl.org

http://www.libsdl.org/mailman/listinfo/sdl

have only found them for lines, triangles, circles etc. and I really

donâ€™t want to write my own.

Basically you do the same thing as for lines or circles. You iterate

over the edge-pixels and draw a horizontal line from one pixel to the

other. Well - this works for konvex Polygons, but not for concav

(S-Shape) or intersecting polygons (5-edged star).

To write this on your own would be rather tricky (I did once - scaaary

thing =) and I guess the way Alan suggested is probably one of the

smoothest, because triangles are always convex. Anyways finding the

triangles is still a bit tricky, too.

Search google for â€śpolygon fillingâ€ť - there are quite many tutorials on it.

Ciao

Arne

You wrote:

have only found them for lines, triangles, circles etc. and I really

donâ€™t want to write my own.

You can try this:

#define MaxPoints 50

void FilledPolygon(int NumPoints,int Pointsx[],int Pointsy[])

{

struct all_edges{

int ymin;

int ymax;

float x;

float m;

} *Edges[MaxPoints];

if (NumPoints > 0) {

int i,succ;

for(i=0;(i<NumPoints);i++) {

if (i == (NumPoints-1)) succ = 0;

else succ = i+1;

if ((Pointsy[succ]-Pointsy[i]) != 0) {

Edges[i] = (all_edges *) malloc(sizeof(all_edges));

Edges[i]->ymin=Mini(Pointsy[i],Pointsy[succ]);

Edges[i]->ymax=Maxi(Pointsy[i],Pointsy[succ]);

if (Edges[i]->ymin == Pointsy[i]) Edges[i]->x=Pointsx[i];

else Edges[i]->x=Pointsx[succ];

Edges[i]->m=((float)(Pointsx[succ]-Pointsx[i]))/

(Pointsy[succ]-Pointsy[i]);

}

else Edges[i]=NULL;

}

int j,t,m;

bool found;

all_edges *Global[MaxPoints];

for(i=t=0;(i<NumPoints);i++) {

if (Edges[i]!=NULL) {

found = false;

Global[t] = Edges[i];

for(j=0;((j<t) && (!found));j++) {

if ((Global[t]->ymin < Global[j]->ymin) ||

((Global[t]->ymin == Global[j]->ymin) &&

(Global[t]->x < Global[j]->x)) ||

((Global[t]->ymin == Global[j]->ymin) &&

(((int)Global[t]->x) == ((int)Global[j]->x))

&& (Global[t]->ymax < Global[j]->ymax)))

found = true;

}

if (found) {

all_edges *TempEdges = (all_edges *) malloc(sizeof(all_edges));

TempEdges->ymin = Global[t]->ymin;

TempEdges->ymax = Global[t]->ymax;

TempEdges->x = Global[t]->x;

TempEdges->m = Global[t]->m;

for(m=t;(m>=j);mâ€“) {

Global[m]->ymin = Global[m-1]->ymin;

Global[m]->ymax = Global[m-1]->ymax;

Global[m]->x = Global[m-1]->x;

Global[m]->m = Global[m-1]->m;

}

Global[m]->ymin = TempEdges->ymin;

Global[m]->ymax = TempEdges->ymax;

Global[m]->x = TempEdges->x;

Global[m]->m = TempEdges->m;

free(TempEdges);

}

t++;

}

}

int NumEdges = t;

if (NumEdges > 0) {

int ScanLine = Global[0]->ymin;

int MaxScanLine = ScanLine;

for(i=1;i<NumEdges;i++) {

if (Global[i]->ymax > MaxScanLine) MaxScanLine = Global[i]->ymax;

}

int xmin,xmax;

xmin = xmax = (int) Global[0]->x;

for(i=1;i<NumEdges;i++) {

if (Global[i]->x < xmin) xmin = (int) Global[i]->x;

if (Global[i]->x > xmax) xmax = (int) Global[i]->x;

}

for(i=0;i<NumPoints;i++) Edges[i] = NULL;

t = 0;

while((t<NumEdges) && (Global[t]->ymin == ScanLine)) {

Edges[t] = Global[t];

Global[t] = NULL;

t++;

}

int NumActive = t;

while(ScanLine<MaxScanLine) {

for(j=0;j<NumActive;j++) {

if (j != (NumActive-1))

Line ((int)(Edges[j]->x),ScanLine,

(int)(Edges[j+1]->x),ScanLine);

j++;

}

ScanLine++;

for(j=0;j<NumActive;j++) {

if (Edges[j]->ymax == ScanLine) {

free(Edges[j]);

Edges[j] = NULL;

}

}

for(j=t=0;j<NumActive;j++) {

if (Edges[j] != NULL) {

if (t != j) {

Edges[t] = Edges[j];

Edges[j] = NULL;

}

t++;

}

}

NumActive = t;

for(j=0;j<NumActive;j++)

Edges[j]->x += Edges[j]->m;

for(j=0;j<NumEdges;j++) {

if (Global[j] != NULL) {

if (Global[j]->ymin == ScanLine) {

Edges[NumActive] = Global[j];

Global[j] = NULL;

NumActive++;

}

}

}

for(i=0;(i<NumActive);i++) {

found = false;

for(j=0;((j<i) && (!found));j++) {

if ((Edges[i]->x < Edges[j]->x) ||

((Edges[i]->x == Edges[j]->x) &&

(Edges[i]->ymax < Edges[i]->ymax)))

found = true;

}

if (found) {

all_edges *TempEdges = (all_edges *) malloc(sizeof(all_edges));

TempEdges->ymin = Edges[i]->ymin;

TempEdges->ymax = Edges[i]->ymax;

TempEdges->x = Edges[i]->x;

TempEdges->m = Edges[i]->m;

for(m=i;(m>=j);mâ€“) {

Edges[m]->ymin = Edges[m-1]->ymin;

Edges[m]->ymax = Edges[m-1]->ymax;

Edges[m]->x = Edges[m-1]->x;

Edges[m]->m = Edges[m-1]->m;

}

Edges[m]->ymin = TempEdges->ymin;

Edges[m]->ymax = TempEdges->ymax;

Edges[m]->x = TempEdges->x;

Edges[m]->m = TempEdges->m;

free(TempEdges);

}

}

}

}

}

}