Algoritmo para criar células por espiral no campo hexagonal

Question

Ajude a encontrar um algoritmo para criar células em espiral no campo hexagonal.

Olhe para a imagem:

Vamos imaginar uma matriz 2D sem dimensão. O eixo x é a linha azul, y é horizontal, a espiral é vermelha.

Eu preciso adicionar células do ponto central x0y0 ao ponto n por espiral

Diga -me a maneira de resolver o problema, por favor. Obrigada!

Answer 1

Eu sugiro alterar as células numerando o Sligtly, para que X permaneça o mesmo quando você desce e para a direita (ou para cima e para a esquerda). Em seguida, o algoritmo simples como o seguinte deve funcionar:

  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
  }

Isso gera os pontos da seguinte maneira:

Após uma transformação, obtemos:

Answer 2

(Os círculos têm um diâmetro de 1)

Aqui está uma função para obter posição 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 );
  }

Escalando o resultado por Math.Sqrt(.75) dá

Se você estiver interessado nas coordenadas distorcidas, como na resposta de 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

Imagine que você teve uma grade normal com quadrados em vez de hexágonos, crie a espiral usando essa grade e, em seguida, desenhe -a, digamos, cada ímpar para a esquerda por m pixels, que lhe dará esse efeito.

Answer 4

Você pode escolher Hexes, um de cada vez, usando uma função de pontuação apropriada para selecionar o melhor dos seis hexates adjacentes ainda não selecionados aos hexadecipais selecionados na rodada anterior. Eu acho que uma função de pontuação que funciona é escolher o mais próximo de (0,0) (forças que selecionam hexágonos em um "shell" por vez), quebrando laços escolhendo o mais próximo de (1,0) (força uma direção espiral consistente no novo shell). A distância na grade hexadecimal pode ser calculada usando a seguinte função:

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

Você pode fazer isso simulando direções. Se suas instruções estiverem "0 pontos para cima", o incremento em 1 à medida que você passa por relógio, o seguinte deve fazer:

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

Eu amei a maneira de @shura de abordar o problema, mas não consegui fazer com que esse algoritmo exato funcionasse. Além disso, estou usando um espaçamento de hexágono 2x1 (onde as células X são espaçadas 2 separadas e todos os outros itens X estão ocultos).

Aqui está o que eu consegui funcionar (embora em 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
    }