Was ist das für ein Algorithmus, der Koordinaten an Zahlen anordnet?

Question

Ich schreibe ein Programm zur Visualisierung von Kristallen. Als Teil des Programms muss ich alle verschiedenen grundlegenden Punkte in einer Gitterstruktur erzeugen. Für diejenigen, die nicht mit Kristallographie vertraut sind, finden Sie die allgemeinsten Fälle dieser Strukturen hier: https://en.wikipedia.org/wiki/Hermann%E2%80%93Mauguin_notation#Lattice_types

Das Problem war, dass ich all diese Punkte verfolgen wollte. Also gab ich ihnen eine Nummer. Ich habe ein bisschen mit Stift und Papier versucht und einen schönen Algorithmus gefunden, um eine Koordinate (entweder in 2D oder in 3D) mit einer Zahl zu verbinden (und umgekehrt), indem ich sie in binärer Form schreibe.

Wenn Sie also zum Beispiel ein einfaches kubisches Gitter in 2D wollen und Sie die Koordinaten von Punkt Nummer 14 kennen, können Sie diese Binärzahl als 001110 schreiben. Sie teilen die Zahl in 00 | 11 | 10, in der der rechte Teil für (x, y) * 1 steht, der mittlere Teil steht für (x, y) * 2, der linke Teil für (x, y) * 4 (was für die Zahl 14 unbrauchbar ist, nur um alles klar zu machen) und so weiter. So nummeriert Nummer 14 auf den Punkt (3, 2).

Eine einfache C++ Programm erzeugen Koordinaten für die ersten 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 diesen Algorithmus durch die Reservierung eine zusätzliche Spalte für den Z-Wert ist, und für die anderen Gittertypen auf 3D erweitert die durch die Reservierung erste ein oder zwei Spalten mit einer Art von x + 1/2, y + 1/2, z + 1/2 Eigenschaften, unterschiedlich für jeden Gittertyp.

Also hier ist meine Frage: ist dieser Algorithmus bereits existiert? Hat es einen Namen? Oder ist das nur eine naheliegende Anwendung der binären Mathematik? Ich habe einige Dinge über Hashmaps gelesen, aber das scheint mir effizienter zu sein, zumindest wenn es sich um ganzzahlige Zahlen handelt.

Das ist meine allererste Frage beim Stackexchange, ich zweifelte daran, dass ich das hier oder im Physikforum posten musste. Oder vielleicht im Mathematik-Forum, weil das eine Art von Bijektion ist. Also korrigiere mich bitte, wenn diese Frage nicht am richtigen Ort ist.

Answer 1

Also hier ist meine Frage: Gibt es diesen Algorithmus bereits? Hat es einen Namen?

Diese Zuordnung die Z-Order-Kurve oder Morton code genannt wird:

In der mathematischen Analyse und Informatik, Z-Reihenfolge, Morton bestellen oder Morton-Code ist eine Funktion, die zu einem multidimensionalen Datenkarten Dimension unter Beibehaltung der Lokalität der Datenpunkte. Es wurde 1966 von G. M. Morton eingeführt. Der Z-Wert eines Punktes in Multidimensionen wird einfach durch Verschachteln der Binärdarstellungen seiner Koordinatenwerte berechnet. Sobald die Daten in diese Reihenfolge sortiert sind, kann jede eindimensionale Datenstruktur verwendet werden, wie etwa binäre Suchbäume, B-Bäume, Sprunglisten oder Hashtabellen (mit niedrigwertigen Bits abgeschnitten). Die resultierende Ordnung kann äquivalent als die Reihenfolge beschrieben werden, die man von einer Tiefenquerung eines Quadtree erhalten würde.

Wie im Beispiel C++ Code gezeigt, der die x-Koordinate wird in den geradzahligen Bits und das y-Koordinate wird in dem ungeradzahligen Bits gespeichert wird. Das Mapping kann einfach auf höhere Dimensionen erweitert werden.

Einige Algorithmen zum schnellen Verschachteln von Bits zum Codieren dieser Zahlen unter Verwendung von Bitmanipulationsoperationen finden Sie unter here.

Answer 2

Ich kann Ihren Code falsch interpretieren, aber es scheint, als ob Sie gerade die geradzahligen Bits der Binärzahl nehmen, sie zu einer neuen Zahl verketten und diese Zahl als Ihre x-Koordinate verwenden. Du scheinst dasselbe für die y-Koordinate zu tun.

Ich glaube nicht, dass es einen Namen für diesen Algorithmus gibt, obwohl es wie eine hübsche Standardtechnik scheint. Für das, was es wert ist, denke ich, dass es viel einfacher Weg ist, zu erreichen, was Sie hier tun, indem Bitoperatoren statt bitset und pow mit:

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; 
} 

Der Wert 1 << k ist eine Zahl, deren k-te Bit ist 1 und die ist sonst 0. Wenn Sie den bitweisen AND-Operator zu AND verwenden, wird diese Zahl mit n 0 zurückgeben, wenn das k-te Bit n 0 ist und andernfalls eine Zahl ungleich Null ist. Daher prüft der Test if (n & (1 << k) != 0), ob das k-te Bit n gesetzt ist oder nicht. Anstatt pow zu verwenden, um 2 ⁿ auszuwerten, verwenden wir die Tatsache, dass 1 << k den numerischen Wert 2 ^k hat.

Hoffe, das hilft!

Answer 3

Es ist wahrscheinlich keine Hilfe für Sie, aber als eine seltsame Kleinigkeit, entspricht dies dem Operator INTERLEAVE (oder MINGLE) aus der joke language INTERCAL.

Ich kenne keinen anderen Namen für diese Codierung. Aber es wird im Allgemeinen nicht viel verwendet, da es mit den auf den meisten Computern verfügbaren Anweisungen viel einfacher und schneller ist, die Binärdarstellungen der zwei (oder wie viele) ganzen Zahlen einfach miteinander zu verketten, was nur O (d) Zeit benötigt (und vielleicht so wenig) als d-1 Maschinenanweisungen) für d Dimensionen. Der einzige Vorteil, den ich mir für Ihre Codierung vorstellen kann, ist, dass Sie nicht für jede Dimension eine feste Bitgröße festlegen müssen. Daher ist die maximale Anzahl an Bits, die Sie zum Codieren eines Gitterpunkts benötigen, proportional zum Protokoll der maximaler Koordinatenwert - nutzen Sie das eigentlich?