Lucene 기반 콘텐츠 검색 프로세스 기간 동안 Lucene이 텍스트 정보와 수치 정보를 검색 할 수 있다는 것을 알게되었으며 공간 거리는 소스 코드에서 구현되는 것으로 보입니다. 지난 6 개월 동안, 나는 공간 거리 검색 (위도 및 경도)을 가진 Solr과 접촉했습니다. 최근에, 나는 구현에 대해 배웠고 공간 거리 검색을 실현하는 비교적 일반적인 기술 -Eohash가 있다는 것을 알게되었습니다. 아래에 Geohash를 소개하겠습니다.
지오 하쉬 기능
따라서 거리 검색을 수행하면 Geohash와 일치하는 경우 만 접두사 만 접두어야합니다. 특정 이유는 나중에 소개됩니다.
지오 하쉬 원리
Geohash에 대한 가장 간단한 설명은 위치 정보를 정렬 가능하고 비슷한 문자열 인코딩으로 변환하는 것입니다. 다음 구현 프로세스는 다음과 같습니다.
먼저 위도 (-90, 90)를 두 간격 (-90, 0)과 (0, 90)로 나눕니다. 좌표 위치의 위도 값이 첫 번째 간격이면 인코딩은 0이면 인코딩은 1입니다. 40.222012를 예로 사용합니다. 40.222012는 (0, 90)에 속하므로 인코딩은 1입니다. 그런 다음 (0, 90)은 (0, 45)와 (45, 90)으로 계속 나누고 40.222012는 (0, 45)에 위치하고 있기 때문에 0, 0이됩니다. 우리는 20 번 나누고 마지막으로 40.222012의 인코딩이 10111001001101000110이라고 계산합니다.
동일한 방법이 경도에 사용되며 116.248283 인코딩은 1101001010101010101010101010101010101010101로 얻습니다.
다음으로, 우리는 위도와 경도의 인코딩을 병합합니다. 홀수는 위도이며 짝수는 경도입니다. 결과 인코딩은 1110011101001001100100111001110011100111110010000110110입니다 (여기서는 특별한주의가 필요합니다. 여기에 언급 된 홀수 및 짝수는 0부터 시작하는 값 배열의 첨자입니다).
마지막으로 Base32가 인코딩됩니다. 이진 스트링에 해당하는 소수점은 각각 28, 29, 4, 24, 27, 6, 1, 22입니다. Base32로의 전환은 WX4SV61Q이므로 (40.222012, 116.248283)는 WX4SV61Q로 인코딩됩니다. (다음 그림은 Base32의 서신을 소개합니다)
지도에서 코드 WX4SV61Q의 해당 위치는 다음과 같습니다.
여기서 Geohash의 인코딩 길이는 8이고 정확도는 19 미터입니다. 다음 표는 다른 인코딩 길이에 해당하는 정확도를 나열합니다.
위의 정확성에서, 우리는 당신이 나의 2km 이내의 항목을 선택하려면 (40.222012, 116.248283), 우리는 wx4sv가있는 항목의 좌표에 해당하는 Geohash를 찾아야한다는 것을 알 수 있습니다.
Geohash 확장
지금까지 우리는 공간 지수에 대한 특정 이해를 가지고 있지만 위의 소개는 다음과 같은 상황 중 하나를 달성 할 수 없습니다.
우리는 빨간색 점이 위의 녹색 점에 더 가깝고 아래의 녹색 점에서 더 멀리 떨어져 있음을 알 수 있지만, 빨간색 점은 아래의 녹색 점의 인코딩 된 문자열과 동일하며 둘 다 WX4G0입니다. Geohash와 같은 경계 문제를 해결한다는 아이디어는 매우 간단합니다. 검색 또는 쿼리시 주변 8 개 영역과 일치하여 경계 문제를 잘 해결할 수 있습니다. 다음으로 Java에서 Geohash를 구현할 것입니다.
Java 구현
구현하기 전에 먼저 LocationBean을 정의하고 위도 및 경도 정보를 나타내는 데 사용합니다.
/ ***@description : 위도 및 경도 정보 저장*/ 패키지 com.lulei.geo.bean; 공개 클래스 LocationBean {public static final double minlat = -90; 퍼블릭 정적 최종 이중 최대 율 = 90; 공개 정적 최종 이중 Minlng = -180; 공개 정적 최종 이중 Maxlng = 180; Private Double Lat; // 위도 [-90,90] Private Double Lng; // 경도 [-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; }} 그런 다음 Geohash를 구현하기 위해 수업을 작성합니다. Geohash를 구현하는 과정에서 다음과 같이 일부 상수 및 위도 및 경도 정보를 정의해야합니다.
공개 클래스 Geohash {Private LocationBean 위치; /** * 1 2500km; 2 630km; 3 78km; 4 30km * 5 2.4km; 6 610m; 7 76m; 8 19m */ 개인 int 해시 길이 = 8; // 위도와 경도는 Geohash 길이로 변환됩니다. Private int latlength = 20; // 위도와 경도는 이진 길이로 변환됩니다. 개인 int lnglength = 20; // 각 그리드 위도의 단위 크기 개인의 단위 크기 프라이빗 개인 이중 최소; // 각 경도의 낙상은 개인 정적 최종 문자 [] chars = { '0', '1', '2', '4', '5', '6', '7', '8', '', '', '' 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; } Geohash를 인스턴스화 할 때는 몇 가지 속성을 할당해야합니다.
Public Geohash (Double Lat, Double Lng) {Location = New LocationBean (Lat, Lng); setminlatlng (); } public int gethashlength () {return 해시 길이; } / *** @author : lulei* @description : 최소 위도 및 경도의 최소 단위를 설정* / 개인 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; }} Geohash를 사용하면 최종 인코딩 길이를 설정해야하므로 Geohash 길이를 설정하는 메소드를 작성해야합니다.
public boolean sethashlength (int length) {if (length <1) {return false; } 해시 길이 = 길이; latlength = (길이 * 5) / 2; if (길이 % 2 == 0) {lnglength = latlength; } else {lnglength = latlength + 1; } setMinlatlng (); 진실을 반환하십시오. } 이 설정을 사용하면 경도와 위도를 해당 바이너리 인코딩으로 변환해야합니다.
개인 부울 [] gethasharray (이중 값, 이중 최소, 이중 최대, int 길이) {if (value <min || value> max) {return null; } if (길이 <1) {return null; } 부울 [] 결과 = 새로운 부울 [길이]; for (int i = 0; i <길이; i ++) {double mid = (min+max) / 2.0; if (value> mid) {결과 [i] = true; 최소 = 중간; } else {결과 [i] = false; MAX = MID; }} 반환 결과; } 위도와 경도의 이진 인코딩을 각각 얻은 후 두 이진 문자열을 하나로 병합해야합니다.
개인 부울 [] merge (boolean [] latarray, boolean [] lngarray) {if (latarray == null || lngarray == null) {return null; } 부울 [] 결과 = 새로운 부울 [lngarray.length + latarray.length]; 배열 .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]; } 반환 결과; } 마지막으로, 우리는 얻은 이진 변환의 변환을베이스해야합니다.
/ ** * @param lat * @param lng * @return * @author : lulei * @description : base32 위도 및 경도 문자열 */ 개인 문자열 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 = 새로운 부울 [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 : 5 비트 바이너리를 Base32 * / private char getbase32char (boolean [] base32) {if (base32 == null || base32.length! = 5) {return ''; } int num = 0; for (부울 bool : base32) {num << = 1; if (bool) {num += 1; }} return chars [num % chars.length]; } 8 개의 주변 지역의 Geohash 값을 얻는 방법에 대한 질문은 다음과 같은 변환을 수행 할 수 있습니다. 우리는 이미 현재 지점의 위도와 경도를 알고 있으며 각 영역의 경도와 위도 너비도 알고 있습니다. 경도가 추가되거나 빼면 해당 지역의 왼쪽 및 오른쪽 지역의 경도에 위치 할 수 있습니다. 위도가 추가되거나 빼면 해당 지역의 상부 및 하단 부분의 위도를 얻을 수있어 해당 지역 주변의 8 개 지역에서 한 지점의 좌표를 얻을 수 있습니다. 우리는 8 개의 영역에 해당하는 Geohash 코드 인이 8 점의 좌표를 계산합니다.
공개 목록 <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> (); // 왼쪽의 3 문자열 = getGeoHashBase32 (leftLat, uplng); if (! (leftup == null || "".Equals (leftup))) {base32for9.Add (왼쪽); } string leftmid = getgeohashbase32 (leftlat, location.getlng ()); If (! } string leftdown = getgeohashbase32 (leftlat, downlng); if (! } // 중간에있는 3 문자열 상단에서 하단으로 미드 up = getgeohashbase32 (location.getlat (), uplng); if (! } 문자열 midmid = getgeohashbase32 (location.getlat (), location.getlng ()); if (! } 문자열 middown = getGeoHashBase32 (location.getLat (), downlng); if (! } // 오른쪽 위에서 아래로 오른쪽으로 오른쪽으로 3 문자열 = 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 (오른쪽))) {base32for9.Add (오른쪽 다운); } return base32for9; } 실행 결과
완전한 코드
위의 블로그에는 이미 완전한 loacationbean 코드가 있으므로 여기에 쓰지 않을 것입니다.
/ ***@description : Geohash는 위도와 경도의 변환을 깨닫습니다*/ 패키지 com.lulei.geo; java.util.arraylist 가져 오기; import java.util.arrays; Java.util.list 가져 오기; com.lulei.geo.bean.locationbean import; import com.lulei.util.jsonutil; 공개 클래스 Geohash {Private LocationBean 위치; /** * 1 2500km; 2 630km; 3 78km; 4 30km * 5 2.4km; 6 610m; 7 76m; 8 19m */ 개인 int 해시 길이 = 8; // 위도와 경도는 Geohash 길이로 변환됩니다. Private int latlength = 20; // 위도와 경도는 이진 길이로 변환됩니다. 개인 int lnglength = 20; // 위도와 경도는 이진 길이 개인 이중 최소로 변환됩니다. // 각 위도의 단위 크기 개인 개인 이중 minlng; // 각 경도에서 떨어진 개인 정적 최종 char [] chars = { '0', '1', '2', '3', '4', '4', '5', '6', '7', '8', '9', 'B', 'C', 'd', '', 'g', 'h', 'j', 'k', '', ',', ',', ',', ',', ',', ',', ',', ',', ',', ',', '', 'k' 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; Public Geohash (Double Lat, Double Lng) {Location = New LocationBean (Lat, Lng); setminlatlng (); } public int gethashlength () {return 해시 길이; } / *** @author : lulei* @description : 최소 위도 및 경도의 최소 단위를 설정* / 개인 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 : 9 개의 좌표 지점과 주변 포인트 * / 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> (); // 왼쪽의 3 문자열 = getGeoHashBase32 (leftLat, uplng); if (! (leftup == null || "".Equals (leftup))) {base32for9.Add (왼쪽); } string leftmid = getgeohashbase32 (leftlat, location.getlng ()); If (! } string leftdown = getgeohashbase32 (leftlat, downlng); if (! } // 중간 중간의 위에서 아래로 3 문자열 = GetGeoHashBase32 (location.getLat (), uplng); if (! } 문자열 midmid = getgeohashbase32 (location.getlat (), location.getlng ()); if (! } 문자열 middown = getGeoHashBase32 (location.getLat (), downlng); if (! } // 오른쪽의 위에서 아래로 3 문자열 오른쪽 오른쪽으로 = GetGeoHashBase32 (오른쪽, 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 (오른쪽))) {base32for9.Add (오른쪽 다운); } return base32for9; } / ** * @param length * @return * @author : lulei * @description : 위도와 경도를 Geohash 길이 * / public boolean sethashlength (int length) {if (length <1) {return false; } 해시 길이 = 길이; latlength = (길이 * 5) / 2; if (길이 % 2 == 0) {lnglength = latlength; } else {lnglength = latlength + 1; } setMinlatlng (); 진실을 반환하십시오. } / ** * @return * @author : lulei * @description : base32 위도 및 경도 문자열 * / public string getgeohashbase32 (return getgeohashbase32 (location.getlat (), location.getlng ()); } / ** * @param lat * @param lng * @return * @author : lulei * @description : base32 위도 및 경도를 얻습니다 * / 개인 문자열 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 = 새로운 부울 [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 : 5 비트 바이너리를 Base32 * / private char getbase32char (boolean [] base32) {if (base32 == null || base32.length! = 5) {return ''; } int num = 0; for (부울 bool : base32) {num << = 1; if (bool) {num += 1; }} return chars [num % chars.length]; } / ** * @param lat * @param lng * @return * @author : lulei * @description : get get get get the get get the get get the get binain string * / private boolean [] getgeobinary (double lat, double lng) {boolean [] latarray = gethasharray (lat, locationbean.minlat, latllatt); 부울 [] lngarray = gethasharray (lng, locationbean.minlng, locationBean.maxlng, lnglength); 반환 병합 (Latarray, lngarray); } / ** * @param latarray * @param lngarray * @return * @author : lulei * @description : 합병 위도 및 경도 이진 * / private boolean [] merge (boolean [] latarray, boolean [] lngarray) {if (latarray == null || lngarrray == null); } 부울 [] 결과 = 새로운 부울 [lngarray.length + latarray.length]; 배열 .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]; } 반환 결과; } / ** * @param value * @param min * @param max * @return * @author : lulei * @description : 숫자를 geohash binary string * / private boolean [] gethasharray (double value, double min, double max, int length) {if (value <min || value> max) {return null; } if (길이 <1) {return null; } 부울 [] 결과 = 새로운 부울 [길이]; for (int i = 0; i <길이; i ++) {double mid = (min+max) / 2.0; if (value> mid) {결과 [i] = true; 최소 = 중간; } else {결과 [i] = false; MAX = MID; }} 반환 결과; } public static void main (String [] args) {// todo 자동 생성 메소드 스터브 Geohash G = New Geohash (40.222012, 116.248283); System.out.println (g.getgeohashbase32 ()); System.out.println (jsonutil.parsejson (g.getgeohashbase32for9 ())); }}위는이 기사의 모든 내용입니다. 모든 사람의 학습에 도움이되기를 바랍니다. 모든 사람이 wulin.com을 더 지원하기를 바랍니다.