Наводнение заполнить аварию

Question

Я пытался заставить работать простой алгоритм Flood Fill для приложения для iPhone, которое я разрабатываю, и я просто не могу заставить его работать правильно.

У меня есть фактический процесс, чтобы работать отлично, однако приложение будет зависать, когда заливка слишком велика. Из того, что я могу сказать, потому что поток переполняется от всех выполняющихся функций. Из того, что я прочитал, мне нужно реализовать стек, но я не могу понять, как это работает.

typedef struct {
int red;
int green;
int blue;
} color;

@interface EMFloodTest : UIViewController {

UIImageView *mainImage;
unsigned char *imageData;

color selColor;
color newColor;

int maxByte;
}

@end


@implementation EMFloodTest

- (void)setupImageData {
CGImageRef imageRef = mainImage.image.CGImage;
if (imageRef == NULL) { return; }
NSUInteger width = CGImageGetWidth(imageRef);
NSUInteger height = CGImageGetHeight(imageRef);
CGColorSpaceRef colorSpace = CGColorSpaceCreateDeviceRGB();
NSUInteger bytesPerPixel = 4;
NSUInteger bytesPerRow = bytesPerPixel * width;
NSUInteger bitsPerComponent = 8;

maxByte = height * width * 4;
imageData = malloc(height * width * 4);

CGContextRef context = CGBitmapContextCreate(imageData, width, height, bitsPerComponent, bytesPerRow, colorSpace,
                                             kCGImageAlphaPremultipliedLast | kCGBitmapByteOrder32Big);
CGColorSpaceRelease(colorSpace);
CGContextDrawImage(context, CGRectMake(0, 0, width, height), imageRef);
CGContextRelease(context);
}

- (id)initWithNibName:(NSString *)nibNameOrNil bundle:(NSBundle *)nibBundleOrNil
{
self = [super initWithNibName:nibNameOrNil bundle:nibBundleOrNil];
if (self) {
    mainImage = [[UIImageView alloc]initWithImage:[UIImage imageNamed:@"Color6.png"]];
    [self.view addSubview:mainImage];
    newColor.red = 255;
    newColor.green = 94;
    newColor.blue = 0;
    [self setupImageData];
}
return self;
}

- (void)updateImage {
CGImageRef imageRef = mainImage.image.CGImage;
if (imageRef == NULL) { return; }
NSUInteger width = CGImageGetWidth(imageRef);
NSUInteger height = CGImageGetHeight(imageRef);
CGColorSpaceRef colorSpace = CGColorSpaceCreateDeviceRGB();
NSUInteger bytesPerPixel = 4;
NSUInteger bytesPerRow = bytesPerPixel * width;
NSUInteger bitsPerComponent = 8;

CGContextRef context = CGBitmapContextCreate(imageData, width, height, bitsPerComponent, bytesPerRow, colorSpace, kCGImageAlphaPremultipliedLast ); 

imageRef = CGBitmapContextCreateImage (context);
mainImage.image = [UIImage imageWithCGImage:imageRef];  

CGContextRelease(context);  
}

- (void)setPixel:(NSUInteger)byte toColor:(color)color {
imageData[byte] = color.red;
imageData[byte+1] = color.green;
imageData[byte+2] = color.blue;
}

- (BOOL)testByte:(NSInteger)byte againstColor:(color)color {
if (imageData[byte] == color.red && imageData[byte+1] == color.green && imageData[byte+2] == color.blue) {
    return YES;
} else {
    return NO;
}
}

// This is where the flood fill starts. Its a basic implementation but crashes when filling large sections.

- (void)floodFillFrom:(NSInteger)byte bytesPerRow:(NSInteger)bpr {
int u = byte - bpr;
int r = byte + 4;
int d = byte + bpr;
int l = byte - 4;
if ([self testByte:u againstColor:selColor]) {
    [self setPixel:u toColor:newColor];
    [self floodFillFrom:u bytesPerRow:bpr];
}
if ([self testByte:r againstColor:selColor]) {
    [self setPixel:r toColor:newColor];
    [self floodFillFrom:r bytesPerRow:bpr];
}
if ([self testByte:d againstColor:selColor]) {
    [self setPixel:d toColor:newColor];
    [self floodFillFrom:d bytesPerRow:bpr];
}
if ([self testByte:l againstColor:selColor]) {
    [self setPixel:l toColor:newColor];
    [self floodFillFrom:l bytesPerRow:bpr];
}
}

- (void)startFillFrom:(NSInteger)byte bytesPerRow:(NSInteger)bpr {
if (imageData[byte] == 0 && imageData[byte+1] == 0 && imageData[byte+2] == 0) {
    NSLog(@"Black Selected");
    return;
} else if ([self testByte:byte againstColor:newColor]) {
    NSLog(@"Same Fill Color");
} else {
    // code goes here
    NSLog(@"Color to be replaced");
    [self floodFrom:byte bytesPerRow:bpr];
    [self updateImage];
}
}


- (void)selectedColor:(CGPoint)point {
CGImageRef imageRef = mainImage.image.CGImage;
if (imageRef == NULL) { return; }
if (imageData == NULL) { return; }
NSInteger width = CGImageGetWidth(imageRef);
NSInteger byteNumber = 4*((width*round(point.y))+round(point.x));
NSInteger bytesPerPixel = 4;
NSInteger bytesPerRow = bytesPerPixel * width;

selColor.red = imageData[byteNumber];
selColor.green = imageData[byteNumber + 1];
selColor.blue = imageData[byteNumber + 2];
NSLog(@"Selected Color, RGB: %i, %i, %i",selColor.red, selColor.green, selColor.blue);
NSLog(@"Byte:%i",byteNumber);
[self startFillFrom:byteNumber bytesPerRow:bytesPerRow];
}

- (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event {
UITouch *touch = [touches anyObject];
CGPoint location = [touch locationInView:mainImage];
[self selectedColor:location];
}

Буду очень признателен за любую помощь в том, как я могу реализовать стек или даже использовать другой алгоритм.

Бест, Даррен

Answer 1

Проблема в рекурсивной реализации.

Слишком глубокий рекурсивный вызов функции вызывает ошибку переполнения стека.

Вы должны реализовать свой алгоритм итеративным способом.

Если вы хотите увидеть итерационный пример Fill Fill, вы можете посетить:
https://github.com/Chintan-Dave/UIImageScanlineFloodfill