Thread: Hello!a simple optimisation required!

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    225

    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;
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.)

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Jan 2008
    Posts
    225
    Quote Originally Posted by tabstop View Post
    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.

  5. #5
    Registered User
    Join Date
    Jan 2008
    Posts
    225
    Quote Originally Posted by Salem View Post
    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 ...

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by chottachatri View Post
    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.

  8. #8
    Registered User
    Join Date
    Jan 2008
    Posts
    225
    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

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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........
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by chottachatri View Post
    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.

  11. #11
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Quote Originally Posted by chottachatri View Post
    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.
    Last edited by mike_g; 10-19-2008 at 07:23 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  2. Simple simple program
    By Ryback in forum C++ Programming
    Replies: 10
    Last Post: 09-09-2004, 05:48 AM
  3. Help me with these simple programs
    By Help me in forum C Programming
    Replies: 4
    Last Post: 11-08-2001, 10:38 AM
  4. Need help with simple data types
    By partnole in forum C++ Programming
    Replies: 1
    Last Post: 10-03-2001, 08:36 AM
  5. Linker errors with simple static library
    By Dang in forum Windows Programming
    Replies: 5
    Last Post: 09-08-2001, 09:38 AM