Optimal data structure for arbitrary two-dimensional crawl?

Question

I work on image-related algorithms and wondered what might be a good choice for unpredictable 2D intersection of structures as such:

• Start with a set of pixels.
• Go to the next one (top left, right or diagonal, always 1 away, no transitions).
• Continue doing more of these rounds to the next pixel with the next direction depending on some output (the same speed for each direction over time).

For a simple bypass, arrays are just fine and very fast when reading sequentially, there is not much that can be done for random access, but I'm wondering if something can be done here, if you just store it in an array going up, be quite far in memory on large (5 + megapixels). Can you think of any good structures for this? I am more than happy to trade memory for speed here, but I can’t think of any structure that could help if not make an array of elements, each of which stores a pointer to its 8 neighbors, but it looks like it will be slow for creation, and I do not do more than 1 - 3 passes on these images, so it may turn out to be slower than the implementation of a naive array.

Any suggestions are welcome.

Answer 1

Gap filling curves are what you are looking for. They provide in-memory caching for neighbor operations.

However, remember premature optimization . Before making any optimizations, make sure you have a working algorithm. Then you can start the optimization by taking tests and comparing them with the base non-optimized version.