1
\$\begingroup\$

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),
};
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Column count is indeed static but what do you mean by pre-compute the first part. The first row? \$\endgroup\$ – brainoverflow Jan 18 '15 at 1:40
  • \$\begingroup\$ The point is the idea what you need - compute total count of members on previous rows. Code is irrelevant. You can also compute average of largest row and y-1 row and multiply it be y. \$\endgroup\$ – wondra Jan 18 '15 at 1:40
  • \$\begingroup\$ @brainoverflow sum from 1 to m is static. Sum from 1 to n is based on y. \$\endgroup\$ – wondra Jan 18 '15 at 1:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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