c - 这个 floodfill 算法有什么问题？

Question

我一直在使用基于堆栈的非递归变体的填充算法，它似乎完美地工作除了一个烦人的情况:如果使用一条线将图像切成两半然后floodfill 一半，它淹没了整个图像!然而，只有当我没有在图像周围放置“边框”时，才会发生这种情况。如果我绘制一个封装图像的矩形(即在图像上放置边框)，那么它就可以正常工作。所以很明显，代码的边界查找方面有问题，但我终究无法找到问题所在。有(希望)比我更敏锐的眼睛的人能发现问题吗？这让我疯狂! (p.s语言是C)

/** scanfill algorithm **/
/* the stack */
#define stackSize 16777218
int stack[stackSize];
int stackPointer;

static bool
pop(int * x, int * y, int h) 
{ 
    if(stackPointer > 0) 
    { 
        int p = stack[stackPointer]; 
        *x = p / h; 
        *y = p % h; 
        stackPointer--; 
        return true; 
    }     
    else 
    { 
        return false;
    }    
}    

static bool
push(int x, int y, int h) 
{ 
    if(stackPointer < stackSize - 1) 
    { 
        stackPointer++; 
        stack[stackPointer] = h * x + y; 
        return true;
    }     
    else 
    { 
        return false;
    }    
}     

static void
emptyStack() 
{ 
    int x, y; 
    while(pop(&x, &y, 0)); 
}

void
scan_fill_do_action(int x, int y, texture_info * tex, VALUE hash_arg,
                sync sync_mode, bool primary, action_struct * payload)
{
    action_struct cur;
    rgba old_color;
    int y1;
    bool spanLeft, spanRight;

    if(!bound_by_rect(x, y, 0, 0, tex->width - 1, tex->height - 1)) return;

    draw_prologue(&cur, tex, 0, 0, 1024, 1024, &hash_arg, sync_mode, primary, &payload);

    old_color = get_pixel_color(tex, x, y);

    if(cmp_color(old_color, cur.color)) return;

    emptyStack();

    if(!push(x, y, tex->width)) return;

    while(pop(&x, &y, tex->width))
    {    
        y1 = y;
        while(y1 >= 0 && cmp_color(old_color, get_pixel_color(tex, x, y1))) y1--;
        y1++;
        spanLeft = spanRight = false;
        while(y1 < tex->height  && cmp_color(old_color, get_pixel_color(tex, x, y1)) )
            {
                set_pixel_color_with_style(payload, tex, x, y1);

                if(!spanLeft && x > 0 && cmp_color(old_color, get_pixel_color(tex, x - 1, y1))) 
                    {
                        if(!push(x - 1, y1, tex->width)) return;
                        spanLeft = true;
                    }
                else if(spanLeft && x > 0 && !cmp_color(old_color, get_pixel_color(tex, x - 1, y1)))
                    {
                        spanLeft = false;
                    }


                if(!spanRight && x < tex->width && cmp_color(old_color,
                                                                 get_pixel_color(tex, x + 1, y1))) 
                    {
                        if(!push(x + 1, y1, tex->width)) return;
                        spanRight = true;
                    }

                else if(spanRight && x < tex->width && !cmp_color(old_color,
                                                                      get_pixel_color(tex, x + 1, y1)))
                    {
                        spanRight = false;
                    } 
                y1++;
            }
    }
   draw_epilogue(&cur, tex, primary);
}

Answer 1

我只是粗略地看了一眼，但好像你有一个边界换行在

if(!spanRight && x < tex->width && ...

´和

else if(spanRight && x < tex->width && ...

这些行应该是

   if(!spanRight && x < tex->width-1 && ...
   else if(spanRight && x < tex->width-1 && ...