Sebelumnya, selama proses pencarian konten berbasis Lucene, saya belajar bahwa Lucene dapat mengambil informasi teks dan informasi numerik, dan jarak spasial tampaknya diimplementasikan dalam kode sumber. Dalam enam bulan terakhir, saya bersentuhan dengan Solr, yang memiliki pencarian jarak spasial (lintang dan bujur). Baru -baru ini, saya belajar tentang implementasi dan belajar bahwa ada teknologi yang relatif umum untuk mewujudkan pencarian jarak spasial - Geohash. Izinkan saya memperkenalkan Geohash di bawah ini.
Fitur Geohash
Karena itu, ketika kita melakukan pencarian jarak, kita hanya perlu mencocokkan Geohash. Alasan spesifik diperkenalkan nanti.
Prinsip Geohash
Penjelasan paling sederhana dari GeoHash adalah untuk mengubah informasi lokasi menjadi pengkodean string yang dapat diurutkan dan sebanding. Proses implementasi berikut dijelaskan secara rinci di bawah ini:
Pertama, kami membagi garis lintang (-90, 90) menjadi dua interval (-90, 0) dan (0, 90). Jika nilai lintang dari posisi koordinat berada dalam interval pertama, pengkodean adalah 0, jika tidak pengkodean adalah 1. Kami menggunakan 40.222012 sebagai contoh. Karena 40.222012 milik (0, 90), pengkodean adalah 1. Kemudian kami terus membagi (0, 90) menjadi dua interval (0, 45) dan (45, 90), sedangkan 40.222012 terletak di (0, 45), sehingga pengkodeannya adalah 0, dan seterusnya. Kami berpisah 20 kali, dan akhirnya menghitung bahwa pengkodean 40.222012 adalah 10111001001101000110.
Metode yang sama digunakan untuk bujur, dan pengkodean 116.248283 diperoleh sebagai 1101001010101010101010101010101010101010101010101.
Selanjutnya, kami menggabungkan pengkodean garis lintang dan bujur. Angka ganjil adalah garis lintang dan bahkan angka adalah bujur. Pengkodean yang dihasilkan adalah 1110011101001001100011011001101100110011011001100110110 (Perlu perhatian khusus di sini, nomor ganjil dan bahkan angka yang disebutkan di sini adalah subskrip dari array nilai, mulai dari 0);
Akhirnya, Base32 dikodekan. Desimal yang sesuai dengan string biner adalah 28, 29, 4, 24, 27, 6, 1, 22, masing -masing. Konversi ke Base32 adalah WX4SV61Q, SO (40.222012, 116.248283) dikodekan sebagai WX4SV61Q. (Gambar berikut memperkenalkan korespondensi Base32)
Lokasi yang sesuai dari kode WX4SV61Q pada peta adalah sebagai berikut:
Di sini, panjang penyandian Geohash kami adalah 8, dan akurasinya adalah 19 meter. Tabel berikut mencantumkan keakuratan yang sesuai dengan panjang penyandian yang berbeda:
Dari akurasi di atas, kita dapat melihat bahwa jika Anda ingin memilih item dalam 2 km dari saya (40.222012, 116.248283), kita hanya perlu menemukan geohash yang sesuai dengan koordinat item dengan WX4SV sebagai awalan.
Ekstensi Geohash
Sejauh ini kami memiliki pemahaman tertentu tentang indeks spasial, tetapi pengantar di atas tidak dapat mencapai salah satu dari situasi berikut:
Kita dapat melihat dari gambar bahwa titik merah lebih dekat ke titik hijau di atas dan lebih jauh dari titik hijau di bawah, tetapi titik merah sama dengan string yang dikodekan dari titik hijau di bawah, dan keduanya WX4G0. Gagasan menyelesaikan masalah batas seperti Geohash sangat sederhana. Saat kami mencari atau meminta, kami mencocokkan delapan area di sekitarnya, yang dapat menyelesaikan masalah batas dengan baik. Selanjutnya, kami akan menerapkan Geohash di Java.
Implementasi Java
Sebelum implementasi, pertama -tama kami mendefinisikan lokasi dan menggunakannya untuk mewakili informasi garis lintang dan bujur:
/ ***@Deskripsi: Store Informasi Latitude dan Longitude*/ Paket com.lulei.geo.bean; Public Class LocationBean {public static final double minlat = -90; Maxlat ganda final statis publik = 90; Minlng ganda final public static = -180; Maxlng ganda final public static = 180; private double lat; // latitude [-90,90] private double lng; // longitude [-180,180] Lokasi umum (lat ganda, lng ganda) {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; }} Kemudian kami menulis kelas untuk mengimplementasikan GeoHash. Dalam proses penerapan Geohash, kita perlu mendefinisikan beberapa konstanta dan informasi lintang dan bujur, sebagai berikut:
Kelas Publik GeoHash {Lokasi PrivateBean Private; /** * 1 2500km; 2 630 km; 3 78km; 4 30 km * 5 2.4 km; 6 610m; 7 76m; 8 19m */ private int hashlength = 8; // Latitude dan bujur dikonversi menjadi panjang geohash pribadi int latlength = 20; // Latitude dan bujur dikonversi menjadi panjang biner private int lnglength = 20; // bujur dan bujur dikonversi menjadi minlat ganda private biner panjang; // Ukuran unit dari setiap grid latitude private double minlng; // jatuh dari setiap bujur adalah crobsed private static final char [] chars = {'0', '1', '2', '3', '4', '5', '6', '7', ',' 8 ',', '9', ',' Ca 'F', 'g', 'h', 'j', 'k', 'm', 'n', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; } Saat instantiating Geohash, kita perlu menetapkan beberapa properti:
geohash publik (lat ganda, lng ganda) {location = new locationbean (lat, lng); setminlatlng (); } public int getHashLength () {return hashlength; } / *** @Author: lulei* @description: Setel unit minimum lintang dan bujur* / private void setminlatlng () {minlat = locationbean.maxlat - locationbean.minlat; untuk (int i = 0; i <latlength; i ++) {minlat /= 2.0; } minlng = locationbean.maxlng - locationbean.minlng; untuk (int i = 0; i <lnglength; i ++) {minlng /= 2.0; }} Saat kami menggunakan GeoHash, kami perlu mengatur panjang penyandian akhir, jadi kami menulis metode untuk mengatur panjang geohash
SetHashLength public boolean (panjang int) {if (panjang <1) {return false; } hashlength = panjang; latlength = (panjang * 5) / 2; if (panjang % 2 == 0) {lnglength = latlength; } else {lnglength = latlength + 1; } setminlatlng (); Kembali Benar; } Dengan pengaturan ini, kita perlu mengubah bujur dan garis lintang menjadi penyandian biner yang sesuai
private boolean [] gethasharray (nilai ganda, min ganda, maks ganda, panjang int) {if (nilai <min || value> max) {return null; } if (panjang <1) {return null; } boolean [] hasil = boolean baru [panjang]; untuk (int i = 0; i <panjang; i ++) {double mid = (min+max) / 2.0; if (value> mid) {result [i] = true; min = mid; } else {hasil [i] = false; max = mid; }} hasil pengembalian; } Setelah memperoleh penyandian biner dari garis lintang dan bujur masing -masing, kita perlu menggabungkan dua string biner menjadi satu
private boolean [] gabungan (boolean [] latasray, boolean [] lngarray) {if (lATarray == null || lngarray == null) {return null; } boolean [] hasil = boolean baru [lngarray.length + latasray.length]; Arrays.fill (hasil, salah); untuk (int i = 0; i <lngarray.length; i ++) {hasil [2 * i] = lngarray [i]; } untuk (int i = 0; i <latarray.length; i ++) {result [2 * i+1] = latarray [i]; } hasil pengembalian; } Akhirnya, kita perlu melakukan konversi 32 dari konversi biner yang diperoleh
/ ** * @param lat * @param lng * @return * @author: lulei * @description: Dapatkan string base32 dari latitude dan bujur */ string privat getGeohashbase32 (lat ganda, lng ganda) {boolean [] bools = getGeobinary (lat, lng); if (bools == null) {return null; } StringBuffer SB = StringBuffer baru (); untuk (int i = 0; i <bools.length; i = i + 5) {boolean [] base32 = boolean baru [5]; untuk (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: Konversi biner lima-bit ke base32 * / private char getBase32char (boolean [] base32) {if (base32 == null || base32.length! = 5) {return ''; } int num = 0; untuk (boolean bool: base32) {num << = 1; if (bool) {num += 1; }} return chars [num % chars.length]; } Untuk pertanyaan tentang bagaimana mendapatkan nilai Geohash dari delapan daerah sekitarnya, kita dapat melakukan transformasi berikut. Kita sudah tahu garis lintang dan bujur dari titik saat ini, dan kita juga tahu lebar garis bujur dan garis lintang di setiap area. Jika bujur ditambahkan atau dikurangi, kita dapat ditempatkan di bujur area kiri dan kanan area. Jika garis lintang ditambahkan atau dikurangi, kita dapat memperoleh garis lintang bagian atas dan bawah area, sehingga kita dapat memperoleh koordinat titik di delapan area di sekitar area. Kami menghitung koordinat dari delapan poin ini, yang merupakan kode geohash yang sesuai dengan delapan area.
Daftar Publik <String> getGeoHashBase32For9 () {ganda leftlat = location.getlat () - minlat; double rightlat = location.getlat () + minlat; double uplng = location.getlng () - minlng; double downlng = location.getlng () + minlng; Daftar <String> base32for9 = ArrayList baru <string> (); // 3 string di sebelah kiri = 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 (kiri); } // 3 string di tengah dari atas ke bawah ke bawah = 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 string di sebelah kanan dari atas ke kanan bawah = 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; } Hasil berjalan
Kode lengkap
Sudah ada kode LoacationBean lengkap di blog di atas, jadi saya tidak akan menulisnya di sini.
/ ***@Deskripsi: GeoHash menyadari konversi lintang dan bujur*/ paket com.lulei.geo; impor java.util.arraylist; impor java.util.arrays; impor java.util.list; impor com.lulei.geo.bean.locationbean; impor com.lulei.util.jsonutil; Kelas Publik GeoHash {Lokasi PrivateBean Private; /** * 1 2500km; 2 630 km; 3 78km; 4 30 km * 5 2.4 km; 6 610m; 7 76m; 8 19m */ private int hashlength = 8; // Latitude dan bujur dikonversi menjadi panjang geohash pribadi int latlength = 20; // Latitude dan bujur dikonversi menjadi panjang biner private int lnglength = 20; // Latitude dan bujur dikonversi menjadi minlat ganda privat panjang biner; // Ukuran satuan dari setiap lintang swasta ganda 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'}; geohash publik (lat ganda, lng ganda) {location = new locationbean (lat, lng); setminlatlng (); } public int getHashLength () {return hashlength; } / *** @Author: lulei* @description: Setel unit minimum lintang dan bujur* / private void setminlatlng () {minlat = locationbean.maxlat - locationbean.minlat; untuk (int i = 0; i <latlength; i ++) {minlat /= 2.0; } minlng = locationbean.maxlng - locationbean.minlng; untuk (int i = 0; i <lnglength; i ++) {minlng /= 2.0; }} / ** * @return * @Author: lulei * @description: Temukan sembilan titik koordinat dan titik sekitarnya * / Daftar publik <string> getGeoHashBase32for9 () {ganda leftlat = location.getlat () - minlat; double rightlat = location.getlat () + minlat; double uplng = location.getlng () - minlng; double downlng = location.getlng () + minlng; Daftar <String> base32for9 = ArrayList baru <string> (); // 3 string di sebelah kiri = 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 (kiri); } // 3 string dari atas ke bawah di midup tengah = 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 string dari atas ke bawah di sisi kanan 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 panjang * @return * @author: lulei * @description: atur lintang dan bujur ke geohash panjang * / public boolean setHashlength (int int) {if (panjang <1) {return false; } hashlength = panjang; latlength = (panjang * 5) / 2; if (panjang % 2 == 0) {lnglength = latlength; } else {lnglength = latlength + 1; } setminlatlng (); Kembali Benar; } / ** * @return * @author: lulei * @description: Dapatkan string base32 dari lintang dan bujur * / string publik getGeohashBase32 () {return getGeoHashBase32 (location.getlat (), location.getlng ()); } / ** * @param lat * @param lng * @return * @author: lulei * @description: Dapatkan string base32 latitude dan bujur * / string privat getGeohashbase32 (lat ganda, lng ganda) {boolean [] bools = getGeobinary (lat, lng); if (bools == null) {return null; } StringBuffer SB = StringBuffer baru (); untuk (int i = 0; i <bools.length; i = i + 5) {boolean [] base32 = boolean baru [5]; untuk (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: Konversi biner lima-bit ke base32 * / private char getBase32char (boolean [] base32) {if (base32 == null || base32.length! = 5) {return ''; } int num = 0; untuk (boolean bool: base32) {num << = 1; if (bool) {num += 1; }} return chars [num % chars.length]; } / ** * @param lat * @param lng * @return * @author: lulei * @description: Dapatkan string koordinat geo biner * / boolean privat [] getGeobinary (lat ganda, lng ganda) {boolean [] latasray = gethasharray (lat, locatlat.miner) {boolean [] latasray = gethasharray (lat, locationbean.miner) {boolean [] latasray = gethasharray (lat, locationbean.minere.min boolean [] lngarray = gethasharray (lng, locationbean.minlng, locationbean.maxlng, lnglength); return gabungan (latasray, lngarray); } / ** * @param latarray * @param lngarray * @return * @author: lulei * @description: gabungkan latitude dan longitude biner * / private boolean [] gabungan (boolean [] lataray, boolean [] lngarray) {if (latasray == null || } boolean [] hasil = boolean baru [lngarray.length + latasray.length]; Arrays.fill (hasil, salah); untuk (int i = 0; i <lngarray.length; i ++) {hasil [2 * i] = lngarray [i]; } untuk (int i = 0; i <latarray.length; i ++) {result [2 * i+1] = latarray [i]; } hasil pengembalian; } / ** * @param nilai * @param min * @param max * @return * @author: lulei * @description: Konversi angka menjadi geohash biner string * / private boolean [] gethasharray (nilai ganda, min double, double max, int length) {if (value <min || value> max) {return null; } if (panjang <1) {return null; } boolean [] hasil = boolean baru [panjang]; untuk (int i = 0; i <panjang; i ++) {double mid = (min+max) / 2.0; if (value> mid) {result [i] = true; min = mid; } else {hasil [i] = false; max = mid; }} hasil pengembalian; } public static void main (string [] args) {// TODO Metode yang dihasilkan otomatis Stub geohash g = baru geohash (40.222012, 116.248283); System.out.println (G.GetGeohashBase32 ()); System.out.println (jsonutil.parsejson (g.getgeohashbase32for9 ())); }}Di atas adalah semua konten artikel ini. Saya berharap ini akan membantu untuk pembelajaran semua orang dan saya harap semua orang akan lebih mendukung wulin.com.