javascript实现geohash算法
geohash有以下几个特点:
首先,geohash用一个字符串表示经度和纬度两个坐标。某些情况下无法在两列上同时应用索引 (例如MySQL 4之前的版本,Google App Engine的数据层等),利用geohash,只需在一列上应用索引即可。
其次,geohash表示的并不是一个点,而是一个矩形区域。比如编码wx4g0ec19,它表示的是一个矩形区域。 使用者可以发布地址编码,既能表明自己位于北海公园附近,又不至于暴露自己的精确坐标,有助于隐私保护。
第三,编码的前缀可以表示更大的区域。例如wx4g0ec1,它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。 这个特性可以用于附近地点搜索。首先根据用户当前坐标计算geohash(例如wx4g0ec1)然后取其前缀进行查询 (SELECT * FROM place WHERE geohash LIKE 'wx4g0e%'),即可查询附近的所有地点。
Geohash比直接用经纬度的效率高很多。
Geohash的原理
Geohash的最简单的解释就是:将一个经纬度信息,转换成一个可以排序,可以比较的字符串编码
首先将纬度范围(-90, 90)平分成两个区间(-90,0)、(0, 90),如果目标纬度位于前一个区间,则编码为0,否则编码为1。
由于39.92324属于(0, 90),所以取编码为1。
然后再将(0, 90)分成 (0, 45), (45, 90)两个区间,而39.92324位于(0, 45),所以编码为0。
以此类推,直到精度符合要求为止,得到纬度编码为1011 1000 1100 0111 1001。
纬度范围 |
划分区间0 |
划分区间1 |
39.92324所属区间 |
(-90, 90) |
(-90, 0.0) |
(0.0, 90) |
1 |
(0.0, 90) |
(0.0, 45.0) |
(45.0, 90) |
0 |
(0.0, 45.0) |
(0.0, 22.5) |
(22.5, 45.0) |
1 |
(22.5, 45.0) |
(22.5, 33.75) |
(33.75, 45.0) |
1 |
(33.75, 45.0) |
(33.75, 39.375) |
(39.375, 45.0) |
1 |
(39.375, 45.0) |
(39.375, 42.1875) |
(42.1875, 45.0) |
0 |
(39.375, 42.1875) |
(39.375, 40.7812) |
(40.7812, 42.1875) |
0 |
(39.375, 40.7812) |
(39.375, 40.0781) |
(40.0781, 40.7812) |
0 |
(39.375, 40.0781) |
(39.375, 39.7265) |
(39.7265, 40.0781) |
1 |
(39.7265, 40.0781) |
(39.7265, 39.9023) |
(39.9023, 40.0781) |
1 |
(39.9023, 40.0781) |
(39.9023, 39.9902) |
(39.9902, 40.0781) |
0 |
(39.9023, 39.9902) |
(39.9023, 39.9462) |
(39.9462, 39.9902) |
0 |
(39.9023, 39.9462) |
(39.9023, 39.9243) |
(39.9243, 39.9462) |
0 |
(39.9023, 39.9243) |
(39.9023, 39.9133) |
(39.9133, 39.9243) |
1 |
(39.9133, 39.9243) |
(39.9133, 39.9188) |
(39.9188, 39.9243) |
1 |
(39.9188, 39.9243) |
(39.9188, 39.9215) |
(39.9215, 39.9243) |
1 |
经度也用同样的算法,对(-180, 180)依次细分,得到116.3906的编码为1101 0010 1100 0100 0100。
经度范围 |
划分区间0 |
划分区间1 |
116.3906所属区间 |
(-180, 180) |
(-180, 0.0) |
(0.0, 180) |
1 |
(0.0, 180) |
(0.0, 90.0) |
(90.0, 180) |
1 |
(90.0, 180) |
(90.0, 135.0) |
(135.0, 180) |
0 |
(90.0, 135.0) |
(90.0, 112.5) |
(112.5, 135.0) |
1 |
(112.5, 135.0) |
(112.5, 123.75) |
(123.75, 135.0) |
0 |
(112.5, 123.75) |
(112.5, 118.125) |
(118.125, 123.75) |
0 |
(112.5, 118.125) |
(112.5, 115.312) |
(115.312, 118.125) |
1 |
(115.312, 118.125) |
(115.312, 116.718) |
(116.718, 118.125) |
0 |
(115.312, 116.718) |
(115.312, 116.015) |
(116.015, 116.718) |
1 |
(116.015, 116.718) |
(116.015, 116.367) |
(116.367, 116.718) |
1 |
(116.367, 116.718) |
(116.367, 116.542) |
(116.542, 116.718) |
0 |
(116.367, 116.542) |
(116.367, 116.455) |
(116.455, 116.542) |
0 |
(116.367, 116.455) |
(116.367, 116.411) |
(116.411, 116.455) |
0 |
(116.367, 116.411) |
(116.367, 116.389) |
(116.389, 116.411) |
1 |
(116.389, 116.411) |
(116.389, 116.400) |
(116.400, 116.411) |
0 |
(116.389, 116.400) |
(116.389, 116.394) |
(116.394, 116.400) |
0 |
接下来将经度和纬度的编码合并,奇数位是纬度,偶数位是经度,得到编码 11100 11101 00100 01111 00000 01101 01011 00001。
最后,用0-9、b-z(去掉a, i, l, o)这32个字母进行base32编码,得到(39.92324, 116.3906)的编码为wx4g0ec1。
十进制 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
base32 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
b |
c |
d |
e |
f |
g |
十进制 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
base32 |
h |
j |
k |
m |
n |
p |
q |
r |
s |
t |
u |
v |
w |
x |
y |
z |
解码算法与编码算法相反,先进行base32解码,然后分离出经纬度,最后根据二进制编码对经纬度范围进行细分即可,这里不再赘述。
以上来源:http://www.cnblogs.com/dengxinglin/archive/2012/12/14/2817761.html
来源:http://blog.csdn.net/ghsau/article/details/50591932
拿到移动设备的经纬度,计算geohash code,这时可以指定精度计算,那指定多长呢?我们需要一个geohash code长度和距离的对照表:
geohash length width height 1 5,009.4km 4,992.6km 2 1,252.3km 624.1km 3 156.5km 156km 4 39.1km 19.5km 5 4.9km 4.9km 6 1.2km 609.4m 7 152.9m 152.4m 8 38.2m 19m 9 4.8m 4.8m 10 1.2m 59.5cm 11 14.9cm 14.9cm 12 3.7cm 1.9cm https://en.wikipedia.org/wiki/Geohash#Cell_Dimensions
假设我们的需求是1公里范围内的商户,geohash code的长度设置为5就可以了,计算出移动设备经纬度的geohash code之后,SQL是这样:
SELECT id, name FROM customer WHERE geo_code LIKE CONCAT(?, '%');
javascript实现geohash算法
// geohash.js // Geohash library for Javascript // (c) 2008 David Troy // Distributed under the MIT License BITS = [16, 8, 4, 2, 1]; BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"; NEIGHBORS = { right : { even : "bc01fg45238967deuvhjyznpkmstqrwx" }, left : { even : "238967debc01fg45kmstqrwxuvhjyznp" }, top : { even : "p0r21436x8zb9dcf5h7kjnmqesgutwvy" }, bottom : { even : "14365h7k9dcfesgujnmqp0r2twvyx8zb" } }; BORDERS = { right : { even : "bcfguvyz" }, left : { even : "0145hjnp" }, top : { even : "prxz" }, bottom : { even : "028b" } }; NEIGHBORS.bottom.odd = NEIGHBORS.left.even; NEIGHBORS.top.odd = NEIGHBORS.right.even; NEIGHBORS.left.odd = NEIGHBORS.bottom.even; NEIGHBORS.right.odd = NEIGHBORS.top.even; BORDERS.bottom.odd = BORDERS.left.even; BORDERS.top.odd = BORDERS.right.even; BORDERS.left.odd = BORDERS.bottom.even; BORDERS.right.odd = BORDERS.top.even; function refine_interval(interval, cd, mask) { if (cd&mask) interval[0] = (interval[0] + interval[1])/2; else interval[1] = (interval[0] + interval[1])/2; } function calculateAdjacent(srcHash, dir) { srcHash = srcHash.toLowerCase(); var lastChr = srcHash.charAt(srcHash.length-1); var type = (srcHash.length % 2) ? 'odd' : 'even'; var base = srcHash.substring(0,srcHash.length-1); if (BORDERS[dir][type].indexOf(lastChr)!=-1) base = calculateAdjacent(base, dir); return base + BASE32[NEIGHBORS[dir][type].indexOf(lastChr)]; } function decodeGeoHash(geohash) { var is_even = 1; var lat = []; var lon = []; lat[0] = -90.0; lat[1] = 90.0; lon[0] = -180.0; lon[1] = 180.0; lat_err = 90.0; lon_err = 180.0; for (i=0; i<geohash.length; i++) { c = geohash[i]; cd = BASE32.indexOf(c); for (j=0; j<5; j++) { mask = BITS[j]; if (is_even) { lon_err /= 2; refine_interval(lon, cd, mask); } else { lat_err /= 2; refine_interval(lat, cd, mask); } is_even = !is_even; } } lat[2] = (lat[0] + lat[1])/2; lon[2] = (lon[0] + lon[1])/2; return { latitude: lat, longitude: lon}; } function encodeGeoHash(latitude, longitude) { var is_even=1; var i=0; var lat = []; var lon = []; var bit=0; var ch=0; var precision = 12; geohash = ""; lat[0] = -90.0; lat[1] = 90.0; lon[0] = -180.0; lon[1] = 180.0; while (geohash.length < precision) { if (is_even) { mid = (lon[0] + lon[1]) / 2; if (longitude > mid) { ch |= BITS[bit]; lon[0] = mid; } else lon[1] = mid; } else { mid = (lat[0] + lat[1]) / 2; if (latitude > mid) { ch |= BITS[bit]; lat[0] = mid; } else lat[1] = mid; } is_even = !is_even; if (bit < 4) bit++; else { geohash += BASE32[ch]; bit = 0; ch = 0; } } return geohash; }
来源:https://github.com/davetroy/geohash-js
加支付宝好友偷能量挖...