How to Treat a 1D Data Structure as a 2D Grid

data structuresgraphicsmath

I am working with a native class that represents a 2D image as a 1D array. If you want to change one pixel, for example, you need to now how to derive the index from the x,y coordinates.

So, let's say we have a 1D array array1d like this:

array1d = [ a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y ]

In the context of our program, array1d represents a 2D grid:

a b c d e
f g h i j
k l m n o
p q r s t
u v w x y

And we want to perform operations on array1d such as:

  • Get the value at x,y coordinates (in this example, 1,2 would give l)
  • Get any sub-grid using x,y,width,height (1,2,2,2 would give [l, m, q, r])
  • Set the value at any x,y coordinate (etc.)

How do we do these?

Best Answer

2D / 1D - mapping is pretty simple. Given x and y, and 2D array sizes width (for x-direction) and height (for y-direction), you can calculate the according index i in 1D space (zero-based) by

i = x + width*y;

and the reverse operation is 

x = i % width;    // % is the "modulo operator", the remainder of i / width;
y = i / width;    // where "/" is an integer division

You can extend this easily to 3 or more dimensions. For example, for a 3D matrix with dimensions "width", "height" and "depth":

i = x + width*y + width*height*z;

and reverse:

x = i % width;
y = (i / width)%height;
z = i / (width*height);
Related Topic