-2

私のiPadペイントアプリで再帰的な塗りつぶしアルゴリズムを使用していますが、スタックオーバーフローでクラッシュすると思います。私は初心者なので、サンプルコードまたは良いアドバイスでこの問題を解決するのを手伝ってくれる人はいますか?

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

4 に答える 4

1

これを再帰的ではなく動的なアルゴリズムにする簡単な例を次に示します。

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

}

はい、これは半分客観的 C で半分疑似コードです。申し訳ありません。しかし、あなたはその考えを理解します。英語では次のようになります。

  • 開始点を含む、塗りつぶす必要がある点の配列を作成します。
  • ポイントごとに
    • 埋める
    • アレイから削除します
    • その隣人を見てください。埋める必要がある場合は、配列に各隣人を追加します
    • 配列を埋めるポイントが空になるまで繰り返します

これは、スタックではなくヒープを消費します。

于 2012-09-10T10:53:30.913 に答える
0

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];
}
于 2013-01-25T10:16:49.483 に答える
0

この2つの方法を使用して問題を解決しました。少し遅いですが、このソリューションの最適化に取り組んでいます。

-(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];
}
}
于 2012-09-14T09:16:45.807 に答える
0

個人的には、フラッド フィルに A* アルゴリズムを使用することを好みます。基本的に、訪問したノードに色を付けます。塗りつぶし領域の外側にあることがわかっているポイントへのパスを検索している間。(-1、-1 でうまくいく)

于 2012-11-16T16:36:14.523 に答える