What is this algorithm mapping coordinates to numbers called?

Question

I'm writing a program for visualizing crystals. As a part of the program, I have to generate all different basic points in a lattice structure. For those that aren't familiar with crystallography, you can find the most general cases of these structures here: https://en.wikipedia.org/wiki/Hermann%E2%80%93Mauguin_notation#Lattice_types

The problem was that I wanted to keep track of all these points. So I gave them a number. I was trying a bit with pen and paper, and found a nice algorithm to connect a coordinate (either in 2D or in 3D) with a number (and the other way around) by writing it out in binary form.

So if you want, for example, a simple cubic lattice in 2D, and you want to know the coordinates of point number 14. you can write this binary as 001110. You divide the number into 00|11|10, in which the most right part stands for (x,y)*1, the middle part part stands for (x,y)*2, the left part stands for (x,y)*4 (which is useless for number 14, just to make everything clear) and so on. So number 14 maps to the point (3, 2).

A simple C++ program to generate coordinates for the first 50 ints:

int x, y;

for (int n = 0; n < 50; n++)
{
    x = 0;
    y = 0;

    bitset<16>  nset(n);

    for (int i = 0; i < 16/2; i++)
    {
        x+=(nset[2*i]*pow(2.,i));
        y+=(nset[2*i+1]*pow(2.,i));
    }

    cout  << n << "\t" << x << "\t" << y << endl;
}

I extended this algorithm to 3D by reserving an additional column for the z-value, and for the other Lattice types by reserving the first one or two columns with kind of x+1/2, y+1/2, z+1/2 properties, different for each Lattice type.

So here's my question: does this algorithm exists already? Has it a name? Or is this just an obvious application of binary math? I read some things about hashmaps, but this seems more efficient to me, at least if you are dealing with integer numbers.

This is my very first question at stackexchange, was doubting I had to post this here or at the physics forum. Or perhaps at the math forum, because this is kind of a R^2->R bijection. So please correct me if this question is not at the right place.

Answer 1

So here's my question: does this algorithm exists already? Has it a name?

This mapping is called the Z-order curve or Morton code:

In mathematical analysis and computer science, Z-order, Morton order, or Morton code is a function which maps multidimensional data to one dimension while preserving locality of the data points. It was introduced in 1966 by G. M. Morton. The z-value of a point in multidimensions is simply calculated by interleaving the binary representations of its coordinate values. Once the data are sorted into this ordering, any one-dimensional data structure can be used such as binary search trees, B-trees, skip lists or (with low significant bits truncated) hash tables. The resulting ordering can equivalently be described as the order one would get from a depth-first traversal of a quadtree.

As shown in your example C++ code, the the x co-ordinate is stored in the even numbered bits and the y co-ordinate is stored in the odd numbered bits. The mapping can be easily extended to higher dimensions.

Some algorithms for fast interleaving of bits to encode these numbers using bit-manipulation operations can be found here.

Answer 2

I may be misinterpreting your code, but it seems like what you're doing is taking the even-numbered bits of the binary number, concatenating them together to form a new number, and using that number as your x coordinate. You seem to be doing the same thing for the y coordinate.

I don't think there's a name for this algorithm, though it seems like a pretty standard technique. For what it's worth, I think there's a much easier way to accomplish what you're doing here by using bitwise operators rather than bitset and pow:

for (int n = 0; n < kUpperBound; n++) {
    int x = 0;
    int y = 0;

    for (int i = 0; i < 8; i++) {
        if (n & (1 << (2*i)) != 0) {
           x += 1 << i;
        }
        if (n & (1 << (2*i + 1)) != 0) {
           y += 1 << i;
        }
    }
    cout << n << " " << x << " " << y << endl;
}

The value 1 << k is a number whose kth bit is 1 and which is 0 otherwise. Using the bitwise AND operator to AND this number with n will give back 0 if the kth bit of n is 0 and a nonzero number otherwise. Therefore, the test if (n & (1 << k) != 0) checks whether the kth bit of n is set or not. Then, instead of using pow to evaluate 2ⁿ, we use the fact that 1 << k has the numerical value 2^k.

Hope this helps!

Answer 3

It's probably no help to you unfortunately, but as a strange piece of trivia, this corresponds to the INTERLEAVE (or MINGLE) operator from the joke language INTERCAL.

I don't know of another name for this encoding. But it's generally not used much, since with the instructions available on most computers it's much simpler and faster to simply concatenate the binary representations of the two (or however many) integers together, which requires just O(d) time (and perhaps as few as d-1 machine instructions) for d dimensions. About the one advantage I can think of for your encoding is that it doesn't require you to commit to a fixed bit size for each dimension, so the maximum number of bits you need to encode a lattice point is proportional to the log of the maximum co-ordinate value -- is that something you actually make use of?