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

Answers


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:
    [pointsToCheck addObject:[NSValue valueWithCGPoint:newPoint];
}

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

NSMutableArray *pointsToRender = [NSMutableArray new];
[pointsToRender addObject:startingPoint];

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
        [pointsToRender addObject : point1Above];
    .. 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)


Need Your Help

SQL Reporting Aggregates and Joining Issues

sql

I am attempting to create a report for orders moving through the various actions on a weekly basis. Could you guys help me out with it?

Form field values set with PDFBOX not visible in Adobe Reader

java pdfbox adobe-reader

I am having an issue with trying to set some from fields using Apache PDFBOX(1.8.5). I have a few different Static PDFs that I am using for testing. Using the following code, I can set the values o...