Flood algorithme de remplissage

Question

im travaillant dans une bibliothèque graphique simple en C avec turbo C ++ car im le développement d'une version très primitive d'un programme de style de peinture, everyting fonctionne bien, mais je ne peux pas se rendre au travail l'algorithme de remplissage d'inondation. Im en utilisant l'algorithme de remplissage d'inondation 4 voies, d'abord j'ai essayé avec la version récursive mais il travaille uniquement avec de petites zones, remplir de grandes surfaces en font l'accident; la lecture i Constaté que la mise en œuvre d'une version de la pile explicite de ce résoudre le problème, mais je ne pas vraiment voir.

J'ai développé une pile comme ceci:

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 
}

Et voici le code que je dois faire à la fonction de remplissage d'inondation:

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

Mais il ne pas encore du travail, quand je suis triying pour remplir de grandes surfaces juste arrêt et parce im travailler avec une résolution de 640 X 480 dans mon programme vraiment thats un problème; toutes les idées pour lesquelles il ne fonctionnent pas?

Answer 1

Au lieu de pousser chaque pixel sur la pile, essayez de remplir autant de pixels que possible horizontalement avant de pousser une nouvelle position sur la pile. Voir Wikipedia article pour une discussion.

Answer 2

Je ne vois pas boundschecking nulle part ...

Êtes-vous sûr les valeurs X et Y ne vont pas de l'image?

EDIT:

idées supplémentaires pourquoi il ne pouvait pas travailler:

• Les fonctions de lecture et d'écriture de pixels ont un bug
• La valeur de couleur que vous obtenez en retour est mise à l'échelle jusqu'à 32 bits (car par exemple votre image est de 16 bits) et la couleur que vous essayez d'écrire et de lire à nouveau ne correspondra pas exactement. (Par exemple, vous écrivez la couleur: 0xff00ff mais vous revenez: 0xf800f8 parce que la couleur se est mis à l'échelle à partir de 16 bits) et cela se traduira par le remplissage inondation passe toujours
.