Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Hopefully this is a good question. 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. And I am trying to grok, in abstract terms, how to map a multidimensional object to its underlying unidimensional representation.

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.)

Is there a computer science-related or mathematical term for said operations, which map points/regions in 1D data to coordinates in 2D/3D/4D... objects? If so, what is it? Clearly all computers with displays solve this same issue, so what is this fundamental problem called and how is it conventionally solved?

share|improve this question
    
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" mathworks.com/help/matlab/ref/reshape.html –  MichaelT Sep 28 '13 at 17:08

1 Answer 1

up vote 9 down vote accepted

2D / 1D - mapping is pretty simple. Given x and y, and 2D array sizes width and height, 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*depth*z;

and reverse:

x = i % width;
y = (i / width)%depth;
z = i / (width*depth);
share|improve this answer
    
+1 for simple algebraic solution! –  recursion.ninja Sep 28 '13 at 18:07
    
@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
    
Thanks for the answer (and the reverses)! Is there a name or category for these general types of formulae (which map 1D -> 2D -> 3D etc.)? –  GladstoneKeep Sep 28 '13 at 23:28
    
@mtoast: I don't think so, its just basic integer math. –  Doc Brown Sep 29 '13 at 19:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.