25

I have points with a given latlong and a distance around them - e.g. { 40.6826048,-74.0288632 : 20 miles, 51.5007825,-0.1258957 : 100 miles}. If I pick a fixed geohash length (say equals to ~ 1x1mile) how can I find all the geohash entries of that length that are with the given radius from each point?

To add some background - the reason I want to do that is so I can save a cache keyed by the geohash id with a value of the list of points for which the given geohash is within radius (and also matches some custom eligibility rules). Then I can do a quick lookup for a user's location geohash to find all the eligible points around them.

naumcho
  • 18,671
  • 14
  • 48
  • 59

2 Answers2

62

This is how I would try to do:

Input: Point of interest(lat, long), Query Radius

Step 1: Find the 'MINIMUM' BOUNDING RECTANGLE(MBR) which completely contains the QUERY CIRCLE

Step 2: To create the minimum bounding rectangle, first calculate its minimum and maximum lat, long using the input parameters. Please refer to section 3.1 and 3.3 of Computing the Minimum and Maximum Latitude Longitude – the Correct Way

Step 3: Using (minLat, minLon), (maxLat, maxLon) calculate the four corners of the MBR NorthWest(maxLat, minLon), SouthWest(minLat, minLon), SouthEast(minLat, maxLon), NorthEast(maxLat, maxLon)

Step 4: Calculate the GeoHash of all four corners of MBR

Ex: for a point in NYC, say (40.75798, -73.991516), distance: 800 Meters and GeoHash length: 12

  • NorthWest : dr5ruj4477kd
  • SouthWest : dr5ru46ne2ux
  • SouthEast : dr5ru6ryw0cp
  • NorthEast : dr5rumpfq534

Step 5: From these GeoHashes, calculate the Query Bounding Box(MBR) Prefix: dr5ru

This would give you the coarser GeoHash which completely contains our MBR and hence the query region. In other words, all points indexed by dr5ru, yielding with 32 GeoHashes from dr5ru0 - dr5ruz

Final Step:

To find the exact grids (or) GeoHashes that correspond to our Query Circle(Square(MBR) to be precise), we should pick from these 32 GeoHashes by representing a recurring (4X8) Matrix using 2D Array.

In our example: we get dr5ru + J, M, H, K, 5, 7, 4, 6. All these GeoHashes represent the points that are within 800 meters from the Central Query Point, Except very few GeoHashes, which could not be avoided, because of considering MBR instead of a perfect circle.

THE OVERALL PROCESS IN A SINGLE GIF: (Step 1- 5)

Overall Process

FINAL STEP:

GeoHash

Important: Please find the use of 4 x 8 Grid for GeoHash. It varies for each character along the length of GeoHash. For ODD lengths it is 8 x 4, for even its transpose 4 X 8. In our case, we are inside dr5ru(5 + 1, 6th resolution) and hence we use 4 X 8

