title: Efficient algorithm for finding which hexagon a point belongs to
body: <p>I'm trying to find a more efficient way of determining which hexagon a point belongs to from the following:</p>
  
  <ol>
  <li>an array of points - for the sake of argument, 10000 points.</li>
  <li>an array of center points of hexagons, approximately 1000 hexagons.</li>
  <li>every point will belong to exactly one hexagon, some (most) hexagons will be empty. </li>
  <li>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).</li>
  </ol>
  
  <p>My current solution works, but is rather slow <code>n * (m log m)</code> I think, where <code>n=length(points)</code> and <code>m=length(hexagons)</code>.</p>
  
  <p>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.</p>
  
  <p>My question is: Is there a <em>Much</em> better way of doing it than this? In terms of complexity, I think it's worst case becomes marginally better <code>n * m</code> but the average case should be very good, probably in the region of <code>n * 20</code> (e.g., we only need to look at 20 hexagons per point). Below is my current inefficient solution for reference.</p>
  
  <pre><code>points.forEach((p) =&gt; {
    p.hex = _.sortBy(hexes, (hex) =&gt; {
      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];
  });
  </code></pre>