1
$\begingroup$

This is a purely theoretical question: among the known flood fill algorithms, there is one which does not require any dynamically-sized data structures, explicit or implicit: the so-called Walk-based filling, expressed there in structured English, e.g.

...
while front-pixel is empty do
    move forward
end while

jump to START

MAIN LOOP:
    move forward
    if right-pixel is inside then
        if backtrack is true and findloop is false and either front-pixel or left-pixel is inside then
            set findloop to true
        end if
        turn right
PAINT:
        move forward
    end if
START:
    set count to number of non-diagonally adjacent pixels filled (front/back/left/right ONLY)
...

An attempt to implement that algorithm has revealed that while it is quite clever, it is not robust. For example, given a herringbone pattern,

 *********
 **   *  *
 *  *   **
 * *...* *
 *  .*.. *
 ** ..*. *
 *  *...**
 * *   * *
 *********

if the starting point is one of the locations marked with a period, the algorithm goes into an infinite loop.

Is there a known robust O(1)-space deterministic (apparently, it has to be mentioned) flood fill algorithm? What would be its time complexity?

$\endgroup$
13
  • $\begingroup$ What is your definition of "robust" and how does it differ from correctness on all possible inputs? $\endgroup$
    – D.W.
    Jul 29 at 3:46
  • $\begingroup$ @D.W. In the context, I've used "it is not robust" in the sense "it cannot cope with some of the inputs" (as opposed to "it is not accurate" if the algorithm always terminates successfully, but does not always produce the correct result). I meant to ask, is there any O(1)-space algorithm which is correct on all possible inputs, but the question if there exists a fix of the "Walk-based filling" algorithm, is also of interest. $\endgroup$
    – Leo B.
    Jul 29 at 6:49
  • 1
    $\begingroup$ Don't confuse the algorithm principle (possibly expressed by a textual description or informal pseudocode) and a concrete program that implements it. Bugs are not excluded. Also check if your region is four-connected. $\endgroup$ Jul 29 at 12:35
  • $\begingroup$ @YvesDaoust Unless there is a readily available implementation of the algorithm in a programming language, which is verifiably free from the bug, the question stands. No matter how the region looks like, the algorithm must not loop forever. $\endgroup$
    – Leo B.
    Jul 29 at 20:36
  • $\begingroup$ You are wrong. If the algorithms mandates a four-connected region, you must not run it on a region that is not, or you get UB. $\endgroup$ Jul 29 at 20:41

1 Answer 1

0
$\begingroup$

This is an algorithm I came up with, so I'm not sure that is was known before. It is essentially a modification of the walk-based filling method that you mentioned. I'll give a high-level description, with possibly more details to come later.

EDIT...Please see the edit below


The idea is that we will possibly divide the original region to fill into at most 2 regions. We initially start to go clockwise around the initial fill point, although we could have just as easily gone counter clockwise. (If the original fill location is surrounded by filled pixels, we are done.) It also doesn't matter if we go to the right, left, up, or down. The main idea is that we start circling around going clockwise. So again, we are proceeding around the original fill pixel:

**********
*        *
*  432   *
*  501   *
*  6     *
*        *
**********

Here I numbered the starting position with a 0 and numbered the next selections in increasing order.

The trick is that the algorithm will most likely have to cut itself off:

**********
*    3   *
*  **21  *
*  ***0  *

When it gets to position 3, notice that we've split the original region into 2 regions that both need to be filled. So we will mark the split with an "o", and continue, knowing that we now need to fill 2 regions:

**********
*  543o  *
*  **21  *
*  ***0  *

Eventually, we will either come to another split, or we will completely fill one of the regions (in this case, the region on the left).

If we completely fill one of the regions, we can then continue to fill, starting at the point we marked "o". Otherwise, we come to another split. The idea is to record the last few positions we were at as we go along. Now that we've come to another split, we backtrack to where there was no second split, and mark this location as the next location to work on. Then, we go back to the first marked location, and continue on.

The essential idea is that we go back and forth between the 2 regions, making sure that we never create a third region to fill.


EDIT

The idea is instead to continually circle around clockwise, trying to fill locations whenever they do not divide the current region into 2 regions.

So, for example, consider the following image, where we start at "0" and fill in the numbers in order:

**********
*        *
*  456   *
*  .01   *
***.32   *
*        *
**********

Here we skip the locations marked with a period, because they have the potential of splitting the region into two regions. We take care to proceed along the inside wall. So to continue with this example, we would fill:

**********
*        *
* a4567  *
* ..018  *
***.329  *
*  ....  *
**********

Note that once we get to 9, we stay to the inside, proceeding clockwise, over the periods, and skip some more periods. We do not fill the periods. We eventually arrive at "a" where we again fill.

There's another thing that we have to do. Proceeding again as in our example, we fill:

**********
* ...... *
* a4567b *
* ..018c *
***.329d *
*  ....  *
**********

Here we've skipped and then filled "b", "c", and "d". Next we come to a location that we will not fill. The logic here is that any time we come to a location that we do not fill, we record that position. Then, if we continue cycling through the unfilled positions and we come to this recorded or marked position, we know that the area surrounding area is only one pixel wide.

We now continue clockwise around the filled region, not filling anything, but seeing if there are any forks or branches where there is more than one direction to fill. If there is, we:

  1. Go through the branch, away from the current region we were cycling through, still without filling anything.
  2. We mark or record where we start in this new region.
  3. Cycle clockwise in this new region, seeing if there is anything to fill.
  4. If there is, and it doesn't split the region, we fill it.
  5. Finally, we cycle through until we again arrive at the marked region.
  6. We mark the other branch, so that we will come back to it.
  7. We then proceed to fill the original fork we took, so that it does not split the region into two regions.
  8. We go back to the second region we marked, which is the other fork.
  9. Repeat until there are no more forks, then fill the rest.

If there were no forks around our recently filled region, we fill the remaining pixels and we are done.

This procedure should ensure that there are never more than 2 regions to fill.


This should work. Of course, there's a lot of details to keep track of.

$\endgroup$
2
  • $\begingroup$ Superficially, this looks promising, as it is more or less the walk-based algorithm with a "bird's eye" view. However, the author(s) of the walk-based algorithm likely believed that their algorithm should work in all cases, which proved to be wrong. Thus, implementation and testing are required to validate your new algorithm. $\endgroup$
    – Leo B.
    yesterday
  • $\begingroup$ @LeoB.: Programming it is the tough part. I'm trying to get a bird's eye view of the problem. I keep thinking that the main concern is when there is a branch or fork. I think that if we can handle all of the cases when this happens, we may have a good shot at a better proof. $\endgroup$
    – Matt Groff
    yesterday

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.