Algorithme pour créer des cellules en spirale sur le champ hexagonal

Question

Aide pour trouver un algorithme pour créer des cellules en spirale sur le champ hexagonal.

Regardez l'image:

Imaginons un tableau 2d adimensionnel. L'axe X est la ligne bleue, Y est horizontale, en spirale est rouge.

Je dois ajouter des cellules à partir du point central X0Y0 au point N par spirale

Dites-moi la façon de résoudre le problème, s'il vous plaît. Merci!

Answer 1

Je vous suggère de modifier les cellules de numérotation sligtly, de sorte que X reste le même quand vous allez vers le bas et à droite (ou vers le haut et à gauche). Puis algorithme simple comme ce qui suit devrait fonctionner:

  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
  }

Cela génère des points comme suit:

Après une transformation, nous obtenons:

Answer 2

(Les cercles ont un diamètre de 1)

Voici une fonction pour obtenir la position 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 );
  }

Mise à l'échelle le résultat par Math.Sqrt(.75) donne

Si vous êtes intéressé par les coordonnées faussés comme dans la réponse de la Choura:

  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

Imaginez que vous aviez une grille normale avec des carrés au lieu de hexagones, créer la spirale à l'aide de cette grille, puis dessiner en déplaçant par exemple, tout y impair à la gauche de pixels m, ça va vous donner cet effet.

Answer 4

Vous pouvez choisir hexagones un à la fois en utilisant une fonction de pointage approprié pour sélectionner le meilleur des six hexagones adjacents ne sont pas encore sélectionnés dans l'hexagone sélectionné au tour précédent. Je pense une fonction de pointage qui fonctionne est de choisir le plus proche de (0,0) (forces dans la sélection hexagones une « coquille » à la fois), la rupture des liens en choisissant le plus proche de (1,0) (forces une direction spirale cohérente dans le nouveau shell). Distance de la grille hexagonale peut être calculée en utilisant la fonction suivante:

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

pourrait le faire en simulant les directions. Si vos directions sont « 0 points », puis incrémenter par 1 que vous allez sens horaire, ce qui suit devrait faire:

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

J'ai adoré @ la manière de choura d'aborder le problème, mais n'a pas pu obtenir cet algorithme exact de travailler. En outre, j'utilise un espacement hexagonal 2x1 (où x cellules sont espacées à part 2, et chaque autre point x est caché).

Voici ce que je viens de faire marcher (mais en 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
    }