Hexagonal Grids, how do you find which hexagon a point is in?

I have a开发者_如何学Python 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

---

(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

---

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.

---

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

}

---

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

---

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

---

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 !

---

I found a different way to see if the mouse is in a hexagon. Using a bit of trig you can find the angle of the line between the mouse and the centre of the hexagon, using this angle you can work out how long the line would be from the centre of the hexagon to the edge of the hexagon at that angle. Then just check the length of the line between the mouse is less than the expected length to the edge of the hexagon. If anyone wants an example code i can share.

---

I know this is remarkably late, but I'm working with a hexagon grid currently and was trying to find the solution this problem. The heavy math methods seems overkill to me, but I understood why and how they worked. By almost accident I found a super simple solution, which can be accomplished in a few lines of code.

In my example, I have a custom Hexagon class that contains a member Point variable that stores (x, y) of the center of the hexagon. I then calculate and draw the hexagon based on this center value.

Each Hexagon class also is attached to a Tile class which stores a row, and col variable (given when the grid is drawn).

Variables required: - Radius - Grid row - Grid col - Hexagon Center point - Mouse click point(or other given point) - List of tiles / hexagons

My mouseListener:

addMouseListener(new MouseAdapter() {
        @Override
        public void mouseClicked(MouseEvent e) {
            super.mouseClicked(e);
            System.out.println("Mouse Click Registered");
            double closestDistance = Double.MAX_VALUE;
            int closestIndex = -1;
            for (int i = 0; i < tiles.size(); i++) {
                double distance = tiles.get(i).getDistance(new myPoint(e.getX(), e.getY()));
                if (distance < closestDistance) {
                    closestDistance = distance;
                    if (closestDistance <= radius) {
                        closestIndex = i;
                    }
                }
            }
            if (closestIndex > -1) {
                Tile t = tiles.get(closestIndex);
                System.out.println("Selected tile: " + t.getCol() + ", " + t.getRow());
            }
        }
    });

My calculation performed from Tile class:

public double getDistance(myPoint p) {
    myPoint center = this.hexagon.getCenter();
    double xd = center.x - p.x;
    double yd = center.y - p.y;
    return Math.abs(Math.sqrt((xd * xd) + (yd * yd)));
}

What this does. Goes through the list of hexagons on the map, calculates the absolute value of the distance from the specified point and the hexagon center point. If the distance is less than the previously calculated distance, sets that value as the lowest. If that number is less than the radius, sets the closestIndex to that index #. Continues until end of tiles loop.

After loop, verifies that value index was saved, if so, selects that index.

NOTE: This could probably be further optimized by calculating the row/col from specified point. With that information you could limit the amount of tiles you are looping through to the tiles sounding that point.

---

This is similar to other answers, but I think a cleaner implementation. It is mostly based on Amit's guide.

Note that the northeast corner does give a false result like the one described by P i.

I use cube coordinates. Part of the secret is cube-round, which takes a float result and rounds to the nearest hex.

I find these kinds of things easier to achieve with matrices. First we multiply by a skew and scale matrix, which gives us floating axial hex coordinates, and then we round that down to find the actual hex. size corresponds to the cell radius.

Here it is in Parenscript:

    (defmacro cube-round (coord)
      ;; round cube coordinates
      `(let* ((x (@ ,coord 0))
              (y (@ ,coord 1))
              (z (@ ,coord 2))
              ;; rounded components - used in calculations
              (rx (round x))
              (ry (round y))
              (rz (round z))
              ;; get the differential of each component
              (diffx (abs (- rx x)))
              (diffy (abs (- ry y)))
              (diffz (abs (- rz z))))
         ;; at this point coordinates might not add up to 1 (which is required by cube coordinates). Find the component that changed the most, and reset it to -1 * (ra + rb).
         (if (> diffx diffy diffz)
             ;; x was largest - reset it
             (setf rx (* -1 (+ ry rz)))
             (if (> diffy diffz)
                 ;; y was largest
                 (setf ry (* -1 (+ rx rz)))
                 ;; z was largest
                 (setf rz (* -1 (+ rx ry)))))
         ;; return final vector
         (make-vec3 (list rx ry rz))))

    (defmacro pixel-to-cube (coord size)
      (let ((sqrt3 (sqrt 3.0)))
        `(let* ((c ,coord)
                ;; skew+scale matrix for mapping pixel to axial coordinates [[sqrt(3)/3/size, -1/3/size], [0, 2/3/size]]
                (m (make-mat2 (list
                               (/ (/ ,sqrt3 3.0) ,size) (/ (/ -1 3.0) ,size)
                               0 (/ (/ 2 3.0) ,size))))
                (axial-coords (vec2-mat-mul m c))
                (q (@ axial-coords 0))
                (r (@ axial-coords 1))
                ;; make cube float coordinates from axial - make z = -1 * (x + y)
                (cube-float (make-vec3-float
                             (list q r (* -1 (+ q r))))))
           ;; finally, round coordinates to snap to a cell
           (cube-round cube-float))))