Algorithmus zum Erstellen von Zellen durch Spirale auf dem hexagonalen Feld

Question

Helfen Sie, einen Algorithmus für die Erstellung von Zellen durch Spirale auf dem hexagonalen Feld zu finden.

Schauen Sie sich das Bild an:

Stellen wir uns ein dimensionsloses 2D -Array vor. Die x -Achse ist die blaue Linie, y ist horizontal, Spirale rot.

Ich muss Zellen vom zentralen Punkt x0Y0 bis zu Punkt n durch Spirale hinzufügen

Sagen Sie mir bitte den Weg, um das Problem zu lösen. Vielen Dank!

Answer 1

Ich würde empfehlen, die Zellen zu ändern, die sich schlampig nummerieren, so dass X gleich bleibt, wenn Sie runter und rechts (oder nach links) gehen. Dann sollte einfacher Algorithmus wie folgt 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
  }

Dies erzeugt die Punkte wie folgt:

Nach einer Transformation bekommen wir:

Answer 2

(Die Kreise haben einen Durchmesser von 1)

Hier ist eine Funktion, um Position zu bekommen 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 interessiert sind wie in Shuras Antwort:

  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 Gitter mit Quadraten anstelle von Sechseckern, erstellen Sie die Spirale mit diesem Raster und zeichnen Sie es dann, indem Sie sagen, dass jedes merkwürdige y nach links von M -Pixeln, das Ihnen diesen Effekt verleiht.

Answer 4

Sie können nacheinander Fexes auswählen, indem Sie eine geeignete Bewertungsfunktion verwenden, um das Beste aus den sechs nicht ausgewählten benachbarten Fecken für die in der vorherigen Runde ausgewählte Hex auszuwählen. Ich denke, eine Bewertungsfunktion, die funktioniert in der neuen Hülle). Die Entfernung im HEX -Gitter kann unter Verwendung 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

Sie könnten es tun, indem Sie Richtungen simulieren. Wenn Ihre Anweisungen "0 Punkte hoch" sind, dann sollte das Folgende um 1 erhöht werden.

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

Ich habe @Shuras Art geliebt, sich dem Problem zu nähern, konnte aber diesen Algorithmus nicht genau zum Laufen bringen. Außerdem verwende ich einen 2x1 -Hexagon -Abstand (in dem X -Zellen von 2 auseinander sind und jedes andere X -Element versteckt ist).

Folgendes habe ich gearbeitet (obwohl 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
    }