Recursive flood fill on an iPad paint app

Im using recursive flood fill algorithm on my ipad painting app and it crashes with stack overflow i think. Can someone help me solve this problem with example code or good advice because im a noob?

```-(void)paintingBucket:(int)point point2:(int)point2 width:(int)width colorAtPoint:(UIColor *)color {

int offset = 0;
int x = point;
int y = point2;
offset = 4*((width*round(y))+round(x));

if (((x<1025 && y<705)||(x<1025) ||(y<705)) && (x>0 && y>0) && (offset<2887648)) {

int alpha = data[offset];
int red = data[offset + 1];
int green = data[offset + 2];
int blue = data[offset + 3];
color1 = [UIColor colorWithRed:(green/255.0f) green:(red/255.0f) blue:(alpha/255.0f) alpha:(blue/255.0f)];

if (![color1 isEqual: color] ) {
return;
} else {
color3 = self.currentColor ;
CGFloat r,g,b,a;
[color3 getRed:&r green:&g blue: &b alpha: &a];
int reda = (int)(255.0 * r);
int greena = (int)(255.0 * g);
int bluea = (int)(255.0 * b);
int alphaa = (int)(255.0 * a);
// NSLog(@" red: %u green: %u blue: %u alpha: %u", reda, greena, bluea, alphaa);

data[offset + 3] = alphaa;
data[offset + 2] = reda;
data[offset + 1] = greena;
data[offset] = bluea;
}
}

[self paintingBucket:x+1 point2:y    width:width colorAtPoint:color];
[self paintingBucket:x-1 point2:y    width:width colorAtPoint:color];
[self paintingBucket:x   point2:y+1  width:width colorAtPoint:color];
[self paintingBucket:x   point2:y-1  width:width colorAtPoint:color];
}
```

Breaking the function into the fillRight and fillLeft methods isn't a long-term solution because if the image gets bigger, overflow may occur again.

I'd recommend using a faster flood-fill algorithm. The 4-Way flood fill described on Wikipedia is easy to implement, but goes through every point four times.

I'd recommend using a scanline fill: see http://lodev.org/cgtutor/floodfill.html - Scanline Floodfill Algorithm With Stack. I replaced my 4-way flood fill in my drawing app and it now is much faster and fills a 1024x768px area in less than a second. Of course, the speed may vary depending on your implementation.

And at last, some notes:

1.You can use CGPoint to store points in an array.

```CGPoint point=CGPointMake(100, 50); //Declare a point and put a value in it
```

Then you can get and set the x and y values using point.x and point.y

2.Use an array to store the points to be checked as deanWombourne suggested.

```NSMutableArray * pointsToCheck=[[NSMutableArray alloc]init];//Initialise the array
[pointsToCheck addObject:[NSValue valueWithCGPoint:start]];//Assuming you have a CGPoint start, you need to convert it to a NSValue before you put it into the array like [NSValue valueWithCGPoint:point]

while ([pointsToCheck count]>0){//While there are points to be checked:
NSValue * pointValue=[pointsToCheck objectAtIndex:0];//Get the point: It doesn't matter if you get the first or last item
[pointsToCheck removeObjectAtIndex:0];//Remove the point from the queue so we won't go through it again

CGPoint point=[pointValue CGPointValue];//Get the CGPoint from the NSValue object

//Implement your algorithm here: check for neighbour points, paint the current point or whatever. I'd recommend  using scanline fill - see above
//When you need to add a point to the queue (If it was a recursive function, then you'd call the function from itself with different parameters) use:
}
```

Here's a naive example fo making this a dynamic algorithm, not recursive.

```NSMutableArray *pointsToRender = [NSMutableArray new];

while (pointsToRender.length>0) {

// Get a point from the array and fill it
MyPoint *point = [pointsToRender lastObject];
[pointsToRender removeLastObject];
[self drawColor:color atPoint:point];

// Are any surrounding points needing to be filled?
if (point 1px above) needs to be filled
.. repeat for the other three points

}
```

Yea, this is half objective C and half pseudocode, sorry. But you get the idea. In English it's this :

• Make an array of points that you need to fill, containing the start point.
• For each point
• Fill it
• Remove it from the array
• Look at it's neighbours. Add each neighbour to the array if it also needs to be filled
• repeat until your points to be filled array is empty

This will consume heap, not stack.

i solved my problem using this two methods. it is a little slow but im working on optimizing this solution.

```-(void)fillRight:(int)x point2:(int)y witdh:(int)width {
int x1 = x;
int y1 = y;

int offset = 4*((width*round(y1))+round(x1));
int alpha = data[offset];
int red = data[offset + 1];
int green = data[offset + 2];
int blue = data[offset + 3];
color1 = [UIColor colorWithRed:(green/255.0f) green:(red/255.0f) blue:(alpha/255.0f) alpha:(blue/255.0f)];
// NSLog(@"%d %d %@ %@", x,y,color,color1);

if([color1 isEqual: color])
{
color3 = self.currentColor ;
CGFloat r,g,b,a;
[color3 getRed:&r green:&g blue: &b alpha: &a];
int reda = (int)(255.0 * r);
int greena = (int)(255.0 * g);
int bluea = (int)(255.0 * b);
int alphaa = (int)(255.0 * a);
// NSLog(@" red: %u green: %u blue: %u alpha: %u", reda, greena, bluea, alphaa);

data[offset + 3] = alphaa;
data[offset + 2] = reda;
data[offset + 1] = greena;
data[offset] = bluea;

[self fillRight:++x1 point2:y1 witdh:width];
x1 = x1 - 1 ;
[self fillRight:x1 point2:y1-1 witdh:width];
[self fillRight:x1 point2:y1+1 witdh:width];
}
}

-(void)fillLeft:(int)x point2:(int)y width:(int)width {
int x1 = x;
int y1 = y;

int offset = 4*((width*round(y1))+round(x1));
int alpha = data[offset];
int red = data[offset + 1];
int green = data[offset + 2];
int blue = data[offset + 3];
color1 = [UIColor colorWithRed:(green/255.0f) green:(red/255.0f) blue:(alpha/255.0f) alpha:(blue/255.0f)];
// NSLog(@"%d %d %@ %@", x,y,color,color1);

if([color1 isEqual: color])
{
color3 = self.currentColor ;
CGFloat r,g,b,a;
[color3 getRed:&r green:&g blue: &b alpha: &a];
int reda = (int)(255.0 * r);
int greena = (int)(255.0 * g);
int bluea = (int)(255.0 * b);
int alphaa = (int)(255.0 * a);
// NSLog(@" red: %u green: %u blue: %u alpha: %u", reda, greena, bluea, alphaa);

data[offset + 3] = alphaa;
data[offset + 2] = reda;
data[offset + 1] = greena;
data[offset] = bluea;

[self fillLeft:--x1 point2:y1 width:width];
x1 = x1 + 1 ;
[self fillLeft:x1 point2:y1-1 width:width];
[self fillLeft:x1 point2:y1+1 width:width];
}
}
```

Personally I prefer using the A* algorithm for flood fills. Basically, you color the visited nodes. while searching for path to a point that is known to be outside of your fill area. (-1, -1 does the trick)