Couldn't find any satisfactory explanation online, so here is a question. Discussions idea etc are welcome.

How is the colour fill tool implemented in paint or other software?

I remember it running superfast on old 98 machines. Got me curious to think how they achieved it.

(correct me if I am wrong, recursion won't be a good idea for large images.)

@oudalally thanks!
will need to write and test out flood fill on larger images then, cause I always thought recursion on some 1000x1000 pixels would take some noticeable time at least.

@oudalally yes, I get the process totally, but wouldn't the overhead on larger images be great too when running on single thread? So if my operation is a simple one I can get away with a larger recursion depth. Now the question is, is that enough for large images?

@Maroti @oudalally
Rendering line by line would still probably be faster though, if a bit more annoying to implement.
Unless I've got it totally wrong, you basically go across the image in a line and fill in the pixels that are in the interior of your shape.
The problem with the recursive flood fill is that it's very cache unfriendly assuming that you've stored your image as a straightforward matrix. You have to access pixels in adjacent columns or rows, and that's terrible if you have a decent sized image that's stored row or column wise. Here Z-ordering (Morton coding) can help you by decreasing the locality penalty somewhat.

@oudalally oh whoops I was thinking of a different flood fill, one that immediately recurses on all non-filled neighbors.