Hello!a simple optimisation required!

Hello,

i wrote a program for filling polygon.First i did it with recursive calls. But recursive calls are too bad they fill the stack memory and my compiler crashed. So then i used stack now in stack also my work is done but the memory requirement is way too high. This is a flood fill algorithm. Can anybody optimize my solution i will be very grateful to that person. The code is .

Code:

#include <stdio.h>
#include <graphics.h>
#include <stdlib.h>

struct points
{
 int x;
 int y;
};
struct stack
{
 int dataX[10000];
 int dataY[10000];
 int top;
};
void push(struct stack *s,int m,int n)
{
	s->top++;
	s->dataX[s->top]=m;
	s->dataY[s->top]=n;
}
struct points pop(struct stack *s)
{
	struct points t;
	t.x=s->dataX[s->top];
	t.y=s->dataY[s->top];
	s->top--;
	return t;
}


int main(void)
{
 int gd=DETECT,gm,errorcode;
 int n=4,i;
 struct points w[10],t;
 int x=105,y=105;
 struct stack s;
 s.top=-1;

 initgraph(&gd,&gm,"c:\\tc\\bgi");
 errorcode=graphresult();
 if(errorcode!=grOk)
 {
	printf("%s",grapherrormsg(errorcode));
	exit(1);
 }
 w[0].x=100; // assigning to draw square
 w[0].y=100;

 w[1].x=200;
 w[1].y=100;

 w[2].x=200;
 w[2].y=200;

 w[3].x=100;
 w[3].y=200;

 for(i=0;i<=n-2;i++) //drawing square
	line(w[i].x,w[i].y,w[i+1].x,w[i+1].y);
 line(w[0].x,w[0].y,w[n-1].x,w[n-1].y); 
 push(&s,x,y);
 while(s.top!=-1) //code for flood fill
 {
	putpixel(x,y,14);
	if(getpixel(x,y+1)==0)
		push(&s,x,y+1);
	if(getpixel(x,y-1)==0)
		push(&s,x,y-1);

	if(getpixel(x+1,y)==0)
		push(&s,x+1,y);
	if(getpixel(x-1,y)==0)
		push(&s,x-1,y);
	delay(3);
	t=pop(&s);
	x=t.x;
	y=t.y;
 }
 return 0;
}

The only memory requirements for the stack are here:

Code:

struct stack
{
 int dataX[10000];
 int dataY[10000];
 int top;
};

Do you expect to have 10000 points? Why not make it 100, or however many you expect to have? (Also: 20000 ints is what, 80K of memory? That doesn't seem outrageously outrageous, although it is probably more than you need.)

80K is monstrous, when you're using
initgraph(&gd,&gm,"c:\\tc\\bgi");

AKA, "the fossil" which is TurboC
64K is the max for any single data structure.

Just get a 32-bit compiler, which comes with a decent graphics API and stop being a caveman playing with pebbles on the beach.

Originally Posted by tabstop

Do you expect to have 10000 points? Why not make it 100, or however many you expect to have? (Also: 20000 ints is what, 80K of memory? That doesn't seem outrageously outrageous, although it is probably more than you need.)

Do you know what a flood fill algorithm is?Before replying anything please have a look at this and then you put your point

http://www.codeproject.com/KB/GDI/QuickFill.aspx

As you can see in basic 4 way recursive method we keep calling the function again and again and so stack gets filled up and my compiler crashes. And yeah i need 10000 points (if i dont optimise my algorithm) because i keep push every point on stack. You can caculate that even a 100 * 100 pixel rectangle would take 10000 points.

Originally Posted by Salem

Just get a 32-bit compiler, which comes with a decent graphics API and stop being a caveman playing with pebbles on the beach.

in TC also we have graphics API for flood fill but what i want is to implement my own flood fill algorithm. You may say why to reinvent the wheel but i want to have a better look at how things work and so ...

http://clusty.com/search?query=scanl...Mozilla-search
One optimisation is to fill y,x+1 with a simple loop, and not recursion.
Then the maximum depth of recursion is the height of your screen, and not the number of pixels.

Originally Posted by chottachatri

Do you know what a flood fill algorithm is?Before replying anything please have a look at this and then you put your point

http://www.codeproject.com/KB/GDI/QuickFill.aspx

As you can see in basic 4 way recursive method we keep calling the function again and again and so stack gets filled up and my compiler crashes. And yeah i need 10000 points (if i dont optimise my algorithm) because i keep push every point on stack. You can caculate that even a 100 * 100 pixel rectangle would take 10000 points.

Are you claiming that you have any recursion at all in your program as posted here?

Also, that stack that you have is not the stack people talk about overflowing when they talk about recursion (but rather the call stack). If you reformed your program to be recursive in nature, then you would not have a stack in your program at all.

And yes, I know what flood fill is. In fact you've done pretty good at beating that 4-way recursive algorithm you keep talking about.

I think you're confused! i said that i used recursion in my previous program and while running that progran (with recursion) my compiler crashed. So i used stack with an array size of 10000. Now my program is working fine(without any crashes...for small polygons) but i want to optimise it. Now did you understand what i mean?and yeah i know what is a recursion and what is stack. :d

Like I said, +/- x can be filled with a simple loop.

For convex polygons, that's dead easy.

For concave polygons, like this

Code:

|\      /|
| \    / |
|  \  /  |
|   \/   |
|        |
|        |
|        |
|        |
----------

You need some care when you reach the tip of the inward pointing vertex to make sure you fill the part of the polygon which is presently out of sight of the other part.
I'm sure the links I posted explain all........

Originally Posted by chottachatri

I think you're confused! i said that i used recursion in my previous program and while running that progran (with recursion) my compiler crashed. So i used stack with an array size of 10000. Now my program is working fine(without any crashes...for small polygons) but i want to optimise it. Now did you understand what i mean?and yeah i know what is a recursion and what is stack. :d

Right. So in this version the only memory requirement is the stack. I'm pretty sure that's what I said the first time?

If you want to make the stack as memory-light as possible, you could implement it as a linked list. (You've already got the structures set up, so your stack would just contain a pointer to "points" and push would malloc a struct and set it in the list, pop would return the struct and de-link it.)

I suppose you could cut your memory usage in half/quarter by using unsigned char rather than int, since you don't seem to need numbers larger than 255.

Originally Posted by chottachatri

Do you know what a flood fill algorithm is?Before replying anything please have a look at this and then you put your point

http://www.codeproject.com/KB/GDI/QuickFill.aspx

From what I can tell you have implemented a 4way iterative solution, not the quickfill algorithm you linked to.

I think that one of the optimisations you missed is that you don't want to be hopping scanlines each iteration; you want to fill lines until you reach an end point, then search for adjacent scanlines to hop to.. The page also mentions replacing an array with a list, as tabstop suggested.

I always wanted to have a go at implementing a fast fill, but never got around to it. So, tbh, the best advice I can really give is to get back to the example you found and try and figure it out. Pretty much all the optimisations you need can be found there.