The algorithm uses about half a byte per pixel and saves the path it follows. That kind of implies that the stack is still there and present, it’s just bounded to the number of pixels, and could actually be modified to just use a bounded area of the heap. But conceptually it’s easier to follow the way the paper was written. Neat.
In a sense it uses half a byte per pixel, but Nils M Holm's suggested implementation is to reserve 16 colors for the flood-fill algorithm, because you don't need to remember the color of the pixels you're flood-filling, so you can overwrite them with the flood-fill algorithm's state. The path is saved in those same 16 colors. This reduces your available color space, assuming 8-bit color, from 256 colors to 240 colors, which means you get 7.91-bit color instead of 8-bit color. So it actually only uses 0.09 bits per pixel, which at 1024×768 is 9154 bytes.
If you were to instead use a bounded area of the heap with 4 bits per pixel, as you are suggesting, your bound would be 393216 bytes.
However, it's not totally clear that that's the right way to account for it, because if you have a 256-color image that you have to reduce to 240 colors to have space for this algorithm, there isn't an obvious way to get back the lost colors by storing 9154 bytes somewhere else. You might be able to do something like pick the least popular 16 colors from the image (which occupy a maximum of 49152 pixels and usually less), store a bitmap telling where they were (98304 bytes), store the colors of the marked pixels into a 24576-byte array, replace them with some neutral color, run the flood fill, and then restore the colors. But, while that uses significantly less than 393216 bytes, it still uses a lot more than 9154 bytes, and it's probably pretty slow on the kind of computer where you'd be trying to do something like this.
At the other extreme, if your 256-color image actually only used the 216 "web-safe" colors (#000, #003, #006, ... #030, #033, etc.), you'd already have 16 leftover colors available. And freeing up 16 colors on a 16-bit or 24-bit TrueColor display would damage the image quality only imperceptibly.
I remember Mario Paint on Super Nintendo visibly flood-filling an area, but a computer that paints in modern image formats is probably not going to mind temporary allocation of a few hundred K. There are some fun opportunities to optimize, though, like checking a cache line of pixels at a time, or maybe tiling the image in 16-pixel squares using the same algorithm, and then cleaning up the edges.
The author of the submitted article has written about working in constrained environments. The algorithm he describes would be suitable for that kind of environment, where a few hundred K may not be available, or not without jumping through hoops to make it available.
https://t3x.org/#wyorc - One example, this is a book on writing a compiler targeting Z80 processors.
The pixels are effectively being turned into a linked list using the special values as ‘pointers’. This list is used as a stack, and the current position is the stack pointer.
I don’t think they explain the backtracking part very well, and they should have used an example that fills a non-rectangular area so it actually demonstrates the whole algorithm.
It’s a neat trick if you have spare values to use as markers, though. :)
To find connected regions on a map. I could probably have been smarter about the initial generation and connected things as they were generated (but that has only just occurred to me. Worth a go, I suppose.)
What I mean could be described that way, but I'm not sure if you mean the same thing. Just in case, I elicited an implementation from Opus 5.5. I have carefully verified that this implementation implements what I mean: http://canonical.org/~kragen/sw/union-find-components.html
I also wrote a floodfill a while ago! We have a mapping app, and our imagery provider returns half-filled tiles at the edge of their coverage. And annoyingly, they don't have any metadata within the tile itself that indicates the coverage. They just return black pixels for a part of the tile.
So I needed a way to detect that, and doing a floodfill from the edge of the image turned out to be the easiest way.
How does this deal with one pixel gaps? The algorithm can enter it just fine but there's no space to go back out again, and there doesn't seem to be a system for backtracking, unless I've misunderstood the algorithm
It backtracks using the origin direction. As it traces back to the original starting pixel, before filling the current pixel it attempts to scan the remaining directions for each pixel (which may be none). If those lead to further pixels needing to be filled it'll start going forward again, and eventually hit a dead end and trace back to the branch point and continue to scan around it, eventually discovering is itself a dead end and go to its own predecessor.
Basically, a pixel will go through states like:
(U,R) ;; came from up, went right
(U,D) ;; came from up, went down
(U,L) ;; came from up, went left
(U,U) ;; came from up, went up
Each of the neighboring pixels will be checked (that last one is superfluous and could be skipped for efficiency). Once all have been checked the pixel will be filled, and the current pixel will be set by using its predecessor direction.
What's the utility of this? It's arguably still using a stack, just encoded in the original data structure itself. If your original data structure somehow uses colors but is also fine with the algorithm overwriting with its own colors, I guess it works? But those are very unusual preconditions. For any real world scenario I can imagine, I feel like there's a better solution.
If the colors in your original data are important, then you can't really just overwrite them and/or assume that the algorithm can use its own colors. You're going to have to add a stack.
If your original data doesn't have colors, adding a stack is better than integrating metadata into the original data structure.
If for some reason your original data has colors but they aren't considered important, then just remove the colors and add a stack.
If your concern is about dynamic memory, preallocate static memory equal to the size of the original data structure.
Constant memory usage. It uses a small amount of additional memory (tracking the current pixel, pixel value, and a couple temp variables used for calculations) over the image itself making it a very low overhead algorithm. You can basically get away with 5 more variables, 20 more bytes if they're all 4-byte values, using this approach compared to the much greater memory needs of a stack-based approach (either a stack data structure or recursive). And actually just 4 variables since the D and P variables don't overlap in lifetime.
EDIT: Light editing of the above for grammar and clarity.
But that's only assuming that your original data structure already has space for the algorithm to store metadata. If there's space that can be manipulated freely to store metadata, can't you just remove that space to save memory, and then use the extra space for a stack?
Another option if you find yourself with this problem (flood fill, no recursion) is union find/connected components. Like the algorithm proposed in the article, you still need to store O(N) things, and runtime is still O(N).
The algorithm uses about half a byte per pixel and saves the path it follows. That kind of implies that the stack is still there and present, it’s just bounded to the number of pixels, and could actually be modified to just use a bounded area of the heap. But conceptually it’s easier to follow the way the paper was written. Neat.
In a sense it uses half a byte per pixel, but Nils M Holm's suggested implementation is to reserve 16 colors for the flood-fill algorithm, because you don't need to remember the color of the pixels you're flood-filling, so you can overwrite them with the flood-fill algorithm's state. The path is saved in those same 16 colors. This reduces your available color space, assuming 8-bit color, from 256 colors to 240 colors, which means you get 7.91-bit color instead of 8-bit color. So it actually only uses 0.09 bits per pixel, which at 1024×768 is 9154 bytes.
If you were to instead use a bounded area of the heap with 4 bits per pixel, as you are suggesting, your bound would be 393216 bytes.
However, it's not totally clear that that's the right way to account for it, because if you have a 256-color image that you have to reduce to 240 colors to have space for this algorithm, there isn't an obvious way to get back the lost colors by storing 9154 bytes somewhere else. You might be able to do something like pick the least popular 16 colors from the image (which occupy a maximum of 49152 pixels and usually less), store a bitmap telling where they were (98304 bytes), store the colors of the marked pixels into a 24576-byte array, replace them with some neutral color, run the flood fill, and then restore the colors. But, while that uses significantly less than 393216 bytes, it still uses a lot more than 9154 bytes, and it's probably pretty slow on the kind of computer where you'd be trying to do something like this.
At the other extreme, if your 256-color image actually only used the 216 "web-safe" colors (#000, #003, #006, ... #030, #033, etc.), you'd already have 16 leftover colors available. And freeing up 16 colors on a 16-bit or 24-bit TrueColor display would damage the image quality only imperceptibly.
I remember Mario Paint on Super Nintendo visibly flood-filling an area, but a computer that paints in modern image formats is probably not going to mind temporary allocation of a few hundred K. There are some fun opportunities to optimize, though, like checking a cache line of pixels at a time, or maybe tiling the image in 16-pixel squares using the same algorithm, and then cleaning up the edges.
The author of the submitted article has written about working in constrained environments. The algorithm he describes would be suitable for that kind of environment, where a few hundred K may not be available, or not without jumping through hoops to make it available.
https://t3x.org/#wyorc - One example, this is a book on writing a compiler targeting Z80 processors.
The pixels are effectively being turned into a linked list using the special values as ‘pointers’. This list is used as a stack, and the current position is the stack pointer.
I don’t think they explain the backtracking part very well, and they should have used an example that fills a non-rectangular area so it actually demonstrates the whole algorithm.
It’s a neat trick if you have spare values to use as markers, though. :)
Huh, that's useful because I had to write a floodfill a couple of days ago and it was a pain in the arse.
I'll be converting my code to the stackless version toot sweet.
Why were you needing floodfill?
To find connected regions on a map. I could probably have been smarter about the initial generation and connected things as they were generated (but that has only just occurred to me. Worth a go, I suppose.)
Use union-find to find connected regions on a map, not flood-fill.
I assume you mean "connected-component labeling" with union-find as the underlying "manage the sets" algorithm? If not, a link would be helpful.
What I mean could be described that way, but I'm not sure if you mean the same thing. Just in case, I elicited an implementation from Opus 5.5. I have carefully verified that this implementation implements what I mean: http://canonical.org/~kragen/sw/union-find-components.html
I also wrote a floodfill a while ago! We have a mapping app, and our imagery provider returns half-filled tiles at the edge of their coverage. And annoyingly, they don't have any metadata within the tile itself that indicates the coverage. They just return black pixels for a part of the tile.
So I needed a way to detect that, and doing a floodfill from the edge of the image turned out to be the easiest way.
How does this deal with one pixel gaps? The algorithm can enter it just fine but there's no space to go back out again, and there doesn't seem to be a system for backtracking, unless I've misunderstood the algorithm
It backtracks using the origin direction. As it traces back to the original starting pixel, before filling the current pixel it attempts to scan the remaining directions for each pixel (which may be none). If those lead to further pixels needing to be filled it'll start going forward again, and eventually hit a dead end and trace back to the branch point and continue to scan around it, eventually discovering is itself a dead end and go to its own predecessor.
Basically, a pixel will go through states like:
Each of the neighboring pixels will be checked (that last one is superfluous and could be skipped for efficiency). Once all have been checked the pixel will be filled, and the current pixel will be set by using its predecessor direction.What's the utility of this? It's arguably still using a stack, just encoded in the original data structure itself. If your original data structure somehow uses colors but is also fine with the algorithm overwriting with its own colors, I guess it works? But those are very unusual preconditions. For any real world scenario I can imagine, I feel like there's a better solution.
If the colors in your original data are important, then you can't really just overwrite them and/or assume that the algorithm can use its own colors. You're going to have to add a stack.
If your original data doesn't have colors, adding a stack is better than integrating metadata into the original data structure.
If for some reason your original data has colors but they aren't considered important, then just remove the colors and add a stack.
If your concern is about dynamic memory, preallocate static memory equal to the size of the original data structure.
> What's the utility of this?
Constant memory usage. It uses a small amount of additional memory (tracking the current pixel, pixel value, and a couple temp variables used for calculations) over the image itself making it a very low overhead algorithm. You can basically get away with 5 more variables, 20 more bytes if they're all 4-byte values, using this approach compared to the much greater memory needs of a stack-based approach (either a stack data structure or recursive). And actually just 4 variables since the D and P variables don't overlap in lifetime.
EDIT: Light editing of the above for grammar and clarity.
But that's only assuming that your original data structure already has space for the algorithm to store metadata. If there's space that can be manipulated freely to store metadata, can't you just remove that space to save memory, and then use the extra space for a stack?
Another option if you find yourself with this problem (flood fill, no recursion) is union find/connected components. Like the algorithm proposed in the article, you still need to store O(N) things, and runtime is still O(N).
Runtime of union find is slightly worse than O(N). https://www2.eecs.berkeley.edu/Pubs/TechRpts/1974/28764.html
Sure, but as far as "slightly" goes, it's pretty good!
Yup.
Curious if Claude could come up with this when asked to implement a flood fill without stack. Alas, out of tokens.
This document is from 2023, so maybe.
[pdf]