Hexagonal Grids, how do you find which hexagon a p

Question

I have a map made up of rows and columns of hexagons

This isn't an actual image of the hex-map I am using, but uses the same size and shape hexagons

I need to be able to tell which one the mouse is over when the user clicks,

Each Hexagon is represented by an instance of a "Tile" class, however this doesn't hold any location specific data, or even a polygon, so basically the only way to tell where a particular hexagon is, is to know it's position in the 2D array.

I have used a square grid before, and it was relatively easy to figure out which square was selected, because pixels are also square,

        // 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();
    }

But I'm not even sure where to start with Hexagons, does anyone have any experience?

I cannot use polygons (Java), as when I get onto moving the map around on screen, and increasing it's size I'll run into problems with updating vast amounts of polygons each frame. Although then I could just check to see if a point is included in any of the map's tile's polygons!

At the moment the hexagons displayed are just BufferedImages.

If you want to know any more information please ask, Thanks for your time :D

Answer 1

EDIT: this question is more difficult than I thought at first, I will rewrite my answer with some working, however I'm not sure whether the solution path is any improvement on the other answers.

The question could be rephrased: given any x,y find the hexagon whose centre is closest to x,y

i.e. minimise dist_squared( Hex[n].center, (x,y) ) over n (squared means you don't need to worry about square roots which saves some CPU)

However, first we should narrow down the number of hexagons to check against -- we can narrow it down to a maximum of 5 by the following method:

So, first step is Express your point (x,y) in UV-space i.e. (x,y) = lambdaU + muV, so = (lambda, mu) in UV-space

That's just a 2D matrix transform (http://playtechs.blogspot.co.uk/2007/04/hex-grids.html might be helpful if you don't understand linear transforms).

Now given a point (lambda, mu), if we round both to the nearest integer then we have this:

Everywhere within the Green Square maps back to (2,1)

So most points within that Green Square will be correct, i.e. They are in hexagon (2,1).

But some points should be returning hexagon # (2,2), i.e:

Similarly some should be returning hexagon # (3,1). And then on the opposite corner of that green parallelogram, there will be 2 further regions.

So to summarise, if int(lambda,mu) = (p,q) then we are probably inside hexagon (p,q) but we could also be inside hexagons (p+1,q), (p,q+1), (p-1,q) or (p,q-1)

Several ways to determine which of these is the case. The easiest would be to convert the centres of all of these 5 hexagons back into the original coordinate system, and find which is closest to our point.

But it turns out you can narrow that down to ~50% of the time doing no distance checks, ~25% of the time doing one distance check, and the remaining ~25% of the time doing 2 distance checks (I'm guessing the numbers by looking at the areas each check works on):

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)

And that last test can be tidied up:

     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)

Now we have narrowed it down to one other possible hexagon, we just need to find which is closer:

        dist2_cand = dist2( Hex2Rect(lambda, mu), Hex2Rect(candHex) )

        outPQ = ( distSquared < dist2_cand ) ? (p,q) : candHex

A Dist2_hexSpace(A,B) function would tidy things up further.

Answer 2

I've had another look at http://playtechs.blogspot.co.uk/2007/04/hex-grids.html and it is very tidy mathematically.

However Sebastian's approach does seem to cut to the chase, and accomplish the task in remarkably few lines of code.

If you read through the comments section you can find that someone has written a Python implementation at http://gist.github.com/583180

I will repaste that here for posterity:

# 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 3

I dont know if it's going to help anyone but i have come up with a much simpler solution. When i create my Hexagon im just giving them a middle point and by finding the closest middle point with the mouse coordonate i can find wich one im on !

Answer 4

I started out by looking at @pi 's answer https://stackoverflow.com/a/23370350/5776618 and thought it would be interesting to try something similar in cube coordinates with UVW-space (rather than the 2D, axial, UV-space).

The following equations map (x,y) => (u,v,w)

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

Then it's as simple as rounding u, v, and w to the nearest integer and converting back to x,y. However there is a major snag...

In the answer above, it's noted that rounding in UV-space will have a few areas that map incorrectly:

This still happens when using cube coordinates as well:

Any area in the orange triangles is >0.5 units from the center of the hexagon and when rounded will round AWAY from the center. This is shown above as anything in the red triangle (to the left of the u=1.5 line) will have u rounded incorrectly to u=1 rather than u=2.

Some key observations here though...

1. The orange/red problem areas are non-overlapping

2. In cube coordinates, valid hex centers have u + v + w = 0

In the below code, u, v, and w, are all rounded from the start as rounding in only an issue if the rounded coordinates do not sum to zero.

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

If these do not sum to zero, because the problem areas are non-overlapping, there will be only 1 coordinate that is rounded incorrectly. This coordinate is also the coordinate that was rounded the most.

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

After the problem coordinate is found, it is rounded in the other direction. The final (x,y) are then calculated from rounded/corrected (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 5

This is an addendum to SebastianTroy's answer. I would leave it as a comment but I don't enough reputation yet.

If you want to implement an axial coordinate system as described here: http://www.redblobgames.com/grids/hexagons/

You can make a slight modification to the code.

Instead of

// 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 this

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

This will make the coordinate (0, 2) be on the same diagonal column as (0, 0) and (0, 1) instead of being directly below (0, 0).

Answer 6

(UPDATED: Refactored code to make more understandable and more efficient) (UPDATED: Reduced answer length, fixed bugs in code, improved quality of images)

This image shows the top left corner of a hexagonal grid and overlaid is a blue square grid. It is easy to find which of the squares a point is inside and this would give a rough approximation of which hexagon too. The white portions of the hexagons show where the square and hexagonal grid share the same coordinates and the grey portions of the hexagons show where they do not.

The solution is now as simple as finding which box a point is in, then checking to see if the point is in either of the triangles, and correcting the answer if necessary.

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

At this point we have the row and column of the box our point is in, next we need to test our point against the two top edges of the hexagon to see if our point lies in either of the hexagons above:

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

Having relative coordinates makes the next step easier.

Like in the image above, if the y of our point is > mx + c we know our point lies above the line, and in our case, the hexagon above and to the left of the current row and column. Note that the coordinate system in java has y starting at 0 in the top left of the screen and not the bottom left as is usual in mathematics, hence the negative gradient used for the left edge and the positive gradient used for the right.

    // 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];
}

---

A quick explanation of the variables used in the above example:

m is the gradient, so m = c / halfWidth