#

Geohash
随着移动终端的普及，很多应用都基于LBS功能，附近的某某（餐馆、银行、妹纸等等）。

基础数据中，一般保存了目标位置的经纬度；利用用户提供的经纬度，进行对比，从而获得是否在附近。

目标：
查找附近的XXX，由近到远返回结果，且结果中有与目标点的距离。

针对查找附近的XXX，提出两个方案，如下：

一、方案A:

抽象为球面两点距离的计算，即已知道球面上两点的经纬度；
点（纬度，经度），A($radLat1,$radLng1)、B($radLat2,$radLng2);

优点：通俗易懂，部署简单便捷

缺点：每次都会查询数据库，性能堪忧

1、推导

通过余弦定理以及弧度计算方法，最终推导出来的算式A为：

帮助

1	`$s` `=` `acos` `(` `cos` `(` `$radLat1` `)` `cos` `(` `$radLat2` `)` `cos` `(` `$radLng1` `-` `$radLng2` `)+sin(` `$radLat1` `)sin(` `$radLat2` `))` `$R` `;`

目前网上大多使用Google公开的距离计算公司，推导算式B为：

帮助

1	`$s` `= 2asin(sqrt(pow(sin((` `$radLat1` `-` `$radLat2` `)/2),2)+` `cos` `(` `$radLat1` `)` `cos` `(` `$radLat2` `)pow(sin((` `$radLng1` `-` `$radLng2` `)/2),2)))` `$R` `;`

其中 :
$radLat1、$radLng1，$radLat2，$radLng2 为弧度

$R 为地球半径

2、通过测试两种算法，结果相同且都正确，但通过PHP代码测试，两点间距离，10W次性能对比，自行推导版本计算时长算式B较优，如下：

//算式A
0.56368780136108float(431)
0.57460689544678float(431)
0.59051203727722float(431)

//算式B
0.47404885292053float(431)
0.47808718681335float(431)
0.47946381568909float(431)

3、所以采用数学方法推导出的公式:

帮助

<?php

//根据经纬度计算距离其中A($lat1,$lng1)、B($lat2,$lng2)

public
static
function
getDistance(
$lat1
,
$lng1
,
$lat2
,
$lng2
)

{

//地球半径

$R
= 6378137;

//将角度转为狐度

$radLat1
=
deg2rad
(
$lat1
);

$radLat2
=
deg2rad
(
$lat2
);

$radLng1
=
deg2rad
(
$lng1
);

$radLng2
=
deg2rad
(
$lng2
);

//结果

$s
=
acos
(
cos
(
$radLat1
)
cos
(
$radLat2
)
cos
(
$radLng1
-
$radLng2
)+sin(
$radLat1
)sin(
$radLat2
))
$R
;

//精度

$s
=
round
(
$s
* 10000)/10000;

return
round
(
$s
);

}

?>

4、在实际应用中，需要从数据库中遍历取出符合条件，以及排序等操作，

将所有数据取出，然后通过PHP循环对比，筛选符合条件结果，显然性能低下；所以我们利用下Mysql存储函数来解决这个问题吧。

4.1、创建Mysql存储函数,并对经纬度字段建立索引

帮助

DELIMITER $$

CREATE DEFINER=root@% FUNCTION GETDISTANCE(lat1 DOUBLE, lng1 DOUBLE, lat2 DOUBLE, lng2 DOUBLE) RETURNS double

READS SQL DATA

DETERMINISTIC

BEGIN

DECLARE RAD DOUBLE;

DECLARE EARTH_RADIUS DOUBLE DEFAULT 6378137;

DECLARE radLat1 DOUBLE;

DECLARE radLat2 DOUBLE;

DECLARE radLng1 DOUBLE;

DECLARE radLng2 DOUBLE;

DECLARE s DOUBLE;

SET RAD = PI() / 180.0;

SET radLat1 = lat1 RAD;

SET radLat2 = lat2 RAD;

SET radLng1 = lng1 RAD;

SET radLng2 = lng2 RAD;

SET s =
ACOS
(
COS
(radLat1)
COS
(radLat2)
COS
(radLng1-radLng2)+SIN(radLat1)SIN(radLat2))EARTH_RADIUS;

SET s =
ROUND
(s * 10000) / 10000;

RETURN s;

END
$$

DELIMITER ;

4.2、查询SQL

通过SQL，可设置距离以及排序；可搜索出符合条件的信息，以及有一个较好的排序

帮助

1	`SELECT *,latitude,longitude,GETDISTANCE(latitude,longitude,30.663262,104.071619) AS distance FROM mb_shop_ext where 1 HAVING distance<1000 ORDER BY distance ASC LIMIT 0,10`

二、方案B

Geohash算法；geohash是一种地址编码，它能把二维的经纬度编码成一维的字符串。
比如，成都永丰立交的编码是wm3yr31d2524

优点:

1、利用一个字段，即可存储经纬度；搜索时，只需一条索引，效率较高
2、编码的前缀可以表示更大的区域，查找附近的，非常方便。 SQL中，LIKE ‘wm3yr3%’，即可查询附近的所有地点。
3、通过编码精度可模糊坐标、隐私保护等。

