Fuell Algorithmus

Question

im in einer einfachen grafischen Bibliothek in C mit Turbo C ++ arbeiten, weil im eine sehr primitive Version eines Farbenart Programm zu entwickeln, das Every funktioniert gut, aber ich kann nicht die Flußfüllen Algorithmus zu arbeiten. Im mit dem 4-Wege-Flußfüllen Algorithmus, zuerst hatte ich versucht, mit der rekursiven Version aber nur mit kleinen Bereichen arbeiten, füllen große Flächen es zum Absturz zu bringen; Lesen i eine explizite Stack Version davon, daß das Gerät gefunden, das Problem lösen, aber ich sehe es dont wirklich.

Ich habe einen Stapel wie folgt entwickelt:

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 
}

Und das ist der Code, den ich an die Flutfüllung Funktion machen:

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

Aber es noch Arbeit dont, wenn im triying großen Flächen füllen Sie es einfach aufhören und weil im mit einer Auflösung von 640 x 480 in meinem Programm das ist wirklich ein Problem arbeiten; irgendwelche Ideen, warum es nicht funktionieren?

Answer 1

Statt jedes Pixel auf dem Stapel zu schieben, versuchen, so viele Pixel wie möglich horizontal zu füllen, bevor eine neue Position auf dem Stapel schieben. Sehen Sie sich die Wikipedia-Artikel für eine Diskussion.

Answer 2

Ich sehe keinen boundschecking überall ...

Sind Sie sicher, dass die X- und Y-Werte gehen nicht aus dem Bild?

EDIT:

Zusätzliche Ideen, warum es könnte nicht funktionieren:

• Die Lese- und Schreibpixelfunktionen haben einen Fehler
• Der Farbwert Sie zurück auf 32 Bit skaliert (weil zum Beispiel Ihr Bild ist 16 Bit) und die Farbe, die Sie versuchen, wieder zu schreiben und lesen wieder exakt überein. (Zum Beispiel schreiben Sie die Farbe: 0xFF00FF aber Sie: 0xf800f8, weil die Farbe von 16 Bit wurde skaliert) und dies führt in den Flußfüllen für immer los
.