快速获取泛洪填充的边界矩形的方法

Question

4

我需要对图像的某个区域执行泛洪填充。但是，我实际上并不需要生成结果图像，我只需要知道包含所有受泛洪填充影响的像素的最小矩形。

是否有一种泛洪填充算法的变体可以比完整的泛洪填充更便宜地计算出此矩形？

示例输入和输出（仅需要红色矩形）：

编辑

很抱歉，由于硬盘故障，图片丢失了。当我首次发布这篇文章时，SO并没有提供图片托管服务，所以我将它们放在自己的服务器上。

- finnw

1

我觉得这类问题非常有趣。我们可以通过观察立即确定边界矩形，但很难确定一个算法。 - Brian R. Bondy

2个回答

1

一个可能的方法是从起点尽可能向左、上、下、右四个方向走，然后顺时针或逆时针沿着边缘走直到回到第一个边缘点。在遍历边缘时跟踪最小值(X,Y)和最大值(X,Y)。

这应该能让您查看更少的像素，除非您有相当奇怪的形状需要填充。

- Vatine

有趣，但我认为需要修改以适应我的第二个示例，否则它将返回一个包含一个或多个岛屿而不是整个区域的方框。 - finnw

可能有一些可以想象的形状，但是在第二个例子中，它应该碰到一个“岛屿”，然后转向并前往边界，然后沿着边界走。 - Vatine

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Brian R. Bondy · Accepted Answer

基本上你需要确定最大的X值，最大的Y值，最小的X值和最小的Y值。

找到真正边缘的右下角：

您可以通过在您的颜色内尽可能向右+向下移动来实现此目标。

当您无法再向右+向下移动时，您需要检查是否卡在岛屿的角落里。为了检查这一点，您需要沿着整个边缘寻找机会向右+向下移动。每次发生这种情况时，您可以跟踪（biggestX、biggestY、smallestX、smallestY），以防您实际上拥有真正的边缘。

如果您确实有一个岛屿，您最终会找到一个沿着边缘走的地方，可以更多地向右+向下移动。

如果您没有机会向右+向下移动，并且到达起始点，则您已经找到了实际边缘。并且您已经计算出了您的（biggestX、biggestY、smallestX和smallestY）。