ملء الفيضانات خوارزمية

Question

أنا أعمل في مكتبة رسومية بسيطة في C مع Turbo C ++ لأن Im تطوير نسخة بدائية للغاية من برنامج أسلوب الطلاء، كل شيء يعمل بشكل جيد ولكن لا يمكنني الحصول على خوارزمية ملء الفيضانات للعمل. IM باستخدام خوارزمية ملء الفيضانات الأربعة، أولا حاولت مع الإصدار العريز ولكنها تعمل فقط مع المناطق الصغيرة، ملء المناطق الكبيرة تجعل تحطمها؛ قراءة وجدت أن تنفيذ نسخة مكدس صريحة من حل المشكلة، لكنني لا أرى ذلك حقا.

لقد طورت مكدسة مثل هذا:

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 × 480 في برنامجي هذه مشكلة حقا؛ أي أفكار لماذا لا تعمل؟

Answer 1

بدلا من دفع كل بكسل على المكدس، حاول ملء أكبر عدد ممكن من وحدات البكسل أفقيا قبل دفع موقف جديد على المكدس. انظر ويكيبيديا المادة لمناقشة.

Answer 2

أنا لا أرى أي حدودية في أي مكان ...

هل أنت متأكد من أن قيم x و y لا تخرج من الصورة؟

تعديل:

أفكار إضافية لماذا لا يمكن أن تعمل:

• وظائف القراءة والكتابة بكسل لها خطأ
• يتم تحجيم قيمة اللون التي تعودها حتى 32 بت (لأنه على سبيل المثال، صورتك هي 16 بت) واللون الذي تحاول الكتابة والقراءة مرة أخرى لن يتطابق مرة أخرى. (على سبيل المثال، تكتب اللون: 0xFF00FF ولكنك تعود: 0xf800f8 لأن اللون حصل على ارتفاع من 16 بت) وهذا سيؤدي إلى تعبئة الفيضانات التي تسير إلى الأبد.