Optimal data structure for abritrary 2D traversal?

Question

I'm working on image related algorithms and was wondering what some good choices would be for unpredictable 2D traversal of structures as such:

• Start from a set pixel
• Traverse to a neighbor (up left down right or diagonal, always 1 away, no jumps).
• Keep doing more of those traversals to the next pixel with the next direction depending on some output (similar rate of each direction over time).

For simple traversal then arrays are just fine and very fast when reading sequentially, for random access not much can be done but i'm wondering if here Something could be done, if simply stored in an array going "up" could actually be pretty far in memory on large is (5+megapixel). Can you think of any good structures for this? I'm more than happy to trade memory for speed here but i can't think of any structure that could help short of actually making an array of items that each store a pointer to their 8 neighbors, but that sounds like it would be slow to create to begin with and i'm not making more than 1 to 3 passes on those images so it may end up being slower than the naive array implementation.

Any suggestions are welcome.

Answer 1

Space-filling curves are what you are looking for. They provide cache-friendly data layout in memory for neighbor-related operations.

However, be aware of premature optimization. Before doing any kind of optimizations, make sure you have a working algorithm. Then you can start optimizing it, taking benchmarks and comparing them with the base non-optimized version.