我希望Flood Fill不使用堆栈和递归

Question

我想知道如何在数组上应用泛洪填充，我的数组是二维的，它包含了几次新的罗马字体字母边界。边界线上有1，里面和外面都是0，我想把所有的1都填进去，而只在里面填0。但我需要一个不需要更多内存的逻辑。因此要避免递归和堆栈或队列

Answer 1

我通常不会为别人做作业，但我喜欢挑战：

int c = -1;
while (c < 0)
{    
    /* Store breadcrumb trail, look to carry on */
    a[x][y] = c--;
    if (!hunt(0))
    {
        /* Nowhere to go, so back-track by looking for breadcrumb */
        a[x][y] = 1;
        c += 2;
        hunt(c);
    }
}

bool_t hunt(int v)
{
    if (a[x-1][y] == v)  { x--; return TRUE; }
    if (a[x+1][y] == v)  { x++; return TRUE; }
    if (a[x][y-1] == v)  { y--; return TRUE; }
    if (a[x][y+1] == v)  { y++; return TRUE; }
    return FALSE;
}

请注意，这不会检查命中数组的边缘。此外，它还假设您的数组元素是例如ints，并且您在映像中仅使用了值0和1。

Answer 2

你的任务没有多大意义。如果你有一个字体，你不想用泛洪填充来填充它，而是直接将它渲染为填充的多边形。确定哪些部分在字体中和哪些部分在字体之外，特别是对于serif字体，如果不能可靠地给出好的结果的话。

填充多边形的典型示意图算法是这样的(不需要堆栈或递归)，并且在某些条件下也可以应用于位图(我将介绍)：

对于每一行(或列，只要更适合您的数据结构)，切换您正在跟踪的虚拟线和所有多边形线(边界)的每个交叉点处的填充。

假设(可能是O字符的中间行)：

00010010001001000
   ^  ^   ^  ^
   |  |   |  stop
   |  |   start
   |  stop
   start

结果：

00011110001111000

这也适用于位图，但只有当您实际上总是有两个边界的开始和停止。

Answer 3

function LowMemFloodFill(pixel)
  FillPixel(pixel)
  Do
    didFill = false
    For each pixel
      If current pixel has been filled
        For each adjacent pixel
          If adjacent has not been filled
            FillPixel(adjacent)
            didFill = true
          End
        End
      End
    End
  While didFill
End

需要注意的是，您必须能够分辨出像素已被填充(用未使用的颜色填充它)。而且，这将是非常慢的。