title: Geohash bounding box search
body: <p>I want to do a bounding box query a Trie of geohashed strings where the points lie all around the center of the space. I can't seem to find a good way to query the trie when the points straddle the center point.</p>
  
  <p>Say you have 4 bits per coordinate (8 total) of information on a 16x16 space where each box is 1x1. Essentially, a 16x16 grid.</p>
  
  <p>The red line shows the most corse division of the quad tree which is used in the geohash.</p>
  
  <p><img src="https://i.stack.imgur.com/5guXg.png" alt="Example image"></p>
  
  <p>Trie representing the graphic above.</p>
  
  <pre><code>bits=4, min=0, max=16, numBuckets=16.0, scaling=1.0, tree={
  └── null
      ├── 0
      │   ├── (0110100) 00110100 = {(6, 6), hash=00110100}
      │   └── (1100000) 01100000 = {(6, 8), hash=01100000}
      └── 1
          ├── (0010101) 10010101 = {(8, 7), hash=10010101}
          └── (1000010) 11000010 = {(9, 8), hash=11000010}
  </code></pre>
  
  <p>A bounding box query is defined as a upper-left point and a length, width.
  e.g. (6,6 4x4) Should return 6,6 6,8 8,7 and 9,8.</p>
  
  <p>One approach I thought of is: Start from the most precise box containing the upper-left coordinate and keep getting less precise until I can cover the 4x4 square. But if I do that  I end up querying the whole tree in this example. I just don't see a "better" way to do it.</p>