algorithm - 获取洪水填充的边界矩形的快速方法

Question

我需要对图像的某个区域进行填充。但是我实际上并不需要生成的图像，我只需要知道包含将被洪水填充更改的所有像素的最小矩形。

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

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

样本输入图像。红点是起始像素。要填充的区域是青色 Z-tetromino，其中包含点 http://www.finnw.me.uk/ffinput.png示例输出。只有红色矩形的位置/宽度/高度很重要 http://www.finnw.me.uk/ffoutput.png

---

编辑：带有岛屿的示例#2：带有岛屿的
示例输入 http://www.finnw.me.uk/ffinput2.png 示例输出 http://www.finnw.me.uk/ffoutput2.png

示例 #3：
假岛示例 http://www.finnw.me.uk/ffinput3.png

---

编辑

抱歉，由于硬盘故障，图像丢失了。当我第一次发布此内容时，SO 没有托管图像，因此我将它们保存在自己的服务器上。

Answer 1

基本上你需要确定最大X、最大Y、最小X和最小Y。

找到真实边缘的右下角：

您可以通过在您的颜色内尽可能向右+向下移动来做到这一点。

当您不能再向右+向下时，您需要检查以确保您没有被困在岛屿的角落。要检查这一点，您需要沿着整个边缘寻找机会向右+向下移动。每次发生这种情况时，您都可以跟踪 (biggestX, largeY, minimumX, minimumY)，以防您真正拥有真正的优势。

如果你真的有一个岛，你最终会在边缘找到一个可以向右+向下走的地方。

如果您没有机会向右+向下走，并且到达起点，那么您就有了真正的优势。你已经计算出你的（biggestX、biggestY、smallestX 和 minimumY）。

Answer 2

一种可能的方法是从起点尽可能远（左、上、下、右），然后顺时针或逆时针跟随边缘，直到返回第一个边缘点。遍历边缘时跟踪 min(X,y) 和 max(X,Y)。

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