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

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