Is there a working O(1)-space flood fill algorithm?

Question

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?

Answer 1

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.