缺点: 距离和排序需二次运算（筛选结果中运行，其实挺快）

1、geohash的编码算法

成都永丰立交经纬度(30.63578,104.031601)

1.1、纬度范围(-90, 90)平分成两个区间(-90, 0)、(0, 90)，如果目标纬度位于前一个区间，则编码为0，否则编码为1。
由于30.625265属于(0, 90)，所以取编码为1。
然后再将(0, 90)分成 (0, 45), (45, 90)两个区间，而39.92324位于(0, 45)，所以编码为0，
然后再将(0, 45)分成 (0, 22.5), (22.5, 45)两个区间，而39.92324位于(22.5, 45)，所以编码为1，
依次类推可得永丰立交纬度编码为101010111001001000100101101010。

1.2、经度也用同样的算法，对(-180, 180)依次细分，(-180，0)、(0,180) 得出编码110010011111101001100000000000

1.3、合并经纬度编码，从高到低，先取一位经度，再取一位纬度；得出结果 111001001100011111101011100011000010110000010001010001000100

1.4、用0-9、b-z（去掉a, i, l, o）这32个字母进行base32编码，得到(30.63578,104.031601)的编码为wm3yr31d2524。

帮助

11100 10011 00011 11110 10111 00011 00001 01100 00010 00101 00010 00100 => wm3yr31d2524

十进制 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

2、策略

1、在纬度和经度入库时，数据库新加一字段geohash，记录此点的geohash值

2、查找附近，利用在SQL中 LIKE ‘wm3yr3%’；且此结果可缓存；在小区域内，不会因为改变经纬度，而重新数据库查询

3、查找出的有限结果，如需要求距离或者排序，可利用距离公式和二维数据排序；此时也是少量数据，会很快的。

3、PHP基类

geohash.class.php

帮助

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

<?php

