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.