algoritmo di riempimento Flood

Question

im lavorando in una semplice libreria grafica in C con Turbo C ++, perché im lo sviluppo di una versione molto primitiva di un programma di stile di vernice, everyting funziona bene, ma non posso ottenere l'algoritmo di riempimento diluvio di lavorare. Im utilizzando l'algoritmo di riempimento alluvione a 4 vie, in primo luogo ho provato con la versione ricorsiva, ma funzionano solo con piccole aree, riempire grandi spazi rendono incidente; leggendo ho scoperto che implementare una versione dello stack esplicito di esso risolvere il problema, ma Io non vedo davvero.

Ho sviluppato una pila in questo modo:

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 questo è il codice che ho rendono alla funzione di riempimento delle inondazioni:

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

Ma è ancora tiratevi lavoro, quando im triying per riempire grandi aree che fanno fermare a causa im lavorando con risoluzione di 640 x 480 nei miei thats di programma davvero un problema; tutte le idee perché non funzionano?

Answer 1

Invece di spingere ogni pixel in pila, cercare di riempire il maggior numero possibile di pixel in orizzontale prima di spingere una nuova posizione in pila. Vedere la Wikipedia articolo per una discussione.

Answer 2

Non vedo alcun boundschecking ovunque ...

Sei sicuro che il X e Y i valori non vanno fuori dal quadro?

EDIT:

idee extra perché non potrebbe funzionare:

• Le funzioni di pixel di lettura e scrittura hanno un bug
• Il valore di colore si ottiene indietro è scalato fino a 32 bit (perché, per esempio, l'immagine è a 16 bit) e il colore che si sta tentando di scrivere e leggere di nuovo non corrispondere esattamente. (Ad esempio, si scrive il colore: 0xFF00FF ma si ottiene indietro: 0xf800f8 perché il colore ottenuto scalato da 16 bit) e questo si tradurrà nel riempimento delle inondazioni in corso per sempre
.