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

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

La pregunta podría ser reformulada: dado cualquier x, y encontrar el hexágono cuyo centro es más cercano a x, y

Es decir, minimizar dist_squared (Hex[n].center, (x, y)) sobre n (al 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 para comprobar contra-podemos limitar a un máximo de 5 por el siguiente método:

Entonces, el primer paso es Expresar tu punto (x,y) en el espacio UV es decir, (x, y) = lambdaU + muV, so = (lambda, mu) en el espacio UV

Eso es solo una transformada de matriz 2D ( http://playtechs.blogspot.co.uk/2007/04/hex-grids.html podría ser útil si no entiendes las transformaciones lineales).

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

En todas partes dentro de los mapas Cuadrados Verdes de nuevo a (2,1)

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

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

De manera similar, algunos deberían devolver el hexágono # (3,1). Y luego en la esquina opuesta de ese paralelogramo verde, habrá 2 regiones más.

Así que resumen, si int(lambda,mu) = (p,q) entonces estamos probablemente en el interior del hexágono (p,q), pero también podríamos estar dentro de los hexágonos (p+1,q), (p,q+1), (p-1,p) o (p,q-1)

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

Pero resulta que puede reducir eso a ~50% del tiempo sin comprobaciones de distancia, ~25% del tiempo haciendo una comprobación de distancia, y el restante ~25% del tiempo haciendo 2 comprobaciones de distancia (supongo que los números mirando las áreas en las que funciona cada comprobació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 que 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.

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

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

Puede 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);

Use esto

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 ser directamente abajo (0, 0).

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

Las siguientes ecuaciones map (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 gran inconveniente...

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

Esto también sucede cuando se usan coordenadas cúbicas:

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

Algunas observaciones clave aquí sin embargo...

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

2. En coordenadas cúbicas, los centros hexadecimales válidos tienen u + v + w = 0

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

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

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

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

Después de encontrar la coordenada 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};

}

He tenido otra mirada en http://playtechs.blogspot.co.uk/2007/04/hex-grids.html y es muy ordenado matemáticamente.

Sin embargo, el enfoque de Sebastian parece ir al grano, y lograr la tarea en muy pocas líneas de código.

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

Voy a reprender que aquí para 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

No sé si va a ayudar a alguien, pero se me ha ocurrido una solución mucho más simple. Cuando creo mi hexágono im solo les da un punto medio y al encontrar el punto medio más cercano con la coordenada del ratón que puedo encontrar uno im en!