ก่อนหน้านี้ในระหว่างกระบวนการค้นหาเนื้อหาที่ใช้ Lucene ฉันได้เรียนรู้ว่า Lucene สามารถดึงข้อมูลข้อความและข้อมูลเชิงตัวเลขได้และระยะทางเชิงพื้นที่ดูเหมือนว่าจะถูกนำไปใช้ในซอร์สโค้ด ในช่วงหกเดือนที่ผ่านมาฉันได้ติดต่อกับ Solr ซึ่งมีการค้นหาระยะทางเชิงพื้นที่ (ละติจูดและลองจิจูด) เมื่อเร็ว ๆ นี้ฉันได้เรียนรู้เกี่ยวกับการใช้งานและเรียนรู้ว่ามีเทคโนโลยีที่ค่อนข้างธรรมดาสำหรับการตระหนักถึงการค้นหาระยะทางเชิงพื้นที่ - Geohash ให้ฉันแนะนำ 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 เราแยก 20 ครั้งและในที่สุดก็คำนวณว่าการเข้ารหัส 40.222012 คือ 10111001001101000110
วิธีการเดียวกันนี้ใช้สำหรับลองจิจูดและการเข้ารหัส 116.248283 ได้รับเป็น 11010010101010101010101010101010101010101010101101
ต่อไปเรารวมการเข้ารหัสของละติจูดและลองจิจูด จำนวนคี่คือละติจูดและจำนวนคือลองจิจูด การเข้ารหัสผลลัพธ์คือ 1110011101001001100011011001101100100110110010000110110 (ต้องการความสนใจเป็นพิเศษที่นี่หมายเลขคี่และจำนวนที่กล่าวถึงที่นี่คือตัวห้อยของอาร์เรย์ค่าเริ่มต้นจาก 0);
ในที่สุด Base32 จะถูกเข้ารหัส ทศนิยมที่สอดคล้องกับสตริงไบนารีคือ 28, 29, 4, 24, 27, 6, 1, 22 ตามลำดับ การแปลงเป็น Base32 คือ WX4SV61Q ดังนั้น (40.222012, 116.248283) ถูกเข้ารหัสเป็น WX4SV61Q (รูปต่อไปนี้แนะนำการติดต่อของ Base32)
ตำแหน่งที่สอดคล้องกันของรหัส WX4SV61Q บนแผนที่มีดังนี้:
ที่นี่ความยาวการเข้ารหัสของ GeoHash ของเราคือ 8 และความแม่นยำคือ 19 เมตร ตารางต่อไปนี้แสดงรายการความแม่นยำที่สอดคล้องกับความยาวการเข้ารหัสที่แตกต่างกัน:
จากความแม่นยำข้างต้นเราจะเห็นว่าหากคุณต้องการเลือกรายการภายใน 2 กม. ของฉัน (40.222012, 116.248283) เราต้องค้นหา geohash ที่สอดคล้องกับพิกัดของรายการที่มี WX4SV เป็นคำนำหน้า
ส่วนขยายทางภูมิศาสตร์
จนถึงตอนนี้เรามีความเข้าใจบางอย่างเกี่ยวกับดัชนีเชิงพื้นที่ แต่การแนะนำข้างต้นไม่สามารถบรรลุสถานการณ์ต่อไปนี้ได้อย่างใดอย่างหนึ่ง:
เราสามารถเห็นได้จากรูปที่จุดสีแดงอยู่ใกล้กับจุดสีเขียวด้านบนและไกลออกไปจากจุดสีเขียวด้านล่าง แต่จุดสีแดงจะเหมือนกับสตริงที่เข้ารหัสของจุดสีเขียวด้านล่างและเป็นทั้ง WX4G0 ความคิดในการแก้ปัญหาขอบเขตเช่น Geohash นั้นง่ายมาก เมื่อเราค้นหาหรือสอบถามเราจะจับคู่พื้นที่แปดแห่งโดยรอบซึ่งสามารถแก้ปัญหาขอบเขตได้ดี ต่อไปเราจะใช้ Geohash ใน Java
การใช้งาน Java
ก่อนการดำเนินการก่อนอื่นเราจะกำหนดสถานที่ตั้งและใช้เพื่อแสดงข้อมูลละติจูดและลองจิจูด:
/ ***@คำอธิบาย: เก็บข้อมูลละติจูดและลองจิจูด*/ แพ็คเกจ com.lulei.geo.bean; Locationbean ชั้นเรียนสาธารณะ {สาธารณะคงที่ double minlat = -90; สาธารณะคงที่สุดท้ายคู่สุดท้าย maxlat = 90; สาธารณะคงที่สุดท้าย double minlng = -180; สาธารณะคงที่สุดท้ายสองครั้ง maxlng = 180; คู่หูสองครั้ง lat; // latitude [-90,90] สองคู่ lng; // ลองจิจูด [-180,180] สถานที่สาธารณะ (สอง lat, lng สองครั้ง) {this.lat = lat; this.lng = lng; } สาธารณะ double getLat () {return lat; } โมฆะสาธารณะ setLat (สอง lat) {this.lat = lat; } สาธารณะ double getlng () {return lng; } โมฆะสาธารณะ setlng (double lng) {this.lng = lng; - จากนั้นเราเขียนชั้นเรียนเพื่อใช้ GeoHash ในกระบวนการดำเนินการทางภูมิศาสตร์เราจำเป็นต้องกำหนดค่าคงที่และข้อมูลละติจูดและลองจิจูดบางอย่างดังนี้:
Geohash ชั้นเรียนสาธารณะ {สถานที่ตั้งส่วนตัว /** * 1 2500km; 2 630km; 3 78km; 4 30km * 5 2.4km; 6 610M; 7 76m; 8 19M */ ส่วนตัว int hashlength = 8; // ละติจูดและลองจิจูดจะถูกแปลงเป็นความยาว geohash ความยาว private int latlength = 20; // ละติจูดและลองจิจูดจะถูกแปลงเป็นความยาวไบนารีส่วนตัว int lnglength = 20; // ลองจิจูดและลองจิจูดจะถูกแปลงเป็นความยาวไบนารีส่วนตัวสองมินัลคู่; // ขนาดหน่วยของแต่ละละติจูดละติจูดแต่ละคู่ minlng; // การล่มสลายของลองจิจูดแต่ละอันจะถูกยุบตัวถ่านสุดท้ายส่วนตัว 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; - เมื่อสร้างอินสแตนซ์ Geohash เราต้องกำหนดคุณสมบัติบางอย่าง:
GeoHash สาธารณะ (Double Lat, Double LNG) {location = new LocationBean (lat, lng); setMinlatlng (); } public int gethashlength () {return hashlength; } / *** @author: lulei* @description: ตั้งค่าหน่วยขั้นต่ำของละติจูดและลองจิจูด* / โมฆะส่วนตัว setminlatlng () {minlat = locationbean.maxlat - locationbean.minlat; สำหรับ (int i = 0; i <latlength; i ++) {minlat /= 2.0; } minlng = locationbean.maxlng - locationbean.minlng; สำหรับ (int i = 0; i <lnglength; i ++) {minlng /= 2.0; - เมื่อเราใช้ Geohash เราต้องตั้งค่าความยาวการเข้ารหัสสุดท้ายดังนั้นเราจึงเขียนวิธีการตั้งค่าความยาว geohash
บูลีนสาธารณะ sethashlength (ความยาว int) {ถ้า (ความยาว <1) {return false; } hashLength = ความยาว; Latlength = (ความยาว * 5) / 2; if (ความยาว % 2 == 0) {lnglength = latlength; } else {lnglength = latlength + 1; } setMinlatlng (); กลับมาจริง; - ด้วยการตั้งค่าเหล่านี้เราจำเป็นต้องแปลงลองจิจูดและละติจูดเป็นการเข้ารหัสไบนารีที่สอดคล้องกัน
บูลีนส่วนตัว [] Gethasharray (ค่าคู่, สองนาที, สองเท่าสูงสุด, ความยาว int) {ถ้า (ค่า <นาที || ค่าสูงสุด> สูงสุด) {return null; } if (ความยาว <1) {return null; } บูลีน [] ผลลัพธ์ = บูลีนใหม่ [ความยาว]; สำหรับ (int i = 0; i <length; i ++) {double mid = (min+max) / 2.0; if (value> mid) {result [i] = true; ขั้นต่ำ = กลาง; } else {result [i] = false; สูงสุด = กลาง; }} ผลการส่งคืน; - หลังจากได้รับการเข้ารหัสไบนารีของละติจูดและลองจิจูดตามลำดับเราจำเป็นต้องรวมสองสายไบนารีเข้าด้วยกันเป็นหนึ่งเดียว
บูลีนส่วนตัว [] Merge (บูลีน [] Latarray, บูลีน [] lngarray) {ถ้า (latarray == null || lngarray == null) {return null; } บูลีน [] ผลลัพธ์ = บูลีนใหม่ [lngarray.length + latarray.length]; array.fill (ผลลัพธ์, เท็จ); สำหรับ (int i = 0; i <lngarray.length; i ++) {ผลลัพธ์ [2 * i] = lngarray [i]; } สำหรับ (int i = 0; i <latarray.length; i ++) {ผลลัพธ์ [2 * i+1] = latarray [i]; } ผลตอบแทนผลลัพธ์; - ในที่สุดเราจำเป็นต้องเปลี่ยนฐาน 32 ของการแปลงไบนารีที่ได้รับ
/ ** * @param lat * @param lng * @return * @author: lulei * @description: รับ base32 สตริงของละติจูดและลองจิจูด */ สตริงส่วนตัว getgeohashbase32 if (bools == null) {return null; } stringBuffer sb = new StringBuffer (); สำหรับ (int i = 0; i <bools.length; i = i + 5) {boolean [] base32 = บูลีนใหม่ [5]; สำหรับ (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: แปลงไบนารีห้าบิตเป็น base32 * / ถ่านส่วนตัว getbase32char (บูลีน [] base32) {ถ้า (base32 == null || base32.length! = 5) {return ''; } int num = 0; สำหรับ (บูลีนบูล: base32) {num << = 1; if (bool) {num += 1; }} return chars [num % chars.length]; - สำหรับคำถามว่าจะได้รับค่าทางภูมิศาสตร์ของพื้นที่รอบ ๆ แปดพื้นที่เราสามารถทำการเปลี่ยนแปลงต่อไปนี้ได้อย่างไร เรารู้ว่าละติจูดและลองจิจูดของจุดปัจจุบันอยู่แล้วและเราก็รู้ถึงความกว้างของลองจิจูดและละติจูดในแต่ละพื้นที่ หากมีการเพิ่มหรือลบลองจิจูดเราสามารถอยู่ที่ลองจิจูดของพื้นที่ด้านซ้ายและด้านขวาของพื้นที่ หากละติจูดถูกเพิ่มหรือลบออกเราสามารถรับละติจูดของส่วนบนและส่วนล่างของพื้นที่เพื่อให้เราสามารถรับพิกัดของจุดหนึ่งในแปดพื้นที่รอบ ๆ พื้นที่ เราคำนวณพิกัดของแปดจุดเหล่านี้ซึ่งเป็นรหัส geohash ที่สอดคล้องกับแปดพื้นที่
รายการสาธารณะ <String> getGeoHashBase32For9 () {double leftflat = location.getLat () - minlat; double rightlat = location.getLat () + minlat; double uplng = location.getlng () - minlng; double downlng = location.getlng () + minlng; รายการ <String> base32For9 = arrayList ใหม่ <String> (); // 3 สตริงทางซ้าย = getGeoHashBase32 (ซ้าย lat, Uplng); if (! (leftup == null || "" .equals (ซ้าย))) {base32for9.add (ซ้าย); } string leftmid = getGeoHashBase32 (ซ้าย, location.getLng ()); if (! (leftmid == null || "" .equals (liftmid))) {base32for9.add (ซ้าย); } string leftdown = getGeoHashBase32 (ซ้าย, downlng); if (! (leftdown == null || "" .equals (ซ้าย))) {base32for9.add (ซ้าย); } // 3 สตริงตรงกลางจากบนลงล่าง midup = getGeoHashBase32 (location.getLat (), UPLNG); if (! (midup == null || "" .equals (midup))) {base32for9.add (midup); } สตริง midmid = getGeoHashBase32 (location.getLat (), location.getlng ()); if (! (midmid == null || "" .equals (midmid))) {base32for9.add (midmid); } สตริง middown = getGeoHashBase32 (location.getLat (), downlng); if (! (middown == null || "" .equals (middown))) {base32for9.add (middown); } // 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); } สตริงขวา = getGeoHashBase32 (Rightlat, downlng); if (! (ขวา == null || "" .Equals (ขวา))) {base32for9.add (ขวา); } return base32for9; - การรันผลลัพธ์
กรอกรหัส
มีรหัส Loacationbean ที่สมบูรณ์ในบล็อกด้านบนดังนั้นฉันจะไม่เขียนที่นี่
/ ***@คำอธิบาย: Geohash ตระหนักถึงการแปลงละติจูดและลองจิจูด*/ แพ็คเกจ com.lulei.geo; นำเข้า java.util.arraylist; นำเข้า Java.util.Arrays; นำเข้า java.util.list; นำเข้า com.lulei.geo.bean.locationbean; นำเข้า com.lulei.util.jsonutil; Geohash ชั้นเรียนสาธารณะ {สถานที่ตั้งส่วนตัว /** * 1 2500km; 2 630km; 3 78km; 4 30km * 5 2.4km; 6 610m; 7 76m; 8 19M */ ส่วนตัว int hashlength = 8; // ละติจูดและลองจิจูดจะถูกแปลงเป็นความยาว geohash ความยาวส่วนตัว int latlength = 20; // ละติจูดและลองจิจูดจะถูกแปลงเป็นความยาวไบนารีส่วนตัว int lnglength = 20; // ละติจูดและลองจิจูดจะถูกแปลงเป็นความยาวไบนารีสองมินลาตส่วนตัว; // ขนาดหน่วยของแต่ละละติจูดส่วนตัวสอง minlng; // ลดลงของ Longitude Private Private Static Final [] chars = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'B', 'c', '' '' '' '' '' '', ' 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; GeoHash สาธารณะ (Double Lat, Double LNG) {location = new LocationBean (lat, lng); setMinlatlng (); } public int gethashlength () {return hashlength; } / *** @author: lulei* @description: ตั้งค่าหน่วยขั้นต่ำของละติจูดและลองจิจูด* / โมฆะส่วนตัว setminlatlng () {minlat = locationbean.maxlat - locationbean.minlat; สำหรับ (int i = 0; i <latlength; i ++) {minlat /= 2.0; } minlng = locationbean.maxlng - locationbean.minlng; สำหรับ (int i = 0; i <lnglength; i ++) {minlng /= 2.0; }} / ** * @return * @author: lulei * @description: ค้นหาจุดประสานงานเก้าจุดและจุดโดยรอบ * / รายการสาธารณะ <String> getGeoHashBase32For9 () {double leftlat = location.getLat () - minlat; double rightlat = location.getLat () + minlat; double uplng = location.getlng () - minlng; double downlng = location.getlng () + minlng; รายการ <String> base32For9 = arrayList ใหม่ <String> (); // 3 สตริงทางซ้าย = getGeoHashBase32 (ซ้าย lat, Uplng); if (! (leftup == null || "" .equals (ซ้าย))) {base32for9.add (ซ้าย); } string leftmid = getGeoHashBase32 (ซ้าย, location.getLng ()); if (! (leftmid == null || "" .equals (liftmid))) {base32for9.add (ซ้าย); } string leftdown = getGeoHashBase32 (ซ้าย, downlng); if (! (leftdown == null || "" .equals (ซ้าย))) {base32for9.add (ซ้าย); } // 3 สตริงจากบนลงล่างใน midup กลาง = getGeoHashBase32 (location.getLat (), UPLNG); if (! (midup == null || "" .equals (midup))) {base32for9.add (midup); } สตริง midmid = getGeoHashBase32 (location.getLat (), location.getlng ()); if (! (midmid == null || "" .equals (midmid))) {base32for9.add (midmid); } สตริง middown = getGeoHashBase32 (location.getLat (), downlng); if (! (middown == null || "" .equals (middown))) {base32for9.add (middown); } // 3 สตริงจากบนลงล่างทางด้านขวาขวา = 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); } สตริงขวา = getGeoHashBase32 (Rightlat, downlng); if (! (ขวา == null || "" .Equals (ขวา))) {base32for9.add (ขวา); } return base32for9; } / ** * @param length * @return * @author: lulei * @description: ตั้งค่าละติจูดและลองจิจูดเป็นความยาว geohash * / public boolean sethashlength (ความยาว int) {ถ้า (ความยาว <1) {return false; } hashLength = ความยาว; Latlength = (ความยาว * 5) / 2; if (ความยาว % 2 == 0) {lnglength = latlength; } else {lnglength = latlength + 1; } setMinlatlng (); กลับมาจริง; } / ** * @return * @author: lulei * @description: รับ base32 สตริงของละติจูดและลองจิจูด * / สตริงสาธารณะ getgeOhashbase32 () {return getGeoHashBase32 (location.getLat (), location.getlng (); } / ** * @param lat * @param lng * @return * @author: lulei * @description: รับ base32 สตริงของละติจูดและลองจิจูด * / สตริงส่วนตัว getgeohashbase32 if (bools == null) {return null; } stringBuffer sb = new StringBuffer (); สำหรับ (int i = 0; i <bools.length; i = i + 5) {boolean [] base32 = บูลีนใหม่ [5]; สำหรับ (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: แปลงไบนารีห้าบิตเป็น base32 * / ถ่านส่วนตัว getbase32char (บูลีน [] base32) {ถ้า (base32 == null || base32.length! = 5) {return ''; } int num = 0; สำหรับ (บูลีนบูล: base32) {num << = 1; if (bool) {num += 1; }} return chars [num % chars.length]; } / ** * @param lat * @param lng * @return * @author: lulei * @description: รับสตริงไบนารี geo ของพิกัด * / บูลีนส่วนตัว [] getGeobinary บูลีน [] lngarray = gethasharray (lng, locationbean.minlng, locationbean.maxlng, lnglength); Return Merge (Latarray, lngarray); } / ** * @param latarray * @param lngarray * @return * @author: lulei * @description: ผสานละติจูดและลองจิจูดไบนารี * / บูลีนส่วนตัว [] ผสาน (บูลีน [] Latarray, boolean [] lngarray) } บูลีน [] ผลลัพธ์ = บูลีนใหม่ [lngarray.length + latarray.length]; array.fill (ผลลัพธ์, เท็จ); สำหรับ (int i = 0; i <lngarray.length; i ++) {ผลลัพธ์ [2 * i] = lngarray [i]; } สำหรับ (int i = 0; i <latarray.length; i ++) {ผลลัพธ์ [2 * i+1] = latarray [i]; } ผลตอบแทนผลลัพธ์; } / ** * @param value * @param min * @param max * @return * @author: lulei * @description: แปลงตัวเลขเป็น geohash ไบนารีสตริง * / บูลีนส่วนตัว [] gethasharray } if (ความยาว <1) {return null; } บูลีน [] ผลลัพธ์ = บูลีนใหม่ [ความยาว]; สำหรับ (int i = 0; i <length; i ++) {double mid = (min+max) / 2.0; if (value> mid) {result [i] = true; ขั้นต่ำ = กลาง; } else {result [i] = false; สูงสุด = กลาง; }} ผลการส่งคืน; } โมฆะคงที่สาธารณะหลัก (สตริง [] args) {// วิธีการที่สร้างขึ้นอัตโนมัติ todo stub geohash g = ใหม่ geohash (40.222012, 116.248283); System.out.println (g.getgeohashbase32 ()); System.out.println (jsonutil.parsejson (g.getgeohashbase32for9 ())); -ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น