Quali sono le coordinate di questo algoritmo per la mappatura dei numeri?

Question

Sto scrivendo un programma per visualizzare i cristalli. Come parte del programma, devo generare tutti i diversi punti di base in una struttura reticolare. Per coloro che non hanno familiarità con la cristallografia, qui puoi trovare i casi più generali di queste strutture: https://en.wikipedia.org/wiki/Hermann%E2%80%93Mauguin_notation#Lattice_types

Il problema era che volevo tenere traccia di tutti questi punti. Quindi ho dato loro un numero. Stavo provando un po 'con carta e penna e ho trovato un buon algoritmo per connettere una coordinata (in 2D o in 3D) con un numero (e viceversa) scrivendolo in forma binaria.

Quindi, se si desidera, ad esempio, un semplice reticolo cubico in 2D e si desidera conoscere le coordinate del punto numero 14. è possibile scrivere questo binario come 001110. Si divide il numero in 00 | 11 | 10, in cui la parte più a destra sta per (x, y) * 1, la parte della parte centrale sta per (x, y) * 2, la parte sinistra sta per (x, y) * 4 (che è inutile per il numero 14, solo per rendere tutto chiaro) e così via. Quindi il numero 14 mappa al punto (3, 2).

Un semplice programma C++ per generare le coordinate per i primi 50 interi:

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

ho esteso questo algoritmo a 3D riservando una colonna supplementare per il valore z, e per gli altri tipi Lattice riservando il prima una o due colonne con tipo di proprietà x + 1/2, y + 1/2, z + 1/2, diverse per ogni tipo di Lattice.

Quindi, ecco la mia domanda: questo algoritmo esiste già? Ha un nome? O è solo una ovvia applicazione della matematica binaria? Ho letto alcune cose su hashmaps, ma questo mi sembra più efficiente, almeno se hai a che fare con numeri interi.

Questa è la mia prima domanda a stackexchange, dubitavo che avrei dovuto postare questo qui o al forum di fisica. O forse al forum di matematica, perché questa è una specie di biiezione R^2> R. Quindi per favore correggimi se questa domanda non è nel posto giusto.

Answer 1

Quindi, ecco la mia domanda: questo algoritmo esiste già? Ha un nome?

Questa mappatura è chiamata la curva Z-ordine o Morton code:

In analisi matematica e informatica, Z-ordine, ordine Morton, o il codice di Morton è una funzione che mappa i dati multidimensionali a uno dimensione pur preservando la localizzazione dei punti dati. Fu introdotto nel 1966 da G. M. Morton. Il valore z di un punto in multidimensioni viene semplicemente calcolato interlacciando le rappresentazioni binarie dei suoi valori di coordinate. Una volta ordinati i dati in questo ordine, è possibile utilizzare qualsiasi struttura dati unidimensionale come ad esempio alberi di ricerca binari, alberi B, elenchi di salto o tabelle hash (con bit significativi bassi troncati). L'ordinamento risultante può essere descritto in modo equivalente come l'ordine che si otterrebbe da un attraversamento in profondità di un quadruplo.

Come mostrato in esempio codice C++, il la coordinata x è memorizzato nei bit di numero pari e la coordinata y è memorizzato nei bit dispari. La mappatura può essere facilmente estesa a dimensioni superiori.

Alcuni algoritmi per l'interleaving veloce di bit per codificare questi numeri utilizzando operazioni di manipolazione dei bit possono essere trovati here.

Answer 2

È possibile che stia interpretando male il codice, ma sembra che quello che stai facendo sia prendere i bit pari del numero binario, concatenarli insieme per formare un nuovo numero e usare quel numero come coordinata x. Sembra che tu stia facendo la stessa cosa per la coordinata y.

Non penso che ci sia un nome per questo algoritmo, anche se sembra una tecnica piuttosto standard. Per quello che vale, credo che ci sia un modo molto più facile da realizzare quello che stai facendo qui utilizzando operatori bit per bit piuttosto che bitset e 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; 
} 

Il valore 1 << k è un numero il cui k-esimo bit è 1, e che è 0 altrimenti. Utilizzando l'operatore AND bit a AND questo numero con n restituirà 0 se il bit kth di n è 0 e un numero diverso da zero altrimenti. Pertanto, il test if (n & (1 << k) != 0) verifica se il kth bit di n è impostato o meno. Quindi, invece di utilizzare pow per valutare 2 ⁿ, usiamo il fatto che 1 << k ha il valore numerico 2 ^k.

Spero che questo aiuti!

Answer 3

Probabilmente non ti è stato d'aiuto, sfortunatamente, ma come strano pezzo di curiosità, questo corrisponde all'operatore INTERLEAVE (o MINGLE) dallo joke language INTERCAL.

Non conosco un altro nome per questa codifica. Ma generalmente non viene usato molto, poiché con le istruzioni disponibili sulla maggior parte dei computer è molto più semplice e veloce concatenare semplicemente le rappresentazioni binarie dei due (o di molti) interi, che richiede solo O (d) tempo (e forse anche pochi come istruzioni macchina d-1) per le dimensioni d. L'unico vantaggio che posso pensare per la codifica è che non richiede il commit di una dimensione di bit fissa per ogni dimensione, quindi il numero massimo di bit necessario per codificare un punto reticolare è proporzionale al log del massimo valore di coordinazione - è qualcosa che effettivamente usi?