Quick way to get fill bounding box

Question

I need to fill a fill in the image area. However, I do not need the resulting image, I only need to know the smallest rectangle containing all the pixels that will be changed by the fill fill.

Is there a variant of the fill filling algorithm that can calculate this rectangle cheaper than filling a full bay?

Example input and output (only a red rectangle is required):

An example of an input image. The red dot is the starting pixel. The area to be filled is a blue Z-tetromino containing the dot http://www.finnw.me.uk/ffinput.png Example output. So, only the position / width / height of the red rectangle is http://www.finnw.me.uk/ffoutput.png

---

Edit: Example # 2 with islands:
Example input with islands http://www.finnw.me.uk/ffinput2.png Example output http://www.finnw.me.uk/ffoutput2.png

Example 3:
Example False Island http://www.finnw.me.uk/ffinput3.png

---

Edit

Sorry, images were lost when the hard drive crashed. When I first posted this, there were no images in SO, so I saved them on my own server.

Answer 1

Basically you need to define mostX, mostY, smallestX and smallestY.

Find the bottom right corner of the real edge:

You can do this by going as far right as possible + down inside your color.

If you can no longer go right + down, you need to check to make sure that you are not stuck in the corner of the island. To make sure of this, you need to follow around the edge, looking for a chance to go even more to the right + down. You can track (largest, largest, smallest, smallest) every time this happens, if you really have a real edge.

If you actually have an island, you will eventually find a place beyond the edge that you can go further on the right + down.

If you have no chance to go even further + down, and you will reach your starting point, then you have a real edge. And you calculated yours (the largest, largest, smallest and smallest).

Answer 2

One possible way would be to go as far as possible (left, up, down. Right), as you can, starting from the starting point, and then follow the edge clockwise or counterclockwise until you return to your first edge point . Keep track of the minimum (X, y) and max (X, Y) while passing the edge.

This should allow you to look at fewer pixels if you don't have some rather strange shapes to fill in.