/*

Encode and decode geohashes

/

class
Geohash

{

private
$coding
=
“0123456789bcdefghjkmnpqrstuvwxyz”
;

private
$codingMap
=
array
();

public
function
Geohash()

{

for
(
$i
=0;
$i
<32;
$i
++)

{

$this
->codingMap[
substr
(
$this
->coding,
$i
,1)]=
str_pad
(
decbin
(
$i
), 5,
“0”
, STR_PAD_LEFT);

}

public
function
decode(
$hash
)

{

$binary
=
“”
;

$hl
=
strlen
(
$hash
);

for
(
$i
=0;
$i
<
$hl
;
$i
++)

{

$binary
.=
$this
->codingMap[
substr
(
$hash
,
$i
,1)];

}

$bl
=
strlen
(
$binary
);

$blat
=
“”
;

$blong
=
“”
;

for
(
$i
=0;
$i
<
$bl
;
$i
++)

{

if
(
$i
%2)

$blat
=
$blat
.
substr
(
$binary
,
$i
,1);

else

$blong
=
$blong
.
substr
(
$binary
,
$i
,1);

}

$lat
=
$this
->binDecode(
$blat
,-90,90);

$long
=
$this
->binDecode(
$blong
,-180,180);

$latErr
=
$this
->calcError(
strlen
(
$blat
),-90,90);

$longErr
=
$this
->calcError(
strlen
(
$blong
),-180,180);

$latPlaces
=max(1, -
round
(log10(
$latErr
))) - 1;

$longPlaces
=max(1, -
round
(log10(
$longErr
))) - 1;

$lat
=
round
(
$lat
,
$latPlaces
);

$long
=
round
(
$long
,
$longPlaces
);

return
array
(
$lat
,
$long
);

}

public
function
encode(
$lat
,
$long
)

{

$plat
=
$this
->precision(
$lat
);

$latbits
=1;

$err
=45;

while
(
$err
>
$plat
)

{

$latbits
++;

$err
/=2;

}

$plong
=
$this
->precision(
$long
);

$longbits
=1;

$err
=90;

while
(
$err
>
$plong
)

{

$longbits
++;

$err
/=2;

}

$bits
=max(
$latbits
,
$longbits
);

$longbits
=
$bits
;

$latbits
=
$bits
;

$addlong
=1;

while
((
$longbits
+
$latbits
)%5 != 0)

{

$longbits
+=
$addlong
;

$latbits
+=!
$addlong
;

$addlong
=!
$addlong
;

}

$blat
=
$this
->binEncode(
$lat
,-90,90,
$latbits
);

$blong
=
$this
->binEncode(
$long
,-180,180,
$longbits
);

$binary
=
“”
;

$uselong
=1;

while
(
strlen
(
$blat
)+
strlen
(
$blong
))

{

if
(
$uselong
)

{

$binary
=
$binary
.
substr
(
$blong
,0,1);

$blong
=
substr
(
$blong
,1);

}

else

{

$binary
=
$binary
.
substr
(
$blat
,0,1);

$blat
=
substr
(
$blat
,1);

}

$uselong
=!
$uselong
;

}

$hash
=
“”
;

for
(
$i
=0;
$i
<
strlen
(
$binary
);
$i
+=5)

{

$n
=
bindec
(
substr
(
$binary
,
$i
,5));

$hash
=
$hash
.
$this
->coding[
$n
];

}

return
$hash
;

}

private
function
calcError(
$bits
,
$min
,
$max
)

{

$err
=(
$max
-
$min
)/2;

while
(
$bits
—)

$err
/=2;

return
$err
;

}

private
function
precision(
$number
)

{

$precision
=0;

$pt
=
strpos
(
$number
,
‘.’
);

if
(
$pt
!==false)

{

$precision
=-(
strlen
(
$number
)-
$pt
-1);

}

return
pow(10,
$precision
)/2;

}

private
function
binEncode(
$number
,
$min
,
$max
,
$bitcount
)

{

if
(
$bitcount
==0)

return
“”
;

$mid
=(
$min
+
$max
)/2;

if
(
$number
>
$mid
)

return
“1”
.
$this
->binEncode(
$number
,
$mid
,
$max
,
$bitcount
-1);

else

return
“0”
.
$this
->binEncode(
$number
,
$min
,
$mid
,
$bitcount
-1);

}

private
function
binDecode(
$binary
,
$min
,
$max
)

{

$mid
=(
$min
+
$max
)/2;

if
(
strlen
(
$binary
)==0)

return
$mid
;

$bit
=
substr
(
$binary
,0,1);

$binary
=
substr
(
$binary
,1);

if
(
$bit
==1)

return
$this
->binDecode(
$binary
,
$mid
,
$max
);

else

return
$this
->binDecode(
$binary
,
$min
,
$mid
);

}

?>

三、测试

帮助

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

<?php

require_once
(
‘Mysql.class.php’
);

require_once
(
‘geohash.class.php’
);

//mysql

$conf
=
array
(

‘host’
=>
‘127.0.0.1’
,

‘port’
=> 3306,

‘user’
=>
‘root’
,

‘password’
=>
‘123456’
,

‘database’
=>
‘mocube’
,

‘charset’
=>
‘utf8’
,

‘persistent’
=> false

);

$mysql
=
new
Db_Mysql(
$conf
);

$geohash
=
new
Geohash;

//经纬度转换成Geohash

/

$sql = ‘select shop_id,latitude,longitude from mb_shop_ext’;

$data = $mysql->queryAll($sql);

foreach($data as $val)

{


$geohash_val = $geohash->encode($val[‘latitude’],$val[‘longitude’]);


$sql = ‘update mb_shop_ext set geohash= “‘.$geohash_val.’” where shop_id = ‘.$val[‘shop_id’];


echo $sql;


$re = $mysql->query($sql);


var_dump($re);

}

/

//获取附近的信息

$n_latitude
=
$_GET
[
‘la’
];

$n_longitude
=
$_GET
[
‘lo’
];

//开始

$b_time
= microtime(true);

//方案A，直接利用数据库存储函数，遍历排序

/

$sql = ‘SELECT

,latitude,longitude,GETDISTANCE(latitude,longitude,’.$n_latitude.’,’.$n_longitude.’) AS distance FROM  mb_shop_ext where 1 HAVING distance<1000 ORDER BY distance ASC’;

$data = $mysql->queryAll($sql);

//结束

$e_time = microtime(true);

echo $e_time - $b_time;

var_dump($data);

exit;

/

//方案B geohash求出附近，然后排序

//当前 geohash值

$n_geohash
=
$geohash
->encode(
$n_latitude
,
$n_longitude
);

//附近

$n
=
$_GET
[
‘n’
];

$like_geohash
=
substr
(
$n_geohash
, 0,
$n
);

$sql
=
‘select from mb_shop_ext where geohash like “‘
.
$like_geohash
.
‘%”‘
;

echo
$sql
;

$data
=
$mysql
->queryAll(
$sql
);

//算出实际距离

foreach
(
$data
as
$key
=>
$val
)

{

$distance
= getDistance(
$n_latitude
,
$n_longitude
,
$val
[
‘latitude’
],
$val
[
‘longitude’
]);

$data
[
$key
][
‘distance’
] =
$distance
;

//排序列

$sortdistance
[
$key
] =
$distance
;

}

//距离排序

array_multisort
(
$sortdistance
,SORT_ASC,
$data
);

//结束

$e_time
= microtime(true);

echo
$e_time
-
$b_time
;

var_dump(
$data
);

//根据经纬度计算距离其中A($lat1,$lng1)、B($lat2,$lng2)

function
getDistance(
$lat1
,
$lng1
,
$lat2
,
$lng2
)

{

//地球半径

$R
= 6378137;

//将角度转为狐度

$radLat1
=
deg2rad
(
$lat1
);

$radLat2
=
deg2rad
(
$lat2
);

$radLng1
=
deg2rad
(
$lng1
);

$radLng2
=
deg2rad
(
$lng2
);

//结果

$s
=
acos
(
cos
(
$radLat1
)
cos
(
$radLat2
)
cos
(
$radLng1
-
$radLng2
)+sin(
$radLat1
)sin(
$radLat2
))
$R
;

//精度

$s
=
round
(
$s
* 10000)/10000;