Fast way to get the bounding rectangle of a flood fill

views:

338

answers:

+4 Q:

Fast way to get the bounding rectangle of a flood fill

I need to perform a flood fill on a region of an image. However I do not actually need the resulting image, I only need to know the smallest rectangle containing all pixels that would be changed by the flood fill.

Is there a variant of a flood fill algorithm that can compute this rectangle more cheaply than doing a full flood fill?

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

Sample input image. The red dot is the start pixel. The area to be filled is the cyan Z-tetromino that contains the dot Sample output. Only the position/width/height of the red rectangle is significant

Edit: Example #2 with islands:
Example input with islands Example output

Example #3:
Example of false island

+2 A:

Basically you need to determine biggestX, biggestY, smallestX, and smallestY.

Find the bottom right corner of the real edge:

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

When you can't go right+down anymore, then you need to check to make sure you aren't stuck in a corner of an island. To check for this you need to follow around the entire edge looking for a chance to go more right+down. You can keep track of (biggestX, biggestY, smallestX, smallestY) every time this happens in case you actually have your real edge.

If you actually do have an island, you will eventually find a place following the edge that you can go more right+down.

If you don't have a chance to go more right+down, and you reach your starting point, then you have your actual edge. And you have calculated your (biggestX, biggestY, smallestX, and smallestY).

Brian R. Bondy 2010-02-14 13:38:55

Sorry, but this fails for the example image; It will return the *whole* input image, because one of the corners will touch one or more neighbouring shapes on each pass. That's why I chose that image as an example.

finnw 2010-02-14 14:25:32

I think you misunderstood my answer. You will visit EVERY pixel. "Continue to call this function until you have 0 neighbors of your color", although you for example stop calling the function on the right pixel, you will call it on the right pixel on all of the neighboring pixels. My method is not very efficient though since you will visit every pixel.

Brian R. Bondy 2010-02-14 14:55:43

I updated my answer to a more efficient method.

Brian R. Bondy 2010-02-14 15:13:47

How can you detect whether the edge you hit belongs to an island?

finnw 2010-02-14 15:15:23

You detect whether it is an island or not by seeing if any point on the edge of what you hit has a more bottom+right spot (which is not bounding the edge) than what you currently have when you started the edge tracing.

Brian R. Bondy 2010-02-14 15:21:27

I think that will work, as long as you trace the whole edge before deciding whether it is an island (if you stop part-way through, it might lead to an infinite loop in some cases, e.g. a spiral-shaped island.)

finnw 2010-02-14 15:29:37

finnw: I'm not sure it will lead to an infinite loop (I can't think of an example that would with a spiral), but I think it will be more efficient sometimes (especially spiral) when tracing the whole island to know where the best spot is to continue your down+right descent.

Brian R. Bondy 2010-02-14 15:38:59

See example #3. The spiral is not an island, but when you reach the yellow dot it appears that you can move further down/right. You cannot be sure until you have traced the whole edge (and you know whether that pixel has the maximum x and/or y coordinate for that edge.)

finnw 2010-02-14 15:42:56

@finnw: Ya I was thinking more along the lines that once you reach the yellow dot, you would go more down+right right away, you may hit the same island you determined was not an island earlier, but you need to re-evaluate if it is an island each time you hit a bottom+right corner again.

Brian R. Bondy 2010-02-14 15:46:34

+1 A:

One possible method would be to go as far (left,up,down.right) as you can from your starting point, then follow the edge clock-wise or counter-clockwise until you return to your first edge-point. Keep track of min(X,y) and max(X,Y) as you traverse the edge.

That ought to let you look at fewer pixels, unless you have rather odd shapes to fill.

Vatine 2010-02-14 14:04:21

Interesting, but I think it will need modifying to work with my 2nd example, otherwise it will return a box containing one or more islands but not the whole region.

finnw 2010-02-14 14:51:42

There may be thinkable shapes where it happens, but in the specific case of the second example, it should hit an "island", then turn and go to the border and then follow the border.

Vatine 2010-02-15 14:44:24

ansaurus

tags:

views:

answers:

Fast way to get the bounding rectangle of a flood fill

related questions