Hariharan Gandhi
  • 1,174
  • 9
  • 19
  • 1
    Hi @naumcho did u find this answer helpful ? is this what u wr looking for ? or this far from what u asked.. any update ? – Hariharan Gandhi Apr 23 '16 at 17:12
  • ObjC - Sample code https://gist.github.com/johndpope/180e63f45f90dc5824e800e4324c8343 – johndpope Dec 15 '16 at 20:39
  • @HariharanGandhi - Can you please explain , step 4 and final step in bit more detail, I am trying to implement this in python and I understood that, we find four corner geohashes, of MBR. But, I am not clear about 4 x 8 matrix and how to calculate the geohashes inside this. Suppose, if I want to find all 30 bit geohashes that fall under this MBR, how would I do that. – Seja Nair Mar 01 '17 at 11:36
  • @seja-nair - with step 4, we have Geohash of all four corners. The common prefix out of these four hashes, `dr5ru` gives the coarser MBR - represented by the red color in the [final step image](https://i.stack.imgur.com/AIoy3.png). Now we increase precision by one more character, then `dr5ru` has 32 boxes from `dr5ru0` - `dr5ruz` – Hariharan Gandhi Mar 10 '17 at 23:34
  • From this image, out of the region in red, we need to find a smallest rectangle that **just** covers the circles - this is represented by the green region within the red region. This is not completely perfect as we have four corners of noise outside the yellow circle & within the green. ``` - NorthWest : dr5ru j4477kd - SouthEast : dr5ru 6ryw0cp ``` The next character I has a 2D array with elements in the Z-order. I need In our example - `dr5ru + J, M, H, K, 5, 7, 4, 6` – Hariharan Gandhi Mar 11 '17 at 00:43
  • Out of red region 4m this image, we need to find a smallest rectangle that **just** covers the circle. this is represented by the green region within the red region. This is not completely perfect as we have 4 corners of noise outside the yellow circle & within the green. - I had a 2D array with elements(from 0 to z) in Z-order(geohash character @ even 4X8 | odd 8X4 ). The next character for the diagonal - NorthWest : `dr5ru j4477kd` | SouthEast : `dr5ru 6ryw0cp` is `j` & `6` respectively. We need all boxes between `J` to `6` - `dr5ru + J, M, H, K, 5, 7, 4, 6`. This gives the green box – Hariharan Gandhi Mar 11 '17 at 00:59
  • We need to take care while creating 2D array. The Z-order actually alternates for each character of Geohash between 'Z' & 'N' order. With image in final step we r looking into a zoom of `dr5r` - 4th character -even - 8rowsX4columns. Note that G-U-V are in same row. But if u increase one char & look at `dr5ru` (the red region) G-U-V are **not** in same row but same column. – Hariharan Gandhi Mar 11 '17 at 01:15
  • @seja-nair - Check [Fig-1](https://www.ibm.com/developerworks/library/ba-mine-spatial-data-spss-r/#fig1) order 1 - odd - in `Z` order - 8X4. Now check [Fig-2](https://www.ibm.com/developerworks/library/ba-mine-spatial-data-spss-r/#fig2) order 2 - even - in `N` order - 4 X 8. Hope this helps! – Hariharan Gandhi Mar 11 '17 at 01:15
  • @HariharanGandhi - I understood it better . Just one more clarification . When I am increasing my radius to 3km from 800ms , I am getting NW 'dr7252xj7tvv' , NE 'dr72j0dvmtzv' , SW 'dr5reqz57wmu' , SE 'dr5rtnfgmwru' . So, how many possible geohashes will fall under the smallest bounding box ? – Seja Nair Mar 15 '17 at 09:04
  • What happens when the vertices of your MBR, even if they are very close, don't share a common prefix or barely share 3 chars? – rogamba Apr 20 '17 at 23:35
  • I have the same question as the previous comment. What happens if the 4 corners of the MBR only have 2 characters in common ? Im doing the following search - 37.7,-122.4, 20 miles -> And my geohashes are (NW,NE,SW,SE) 9q8zf, 9q9pf, 9q8y4,9q9n4. How do i create the range search now ? – kbinstance Aug 23 '18 at 20:44
  • @roGamba Isn't the Final Step exactly answering what you want? The length of the prefix has no impact on the this method. If the prefix is shorter the area is larger. The steps are still the same. >> don't share a common prefix - this can never happen :P The prefix `dr5ru` means that the circle and its MBR is completely within the segment `u` of `dr5r`. Now within `u` we calculate the segments that includes the MBR and neglects the rest - This is explained in the Final Step. – Hariharan Gandhi Aug 24 '18 at 10:52
  • @kbinstance please check prev comment – Hariharan Gandhi Aug 24 '18 at 10:53
  • 1
    @HariharanGandhi The following are the geohashes for my MBR - Nw- bunkv0ns39d4 ne - ch1szbhsq9d6 sw- bgy6t0ww3w6j se- c5cdxbswqw6m This is from point 67.436378,-134.887902 with a radius search of 5000 meters (approx 3 miles) I was trying to do a search for this point. Hence asked about the case where the bounds dont have common prefix. What do I do for such cases ? – kbinstance Aug 24 '18 at 21:20
  • @kbinstance valid point. I'll check how this case is covered once I reach home – Hariharan Gandhi Aug 25 '18 at 23:32
  • @HariharanGandhi - Any update on this ? Im not sure how to solve this issue. I wonder how Lucene or any of the databases that support geoSpatial queries solve this (like maybe mongo or oracle or postgres ? ) – kbinstance Sep 08 '18 at 00:16
  • i dont understand te 4X8 and 8X4 part here. can someone clear this? – krithikaGopalakrishnan Sep 26 '18 at 11:39
7

Have a look at this -> ProximityHash.

ProximityHash generates a set of geohashes that cover a circular area, given the center coordinates and the radius. It also has an additional option to use GeoRaptor that creates the best combination of geohashes across various levels to represent the circle, starting from the highest level and iterating till the optimal blend is brewed. Result accuracy remains the same as that of the starting geohash level, but data size reduces considerably, thereby improving speed and performance.

Ashwin Nair
  • 129
  • 1
  • 7
  • 1
    You should at least explain the quintessence of the linked document here to not enforce everyone here having to visit that link. Not to mention the link might be dead some time. – Markus Jun 12 '17 at 08:56
  • @Markus This was basically a pretty straight solution to the question - "Finding geohashes of certain length within radius from a point". So, did not feel the need. Also, I am pretty new to answering here :) Didn't know it was important. Will make sure to add a brief now on. – Ashwin Nair Jun 12 '17 at 14:43
  • That's not a big deal, it's just to ensure that quintessence is conserved here. :) Maybe this [guide](https://stackoverflow.com/help/how-to-answer) helps you in further improving your answers. – Markus Jun 12 '17 at 18:44
  • Am I right in thinking this lists the squares where the centre is within the circle, rather than those that have any overlap with the circle? Also, I think there are situations away from the equator where your bounding box should be larger than the diameter at the centre of your circle. – Neil Jul 02 '20 at 15:14
  • This library's algorithm seems flawed due to the assumption that the geohash grid [box sizes are constant](https://github.com/ashwin711/proximityhash/blob/a1c3b253b5f6acc8a3647b66a992b277554f3e3e/proximityhash.py#L51), though in fact they vary greatly in size due to the curvature of the earth. Assuming all else is sound, this algorithm should produce accurate results near the equator, with decreasing accuracy approaching the poles. – Stiggler Mar 24 '21 at 15:11