Finding geohashes of certain length within radius from a point
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.
Answer
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)
FINAL STEP:
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