Algoritmo para la creación de células de espiral en el campo hexagonal

Question

Ayuda para encontrar un algoritmo para la creación de células de espiral en el campo hexagonal.

Mire la imagen:

Imaginemos una matriz 2D adimensional. El eje X es la línea azul, Y es horizontal, espiral es rojo.

I que añadir células de la X0Y0 punto central a punto N por espiral

Dime la manera de resolver el problema, por favor. Gracias!

Answer 1

Me gustaría sugerir el cambio de las células de numeración sligtly, de manera que X sigue siendo el mismo cuando vas abajo ya la derecha (o hacia arriba y a la izquierda). Entonces algoritmo sencillo como lo siguiente debería 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
  }

Esto genera los puntos como sigue:

Después de una transformación obtenemos:

Answer 2

(Los círculos tienen un diámetro de 1)

Aquí hay una función para obtener la posición 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 );
  }

Escalado el resultado por Math.Sqrt(.75) da

Si está interesado en las coordenadas sesgadas como en la respuesta 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 tiene una rejilla normal con los cuadrados en lugar de hexágonos, crear la espiral utilizando esa red, y luego sacarla desplazando por ejemplo, cada y extraña a la izquierda por M píxeles, que te dará ese efecto.

Answer 4

Se puede elegir hexágonos uno a la vez mediante el uso de una función de la puntuación apropiada para seleccionar el mejor de los seis hexágonos adyacentes todavía-no-seleccionados al hexágono seleccionada la ronda anterior. Creo que una función de la puntuación que funciona es para recoger el más cercano a (0,0) (fuerzas de la selección de hexágonos en una "cáscara" a la vez), rompiendo los lazos eligiendo el más cercano a (1,0) (fuerzas de un sentido de paso constante en el nuevo shell). Distancia de la cuadrícula hexagonal se puede calcular usando la siguiente función:

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

Usted puede hacerlo mediante la simulación de direcciones. Si sus direcciones son "0 puntos", entonces se incrementan en 1 a medida que las agujas del reloj, lo siguiente debería hacer:

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

Me encantó @ manera de shura de abordar el problema, pero no pudo conseguir que el algoritmo exacto para el trabajo. También, estoy usando un espaciamiento 2x1 hexágono (donde x células están espaciados 2 aparte, y cada otro elemento X es oculto).

Esto es lo que me de trabajo (aunque 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
    }