Efficient algorithm for finding which hexagon a point belongs to

Question

I'm trying to find a more efficient way of determining which hexagon a point belongs to from the following:

1. an array of points - for the sake of argument, 10000 points.
2. an array of center points of hexagons, approximately 1000 hexagons.
3. every point will belong to exactly one hexagon, some (most) hexagons will be empty.
4. The hexagons form a perfect grid, with the point of one hexagon starting in the top left corner (it will overlap the edge of the total area).

My current solution works, but is rather slow n * (m log m) I think, where n=length(points) and m=length(hexagons).

I suspect I can do much better than this, one solution that comes to mind is to sort (just once) both the points and the hexagons by their distance to some arbitrary point (perhaps the middle, perhaps a corner) then iterate over the points and over a subset of the hexagons, starting from the first hexagon whose distance to this point is >= to the last hexagon matched. Similarly, we could stop looking at hexagons once the distance difference between the (point -> ref point) and (hexagon center -> ref point) is larger than the "radius" of the hexagon. In theory, since we know that every point will belong to a hexagon, I don't even have to consider this possibility.

My question is: Is there a Much better way of doing it than this? In terms of complexity, I think it's worst case becomes marginally better n * m but the average case should be very good, probably in the region of n * 20 (e.g., we only need to look at 20 hexagons per point). Below is my current inefficient solution for reference.

points.forEach((p) => {
  p.hex = _.sortBy(hexes, (hex) => {
    const xDist = Math.abs(hex.middle.x - p.x);
    const yDist = Math.abs(hex.middle.y - p.y);
    return Math.sqrt((xDist * xDist) + (yDist * yDist));
  })[0];
});

Answer 1

For an arbitrary point, you can find the nearest hexagon center in two steps (assuming the same arrangement as that of Futurologist):

• divide the abscissa by the horizontal spacing between the centers, and round to the nearest integer.

• divide the ordinate by the half of the vertical spacing, and round to the nearest even or odd integer, depending on the parity found above.

• consider this center and the six ones around it, and keep the closest to the target point.

This gives you the indexes of the tile, in constant time.