Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Map a 2D array onto a 1D array

I want to represent a 2D array with a 1D array. A function will pass the two indicies (x,y) and the value to store. These two indicies would represent a single element of a 1D array, and set it accordingly. I know the 1D array needs to have the size of arrayWidth × arrayHeight, but I don't know how to set each element.

For example, how do I distinguish (2,4,3) from (4,2,3)? I tried setting the array as the x*y, but 2*4 and 4*2 would result in the same spot in the array and I need them to be different.

like image 703
Blackbinary Avatar asked Jan 27 '10 23:01

Blackbinary


People also ask

How do you merge a 2D array into a 1D array?

The logic is simple : you should iterate on elements you have, read each one and add it in your destination array. You begin by a loop for first dimension of the array, then you do an embedded loop for the second dimension of the array and now you can read each data of the two-dimension array.

How do you represent a 2D array in one direction?

You should be able to access the 2d array with a simple pointer in place. The array[x][y] will be arranged in the pointer as p[0x * width + 0y][0x * width + 1y]... [0x * width + n-1y][1x * width + 0y] etc.

How do you convert a 2D matrix to 1D?

Every row in your 2D array is placed end to end in your 1D array. i gives which row you are in, and j gives the column (how far into that row). so if you are in the ith row, you need to place i complete rows end to end, then append j more onto that to get your single array index.

How are 2D arrays and 1D arrays related?

Arrays can be created in 1D or 2D. 1D arrays are just one row of values, while 2D arrays contain a grid of values that has several rows/columns. 1D: 2D: An ArrayList is just like a 1D Array except it's length is unbounded and you can add as many elements as you need.


2 Answers

You need to decide whether the array elements will be stored in row order or column order and then be consistent about it. http://en.wikipedia.org/wiki/Row-major_order

The C language uses row order for Multidimensional arrays

To simulate this with a single dimensional array, you multiply the row index by the width, and add the column index thus:

 int array[width * height];   int SetElement(int row, int col, int value)  {     array[width * row + col] = value;    } 
like image 126
John Knoeller Avatar answered Sep 20 '22 06:09

John Knoeller


The typical formula for recalculation of 2D array indices into 1D array index is

index = indexX * arrayWidth + indexY; 

Alternatively you can use

index = indexY * arrayHeight + indexX; 

(assuming that arrayWidth is measured along X axis, and arrayHeight along Y axis)

Of course, one can come up with many different formulae that provide alternative unique mappings, but normally there's no need to.

In C/C++ languages built-in multidimensional arrays are stored in memory so that the last index changes the fastest, meaning that for an array declared as

int xy[10][10]; 

element xy[5][3] is immediately followed by xy[5][4] in memory. You might want to follow that convention as well, choosing one of the above two formulae depending on which index (X or Y) you consider to be the "last" of the two.

like image 27
AnT Avatar answered Sep 20 '22 06:09

AnT