Recursive loop giving a stack overflow 2

[starsky51]

Hi All,
I've written a simple drawing program which, so far, consists of drawing shapes of various colours using the usual pen drag type method and then filling in these shapes using the recursive function below.
Filling in small shapes is not a problem, but filling in bigger shapes causes a stack overflow.
Are there any obvious problems with this code?

Dave.

(NB. m_cFromColor and m_cToColor are COLORREFs, m_cClientRect is a CRect which has been passed the GetClientRect of the window.)

void CMouseTrackDlg::RecursiveFill(CDC* pDC, int x, int y)
{
pDC->SetPixel(x, y, m_cToColor);
if(x>1 && pDC->GetPixel(x-1,y)==m_cFromColor)
RecursiveFill(pDC, x-1, y);
if(x<m_rClientArea.Width()-1 && pDC->GetPixel(x+1,y)==m_cFromColor)
RecursiveFill(pDC, x+1, y);
if(y>1 && pDC->GetPixel(x,y-1)==m_cFromColor)
RecursiveFill(pDC, x, y-1);
if(y<m_rClientArea.Height()-1 && pDC->GetPixel(x,y+1)==m_cFromColor)
RecursiveFill(pDC, x, y+1);
return;
}

 

[snuv]

I would say that the problem is caused by the design rather than the code

You are making one recursive function call for every pixel you colour in.

Every one of those calls puts more information on the stack
and eventually you run out of space

try something like

for (int i = x; 
     i>1 && pDC->GetPixel(i,y)==m_cFromColor;
     i--)
{
     pDC->SetPixel(i, y, m_cToColor);
}

Go not to cats for advice for they will just walk over the keyboard

 

[Salem]

Click Me
The scan line algorithm is also recursive, but much less so than the approach you have taken.



--

 

[starsky51]

thanks for the advice snuv.
I've expanded on your idea and it works well for basic shapes (eg. square, circle) but not for irregular shapes (eg. star).
I wanted to use the recursive algorithm to grow and 'hunt out' the small empty spaces, if that makes sense.
Can you think of a way to expand your idea to accomodate this?
Should I abandon the recursive idea?

I appreciate your input!
Dave.

 

[snuv]

I would always reccomend that you try to avoid recursive functions if you can, if only because they can be so hard to keep track of ;-)

any irregular shape can be broken down into a sequence of triangles

I would write a function that takes any three points and fills in the triangle that they describe

I would then work out an algorithm to break down the shape into triangles and then pass each triangle to your new function

I will post some pseudo code later if you want me to


Go not to cats for advice for they will just walk over the keyboard

 

[starsky51]

thanks for your help snuv and salem..
i'll try and get my head around the scanline idea and i'll bear in mind what you said... recursive bad, triangles good
here you go.. have some stars..

thanks again,
Dave.