62

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?

GladstoneKeep
  • 2,629
  • 4
  • 19
  • 15
  • In Matlab, and thus likely math types (which spills into CS), to convert one matrix into another (be it a 1x12 into a 2x6 or a 2x6 into a 3x4) is known as "reshaping" http://www.mathworks.com/help/matlab/ref/reshape.html –  Sep 28 '13 at 17:08
  • @MichaelT: the OP is not reshaping the grid. No mention of reshaping the 5x5 to anything else (which wouldn't make sense anyway). :) – IAbstract Feb 17 '16 at 12:21
  • @IAbstract that question *was* in [revision 1](http://programmers.stackexchange.com/posts/212808/revisions) though. –  Feb 17 '16 at 12:51

1 Answers1

129

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);
Doc Brown
  • 199,015
  • 33
  • 367
  • 565
  • 1
    @awashburn that is the traditional way to do it, it's even built into compilers for static 2D arrays – ratchet freak Sep 28 '13 at 18:26
  • @mtoast: I don't think so, its just basic integer math. – Doc Brown Sep 29 '13 at 19:11
  • This example is wrong for 3D. The word depth in the calculation should be height. – jiggunjer Jul 22 '15 at 11:15
  • @jiggunjer: thanks for the correction, changed my answer accordingly. – Doc Brown Jul 22 '15 at 12:47
  • No problem, you might also want to mention the example is for row major indexing. – jiggunjer Jul 22 '15 at 17:32
  • Great!!! Saved me a few hours of head-scratching because you have the 1D -> 3D conversion. Great job! Would you mind me adding a practical implementation? I'm using a byte[] from a BinaryStream. I can give one for both 3D -> 1D and (now) 1D -> 3D. – IAbstract Sep 16 '15 at 13:23
  • @IAbstract: you do not need to ask me for this if you want to write an own answer. But be sure you understand how the Programmers site works, if an answer will not add any real additional value and mostly repeats what another guy already wrote, some people might downvote the answer. – Doc Brown Sep 16 '15 at 16:46
  • @DocBrown: I don't think my answer would provide any additional value. My implementation uses your answer. Sometimes people seeking answers are inspired by practical snippets where an answer has been put into use. – IAbstract Sep 16 '15 at 19:40
  • What is we don't want to have it 0-indexed – iordanis Jun 05 '16 at 18:04
  • 2
    @makakas: that is an exercise left to the reader ;-). Hint: you have to add/substract the lower bound as an offset at the right places. But before you try this, clarify to yourself which of the two arrays you mean, the 1D or the 2D array. – Doc Brown Jun 05 '16 at 18:13
  • @DocBrown Sorry my comment is terribly written, but I was trying to figure out the reverse function for 1-indexed arrays and this is what I found, for anyone looking for it in the future int x = (num-1)%width+1; int y = (num-1)/(width)+1; – iordanis Jun 05 '16 at 19:05
  • How might this be done for a system which also includes negative values of x,y when you need to make sure they all map to indices > -1 for computer arrays. – WDUK Sep 03 '20 at 04:41
  • 1
    @WDUK: you need to know the minimal values for x and y. Lets say you have xmin<0 and ymin<0. Now you replace "x" by "x-xmin" and "y" by "y-ymin" in the first formula above (for calculating i). For the reverse operation, you do the opposite and replace x by "x+xmin" and "y" by "y+min". – Doc Brown Sep 03 '20 at 06:13