algorithm - para - incompetech graph paper hexagonal

Rejillas hexagonales, ¿cómo encuentras en qué hexágono está un punto?

Question

Tengo un mapa formado por filas y columnas de hexágonos.

Esta no es una imagen real del mapa hexadecimal que estoy usando, pero usa hexágonos del mismo tamaño y forma

Necesito poder decir cuál es el mouse cuando el usuario hace clic,

Cada hexágono está representado por una instancia de una clase "Azulejo", sin embargo, esto no contiene ningún dato de ubicación específica, ni siquiera un polígono, por lo que básicamente la única forma de saber dónde está un hexágono en particular es conocer su posición en Matriz 2D

He usado una cuadrícula cuadrada antes, y fue relativamente fácil averiguar qué cuadrado se seleccionó, porque los píxeles también son cuadrados,

 // example where each square is 10 by 10 pixels:
private void getClickedSquare(MouseEvent me)
{
int mouseX = me.getX();// e.g. 25
int mouseY = me.getY();// e.g. 70
int squareX= (int) (mouseX / 10);// in this case 2
int squareY= (int) (mouseY / 10);// in this case 7
//then to access the tile I would do
map.squares[squareX][squareY].whatever();
}

Pero ni siquiera estoy seguro de por dónde empezar con Hexágonos, ¿alguien tiene alguna experiencia?

No puedo usar polígonos (Java), ya que cuando muevo el mapa en la pantalla y, al aumentar su tamaño, tengo problemas para actualizar grandes cantidades de polígonos en cada cuadro. ¡Aunque entonces solo pude verificar si un punto está incluido en alguno de los polígonos del mosaico del mapa!

En el momento en que los hexágonos mostrados son solo BufferedImages.

Si desea saber más información, pregunte, gracias por su tiempo: D

Answer 1

(ACTUALIZADO: código refactorizado para que sea más comprensible y más eficiente) (ACTUALIZADO: longitud de respuesta reducida, errores corregidos en el código, calidad mejorada de las imágenes)

Esta imagen muestra la esquina superior izquierda de una cuadrícula hexagonal y superpuesta es una cuadrícula azul cuadrada. Es fácil encontrar en cuál de los cuadrados hay un punto dentro y esto daría una aproximación aproximada de qué hexágono también. Las partes blancas de los hexágonos muestran donde la cuadrícula y la cuadrícula hexagonal comparten las mismas coordenadas y las partes grises de los hexágonos muestran donde no lo hacen.

La solución ahora es tan simple como encontrar en qué cuadro se encuentra un punto, luego verificar si el punto está en alguno de los triángulos y corregir la respuesta si es necesario.

private final Hexagon getSelectedHexagon(int x, int y)
{
// Find the row and column of the box that the point falls in.
int row = (int) (y / gridHeight);
int column;
boolean rowIsOdd = row % 2 == 1;
// Is the row an odd number?
if (rowIsOdd)// Yes: Offset x to match the indent of the row
column = (int) ((x - halfWidth) / gridWidth);
else// No: Calculate normally
column = (int) (x / gridWidth);

En este punto tenemos la fila y la columna de la caja en la que está nuestro punto, luego debemos probar nuestro punto contra los dos bordes superiores del hexágono para ver si nuestro punto se encuentra en alguno de los hexágonos de arriba:

 // Work out the position of the point relative to the box it is in
double relY = y - (row * gridHeight);
double relX;
if (rowIsOdd)
relX = (x - (column * gridWidth)) - halfWidth;
else
relX = x - (column * gridWidth);

Tener coordenadas relativas facilita el siguiente paso.

Al igual que en la imagen de arriba, si la y de nuestro punto es > mx + c , sabemos que nuestro punto se encuentra sobre la línea y, en nuestro caso, el hexágono arriba y a la izquierda de la fila y columna actuales. Tenga en cuenta que el sistema de coordenadas en java tiene y comenzando en 0 en la parte superior izquierda de la pantalla y no en la parte inferior izquierda como es habitual en matemáticas, de ahí el gradiente negativo utilizado para el borde izquierdo y el gradiente positivo utilizado para la derecha.

 // Work out if the point is above either of the hexagon''s top edges
if (relY < (-m * relX) + c) // LEFT edge
{
row--;
if (!rowIsOdd)
column--;
}
else if (relY < (m * relX) - c) // RIGHT edge
{
row--;
if (rowIsOdd)
column++;
}
return hexagons[column][row];
}

Una explicación rápida de las variables utilizadas en el ejemplo anterior:

m es el gradiente, entonces m = c / halfWidth

Answer 2

Comencé mirando la respuesta de @pi https://.com/a/23370350/5776618 y pensé que sería interesante probar algo similar en coordenadas de cubo con espacio UVW (en lugar de 2D, axial, UV -espacio).

