Geohash

GeoHash(1)-实践篇兄弟篇：GeoHash(2)-实现篇 一、前言最近有个需要，要计算出客户坐标左近5公里的所有门店，并依照步行间隔排序。 最间接的办法就是遍历该城市下的所有门店，然而该办法显著不可取，因为在门店数量微小，且还须要计算步行间隔并排序的状况下，工夫简单度过高。 忽然想到当年做图像遇见一个问题：给定一个视频中间断的三千帧，然而曾经乱序，通知你第一帧，将这三千帧进行排序。遍历图像的所有像素点同样不可取，过后的解决方案是利用感知哈希计算出所有图像的指纹，接着利用明氏间隔计算间隔第一张最近的图像作为第二张，而后计算间隔第二张最近的作为第三张，以此类推。 同样，必定也有哈希办法可将地理位置转换成某种编码，并且编码可用于天文计算。它就是 GeoHash。 二、相干常识进入注释之前，先一起回顾一下初中天文： 本初子午线以西为西经，分十二区，每区15度共180度；以东为东经，同样分十二区，共180度。 赤道以北为北纬，共90度；以南为南纬，同样90度。 那么在计算机中，坐标示意为： 西经为正数，东经为负数，因而经度取值[-180, 180]。 北纬为负数，南纬为正数，因而纬度取值[-90, 90]。 咱们晓得赤道长约四万公里，因而经度上每度约等于111公里。地球实际上是个不规则球体，但为了简便计算，咱们假如把纬度上每度约等于222公里。 三、初识 GeoHash1. 计算二进制编码首先计算二进制编码，经度上以[-180, 180]开始，纬度以[-90, 90]开始，每次将区间进行二分，若输出坐标小于两头值则编码为0，下次区间取左半区间；若大于则编码为1，下次区间取右半区间。以此类推，编码越长，越靠近坐标值，进而越准确。 以 118°04′04, 24°26′46 为例，首先计算经度的编码： 编码长度区间两头值编码阐明精度（千米）1[-180, 180]01118°04′04 大于 0°，因而编码1，取右区间199802[0, 180]901118°04′04 大于 90°99903[90, 180]1350118°04′04 小于 135°，因而编码0，取左区间49954[90, 135]112.51 2497.55[112.5, 135]123.750 1248.756[112.5, 123.75]118.1250 624.375‬7[112.5, 118.125]115.31251 312.1888[115.3125, 118.125]116.71875‬1 156.0949[116.71875‬, 118.125]117.4218751 78.047‬10[117.421875, 118.125]117.7734375‬1 39.024N....... ...同样情理，计算纬度得编码： 编码长度区间两头值编码阐明精度（千米）1[-90, 90]0124°26′46 大于 0°，因而编码1，取右区间199802[0, 90]45024°26′46 小于 45°，因而编码0，取左区间99903[0, 45]22.51 49954[22.5, 45]33.750 2497.55[22.5, 33.75]28.1250 1248.756[22.5, 28.125]25.31250 624.375‬7[22.5, 25.3125]23.9061 312.1888[23.906, 25.3125]24.6090 156.0949[23.906, 24.609]24.2575‬1 78.047‬10[24.2575‬, 24.609]24.4330 39.024N....... ...综上，假如咱们只取十位编码，经度上失去得编码为 1101001111，纬度上编码为 1010001010。 ...