Vor dem von Lucene basierenden Inhaltssuchprozess erfuhr ich, dass Lucene Textinformationen und numerische Informationen abrufen kann, und die räumliche Distanz scheint im Quellcode implementiert zu werden. In den letzten sechs Monaten bin ich mit Solr in Kontakt gekommen, das eine räumliche Distanzsuche (Breitengrad und Längengrad) hat. Kürzlich habe ich die Implementierung erfahren und gelernt, dass es eine relativ häufige Technologie zur Realisierung der räumlichen Distanzsuche gibt - Geohash. Lassen Sie mich unten Geohash vorstellen.
Geohash -Funktionen
Wenn wir Distanzsuche durchführen, müssen wir daher nur das Präfix mit Geohash übereinstimmen. Die spezifischen Gründe werden später eingeführt.
Geohash -Prinzip
Die einfachste Erklärung von Geohash besteht darin, eine Positionsinformationen in eine sortierbare und vergleichbare String -Codierung umzuwandeln. Der folgende Implementierungsprozess wird nachstehend ausführlich beschrieben:
Zunächst teilen wir den Breitengrad (-90, 90) in zwei Intervalle (-90, 0) und (0, 90) auf. Wenn der Breitenwert der Koordinatenposition im ersten Intervall liegt, beträgt die Codierung 0, andernfalls beträgt die Codierung 1. Wir verwenden 40,222012 als Beispiel. Da 40.222012 zu (0, 90) gehört, beteiligt die Codierung 1. Dann teilen wir uns weiter (0, 90) in zwei Intervalle (0, 45) und (45, 90), während 40.222012 sich in (0, 45) befindet, so dass die Kodierung 0 und so weiter ist. Wir haben uns 20 Mal geteilt und schließlich berechnen, dass die Codierung von 40,222012 10111001001101000110 beträgt.
Die gleiche Methode wird für die Länge verwendet, und die Codierung von 116.248283 wird als 110100101010101010101010101010101010101010101 erhalten.
Als nächstes verschmelzen wir die Kodierungen von Breiten- und Längengrad. Die ungerade Zahl ist Breitengrad und sogar die Zahl ist Länge. Die resultierende Codierung ist 11100111010010011000110110011011001111011001110110 (hier sind besondere Aufmerksamkeit erforderlich, die hier genannte ungerade und sogar genannte Zahl sind die Einweise des Wertschriftenarrays ab 0).
Schließlich ist Base32 codiert. Die Dezimalzahl, die der binären Schnur entspricht, beträgt 28, 29, 4, 24, 27, 6, 1, 22. Die Konvertierung in Base32 ist WX4SV61Q, SO (40.222012, 116.248283) als WX4SV61Q codiert. (Die folgende Abbildung führt die Korrespondenz von Base32 ein)
Der entsprechende Ort des Code WX4SV61Q auf der Karte lautet wie folgt:
Hier beträgt die Codierungslänge unserer Geohash 8 und die Genauigkeit 19 Meter. In der folgenden Tabelle entspricht die Genauigkeit, die unterschiedlichen Codierungslängen entspricht:
Aus der obigen Genauigkeit können wir sehen, dass wir nur den Geohash finden müssen, der den Koordinaten des Elements mit WX4SV als Präfix entspricht.
Geohash -Erweiterung
Bisher haben wir ein gewisses Verständnis der räumlichen Indizes, aber die obige Einführung kann keine der folgenden Situationen erreichen:
Aus der Abbildung können wir erkennen, dass der rote Punkt näher am grünen Punkt oben und weiter vom grünen Punkt unten entfernt ist, aber der rote Punkt ist der gleiche wie die codierte Schnur des grünen Punkts unten und ist beide wx4g0. Die Idee, Grenzprobleme wie Geohash zu lösen, ist sehr einfach. Wenn wir suchen oder abfragen, entsprechen wir den umliegenden acht Bereichen, die das Grenzproblem gut lösen können. Als nächstes werden wir Geohash in Java implementieren.
Java -Implementierung
Vor der Implementierung definieren wir zunächst eine Standortbekette und verwenden sie, um die Informationen mit Breitengrad und Längengrad darzustellen:
/ ***@Beschreibung: Speichern und Longitude -Informationen*/ Package com.lulei.geo.bean; öffentliche Klasse Ortbean {public static Final Double Minlat = -90; öffentliches statisches endgültiges Doppel -Maxlat = 90; öffentliche statische endgültige doppelte minlng = -180; öffentliche statische endgültige Doppelmaxlng = 180; Private Double Lat; // Latitude [-90,90] Private Double Lng; // Longitude [-180,180] öffentliche Standortbean (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; }} Dann schreiben wir eine Klasse, um Geohash zu implementieren. Bei der Implementierung von Geohash müssen wir einige Konstanten sowie Breiten- und Längengradinformationen wie folgt definieren:
öffentliche Klasse Geohash {privater Ort für Standortbeams; /** * 1 2500 km; 2 630 km; 3 78 km; 4 30 km * 5 2,4 km; 6 610 m; 7 76m; 8 19m */ private int haslength = 8; // Breitengrad und Länge werden in Geohash Länge private int latlenlänge = 20 umgewandelt; // Breitengrad und Länge werden in binäre Länge private int lnGlength = 20 umgewandelt; //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'}; } Wenn wir Geohash instanziieren, müssen wir einige Eigenschaften zuweisen:
public geohash (double lat, double lng) {location = new location (lat, lng); setMinlatlng (); } public int gethashlength () {return hasHLength; } / *** @Author: lulei* @Description: Stellen Sie die minimale Einheit von Breiten- und Längengrads ein* / private void setminlatlng () {minlat = locationBean.maxlat - locationBean.minlat; für (int i = 0; i <latlength; i ++) {minlat /= 2.0; } minlng = locationBean.maxlng - locationBean.minlng; für (int i = 0; i <lnGlength; i ++) {minlng /= 2.0; }} Wenn wir Geohash verwenden, müssen wir die endgültige Codierungslänge festlegen, damit wir eine Methode zum Einstellen der Geohash -Länge schreiben
public boolean sethashlength (int länge) {if (Länge <1) {return false; } Hashlength = Länge; latlenlänge = (Länge * 5) / 2; if (Länge % 2 == 0) {lnGlength = latlength; } else {lnGlength = latlength + 1; } setminlatlng (); zurückkehren; } Mit diesen Einstellungen müssen wir den Längengrad und den Breitengrad in entsprechende Binärcodierungen umwandeln
private boolean [] Gethasharray (Doppelwert, Doppelmin, Doppelmax, int Länge) {if (Wert <min || Wert> max) {return null; } if (Länge <1) {return null; } boolean [] result = new Boolean [Länge]; für (int i = 0; i <länge; i ++) {double Mid = (min+max) / 2.0; if (value> mid) {result [i] = true; min = mid; } else {result [i] = false; max = mid; }} Rückgabeergebnis; } Nachdem wir die binäre Codierung von Breitengrad und Längengrad erhalten haben, müssen wir zwei binäre Saiten in einen verschmelzen
private boolean [] merge (boolean [] latarray, boolean [] lngarray) {if (latarray == null || lngarray == null) {return null; } boolean [] result = new boolean [lngarray.length + latarray.length]; Arrays.fill (Ergebnis, falsch); für (int i = 0; i <lngarray.length; i ++) {result [2 * i] = lngArray [i]; } für (int i = 0; i <latarray.length; i ++) {result [2 * i+1] = latarray [i]; } Rückgabeergebnis; } Schließlich müssen wir32 -Umwandlung der erhaltenen Binärumwandlung basieren
/ ** * @param lat * @param lng * @return * @Author: lulei * @Description: Holen Sie sich die Base32 -String von Breitengrad und Längengrad */ private String getgeoHashBase32 (double lat, double lng) {boolean [] bools = getGeObinary (lat, lng); if (bools == null) {return null; } StringBuffer sb = new StringBuffer (); für (int i = 0; i <bools.length; i = i + 5) {boolean [] Base32 = neuer boolean [5]; für (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: Fünf-Bit-Binärdehnung in Base32 * / private char getBase32CHAR (boolean [] Base32) {if (Base32 == null || Base32.Length! = 5) {return ''; } int num = 0; für (boolean bool: base32) {num << = 1; if (bool) {num += 1; }} return chars [num % chars.length]; } Für die Frage, wie Sie den Geohash -Wert der acht Umgebungsflächen erhalten können, können wir die folgende Transformation durchführen. Wir kennen bereits den Breitengrad und die Länge des aktuellen Punktes und wissen auch die Länge und Breite in jedem Bereich. Wenn die Länge hinzugefügt oder abgezogen wird, können wir uns auf der Länge der linken und rechten Bereiche des Gebiets befinden. Wenn der Breitengrad hinzugefügt oder subtrahiert wird, können wir den Breitengrad der oberen und unteren Teile des Bereichs erhalten, damit wir die Koordinaten eines Punktes in den acht Bereichen um den Bereich erhalten können. Wir berechnen die Koordinaten dieser acht Punkte, nämlich der Geohash -Code, der den acht Bereichen entspricht.
public list <string> getGgeoHashBase32For9 () {double links = location.getLat () - minlat; double rightlat = location.getLat () + minlat; double uplng = location.getLng () - minlng; double downlng = location.getLng () + minlng; List <String> Base32FOR9 = New ArrayList <String> (); // die 3 Zeichenfolgen auf der linken = getGgeohashbase32 (links, uplng); if (! (rutsUp == null || "" .Equals (links)) {Base32For9.Add (links); } String linkMid = getGeOhashBase32 (links, location.getLng ()); if (! (linkMid == null || "" .Equals (linkMid)) {Base32For9.Add (linkMid); } String linksdown = getgeoHashBase32 (links, Downlng); if (! (linksdown == null || "" .Equals (links)) {Base32For9.Add (links); } // Die 3 Zeichenfolgen in der Mitte von oben nach unten 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 Zeichenfolgen rechts von oben nach unten rechts = getGeOhashBase32 (rechter, uplng); if (! (rightup == null || "" .Equals (rightup)) {Base32For9.Add (rightup); } String rightmid = getGeOhashBase32 (rechtzeitig, uplng); if (! (rightup == null || "" .Equals (rightup)) {Base32For9.Add (rightup); } String rightmid = getGeOhashBase32 (rechter, location.getLng ()); if (! (rightmid == null || "" .Equals (rightmid)) {Base32For9.Add (rightMid); } String rechts = getGeOhashBase32 (rechter, downlng); if (! (rechtsdown == null || "" .Equals (rechts)) {Base32For9.Add (rechts); } return base32For9; } Auslaufergebnisse
Vollständiger Code
Im obigen Blog gibt es bereits einen vollständigen Code für LoacationBean, daher werde ich ihn hier nicht schreiben.
/ ***@Beschreibung: Geohash erkennt die Umwandlung von Breitengrad und Längengrad*/ Package com.lulei.geo; Import Java.util.ArrayList; Import Java.util.Arrays; importieren java.util.list; import com.lulei.geo.bean.locationBean; import com.lulei.util.jsonutil; öffentliche Klasse Geohash {privater Ort für Standortbeams; /** * 1 2500 km; 2 630 km; 3 78 km; 4 30 km * 5 2,4 km; 6 610 m; 7 76m; 8 19m */ private int haslength = 8; // Breitengrad und Länge werden in die Geohash -Länge private int latlenlänge = 20 umgewandelt; // Breitengrad und Länge werden in eine binäre Länge privat intlength = 20 umgewandelt; // Breitengrad und Länge werden in eine binäre Länge privates Double Minlat umgewandelt; // Einheitsgröße jeder Breite private Doppel -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 location (lat, lng); setMinlatlng (); } public int gethashlength () {return hasHLength; } / *** @Author: lulei* @Description: Stellen Sie die minimale Einheit von Breiten- und Längengrads ein* / private void setminlatlng () {minlat = locationBean.maxlat - locationBean.minlat; für (int i = 0; i <latlength; i ++) {minlat /= 2.0; } minlng = locationBean.maxlng - locationBean.minlng; für (int i = 0; i <lnGlength; i ++) {minlng /= 2.0; }} / ** * @return * @Author: lulei * @Description: Finden Sie den neun Koordinatenpunkt und die umliegenden Punkte * / publiclist <string> getgeoHashBase32FOR9 () {Double links = lactlat.getlat () - minlat; double rightlat = location.getLat () + minlat; double uplng = location.getLng () - minlng; double downlng = location.getLng () + minlng; List <String> Base32FOR9 = New ArrayList <String> (); // die 3 Zeichenfolgen auf der linken = getGgeohashbase32 (links, uplng); if (! (rutsUp == null || "" .Equals (links)) {Base32For9.Add (links); } String linkMid = getGeOhashBase32 (links, location.getLng ()); if (! (linkMid == null || "" .Equals (linkMid)) {Base32For9.Add (linkMid); } String linksdown = getgeoHashBase32 (links, Downlng); if (! (linksdown == null || "" .Equals (links)) {Base32For9.Add (links); } // Die 3 Zeichenfolgen von oben nach unten in der Mitte 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 Zeichenfolgen von oben nach unten auf der rechten Seite rechtzeitig if (! (rightup == null || "" .Equals (rightup)) {Base32For9.Add (rightup); } String rightmid = getGeOhashBase32 (rechter, location.getLng ()); if (! (rightmid == null || "" .Equals (rightmid)) {Base32For9.Add (rightMid); } String rechts = getGeOhashBase32 (rechter, downlng); if (! (rechtsdown == null || "" .Equals (rechts)) {Base32For9.Add (rechts); } return base32For9; } / ** * @param Länge * @return * @Author: lulei * @Description: Setzen Sie den Breitengrad und Längengrad auf GeoHash Länge * / public boolean sethashlength (int länge) {if (Länge <1) {return false; } Hashlength = Länge; latlenlänge = (Länge * 5) / 2; if (Länge % 2 == 0) {lnGlength = latlength; } else {lnGlength = latlength + 1; } setminlatlng (); zurückkehren; } / ** * @return * @Author: lulei * @Description: Holen Sie sich die Base32 -String von Breiten- und Längengrad * / public String getGeHashBase32 () {return getgeoHashBase32 (location.getLat (), location.getLng ()); } / ** * @param lat * @param lng * @return * @author: lulei * @Description: Holen Sie sich die Base32 -String von Breitengrad und Länge * / private String getGeOhashBase32 (double lat, double lng) {boolean [] bools = getgeObinary (lat, lngen); if (bools == null) {return null; } StringBuffer sb = new StringBuffer (); für (int i = 0; i <bools.length; i = i + 5) {boolean [] Base32 = neuer boolean [5]; für (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: Fünf-Bit-Binärdehnung in Base32 * / private char getBase32CHAR (boolean [] Base32) {if (Base32 == null || Base32.Length! = 5) {return ''; } int num = 0; für (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, location.maxlng, lnglength); Return Merge (Latarray, Lngarray); } / ** * @param latarray * @param lngarray * @return * @Author: lulei * @Description: Merge Latitude and Longitude Binary * / privat boolean [] merge (boolean [] latarray, boolean [] lngarray) {if (latarray == null || } boolean [] result = new boolean [lngarray.length + latarray.length]; Arrays.fill (Ergebnis, falsch); für (int i = 0; i <lngarray.length; i ++) {result [2 * i] = lngArray [i]; } für (int i = 0; i <latarray.length; i ++) {result [2 * i+1] = latarray [i]; } Rückgabeergebnis; } / ** * @param value * @param min * @param max * @return * @Author: lulei * @Description: Umwandeln Sie Zahlen in GeoHash -Binärstritten * / private boolean [] Gethasharray (Doppelwert, Double min, Double Max, intlänge) {if (value <max | } if (Länge <1) {return null; } boolean [] result = new boolean [Länge]; für (int i = 0; i <länge; i ++) {double Mid = (min+max) / 2.0; if (value> mid) {result [i] = true; min = mid; } else {result [i] = false; max = mid; }} Rückgabeergebnis; } public static void main (String [] args) {// Todo automatisch generierte Methode Stub Geohash g = new Geohash (40.222012, 116.248283); System.out.println (g.getgeohashbase32 ()); System.out.println (jsonutil.parsejson (g.getgeohashbase32For9 ())); }}Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, es wird für das Lernen aller hilfreich sein und ich hoffe, jeder wird Wulin.com mehr unterstützen.