El siguiente mapa de ecuaciones (x, y) => (u, v, w)

u = (2/3)*x;
v = -(1/3)*x + (1/2)*y;
w = -(1/3)*x - (1/2)*y;

Entonces es tan simple como redondear u, v, y w al entero más cercano y convertir de nuevo a x, y . Sin embargo, hay un obstáculo importante ...

En la respuesta anterior, se observa que el redondeo en el espacio UV tendrá algunas áreas que se asignan incorrectamente:

Esto también sucede cuando se usan coordenadas de cubo:

Cualquier área en los triángulos anaranjados es> 0.5 unidades desde el centro del hexágono y cuando se redondea se redondea LEJOS desde el centro. Esto se muestra arriba, ya que cualquier cosa en el triángulo rojo (a la izquierda de la línea u = 1.5) tendrá u redondeada incorrectamente a u = 1 en lugar de u = 2.

Algunas observaciones clave aquí sin embargo ...

1. Las áreas problemáticas de color naranja / rojo no se superponen

2. En coordenadas de cubo, los centros hexadecimales válidos tienen u + v + w = ​​0

En el código a continuación, u, v y w, se redondean desde el principio como redondeo solo en un problema si las coordenadas redondeadas no suman cero.

uR = Math.round(u);
vR = Math.round(v);
wR = Math.round(w);

Si estos no suman cero, ya que las áreas problemáticas no se superponen, solo habrá 1 coordenada que se redondee incorrectamente. Esta coordenada es también la que más se redondea.

arr = [ Math.abs(u-uR), Math.abs(v-vR), Math.abs(w-wR) ];
var i = arr.indexOf(Math.max(...arr));

Una vez que se encuentra la coordenada del problema, se redondea en la otra dirección. El final (x, y) se calcula a partir de redondeado / corregido (u, v, w).

nearestHex = function(x,y){
u = (2/3)*x;
v = -(1/3)*x + (1/2)*y;
w = -(1/3)*x - (1/2)*y;
uR = Math.round(u);
vR = Math.round(v);
wR = Math.round(w);
if(uR+vR+wR !== 0){
arr = [ Math.abs(u-uR), Math.abs(v-vR), Math.abs(w-wR) ];
var i = arr.indexOf(Math.max(...arr));
switch(i){
case 0:
Math.round(u)===Math.floor(u) ? u = Math.ceil(u) : u = Math.floor(u);
v = vR; w = wR;
break;
case 1:
Math.round(v)===Math.floor(v) ? v = Math.ceil(v) : v = Math.floor(v);
u = uR; w = wR;
break;
case 2:
Math.round(w)===Math.floor(w) ? w = Math.ceil(w) : w = Math.floor(w);
u = uR; v = vR;
break;
}
}
return {x: (3/2)*u, y: v-w};
}

Answer 3

EDITAR: esta pregunta es más difícil de lo que pensé al principio, reescribiré mi respuesta con algo de trabajo, sin embargo, no estoy seguro de si la ruta de la solución es una mejora en las otras respuestas.

La pregunta podría reformularse: dada cualquier x, y encuentra el hexágono cuyo centro está más cerca de x, y

es decir, minimizar dist_squared (Hex [n] .center, (x, y)) sobre n (cuadrado significa que no necesita preocuparse por las raíces cuadradas, lo que ahorra algo de CPU)

Sin embargo, primero debemos reducir el número de hexágonos contra los que se puede verificar: podemos reducirlo a un máximo de 5 mediante el siguiente método:

Entonces, el primer paso es Expresar su punto (x, y) en el espacio UV, es decir (x, y) = lambda U + mu V, entonces = (lambda, mu) en el espacio UV

