algoritmo de preenchimento Flood

Question

im trabalham em uma biblioteca gráfica simples em C com turbo C ++ porque im desenvolvendo uma versão muito primitiva de um programa de estilo de pintura, everyting funciona bem, mas eu não posso obter o algoritmo de inundação preenchimento ao trabalho. Im usando o algoritmo de inundação preenchimento maneira 4, primeiro eu tentei com a versão recursiva, mas ele só trabalho com pequenas áreas, enchendo grandes áreas torná-lo falhar; lendo descobri que implementar uma versão pilha explícita de que resolver o problema, mas eu não realmente vê-lo.

Eu desenvolvi uma pilha assim:

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 
}

E este é o código que eu tenho make para a função de inundação preenchimento:

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

Mas ainda NÃO FAZEM trabalho, quando im triying para preencher grandes áreas apenas parar e porque im trabalhando com resolução de 640 X 480 no meu programa isso é realmente um problema; Alguma idéia por que não trabalham?

Answer 1

Em vez de empurrar cada pixel na pilha, tentar preencher o maior número de pixels possível horizontalmente antes de empurrar uma nova posição na pilha. Veja a Wikipedia artigo para uma discussão.

Answer 2

Eu não vejo qualquer lugar boundschecking ...

Você tem certeza dos valores X e Y não saem do quadro?

EDIT:

idéias extra por isso não poderia trabalho:

• As funções de leitura e pixel de escrita tem um bug
• O valor da cor você voltar é escalado até 32 bit (porque, por exemplo, a sua imagem é de 16 bit) e a cor que você está tentando escrever e ler de volta não vai corresponder exatamente. (Por exemplo, você escreve a cor: 0xff00ff mas você voltar: 0xf800f8 porque a cor foi ampliado de 16 bit) e isso vai resultar no preenchimento de inundação acontecendo sempre
.