Friday, May 26, 2017

algorithm - Implementation of finding an index in a 1D array for a triangular grid


Am using a while loop to find an index within a 1D array, is there an easier, less-time-consuming and/or mathmatical way to find the index?


Consider the next grid:


 4   o
|\
| \
| \
3 o---o
|\ |\

| \ | \
| \| \
2 o---o---o
|\ |\ |\
| \ | \ | \
| \| \| \
1 o---o---o---o
|\ |\ |\ |\
| \ | \ | \ | \
| \| \| \| \

0 o---o---o---o---o

0 1 2 3 4

To find an index in the triangular grid within a 1D array I have the next function:


//int size = 5;
int getindex( int x, int y )
{

int columnCount = size;

while( y-- > 0 ) x += columnCount--;

return x;

}

The array (The numbers within the parenthesis are the coordinates and to simplify your view, in reality the (x,y) is in its whole the data):


pointdata data[ 15 ] = {
(0,0), (1,0), (2,0), (3,0), (4,0),
(0,1), (1,1), (2,1), (3,1),

(0,2), (1,2), (2,2),
(0,3), (1,3),
(0,4),
};

Answer



This is rather problem to sum numbers between n and m, which is pretty widely known: it is sum of numbers 1 to m minus sum of numbers 1 to n(n-1 infact, but it gets eliminated in the code) plus x, ofcourse. In your example, it is:


index = columnCount * ( columnCount + 1 ) / 2 - ( columnCount - y ) * ( columnCount - y + 1 ) / 2 ) + x;
plus, since column count is static (presumably), you can pre-cumpute the first part or even better just use total length of your array.


No comments:

Post a Comment

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...