Eso es solo una transformación de matriz 2D ( http://playtechs.blogspot.co.uk/2007/04/hex-grids.html puede ser útil si no comprende las transformaciones lineales).

Ahora, dado un punto (lambda, mu), si redondeamos ambos al entero más cercano, tenemos esto:

En todos los lugares dentro de la Plaza Verde los mapas vuelven a (2,1)

Así que la mayoría de los puntos dentro de esa Plaza Verde serán correctos, es decir, están en hexágono (2,1)

Pero algunos puntos deberían devolver el hexágono # (2,2), es decir:

Del mismo modo, algunos deben devolver hexágono # (3,1). Y luego, en la esquina opuesta de ese paralelogramo verde, habrá 2 regiones más.

Entonces, para resumir, si int (lambda, mu) = (p, q) entonces probablemente estemos dentro del hexágono (p, q) pero también podríamos estar dentro de hexágonos (p + 1, q), (p, q + 1) , (p-1, q) o (p, q-1)

Varias maneras de determinar cuál de estos es el caso. Lo más fácil sería convertir los centros de todos estos 5 hexágonos de nuevo al sistema de coordenadas original, y encontrar cuál es el más cercano a nuestro punto.

Pero resulta que puede reducirlo hasta ~ 50% del tiempo sin realizar verificaciones de distancia, ~ 25% del tiempo haciendo una verificación de distancia, y el restante ~ 25% del tiempo haciendo 2 verificaciones de distancia (supongo los números mirando las áreas en las que trabaja cada verificación):

p,q = int(lambda,mu)
if lambda * mu < 0.0:
// opposite signs, so we are guaranteed to be inside hexagon (p,q)
// look at the picture to understand why; we will be in the green regions
outPQ = p,q

else:
// circle check
distSquared = dist2( Hex2Rect(p,q), Hex2Rect(lambda, mu) )
if distSquared < .5^2:
// inside circle, so guaranteed inside hexagon (p,q)
outPQ = p,q

 else:
if lambda > 0.0:
candHex = (lambda>mu) ? (p+1,q): (p,q+1)
else:
candHex = (lambda<mu) ? (p-1,q) : (p,q-1)

Y esa última prueba puede ser ordenada:

 else:
// same sign, but which end of the parallelogram are we?
sign = (lambda<0) ? -1 : +1
candHex = ( abs(lambda) > abs(mu) ) ? (p+sign,q) : (p,q+sign)

Ahora lo hemos reducido a otro hexágono posible, solo tenemos que encontrar cuál está más cerca:

 dist2_cand = dist2( Hex2Rect(lambda, mu), Hex2Rect(candHex) )
outPQ = ( distSquared < dist2_cand ) ? (p,q) : candHex

Una función Dist2_hexSpace (A, B) ordenaría las cosas aún más.

Answer 4

Esta es una adición a la respuesta de Sebastian Troy. Lo dejaría como un comentario, pero todavía no tengo suficiente reputación.

Si desea implementar un sistema de coordenadas axiales como se describe aquí: redblobgames.com/grids/hexagons

Puedes hacer una ligera modificación al código.

En lugar de

// Is the row an odd number?
if (rowIsOdd)// Yes: Offset x to match the indent of the row
column = (int) ((x - halfWidth) / gridWidth);
else// No: Calculate normally
column = (int) (x / gridWidth);

utilizar esta

float columnOffset = row * halfWidth;
column = (int)(x + columnOffset)/gridWidth; //switch + to - to align the grid the other way

Esto hará que la coordenada (0, 2) esté en la misma columna diagonal que (0, 0) y (0, 1) en lugar de estar directamente debajo (0, 0).

Answer 5

He echado otro vistazo a http://playtechs.blogspot.co.uk/2007/04/hex-grids.html y está muy ordenado matemáticamente.

Sin embargo, el enfoque de Sebastian parece cortar a la persecución y cumplir la tarea en muy pocas líneas de código.

Si lees la sección de comentarios, puedes encontrar que alguien ha escrito una implementación de Python en http://gist.github.com/583180

Repasaré eso aquí por la posteridad:

# copyright 2010 Eric Gradman
# free to use for any purpose, with or without attribution
# from an algorithm by James McNeill at
# http://playtechs.blogspot.com/2007/04/hex-grids.html
# the center of hex (0,0) is located at cartesian coordinates (0,0)
import numpy as np
# R ~ center of hex to edge
# S ~ edge length, also center to vertex
# T ~ "height of triangle"
real_R = 75. # in my application, a hex is 2*75 pixels wide
R = 2.
S = 2.*R/np.sqrt(3.)
T = S/2.
SCALE = real_R/R
# XM*X = I
# XM = Xinv
X = np.array([
[ 0, R],
[-S, S/2.]
])
XM = np.array([
[1./(2.*R), -1./S],
[1./R, 0. ]
])
# YM*Y = I
# YM = Yinv
Y = np.array([
[R, -R],
[S/2., S/2.]
])
YM = np.array([
[ 1./(2.*R), 1./S],
[-1./(2.*R), 1./S],
])
def cartesian2hex(cp):
"""convert cartesian point cp to hex coord hp"""
cp = np.multiply(cp, 1./SCALE)
Mi = np.floor(np.dot(XM, cp))
xi, yi = Mi
i = np.floor((xi+yi+2.)/3.)
Mj = np.floor(np.dot(YM, cp))
xj, yj = Mj
j = np.floor((xj+yj+2.)/3.)
hp = i,j
return hp
def hex2cartesian(hp):
"""convert hex center coordinate hp to cartesian centerpoint cp"""
i,j = hp
cp = np.array([
i*(2*R) + j*R,
j*(S+T)
])
cp = np.multiply(cp, SCALE)
return cp

Answer 6

No sé si va a ayudar a alguien, pero he encontrado una solución mucho más simple. Cuando creo mi imagen de Hexagon, les doy un punto medio y, al encontrar el punto medio más cercano con la coordenada del ratón, ¡puedo encontrar cuál de ellos está encendido!