Color-Region-Interpolation-Scheme
Application of inverse distance weighting in a discrete setting.
The original problem I came up against was trying to interpolate smoothly between different color regions on an image efficiently. This was my original solution.
Some results:
(One other cool application of the same method: easy terrain generation.) https://www.geogebra.org/m/fvs6uvft
The Algorithm
First, I collect all pixels of the same (or similar enough) color in a lookup table. Next, I treat each pixel as a "source" where color can flood out from.
Next, we flood fill outwards from the boundary of each color region making a mark of the iterations it took to get to each pixel. We treat the iteration count as pseudo-distance from the boundary. https://en.wikipedia.org/wiki/Flood_fill
Eventually, the distances from blue, and the distances from red overlap and we store their ratio.
Next, we now know that the pixel near the centre is "5-away" from the red border and "6-away" from the blue border. Therefore, we need to pick a color such that the closer border has more influence.
To do this:
Let the left part of the ratio represent red influence, and right, blue inluence.
We want a weighted average of both channels such that red has more influence.
So take the ratio
5:6
We want more red influence, so take the inverse of both sides
1/5 : 1/6 (Note the left side is now bigger than the right)
Finally, make the ratios add up to 1 so that we may use it in a weighted average.
1/5 + 1/6 = 11/30
So,
1/5 ÷ 11/30 : 1/6 ÷ 11/30
6/11 : 5/11
Hence, we have our weighted average.
We now do 6/11*RedChannel + 5/11*BlueChannel
to produce the new color below.
This is then repeated for every pixel until you get something like this,
Here, I later discovered this simple idea of "inverse-distance-ratios" was part of a much larger interpolation scheme known as https://en.wikipedia.org/wiki/Inverse_distance_weighting and I've since applied it in other places.