地理位置计算之geohash算法
地理位置距离实现目标：
最近在做共享单车单车的项目，用户打开APP后，如果根据当前的经纬度坐标获取附近的车辆呢？
特点：
- geohash用一个字符串表示经度和纬度两个坐标（可以加索引）
- geohash表示的并不是一个点，而是一个矩形区域
- geohash编码的前缀可以表示更大的区域。
原理:
- geohash算法将地球理解为一个二维平面，将平面递归分解成更小的子块，每个子块在一定经纬度范围内拥有相同的编码，这种方式简单粗暴，可以满足对小规模的数据进行经纬度的检索
- 通过对经纬度的分割,将地球分割成无数的小正方形,每个区域,就是个geohash编码
- geohash其实就是将整个地图或者某个分割所得的区域进行一次划分，由于采用的是base32编码方式，即Geohash中的每一个字母或者数字（如wx4g0e中的w）都是由5bits组成（2^5 = 32，base32），这5bits可以有32中不同的组合（0~31），这样我们可以将整个地图区域分为32个区域，通过00000 ~ 11111来标识这32个区域。第一次对地图划分后的情况如下图所示（每个区域中的编号对应于该区域所对应的编码)
- 如图：
Geohash的最简单的解释就是：将一个经纬度信息，转换成一个可以排序，可以比较的字符串编码
Geohash类
namespace geohash;
/**
*
* Encode and decode geohashes
* 编码和解码地理数据
* Find neighbors
* 寻找邻居
*/
class Geohash {
private $bitss = array(16, 8, 4, 2, 1);
private $neighbors = array();
private $borders = array();
private $coding = "0123456789bcdefghjkmnpqrstuvwxyz";
private $codingMap = array();
public function __construct() {
$this->neighbors['right']['even'] = 'bc01fg45238967deuvhjyznpkmstqrwx';
$this->neighbors['left']['even'] = '238967debc01fg45kmstqrwxuvhjyznp';
$this->neighbors['top']['even'] = 'p0r21436x8zb9dcf5h7kjnmqesgutwvy';
$this->neighbors['bottom']['even'] = '14365h7k9dcfesgujnmqp0r2twvyx8zb';
$this->borders['right']['even'] = 'bcfguvyz';
$this->borders['left']['even'] = '0145hjnp';
$this->borders['top']['even'] = 'prxz';
$this->borders['bottom']['even'] = '028b';
$this->neighbors['bottom']['odd'] = $this->neighbors['left']['even'];
$this->neighbors['top']['odd'] = $this->neighbors['right']['even'];
$this->neighbors['left']['odd'] = $this->neighbors['bottom']['even'];
$this->neighbors['right']['odd'] = $this->neighbors['top']['even'];
$this->borders['bottom']['odd'] = $this->borders['left']['even'];
$this->borders['top']['odd'] = $this->borders['right']['even'];
$this->borders['left']['odd'] = $this->borders['bottom']['even'];
$this->borders['right']['odd'] = $this->borders['top']['even'];
//build map from encoding char to 0 padded bitfield
for($i=0; $i<32; $i++) {
$this->codingMap[substr($this->coding, $i, 1)] = str_pad(decbin($i), 5, "0", STR_PAD_LEFT);
}
}
/**
* Decode a geohash and return an array with decimal lat,long in it
* 解码geohash并返回一个带有十进制lat的数组，长整数
* Author: Bruce Chen (weibo: @一个开发者)
*/
public function decode($hash) {
//decode hash into binary string
$binary = "";
$hl = strlen($hash);
for ($i=0; $i<$hl; $i++) {
$binary .= $this->codingMap[substr($hash, $i, 1)];
}
//split the binary into lat and log binary strings
$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);
}
//now concert to decimal
$lat = $this->binDecode($blat, -90, 90);
$long = $this->binDecode($blong, -180, 180);
//figure out how precise the bit count makes this calculation
$latErr = $this->calcError(strlen($blat), -90, 90);
$longErr = $this->calcError(strlen($blong), -180, 180);
//how many decimal places should we use? There's a little art to
//this to ensure I get the same roundings as geohash.org
$latPlaces = max(1, -round(log10($latErr))) - 1;
$longPlaces = max(1, -round(log10($longErr))) - 1;
//round it
$lat = round($lat, $latPlaces);
$long = round($long, $longPlaces);
return array($lat, $long);
}
private function calculateAdjacent($srcHash, $dir) {
$srcHash = strtolower($srcHash);
$lastChr = $srcHash[strlen($srcHash) - 1];
$type = (strlen($srcHash) % 2) ? 'odd' : 'even';
$base = substr($srcHash, 0, strlen($srcHash) - 1);
if (strpos($this->borders[$dir][$type], $lastChr) !== false) {
$base = $this->calculateAdjacent($base, $dir);
}
return $base . $this->coding[strpos($this->neighbors[$dir][$type], $lastChr)];
}
public function neighbors($srcHash) {
$geohashPrefix = substr($srcHash, 0, strlen($srcHash) - 1);
$neighbors['top'] = $this->calculateAdjacent($srcHash, 'top');
$neighbors['bottom'] = $this->calculateAdjacent($srcHash, 'bottom');
$neighbors['right'] = $this->calculateAdjacent($srcHash, 'right');
$neighbors['left'] = $this->calculateAdjacent($srcHash, 'left');
$neighbors['topleft'] = $this->calculateAdjacent($neighbors['left'], 'top');
$neighbors['topright'] = $this->calculateAdjacent($neighbors['right'], 'top');
$neighbors['bottomright'] = $this->calculateAdjacent($neighbors['right'], 'bottom');
$neighbors['bottomleft'] = $this->calculateAdjacent($neighbors['left'], 'bottom');
return $neighbors;
}
/**
* Encode a hash from given lat and long
* Author: Bruce Chen (weibo: @一个开发者)
*/
public function encode($lat, $long) {
//how many bits does latitude need?
$plat = $this->precision($lat);
$latbits = 1;
$err = 45;
while($err > $plat) {
$latbits++;
$err /= 2;
}
//how many bits does longitude need?
$plong = $this->precision($long);
$longbits = 1;
$err = 90;
while($err > $plong) {
$longbits++;
$err /= 2;
}
//bit counts need to be equal
$bits = max($latbits, $longbits);
//as the hash create bits in groups of 5, lets not
//waste any bits - lets bulk it up to a multiple of 5
//and favour the longitude for any odd bits
$longbits = $bits;
$latbits = $bits;
$addlong = 1;
while (($longbits + $latbits) % 5 != 0) {
$longbits += $addlong;
$latbits += !$addlong;
$addlong = !$addlong;
}
//encode each as binary string
$blat = $this->binEncode($lat, -90, 90, $latbits);
$blong = $this->binEncode($long, -180, 180, $longbits);
//merge lat and long together
$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;
}
//convert binary string to hash
$hash = "";
for ($i=0; $i<strlen($binary); $i+=5) {
$n = bindec(substr($binary, $i, 5));
$hash = $hash.$this->coding[$n];
}
return $hash;
}
/**
* What's the maximum error for $bits bits covering a range $min to $max
*/
private function calcError($bits, $min, $max) {
$err = ($max - $min) / 2;
while ($bits--)
$err /= 2;
return $err;
}
/*
* returns precision of number
* precision of 42 is 0.5
* precision of 42.4 is 0.05
* precision of 42.41 is 0.005 etc
*
* Author: Bruce Chen (weibo: @一个开发者)
*/
private function precision($number) {
$precision = 0;
$pt = strpos($number,'.');
if ($pt !== false) {
$precision = -(strlen($number) - $pt - 1);
}
return pow(10, $precision) / 2;
}
/**
* create binary encoding of number as detailed in http://en.wikipedia.org/wiki/Geohash#Example
* removing the tail recursion is left an exercise for the reader
*
* Author: Bruce Chen (weibo: @一个开发者)
*/
private function binEncode($number, $min, $max, $bitcount) {
if ($bitcount == 0)
return "";
#echo "$bitcount: $min $max<br>";
//this is our mid point - we will produce a bit to say
//whether $number is above or below this mid point
$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);
}
/**
* decodes binary encoding of number as detailed in http://en.wikipedia.org/wiki/Geohash#Example
* removing the tail recursion is left an exercise for the reader
*
* Author: Bruce Chen (weibo: @一个开发者)
*/
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);
}
}
使用：
- 首先将共享单车的经纬度转换成geohash编码
$geohash = new Geohash();
//生成逆地理位置编码
$data['car_geohash'] = $geohash->encode($latitude,$longitude);
- 当用户进入APP后，授权获取到用户当前位置的经纬度，然后获取附近的geohash值
$geohash = new Geohash();
//将用户的精度的geohash
$astr = $geohash->encode($lat,$lng);
//取前缀，前缀越长范围越小
$astr = substr($astr, 0, 5);
$data = $geohash->neighbors($astr);
$data['center'] = $astr;
var_dump($data);
- 经过上面的打印，我们可以获取到9个geohash值
Array
(
[top] => wx4eqx
[bottom] => wx4eqt
[right] => wx4eqy
[left] => wx4eqq
[topleft] => wx4eqr
[topright] => wx4eqz
[bottomright] => wx4eqv
[bottomleft] => wx4eqm
[center] => wx4eqw
)
- 然后根据上面的9个geohash值去表中模糊查询（查询字段一定要加索引）
$rows = Db::table('car')
->whereOr('astr','like',$data['top'].'%')
->whereOr('astr','like',$data['bottom'].'%')
->whereOr('astr','like',$data['right'].'%')
->whereOr('astr','like',$data['left'].'%')
->whereOr('astr','like',$data['center'].'%')
->whereOr('astr','like',$data['topleft'].'%')
->whereOr('astr','like',$data['topright'].'%')
->whereOr('astr','like',$data['bottomright'].'%')
->whereOr('astr','like',$data['bottomleft'].'%')
->field('xxx自己需要的字段')
->select();
- 如果需要根据结果进行距离显示以及排序的话，则需要遍历查询的数组，调用两个经纬度之间的函数来进行距离计算
foreach ($rows as $k => $row)
{
$distance = getDistance(当前用户的lat, 当前用户的lng, $row['lat'], $row['lng']);
$rows[$k]['distance'] = $distance;
//排序列
$sortdistance[$k] = $distance;
}
//根据数组排序
array_multisort($sortdistance,$rows);
//计算方法----根据经纬度计算距离 其中A($lat1,$lng1)、B($lat2,$lng2)
// return km
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/1000,1);
}
- 根据上面的就可以获取到用户的位置以及距离排序
附赠geohash精度表
本文为北溟有鱼QAQ原创文章,转载无需和我联系,但请注明来自北溟有鱼QAQ https://www.amdzz.cn
- 上一篇： 高德鼠标绘制覆盖物
- 下一篇： 原生workman实现消息推送
请先登录后发表评论
- 最新评论
- 总共0条评论
最新评论