我想要没有堆栈和递归的洪水填充

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

请注意，这不会检查是否触及数组的边缘。此外，它还假设您的数组元素是 int，并且您仅在图像中使用值 0 和 1。

Answer 2

你的任务没有多大意义。如果您有字体，您不想用洪水填充来填充它，而是直接将其渲染为填充多边形。如果不能可靠地给出良好的结果，则确定哪些部分在字体内和不在字体内，尤其是衬线字体。

填充多边形的典型原理图算法如下（不需要堆栈或递归），并且在某些条件下它也可以应用于位图（我会谈到这一点）：

对于每行（或列，无论适合什么 ）您的数据结构更好），在您所遵循的虚拟线和所有多边形线（边界）的每个交叉点处切换填充。

假设这个（可能是 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

问题是您必须能够判断像素已被填充（用未使用的颜色填充它）。而且，这会非常慢。

Answer 4

你基本上不能。您必须将这些信息存储在某个地方，因为您必须知道在完成当前部分后还可以从哪里开始填写。递归可以让你隐式地完成它。保留自己的堆栈可以让您明确地执行此操作，并可能节省一些费用。 Oli Charlesworth 通过保留与图片大小相同的数组做了一件可爱的事情，但这比递归或保留位置堆栈使用更多的内存。