title: Efficiently determining which grid square observations should belong to
body: <p>I have the following grid with bins defined by x and y, and each grid square given a unique id</p>
  
  <p><code>mapping = pd.DataFrame({'id': [1,2,3,4,5,6,7,8,9], 'x': [1,1,1,2,2,2,3,3,3], 'y': [1,2,3,1,2,3,1,2,3]})</code></p>
  
  <pre><code>   id  x  y
  0   1  1  1
  1   2  1  2
  2   3  1  3
  3   4  2  1
  4   5  2  2
  5   6  2  3
  6   7  3  1
  7   8  3  2
  8   9  3  3
  </code></pre>
  
  <p>I also have a new dataframe of observations for which I would like to know what their associated id should be (e.g. which grid square they fall into)</p>
  
  <p><code>coordinates = pd.DataFrame({'x': [1.4, 2.7], 'y': [1.9, 1.1]})</code></p>
  
  <pre><code>     x    y
  0  1.4  1.9
  1  2.7  1.1
  </code></pre>
  
  <p>My solution is the following function: </p>
  
  <pre><code>import bisect
  def get_id(coords, mapping):
  
      x_val = mapping.x[bisect.bisect_right(mapping.x, coords[0]) - 1]
      y_val = mapping.y[bisect.bisect_right(mapping.y, coords[1]) - 1]
      id = mapping[(mapping.x == x_val) &amp; (mapping.y == y_val)].iloc[0, 0]
      return id
  
  
  coordinates.apply(get_id, mapping = mapping, axis = 1)
  
  Out[21]: 
  0    1
  1    4
  dtype: int64
  </code></pre>
  
  <p>This works but becomes slow as the coordinates dataframe grows long. I'm sure there is a fast way to do this for a coordinates dataframe with 10^6 + observations. Is there a faster way to do this? </p>
  
  <p><strong>Edit:</strong>
  To answer @abdurrehman245 question from the comments below. 
  My current method is to simply round down any data point, this allows me to map it to an ID by using the mapping dataframe which contains the min entries (the bins) for any given ID. So <code>x=1.4 y=1.9</code> round to <code>x=1 y=1</code> which is mapped to <code>id=1</code> according to the <code>mapping</code>.</p>
  
  <p>Maybe this cartesian visualisation makes this a little bit more clear:</p>
  
  <pre><code>    Y
    4 -------------------------
      |   3   |   6   |   9   |
      |       |       |       |
    3 -------------------------
      |   2   |   5   |   8   |
      |       |       |       |
    2 -------------------------
      |   1   |   4   |   7   |
      |       |       |       |
    1 -------------------------  X
      1       2       3       4
  </code></pre>
  
  <p>I would also add that I could not use the floor function as the bins are not necessarily nice integers as in this example. </p>