洪水填埋场边界矩形的快速求取方法

Question

我需要对图像的一个区域进行洪水填充。然而，我实际上不需要结果的图像，我只需要知道最小的矩形，包含所有的像素将被洪水淹没。

是否有一个变体的洪水填充算法，可以计算这个矩形比做一个完整的洪水填充更便宜？

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

样本输入图像红点是起始像素。要填充的区域是包含点http://www.finnw.me.uk/ffinput.png的青色Z-四角体。样本输出只有红色矩形的位置/宽度/高度是有效的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实例

编辑

抱歉，硬盘故障导致图像丢失。当我第一次发布这篇文章时，因为没有托管图像，所以我把它们保存在自己的服务器上。

Answer 1

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

找到真实边的右下角：

您可以通过在您的颜色中尽可能地使用right+down来做到这一点。

当你不能再去right+down，那么你需要检查，以确保你没有被困在一个岛屿的角落。要检查这一点，您需要在整个边缘周围寻找一个机会去更多的right+down。每次发生这种情况时，您都可以跟踪(biggestX、biggestY、smallestX、smallestY)，以防您真正拥有优势。

如果你真的有一个岛，你最终会找到一个地方，沿着边缘，你可以去更多的right+down。

如果你没有机会去更多的right+down，并且你到达了你的起点，那么你就有了你的实际优势。并且计算了你的(biggestX，biggestY，smallestX和smallestY)。

Answer 2

一种可能的方法是从你的起点尽可能走远(左，上，down.right)，然后沿着边时钟方向或逆时针方向走，直到你回到你的第一个边缘点。跟踪最小(X，y)和最大(X，Y)，当你穿越边缘。

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