Алгоритм заполнения залива

Question

Я работаю над простой графической библиотекой на C с Turbo C++, потому что я разрабатываю очень примитивную версию программы стиля рисования, все работает хорошо, но я не могу заставить работать алгоритм заливки.Я использую четырехсторонний алгоритм заливки, сначала я попробовал рекурсивную версию, но она работает только с небольшими областями, заполнение больших областей приводит к сбою;Прочитав, я обнаружил, что реализация явной версии стека решает проблему, но я этого не вижу.

Я разработал такой стек:

struct node
{
    int x, y;
    struct node *next;
};

int push(struct node **top, int x, int y)
{
    struct node *newNode;
    newNode = (struct node *)malloc(sizeof(struct node));
    if(newNode == NULL) //If there is no more memory
        return 0;
    newNode->x = x;
    newNode->y = y;
    newNode->next = *top;
    *top = newNode;
    return 1; //If we push the element correctly
}

int pop(struct node **top, int &x, int &y)
{
    if(*top == NULL) //If the stack is empty
        return 0;
    struct node *temporal;
    temporal = *top;
    x = (*top)->x;
    y = (*top)->y;
    *top = (*top)->next;
    free(temporal);
    return 1; //If we pop an element 
}

И это код, который я создал для функции заливки:

void floodFill(int x, int y, int color_to_replace, int color_to_fill)
{
    if(color_to_replace == color_to_fill)
  return;
 struct node *stack = NULL;
 if(push(&stack, x, y) == 0) //If we can´t push the pixel
            return;
    while(pop(&stack, x, y) == 1) //While are pixels in the stack
    {
        pixel(x, y, color_to_fill);
        if(x+1 < 640 && read_pixel(x+1, y) == color_to_replace)
            if(push(&stack, x+1, y) == 0)
                return;
        if(x-1 >= 0 && read_pixel(x-1, y) == color_to_replace)
            if(push(&stack, x-1, y) == 0)
                return;
        if(y+1 < 480 && read_pixel(x, y+1) == color_to_replace)
            if(push(&stack, x, y+1) == 0)
                return;
        if(y-1 >= 0 && read_pixel(x, y-1) == color_to_replace)
            if(push(&stack, x, y-1) == 0)
                return;
    }
}

Но это все еще не работает: когда я пытаюсь заполнить большие области, он просто останавливается, и поскольку я работаю с разрешением 640 X 480 в своей программе, это действительно проблема;есть идеи, почему это не работает?

Answer 1

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

Answer 2

Я нигде не вижу проверки границ...

Вы уверены, что значения X и Y не выходят за рамки изображения?

РЕДАКТИРОВАТЬ:

Дополнительные идеи, почему это не сработало:

• В функциях чтения и записи пикселей есть ошибка
• Значение цвета, которое вы получаете обратно, масштабируется до 32 бит (потому что, например, ваше изображение 16-битное), и цвет, который вы пытаетесь записать и прочитать снова, не будет точно совпадать.(например.вы пишете цвет:0xff00ff, но вы получаете обратно:0xf800f8, потому что цвет был увеличен с 16 бит), и это приведет к тому, что заливка будет продолжаться вечно.