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

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

(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