Algorithmus zur Erzeugung von Zellen durch Spiralen auf dem hexagonalen Feld

Question

Hilfe bei der Suche nach einem Algorithmus zur Erstellung von Zellen durch Spiralen auf dem sechseckigen Feld.

Sehen Sie sich das Bild an:

Stellen wir uns ein dimensionsloses 2d-Array vor. Die X-Achse ist die blaue Linie, Y ist horizontal, die Spirale ist rot.

Ich muss Zellen vom zentralen Punkt x0y0 zum Punkt N spiralförmig hinzufügen

Sagen Sie mir bitte, wie ich das Problem lösen kann. Ich danke Ihnen!

Answer 1

Ich würde vorschlagen, die Nummerierung der Zellen ein wenig zu ändern, so dass X gleich bleibt, wenn man nach unten und rechts (oder oben und links) geht. Dann sollte ein einfacher Algorithmus wie der folgende funktionieren:

  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
  }

Dadurch werden die Punkte wie folgt erzeugt:

Nach einer Umwandlung erhalten wir:

Answer 2

(die Kreise haben einen Durchmesser von 1)

Hier ist eine Funktion, die die Position ermittelt 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 );
  }

Skalierung des Ergebnisses durch Math.Sqrt(.75) gibt

Wenn Sie an den verzerrten Koordinaten wie in Shuras Antwort interessiert sind:

  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

Stellen Sie sich vor, Sie hätten ein normales Raster mit Quadraten anstelle von Sechsecken, erstellen Sie die Spirale mit diesem Raster und zeichnen Sie sie, indem Sie z. B. jedes ungerade y um m Pixel nach links verschieben, so erhalten Sie diesen Effekt.

Answer 4

Sie können ein Feld nach dem anderen auswählen, indem Sie eine entsprechende Wertungsfunktion verwenden, um das beste der sechs noch nicht ausgewählten Nachbarfelder des in der vorherigen Runde ausgewählten Feldes auszuwählen. Ich denke, eine funktionierende Wertungsfunktion ist die Auswahl des Feldes, das am nächsten an (0,0) liegt (zwingt zur Auswahl von Feldern in jeweils einer "Schale"), wobei Gleichstände durch die Auswahl des Feldes aufgelöst werden, das am nächsten an (1,0) liegt (erzwingt eine einheitliche Spiralrichtung in der neuen Schale). Der Abstand im Sechseckgitter kann mit der folgenden Funktion berechnet werden:

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

Du könntest es tun, indem du Richtungen simulierst. Wenn Ihre Richtungen "0 Punkte nach oben" sind, dann erhöhen Sie um 1, wenn Sie im Uhrzeigersinn gehen, sollte das folgende tun:

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