边界追踪填充
5.00/5 (1投票)
将边界追踪算法与一些填充算法（因为它们使用了堆栈或递归）进行基准测试
引言
当我还在 VB6 中玩弄曼德勃罗集时，我遇到了快速填充集合的问题。我研究了填充算法，偶然发现了 Michael R. Ganss 的边界追踪算法。因为我遇到的填充算法都使用了堆栈或递归，所以我决定将边界追踪算法与其中一些算法进行基准测试。我重写了它，使其代码更加清晰。事实证明它更快，并且对资源的负载很小。
背景
我通常使用 Visual Basic 编程，但这次决定使用 VC10 进行基准测试。我使用了一个应用程序（floodfill.cpp），由 Lode VandeVenne 编写，用于基准测试一些填充算法，并添加了我版本的边界追踪算法。
原始算法的作者是 Michael R. Ganss。这是他的解释：
边界追踪生成方法，追踪单色区域的轮廓并填充它们。我们从像素 (x,y) 开始向右移动，并将“墙壁”保持在我们左侧，直到回到起点。对于每个像素，下一个访问的像素将如下计算：
- 检查左侧像素（根据当前方向查看，即如果当前方向是向右，则左侧像素是其上方的像素）。如果它属于墙壁（即，屏幕外或与我们追踪的颜色不同），则转到 b）。如果不是，则它是下一个像素。
- 对正前方像素执行相同的操作。如果它不属于墙壁，则移至那里。
- 右侧像素同理。如果该像素也属于墙壁，则向后移动一个像素。当我们回到起点时，我们将再次追踪边界。现在，每当我们向上移动时，我们都会在当前像素的右侧绘制像素，直到遇到墙壁。
一个基于相同原理但会访问每个像素的算法，在此链接中有描述（完全非递归，但速度较慢）。我重写了原始算法（用于曼德勃罗集）以执行填充。
Using the Code
源代码包含几种填充算法，包括四种版本的边界追踪算法，其中边界追踪算法表现最佳。BoundaryTrace 的想法是通过尽可能向左移动来追踪要填充区域的轮廓，将不应填充的像素“墙壁”保持在（相对）左侧。相同的算法用于追踪迷宫。在追踪完完整的边界、用填充颜色填充所有边界像素并再次到达起点后，会进行第二次追踪，同时填充边界之间的区域。
BoundaryTrace 函数展示了基本算法，但它存在局限性：如果填充区域在边缘处只有 1 像素宽，它会导致填充不完整；如果填充区域中有“孤岛”，它也会导致填充不完整。BoundaryTrace2 解决了这些问题，对于“孤岛”，它会调用 BoundaryTrace2a（如果需要则递归：如果多个“孤岛”堆叠在一起），其中墙壁保持在右侧，从而绕过孤岛的边缘。
BoundaryTrace3 与 BoundaryTrace2 执行相同操作，但代码经过优化以提高性能——这带来了轻微的改进，但代码的透明度大大降低。
BoundaryTrace4 类似于 BoundaryTrace2，但它使用堆栈，收集用于填充区域的所有边界点，通过向下移动直到遇到一个既不是填充颜色也不是原始颜色的像素——换句话说，我们遇到了相反的边界。这样就不需要第二次追踪了。当然，我也必须使用 BoundaryTrace3 代码测试了堆栈选项。有时它更快，但并非总是如此。所有这些代码都在源下载文件中。在此页面上，我将基本算法作为代码片段提供。
如果您正在寻找更快的 FloodFill，欢迎使用此代码。
初始化
void BoundaryTrace(int x, int y, Uint32 fillcolor, Uint32 oldcolor)
{
//we start at screen position x, y where a MouseClick event happened
// no need to fill if fillcolor is oldcolor
if(fillcolor == oldcolor) return;
// storage for 4 points
int PtX[4];
int PtY[4];
//h = height, w = width
int t = h-1;
int q = w-1;
//find a starting point (boundary spot) by going down until we hit a different color
while(screenBuffer[x][y]==oldcolor)
{
y++;
if (y > t)
break;
}
y--;
bool IsTraced = FALSE;
// The direction we are going (0 = Right, 1 = Down, 2 = Left, 3 = Up), select one to start
int iDir =2;
int Y3;
//save the starting point
int sX = x;
int sY = y;
bool onEdge;
第一个循环
第一个循环在回到我们的起点 (sX, sY) 时终止。我们在第一个循环中执行两项操作：
- 检查我们是否位于屏幕边缘，如果是，则沿着边缘移动。
- 如果不在边缘，则计算当前位置的 4 个邻近点。
所以，首先检查边缘。
while (!IsTraced)
{ // in case we are at the edge of the screen, trace the edge
onEdge = FALSE;
if (x==0) //edge
{
while ((screenBuffer[x][y-1]==oldcolor || screenBuffer[x][y-1]==fillcolor) && y>0)
{
y--;
screenBuffer[x][y] = fillcolor;
}
iDir = 0;
}
if (y==0) //edge
{
while ((screenBuffer[x+1][y]==oldcolor || screenBuffer[x+1][y]==fillcolor) && x<q)
{
x++;
screenBuffer[x][y] = fillcolor;
}
iDir = 1;
}
if (x==q) //edge
{
while ((screenBuffer[x][y+1]==oldcolor || screenBuffer[x][y+1]==fillcolor) && y<t)
{
y++;
screenBuffer[x][y] = fillcolor;
}
iDir = 2;
}
if (y==t) //edge
{
while ((screenBuffer[x-1][y]==oldcolor || screenBuffer[x-1][y]==fillcolor) && x>0)
{
x--;
screenBuffer[x][y] = fillcolor;
//we might encounter the starting point here,
//because we defined the starting point sX, sY at the bottom of the fill area
if (sX==x && sY==y)
{
IsTraced = TRUE;
onEdge = TRUE;
break;
}
}
iDir = 3;
if (!IsTraced && x==0) onEdge = TRUE;
}
如果不在边缘，我们计算 4 个邻近点，它们的检查顺序取决于方向 (iDir)（始终是相对于方向的左侧，然后是正前方，然后是右侧，最后是后退）。
if (!onEdge) //trace boundary
{
switch (iDir)
{
case 0: //going Right
PtX[0] = x;
PtY[0] = y - 1;
PtX[1] = x + 1;
PtY[1] = y;
PtX[2] = x;
PtY[2] = y + 1;
PtX[3] = x - 1;
PtY[3] = y;
break;
case 1: //going Down
PtX[0] = x + 1;
PtY[0] = y;
PtX[1] = x;
PtY[1] = y + 1;
PtX[2] = x - 1;
PtY[2] = y;
PtX[3] = x;
PtY[3] = y - 1;
break;
case 2: //going Left
PtX[0] = x;
PtY[0] = y + 1;
PtX[1] = x - 1;
PtY[1] = y;
PtX[2] = x;
PtY[2] = y - 1;
PtX[3] = x + 1;
PtY[3] = y;
break;
case 3: //going Up
PtX[0] = x - 1;
PtY[0] = y;
PtX[1] = x;
PtY[1] = y - 1;
PtX[2] = x + 1;
PtY[2] = y;
PtX[3] = x;
PtY[3] = y + 1;
break;
}
//proceed to next pixel on the left (relative to Direction) and change Direction
if (screenBuffer[PtX[0]][PtY[0]]==oldcolor ||
screenBuffer[PtX[0]][PtY[0]]==fillcolor)
{
x = PtX[0];
y = PtY[0];
iDir = (iDir + 3)%4;
}
else
{
//if we did hit the wall proceed straight ahead (relative to direction)
if (screenBuffer[PtX[1]][PtY[1]]==oldcolor ||
screenBuffer[PtX[1]][PtY[1]]==fillcolor)
{
x = PtX[1];
y = PtY[1];
}
else
{
// if we did hit the wall go right (relative to Direction)
// and change Direction
if (screenBuffer[PtX[2]][PtY[2]]==oldcolor ||
screenBuffer[PtX[2]][PtY[2]]==fillcolor)
{
x = PtX[2];
y = PtY[2];
iDir = (iDir + 1)%4;
}
else
// we hit the wall in all directions so we go back to the previous pixel
{
x = PtX[3];
y = PtY[3];
iDir = (iDir + 2)%4;
}
}
}
screenBuffer[x][y] = fillcolor;
if (sX==x && sY==y)
// we are back at the starting point
IsTraced = TRUE;
}
}
因此，在第一个循环中，我们已经追踪了要填充区域的完整边界，并将遇到的边界像素设置为 fillcolor 值。
现在我们将再次追踪边界，这次我们将填充该区域：每次我们向右（即我们位于填充区域的顶部）时，我们将从当前像素向下延伸，直到到达填充区域底部的相对边界，并在途中用 fillcolor 填充像素。我们在 y = 0（如果我们位于顶部边缘）或 iDir = 0（=向右）的情况下填充。
// trace the boundary once again, this time filling
IsTraced = FALSE;
iDir = 2;
while (!IsTraced)
{
onEdge = FALSE;
if (x==0)
{
while (screenBuffer[x][y-1]==fillcolor && y>0) y--;
iDir = 0;
}
if (y==0)
{
while ( screenBuffer[x+1][y]==fillcolor && x<q)
{
Y3 = y ;
//fill 1 line going down until we hit the opposite wall
while (screenBuffer[x][Y3] ==oldcolor || screenBuffer[x][Y3]==fillcolor)
{
screenBuffer[x][Y3]=fillcolor;
Y3++;
if (Y3 == t)
break;
}
x++;
}
Y3 = y ;
//fill last line going down
while (screenBuffer[x][Y3] ==oldcolor || screenBuffer[x][Y3]==fillcolor)
{
screenBuffer[x][Y3]=fillcolor;
Y3++;
if (Y3 == t)
break;
}
iDir = 1;
}
if (x==q)
{
while (screenBuffer[x][y+1]==fillcolor && y<t) y++;
iDir = 2;
}
if (y==t)
{
while (screenBuffer[x-1][y]==fillcolor && x>0)
{
x--;
if (sX==x && sY==y)
{
IsTraced = TRUE;
onEdge = TRUE;
break;
}
}
iDir = 3;
if (!IsTraced && x==0) onEdge = TRUE;
}
if (!onEdge)
{
switch (iDir)
{
case 0:
PtX[0] = x;
PtY[0] = y - 1;
PtX[1] = x + 1;
PtY[1] = y;
PtX[2] = x;
PtY[2] = y + 1;
PtX[3] = x - 1;
PtY[3] = y;
Y3 = y ;
//fill 1 line going down until we hit the opposite wall
while (screenBuffer[x][Y3] ==oldcolor || screenBuffer[x][Y3]==fillcolor)
{
screenBuffer[x][Y3]=fillcolor;
Y3++;
if (Y3 == t)
break;
}
break;
case 1:
PtX[0] = x + 1;
PtY[0] = y;
PtX[1] = x;
PtY[1] = y + 1;
PtX[2] = x - 1;
PtY[2] = y;
PtX[3] = x;
PtY[3] = y - 1;
break;
case 2:
PtX[0] = x;
PtY[0] = y + 1;
PtX[1] = x - 1;
PtY[1] = y;
PtX[2] = x;
PtY[2] = y - 1;
PtX[3] = x + 1;
PtY[3] = y;
break;
case 3:
PtX[0] = x - 1;
PtY[0] = y;
PtX[1] = x;
PtY[1] = y - 1;
PtX[2] = x + 1;
PtY[2] = y;
PtX[3] = x;
PtY[3] = y + 1;
break;
}
if (screenBuffer[PtX[0]][PtY[0]]==fillcolor)
{
x = PtX[0];
y = PtY[0];
iDir = (iDir + 3)%4;
}
else
{
if (screenBuffer[PtX[1]][PtY[1]]==fillcolor)
{
x = PtX[1];
y = PtY[1];
}
else
{
if (screenBuffer[PtX[2]][PtY[2]]==fillcolor)
{
x = PtX[2];
y = PtY[2];
iDir = (iDir + 1)%4;
}
else
{
x = PtX[3];
y = PtY[3];
iDir = (iDir + 2)%4;
}
}
}
if (sX==x && sY==y) IsTraced = TRUE;
}
}
}
此代码存在一些局限性：
- 如果填充区域在边缘处只有 1 像素宽，它会过早找到起点。
- 如果填充区域中有“孤岛”，它会导致填充不完整。
因此有了 BoundaryTrace2 和 BoundaryTrace3（使用递归处理“孤岛”）。BoundaryTrace2 是紧凑的代码，而 BoundaryTrace3 是为优化性能而编写的，牺牲了代码的透明度。
在 BoundaryTrace4 和 BoundaryTrace5 中，我们使用堆栈来加快速度（将填充区域顶部的像素放入堆栈，这样就不需要第二次追踪了）。实际上，堆栈并不总是表现更好。尽管存在差异，但所有函数的底层算法都与上述相同。这些函数包含在源下载文件中。
关注点
我非常享受（重）写这段代码的过程，尽管有时在用 VB 工作了很长时间后，我不得不重新适应 VC10。虽然这个算法不是我的原创，但我从未见过它用于填充。
如何使用演示：使用鼠标左键绘制一个形状（确保其边界不中断）。然后用鼠标右键单击要填充的区域内部。要执行基准测试，请在此之后按空格键。时间以毫秒为单位（执行 600 次迭代）。
历史
- 2012 年 9 月 18 日：初始版本