2
\$\begingroup\$

I have a diamond shaped map that is displayed as follows:

*  *  *  0  1  *  *  *
*  *  2  3  4  5  *  *
*  6  7  8  9 10 11  *
12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27
* 28 29 30 31 32 33  *
*  * 34 35 36 37  *  *
*  *  * 38 39  *  *  * 

The tiles are stored as a uni-dimensional array in a file. So, I need to convert from tile number to coordinates, so I can make an array of arrays map[i][j]. I want to convert the tile number to its coordinates in the map (i, j) and back.

To do this, I have simplified it to this form (all tiles flushed to the left):

   j  0  1  2  3  4  5  6  7
i 
0     0  1  *  *  *  *  *  *
1     2  3  4  5  *  *  *  *
2     6  7  8  9 10 11  *  *
3    12 13 14 15 16 17 18 19
4    20 21 22 23 24 25 26 27
5    28 29 30 31 32 33  *  *
6    34 35 36 37  *  *  *  *
7    38 39  *  *  *  *  *  *

I have managed to convert a coordinate to its tile number like so:

def get_tile_number(i, j):
    # Given a map width and height n:
    if i < (n/2):
        number = i*(i+1) + j
    else:
        number = (2*((n/2)*((n/2)+1))) - ((n-i)*(n-i+1))) + j

So:
get_tile_number(0, 0) -> 0;
get_tile_number(6, 0) -> 34;

However, I cannot figure out to go back to the coordinates from the tile numbers, because I have trouble with distilling the i parameter from the tile number.

I have tried googling with terms like "diamond shaped map tile numbers coordinates convert", but no luck.

Can someone point me in the right direction?

Solution

Based on Ed Marty's answer, the formula looks as follows:

def get_ij(tile_number):
    n_serialized_tiles = (2*((n/2)*((n/2)+1)))
    if tile_number < n_serialized_tiles/2: # If before the halfway point of the diamond
        i = math.floor(0.5 * ((math.sqrt((4 * tile_number) + 1)) - 1))
    else:
        i = math.floor(n- (0.5 * ((math.sqrt((4 * ((2 * ((n/ 2) * ((n/ 2) + 1))) - tile_number)) + 1)) - 1)))

This finds the i component, after which I can find j by imputing get_tile_number(i, j=0) in the previous formula which gets me the tile_number at the start of that row. I then subtract the real tile_number from that number to get j j = tile_number - get_tile_number(i, j = 0).

\$\endgroup\$
  • 1
    \$\begingroup\$ In your example, n = 8 so for (i, j) = (0, 3), if ( i < n/2 ) passes, and number = i*(i+1) + j gives 0 * (1) + 3 = 3, so I don't know how (0, 3) -> 0 in this example. Is there something missing from the code or from the description? \$\endgroup\$ – DMGregory Jul 17 at 14:48
  • \$\begingroup\$ @DMGregory oops, I see my mistake, because in serialized form (array of arrays), all tiles should be flushed to the left. Edited and fixed. \$\endgroup\$ – Frank Jul 17 at 17:54
2
\$\begingroup\$

I tried it out in the Online Encyclopedia of Integer Sequences and found this one for the top half of the diamond:

i = floor((-1 + sqrt(1+4*number))/2)

The bottom half just needs to be reversed, like you’ve already done when going the other way.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I would have never thought of visiting the OEIS for this, what an amazing resource. \$\endgroup\$ – Frank Jul 18 at 11:27
  • \$\begingroup\$ Hint: you can also derive this formula by taking your formula for the number at the start of a row, number = i * (i + 1), and rearranging it to solve for i using our good old friend the quadratic formula. \$\endgroup\$ – DMGregory Jul 18 at 11:30

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.