Algoritmo para la creación de células de espiral en el campo hexagonal
-
22-09-2019 - |
Pregunta
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!
Solución
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:
Otros consejos
(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 );
}
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.
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);
}
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
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
}