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

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:

enter image description here

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:

enter image description here

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:

enter image description here

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

enter image description here

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

enter image description here

    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.