fill optimizations

This is a discussion on fill optimizations within the C++ Programming forums, part of the General Programming Boards category; I have the following recursive implementation of the fill algorithm: Code: void fill(int x, int y) { if ( mat[x][y] ...

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    50

    fill optimizations

    I have the following recursive implementation of the fill algorithm:

    Code:
    void fill(int x, int y)
    {		
    	if ( mat[x][y] == 0 )
            {
    	        mat[x][y] = 1;
    		fill(x+1, y);
    		fill(x-1, y);
    		fill(x, y+1);
    		fill(x, y-1);
    	}
    }
    I'm wondering, is this efficient? I read that the recursion doesn't slow things down in this case as much as it does in other algorithms, is this true?

    Would an interative approach give a significant increase in speed? Is it worth implementing it iteratively, and if so, how would I approach that?

  2. #2
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,471
    you don't check bounds
    you use global variable (are you sure you need it?)
    recursion does not slow things down only if it is optimized by compiler...
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,437
    > I'm wondering, is this efficient?
    No. It uses stupid amounts of stack space for even simple shapes.

    Do a web search for "scanline fill algorithm".
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list fill the gaps question..
    By transgalactic2 in forum C Programming
    Replies: 2
    Last Post: 07-06-2009, 12:35 PM
  2. Question On how to Fill icmp_data
    By Antigloss in forum Linux Programming
    Replies: 3
    Last Post: 04-25-2007, 09:42 PM
  3. Replies: 0
    Last Post: 03-23-2006, 11:42 AM
  4. Quick fill question
    By Mr Moe in forum C++ Programming
    Replies: 5
    Last Post: 02-25-2005, 03:26 PM
  5. Replies: 3
    Last Post: 12-22-2004, 06:29 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21