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