Determining all pixels of a specific color directly bordering on another color

Question

I need a data structure/algorithm to efficiently retrieve borders and update changes.

There may be many (unconnected) regions of the same color. The shape of regions changes frequently over time and pixels may be randomly inserted - although most changes happen along the borders.

In this case, a pixel borders another if it is directly above, below, or to the left or right of it (Von Neumann neighborhood).

The lookup is as follows: retrieve all pixel coordinates with value Y that are neighbors of pixels with value X

Example: requesting all blue pixels bordering red pixels should return a list of pixels coordinates, here indicated in white:

So far I have tried the naive approach of checking every pixel, and then checking its neighbors if it is the required color, but this is too slow. I then changed to using a quadtree with a hierarchy of counters to avoid checking quads that do not contain either of the colors, but I feel this is still not the best solution. I have also tried using a bidirectional dictionary that maps values <-> coordinates, but this has been slower than the quadtree.

Edit: Using a better bidirectional directionary implementation, I can achieve about the same speed as the quadtree variant.

Answer 1

I solved this by saving, in addition to the map[y][x] -> color multidimensional array, a defaultdict(lambda : defaultdict(dict)) map, which maps from color -> [True, False] -> (Coordinates -> True).

dict[color][True] contains all coordinates which lie on a border (to either unclaimed or other color values), and so have to be checked when trying to find out borders, and dict[color][False] maps to all coordinates that are surrounded only by their own color (or, in my special case, "unreachable" regions). These can be skipped when trying to search for neighboring pixels of a different color.

The last value is irrelevant, I only use a dictionary there to check if a coordinate is in there in O(1).

When setting a pixel, in addition to updating the map, all its four surrounding neighbors are checked if they have the same value, and if they do, the coordinate is saved in the dictionary[color][False] map, otherwise in dictionary[color][True]. Also, importantly, the same is done for all four neighbors themselves, because from their perspective, a value (may) be changing.