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

评论(0)网络
阅读(163)喜欢(0)不喜欢(0)JavaScript/Ajax开发技巧