Before, during the Lucene-based content search process, I learned that Lucene can retrieve text information and numerical information, and the spatial distance seems to be implemented in the source code. In the past six months, I have come into contact with Solr, which has a spatial distance search (latitude and longitude). Recently, I learned about the implementation and learned that there is a relatively common technology for realizing spatial distance search - GeoHash. Let me introduce GeoHash below.
GeoHash Features
Therefore, when we do distance search, we only need to prefix match GeoHash. The specific reasons are introduced later.
GeoHash Principle
The simplest explanation of GeoHash is to convert a location information into a sortable and comparable string encoding. The following implementation process is described in detail below:
First, we divide the latitude (-90, 90) into two intervals (-90, 0) and (0, 90). If the latitude value of the coordinate position is in the first interval, the encoding is 0, otherwise the encoding is 1. We use 40.222012 as an example. Since 40.222012 belongs to (0, 90), the encoding is 1. Then we continue to divide (0, 90) into two intervals (0, 45) and (45, 90), while 40.222012 is located in (0, 45), so the encoding is 0, and so on. We split 20 times, and finally calculate that the encoding of 40.222012 is 10111001001101000110.
The same method is used for longitude, and the encoding of 116.248283 is obtained as 110100101010101010101010101010101010101010101010101.
Next, we merge the encodings of latitude and longitude. The odd number is latitude and even number is longitude. The resulting encoding is 111001110100100110001101100110110011001101100110000110110 (it needs special attention here, the odd number and even number mentioned here are the subscripts of the value array, starting from 0);
Finally, base32 is encoded. The decimal corresponding to the binary string is 28, 29, 4, 24, 27, 6, 1, 22, respectively. The conversion to base32 is wx4sv61q, so (40.222012, 116.248283) is encoded as wx4sv61q. (The following figure introduces the correspondence of base32)
The corresponding location of the code wx4sv61q on the map is as follows:
Here, our GeoHash's encoding length is 8, and the accuracy is 19 meters. The following table lists the accuracy corresponding to different encoding lengths:
From the above accuracy, we can see that if you want to select an item within 2km of me (40.222012, 116.248283), we only need to find the GeoHash corresponding to the coordinates of the item with wx4sv as the prefix.
GeoHash Extension
So far we have a certain understanding of spatial indexes, but the above introduction cannot achieve one of the following situations:
We can see from the figure that the red dot is closer to the green dot above and farther from the green dot below, but the red dot is the same as the encoded string of the green dot below, and is both wx4g0. The idea of solving boundary problems such as GeoHash is very simple. When we search or query, we match the surrounding eight areas, which can solve the boundary problem well. Next, we will implement GeoHash in Java.
JAVA implementation
Before implementation, we first define a LocationBean and use it to represent the latitude and longitude information:
/** *@Description: Store latitude and longitude information*/ package com.lulei.geo.bean; public class LocationBean { public static final double MINLAT = -90; public static final double MAXLAT = 90; public static final double MINLNG = -180; public static final double MAXLNG = 180; private double lat;//latitude [-90,90] private double lng;//longitude [-180,180] public LocationBean(double lat, double lng) { this.lat = lat; this.lng = lng; } public double getLat() { return lat; } public void setLat(double lat) { this.lat = lat; } public double getLng() { return lng; } public void setLng(double lng) { this.lng = lng; } } Then we write a class to implement GeoHash. In the process of implementing GeoHash, we need to define some constants and latitude and longitude information, as follows:
public class GeoHash { private LocationBean location; /** * 1 2500km;2 630km;3 78km;4 30km * 5 2.4km; 6 610m; 7 76m; 8 19m */ private int hashLength = 8; //Latitude and longitude are converted to geohash length private int latLength = 20; //Latitude and longitude are converted to binary length private int lngLength = 20; //Longitude and longitude are converted to binary length private double minLat;//Unit size of each grid latitude private double minLng;//Fall of each longitude are collapsed private static final char[] CHARS = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; } When instantiating GeoHash, we need to assign some properties:
public GeoHash(double lat, double lng) { location = new LocationBean(lat, lng); setMinLatLng(); } public int gethashLength() { return hashLength; } /** * @Author:lulei * @Description: Set the minimum unit of latitude and longitude*/ private void setMinLatLng() { minLat = LocationBean.MAXLAT - LocationBean.MINLAT; for (int i = 0; i < latLength; i++) { minLat /= 2.0; } minLng = LocationBean.MAXLNG - LocationBean.MINLNG; for (int i = 0; i < lngLength; i++) { minLng /= 2.0; } } When we use GeoHash, we need to set the final encoding length, so we write a method to set the GeoHash length
public boolean sethashLength(int length) { if (length < 1) { return false; } hashLength = length; latLength = (length * 5) / 2; if (length % 2 == 0) { lngLength = latLength; } else { lngLength = latLength + 1; } setMinLatLng(); return true; } With these settings, we need to convert longitude and latitude into corresponding binary encodings
private boolean[] getHashArray(double value, double min, double max, int length) { if (value < min || value > max) { return null; } if (length < 1) { return null; } boolean[] result = new boolean[length]; for (int i = 0; i < length; i++) { double mid = (min + max) / 2.0; if (value > mid) { result[i] = true; min = mid; } else { result[i] = false; max = mid; } } return result; } After obtaining the binary encoding of latitude and longitude respectively, we need to merge two binary strings into one
private boolean[] merge(boolean[] latArray, boolean[] lngArray) { if (latArray == null || lngArray == null) { return null; } boolean[] result = new boolean[lngArray.length + latArray.length]; Arrays.fill(result, false); for (int i = 0; i < lngArray.length; i++) { result[2 * i] = lngArray[i]; } for (int i = 0; i < latArray.length; i++) { result[2 * i + 1] = latArray[i]; } return result; } Finally, we need to base32 conversion of the obtained binary conversion
/** * @param lat * @param lng * @return * @Author:lulei * @Description: Get the base32 string of latitude and longitude*/ private String getGeoHashBase32(double lat, double lng) { boolean[] bools = getGeoBinary(lat, lng); if (bools == null) { return null; } StringBuffer sb = new StringBuffer(); for (int i = 0; i < bools.length; i = i + 5) { boolean[] base32 = new boolean[5]; for (int j = 0; j < 5; j++) { base32[j] = bools[i + j]; } char cha = getBase32Char(base32); if (' ' == cha) { return null; } sb.append(cha); } return sb.toString(); } /** * @param base32 * @return * @Author:lulei * @Description: Convert five-bit binary to base32 */ private char getBase32Char(boolean[] base32) { if (base32 == null || base32.length != 5) { return ' '; } int num = 0; for (boolean bool : base32) { num <<= 1; if (bool) { num += 1; } } return CHARS[num % CHARS.length]; } For the question of how to obtain the GeoHash value of the eight surrounding areas, we can do the following transformation. We already know the latitude and longitude of the current point, and we also know the longitude and latitude width in each area. If the longitude is added or subtracted, we can be located at the longitude of the left and right areas of the area. If the latitude is added or subtracted, we can obtain the latitude of the upper and lower parts of the area, so that we can obtain the coordinates of a point in the eight areas around the area. We calculate the coordinates of these eight points, which is the GeoHash code corresponding to the eight areas.
public List<String> getGeoHashBase32For9() { double leftLat = location.getLat() - minLat; double rightLat = location.getLat() + minLat; double upLng = location.getLng() - minLng; double downLng = location.getLng() + minLng; List<String> base32For9 = new ArrayList<String>(); //The 3 Strings on the leftUp = getGeoHashBase32(leftLat, upLng); if (!(leftUp == null || "".equals(leftUp))) { base32For9.add(leftUp); } String leftMid = getGeoHashBase32(leftLat, location.getLng()); if (!(leftMid == null || "".equals(leftMid))) { base32For9.add(leftMid); } String leftDown = getGeoHashBase32(leftLat, downLng); if (!(leftDown == null || "".equals(leftDown))) { base32For9.add(leftDown); } //The 3 Strings in the middle from top to bottom midUp = getGeoHashBase32(location.getLat(), upLng); if (!(midUp == null || "".equals(midUp))) { base32For9.add(midUp); } String midMid = getGeoHashBase32(location.getLat(), location.getLng()); if (!(midMid == null || "".equals(midMid))) { base32For9.add(midMid); } String midDown = getGeoHashBase32(location.getLat(), downLng); if (!(midDown == null || "".equals(midDown))) { base32For9.add(midDown); } //3 Strings on the right from top to bottom rightUp = getGeoHashBase32(rightLat, upLng); if (!(rightUp == null || "".equals(rightUp))) { base32For9.add(rightUp); } String rightMid = getGeoHashBase32(rightLat, upLng); if (!(rightUp == null || "".equals(rightUp))) { base32For9.add(rightUp); } String rightMid = getGeoHashBase32(rightLat, location.getLng()); if (!(rightMid == null || "".equals(rightMid))) { base32For9.add(rightMid); } String rightDown = getGeoHashBase32(rightLat, downLng); if (!(rightDown == null || "".equals(rightDown))) { base32For9.add(rightDown); } return base32For9; } Running results
Complete code
There is already a complete LoacationBean code in the above blog, so I won't write it here.
/** *@Description: GeoHash realizes the conversion of latitude and longitude*/ package com.lulei.geo; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import com.lulei.geo.bean.LocationBean; import com.lulei.util.JsonUtil; public class GeoHash { private LocationBean location; /** * 1 2500km;2 630km;3 78km;4 30km * 5 2.4km;6 610m; 7 76m; 8 19m */ private int hashLength = 8; //Latitude and longitude are converted into geohash length private int latLength = 20; //Latitude and longitude are converted into binary length private int lngLength = 20; //Latitude and longitude are converted into binary length private double minLat; //Unit size of each latitude private double minLng; //Fallen of each longitude private static final char[] CHARS = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; public GeoHash(double lat, double lng) { location = new LocationBean(lat, lng); setMinLatLng(); } public int gethashLength() { return hashLength; } /** * @Author:lulei * @Description: Set the minimum unit of latitude and longitude*/ private void setMinLatLng() { minLat = LocationBean.MAXLAT - LocationBean.MINLAT; for (int i = 0; i < latLength; i++) { minLat /= 2.0; } minLng = LocationBean.MAXLNG - LocationBean.MINLNG; for (int i = 0; i < lngLength; i++) { minLng /= 2.0; } } /** * @return * @Author:lulei * @Description: Find the nine coordinate point and surrounding points */ public List<String> getGeoHashBase32For9() { double leftLat = location.getLat() - minLat; double rightLat = location.getLat() + minLat; double upLng = location.getLng() - minLng; double downLng = location.getLng() + minLng; List<String> base32For9 = new ArrayList<String>(); //The 3 Strings on the leftUp = getGeoHashBase32(leftLat, upLng); if (!(leftUp == null || "".equals(leftUp))) { base32For9.add(leftUp); } String leftMid = getGeoHashBase32(leftLat, location.getLng()); if (!(leftMid == null || "".equals(leftMid))) { base32For9.add(leftMid); } String leftDown = getGeoHashBase32(leftLat, downLng); if (!(leftDown == null || "".equals(leftDown))) { base32For9.add(leftDown); } //The 3 Strings from top to bottom in the middle midUp = getGeoHashBase32(location.getLat(), upLng); if (!(midUp == null || "".equals(midUp))) { base32For9.add(midUp); } String midMid = getGeoHashBase32(location.getLat(), location.getLng()); if (!(midMid == null || "".equals(midMid))) { base32For9.add(midMid); } String midDown = getGeoHashBase32(location.getLat(), downLng); if (!(midDown == null || "".equals(midDown))) { base32For9.add(midDown); } //3 Strings from top to bottom on the right side rightUp = getGeoHashBase32(rightLat, upLng); if (!(rightUp == null || "".equals(rightUp))) { base32For9.add(rightUp); } String rightMid = getGeoHashBase32(rightLat, location.getLng()); if (!(rightMid == null || "".equals(rightMid))) { base32For9.add(rightMid); } String rightDown = getGeoHashBase32(rightLat, downLng); if (!(rightDown == null || "".equals(rightDown))) { base32For9.add(rightDown); } return base32For9; } /** * @param length * @return * @Author:lulei * @Description: Set the latitude and longitude to geohash length*/ public boolean sethashLength(int length) { if (length < 1) { return false; } hashLength = length; latLength = (length * 5) / 2; if (length % 2 == 0) { lngLength = latLength; } else { lngLength = latLength + 1; } setMinLatLng(); return true; } /** * @return * @Author:lulei * @Description: Get the base32 string of latitude and longitude*/ public String getGeoHashBase32() { return getGeoHashBase32(location.getLat(), location.getLng()); } /** * @param lat * @param lng * @return * @Author:lulei * @Description: Get the base32 string of latitude and longitude*/ private String getGeoHashBase32(double lat, double lng) { boolean[] bools = getGeoBinary(lat, lng); if (bools == null) { return null; } StringBuffer sb = new StringBuffer(); for (int i = 0; i < bools.length; i = i + 5) { boolean[] base32 = new boolean[5]; for (int j = 0; j < 5; j++) { base32[j] = bools[i + j]; } char cha = getBase32Char(base32); if (' ' == cha) { return null; } sb.append(cha); } return sb.toString(); } /** * @param base32 * @return * @Author:lulei * @Description: Convert five-bit binary to base32 */ private char getBase32Char(boolean[] base32) { if (base32 == null || base32.length != 5) { return ' '; } int num = 0; for (boolean bool : base32) { num <<= 1; if (bool) { num += 1; } } return CHARS[num % CHARS.length]; } /** * @param lat * @param lng * @return * @Author:lulei * @Description: Get the geo binary string of coordinates*/ private boolean[] getGeoBinary(double lat, double lng) { boolean[] latArray = getHashArray(lat, LocationBean.MINLAT, LocationBean.MAXLAT, latLength); boolean[] lngArray = getHashArray(lng, LocationBean.MINLNG, LocationBean.MAXLNG, lngLength); return merge(latArray, lngArray); } /** * @param latArray * @param lngArray * @return * @Author:lulei * @Description: Merge latitude and longitude binary*/ private boolean[] merge(boolean[] latArray, boolean[] lngArray) { if (latArray == null || lngArray == null) { return null; } boolean[] result = new boolean[lngArray.length + latArray.length]; Arrays.fill(result, false); for (int i = 0; i < lngArray.length; i++) { result[2 * i] = lngArray[i]; } for (int i = 0; i < latArray.length; i++) { result[2 * i + 1] = latArray[i]; } return result; } /** * @param value * @param min * @param max * @return * @Author:lulei * @Description: Convert numbers into geohash binary string*/ private boolean[] getHashArray(double value, double min, double max, int length) { if (value < min || value > max) { return null; } if (length < 1) { return null; } boolean[] result = new boolean[length]; for (int i = 0; i < length; i++) { double mid = (min + max) / 2.0; if (value > mid) { result[i] = true; min = mid; } else { result[i] = false; max = mid; } } return result; } public static void main(String[] args) { // TODO Auto-generated method stub GeoHash g = new GeoHash(40.222012, 116.248283); System.out.println(g.getGeoHashBase32()); System.out.println(JsonUtil.parseJson(g.getGeoHashBase32For9())); } }The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.