Menu
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.
864
From the GPS coordinates, the geohash is calculated by creating two binary strings, one for the longitude and one for the latitude, by dichotomy of the corresponding intervals. By splitting each interval into 2 equal parts and noting 0 the left interval and 1 the right interval.
Geohashes used in this aggregation can have a choice of precision between 1 and 12. The highest-precision geohash of length 12 produces cells that cover less than a square metre of land and so high-precision requests can be very costly in terms of RAM and result sizes.
Geohash is a geocoding method used to encode geographic coordinates (latitude and longitude) into an alphanumeric string.
Geohashes, created by Gustavo Niemeyer in 2008 and placed in the public domain, are an elegant and succinct geographic encoding. Geohashes work by reducing a two-dimensional longitude, latitude pair into a single alphanumeric string where each additional character adds precision to the location.
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
dr5ruj4477kd dr5ru46ne2ux dr5ru6ryw0cp 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
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.
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
134
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
