Here's an example https://en.m.wikipedia.org/wiki/Connected-component_labeling
https://scikit-image.org/docs/stable/api/skimage.measure.htm...
I guess you are doing the same thing and memoizing the graph ahead of time. Perhaps find an optimized implementation in wasm and save yourself some maintenance time.
1. Use pointIdx instead of a string for fill keys. That's going to be way faster and memory efficient
2. There's no need to have separate added and visited. Just keep added and continue checking it before adding to the queue, and don't delete added entries
3. Even better, don't even use added but instead just check the output image data
4. Compute pointIdx incrementally by adding or subtracting 1 or width, only do a multiplication for the first point
5. Don't keep y coordinates in the loop, instead store the minimum and maximum pointIdx and then divide at the end to find the y coordinates (you still need to keep x to compute the x minimum and maximum if you need it, unless you can make the image have a power of two stride, in which case you can just mask pointIdx to compute x)
6. Use a black border instead of doing boundary checks
7. The % 5000 check is horribly slow since division is horribly slow. Use a power-of-two size and a bitwise and to be safe
8. Doing an update every 5000 pixels seems absurdly low. CPUs do billions of operations per second and a pixel should not take more than 100 CPU cycles with proper optimization, so even at around 100 fps you should be able to do in the magnitude of 100K pixels per frame, which means you shouldn't even need to do it incrementally or pre-process. If you really need incrementality you should use both a pixel number check and a timer and adaptively double or halve the pixel number if the timer check gives a too low or high time elapsed.
9. Using "chunks of pixel" is probably faster than single pixels and using horizontal groups of chunks even better, although that requires significantly more code
10. WebAssembly, with SIMD if available, is going to be faster than JavaScript
In general, this code has clearly not been written by someone experienced in writing optimized code, so I assume the pre-processing can also be greatly optimized (if it's even necessary after optimizing the filling code).
Also, there is no need to limit to 256 areas since you can use multiple images and all channels to store larger integers.
a potential drawback is that it seems like the paths could be several times larger than the original image (consider a checkerboard pattern, where each pixel is its own fill area, or the pathological spiral pattern i suggested in a comment below)
If you would like to dynamically adjust the masks, the following algorithm should be O(sqrt(N)) lines of JavaScript executed for realistic cases:
Split the image up into monochromatic regions of at most 1000-4000 pixels (you want to regions to be roundish rather than long and stringy, so use breadth first search to create them). Then keep track of a graph of these regions with edges between adjacent regions. For a 2000x2000 pixel image, the graph should contain ~4000 nodes, so finding a monochromatic component would not take an appreciable amount of time.
Updating the graph after a fill operation is straightforward - just relabel the color associated with each changed region. The only point I'm uncertain of is whether canvas operations are fast enough that each region can have its own mask and up to 4000 draws as described in the blog post don't take too long. The individual masks wouldn't be very big, and the total number of pixels to be colored isn't any different to the blog post, so it may be possible.
If something is drawn with the pen tool, then every region it touches would need to be recalculated. Assuming the pen tool is circular and not substantially larger than 1000 pixels itself, this should be a fast operation as it won't overlap too many large regions and there are few enough regions we can iterate through all of them every frame for a bounding box test.
There are cases where this goes wrong - for example if the regions end up being very stretched. If there are 1000 1-pixel wide vertical lines, and the drawing tool allows a 1000 pixel horizontal line to be drawn in 1 frame, the algorithm described looks at a million pixels (possibly 4 times each as it checks for adjacency), which might be too slow. However, since this is aimed at a touchscreen, I'd be impressed if your children can and want to draw accurately enough to cause a problem. Further optimisations could work around this problem (and other problems such as having lots of 1-pixel regions that would bloat the graph).
devit's suggestions are also worth incorporating.
Since this algorithm only becomes interesting with edits, it's not really something I could implement as a pull request to the GH repo.