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

Question

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

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

示例输入和输出(只需要红色矩形):

Sample input image. The red dot is the start pixel. The area to be filled is the cyan Z-tetromino that contains the dot http://www.finnw.me.uk/ffinput.png Sample output. Only the position/width/height of the red rectangle is significant http://www.finnw.me.uk/ffoutput.png

---

编辑:带有岛屿的示例 #2:
Example input with islands http://www.finnw.me.uk/ffinput2.png Example output http://www.finnw.me.uk/ffoutput2.png

示例#3:
Example of false island http://www.finnw.me.uk/ffinput3.png

---

编辑

抱歉，图像因硬盘故障而丢失。当我第一次发布这个时，SO 没有托管图像，所以我将它们保存在我自己的服务器上。

Answer 1

基本上您需要确定 biggestX、biggestY、smallestX 和 smallestY。

求真实边的右下角:

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

当您无法再向右+向下移动时，您需要检查以确保您没有被困在岛屿的一角。要检查这一点，您需要跟随整个边缘寻找向右+向下移动的机会。每次发生这种情况时，您都可以跟踪(最大 X、最大 Y、最小 X、最小 Y)，以防您真正拥有真正的优势。

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

如果您没有机会向右+向下走，并且您到达了起点，那么您就有了真正的优势。并且您已经计算了您的(最大 X、最大 Y、最小 X 和最小 Y)。