Algoritmo per la creazione di cellule spirale sul campo esagonale

Question

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!

Answer 1

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:

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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
    }