Algoritmo per la creazione di cellule spirale sul campo esagonale
-
22-09-2019 - |
Domanda
Guida per trovare un algoritmo per la creazione di celle a spirale sul campo esagonale.
Guarda l'immagine:
Immaginiamo una matrice 2D adimensionale. L'asse X è la linea blu, Y è orizzontale, spirale è rosso.
ho bisogno di aggiungere le cellule dal punto X0Y0 centrale a punto N dalla chiocciola
Mi dica il modo per risolvere il problema, per favore. Grazie!
Soluzione
Io suggerirei di cambiare le cellule di numerazione Leggermente, in modo che X rimane lo stesso quando si va in basso ea destra (o verso l'alto ea sinistra). Poi semplice algoritmo simile alla seguente dovrebbe funzionare:
int x=0, y=0;
add(x, y); // add the first cell
int N=1
for( int N=1; <some condition>; ++N ) {
for(int i=0; i<N; ++i) add(++x, y); // move right
for(int i=0; i<N-1; ++i) add(x, ++y); // move down right. Note N-1
for(int i=0; i<N; ++i) add(--x, ++y); // move down left
for(int i=0; i<N; ++i) add(--x, y); // move left
for(int i=0; i<N; ++i) add(x, --y); // move up left
for(int i=0; i<N; ++i) add(++x, --y); // move up right
}
Questo genera i punti come segue:
Dopo una trasformazione otteniamo:
Altri suggerimenti
(I cerchi hanno un diametro di 1)
Ecco una funzione per ottenere la posizione i
:
void getHexPosition( int i, ref double x, ref double y )
{
if ( i == 0 ) { x = y = 0; return; }
int layer = (int) Math.Round( Math.Sqrt( i/3.0 ) );
int firstIdxInLayer = 3*layer*(layer-1) + 1;
int side = (i - firstIdxInLayer) / layer; // note: this is integer division
int idx = (i - firstIdxInLayer) % layer;
x = layer * Math.Cos( (side - 1) * Math.PI/3 ) + (idx + 1) * Math.Cos( (side + 1) * Math.PI/3 );
y = -layer * Math.Sin( (side - 1) * Math.PI/3 ) - (idx + 1) * Math.Sin( (side + 1) * Math.PI/3 );
}
Scaling il risultato per Math.Sqrt(.75)
dà
Se siete interessati alle coordinate distorta come nella risposta di Shura:
int[] h = { 1, 1, 0, -1, -1, 0, 1, 1, 0 };
void getHexSkewedPosition( int i, ref int hx, ref int hy )
{
if ( i == 0 ) { hx = hy = 0; return; }
int layer = (int) Math.Round( Math.Sqrt( i/3.0 ) );
int firstIdxInLayer = 3*layer*(layer-1) + 1;
int side = (i - firstIdxInLayer) / layer;
int idx = (i - firstIdxInLayer) % layer;
hx = layer*h[side+0] + (idx+1) * h[side+2];
hy = layer*h[side+1] + (idx+1) * h[side+3];
}
void getHexPosition( int i, ref double hx, ref double hy )
{
int x = 0, y = 0;
getHexSkewedPosition( i, ref x, ref y );
hx = x - y * .5;
hy = y * Math.Sqrt( .75 );
}
Immagina di avere una griglia con quadrati normale al posto di esagoni, creare la spirale con quella griglia, poi disegnarlo spostando per esempio, ogni y dispari alle di m pixel a sinistra, che ti do in tal senso.
È possibile scegliere esagoni uno alla volta utilizzando una funzione di punteggio appropriato per selezionare la migliore delle sei esagoni adiacenti non ancora selezionati l'esagono selezionato turno precedente. Credo che una funzione di punteggio che funziona è quello di scegliere più vicino a (0,0) (forze selezione esagoni in un "guscio" in un momento), rompendo i legami scegliendo più vicino a (1,0) (forze una direzione coerente spirale nella nuova shell). Distanza della griglia esagono può essere calcolata utilizzando la seguente funzione:
double grid_distance(int dx, int dy) {
double real_dx = dx + y/2.0;
double real_dy = dy * sqrt(3)/2.0;
return sqrt(real_dx * real_dx + real_dy * real_dy);
}
Si potrebbe farlo simulando le direzioni. Se i vostri sensi sono "0 punti up", poi incrementati di 1, come si va in senso orario, il seguente dovrebbe fare:
Pick a centre cell. Pick the second cell (ideally in direction 0). Set direction to 2. While you have more cells to mark: if the cell in (direction+1)%6 is free: set direction = (direction+1)%6 mark current cell as used go to cell in direction
Ho amato @ modo di Shura di affrontare il problema, ma non ha potuto ottenere tale algoritmo esatto per lavorare. Inoltre, sto usando una spaziatura 2x1 esagonale (in cui le cellule sono distanziati x 2 a parte, e ogni altro elemento x è nascosto).
Ecco quello che ho ottenuto a lavorare (anche se in JavaScript):
//Hexagon spiral algorithm, modified from
for(var n=1; n<=rings; ++n) {
x+=2; add(x, y);
for(var i=0; i<n-1; ++i) add(++x,++y); // move down right. Note N-1
for(var i=0; i<n; ++i) add(--x,++y); // move down left
for(var i=0; i<n; ++i) { x-=2; add(x, y); } // move left
for(var i=0; i<n; ++i) add(--x,--y); // move up left
for(var i=0; i<n; ++i) add(++x, --y); // move up right
for(var i=0; i<n; ++i) { x+=2; add(x, y); } // move right
}