geohash查找附近的人-1

     查找附近的人是移动开发非常流行的功能,不但可以用于普通应用开发,也可以用于游戏开发。本人主要简单运用流行的geohash算法来简单实现查找附近的人功能,并制作一个模拟环境,使用Unity和原生安卓来实现;

    目录:

1,实现查找附近的人需要掌握的前提知识;

2,geohash算法的原理,;

3,PHP与JAVA实现geohash算法;

4,unity中模拟实现查找附近的人;


     内容:

第一章,实现查找附近的人需要掌握的前提知识;

1,经纬度



纬线:地球仪上的横线,lat,赤道是最大的纬线,从赤道开始分为北纬和南纬,都是0-90°,纬线是角度数值,并不是米;

经线:地球仪上的竖线,lng,子午线为0°,分为西经和东经,都是0-180°,经线也是角度数值;

经纬线和米的换算:经度或者纬度0.00001度,约等于1米,这个在GPS测算距离的时候可以体会到,GPS只要精确到小数点后五位,就是10米范围内的精度;

2,GPS

1),gps概念太复杂,主要GPS标示的是类似坐标点(XX.XXXXX,Y.XXXXX),gps保留小数5位,大概就可以精确到10米范围以内,比如成都某个地方(30.68635,103.95210)与(30.68635,103.95211)相差在10米以内;

2),测距:

抽象为球面两点距离的计算,即已知道球面上两点的经纬度;

点(纬度,经度),A($radLat1,$radLng1)、B($radLat2,$radLng2);

($radLat1、$radLng1,$radLat2,$radLng2 :弧度;$R: 为地球半径 6378137米

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

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

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

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

算式A比算式B速度更快,本例采用算式A

PHP测距代码:

<?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);
    }
 
?>

在实际操作中,点的位置是通过数据库收索GEOHASH数据(下面提到),然后比较两个点的距离;


 3,geohash算法与原理

1),geohash算法是将坐标点经度纬度转化成一个字符串,通过比较字符串相似度来判断两个坐标点的距离关系,一般前5个字符串相同,可以表示2个点在10平方千米内,前6个字符串相同大概表示在0.34平方千米,字符串相似越多,距离越近;

2),geohash算法大概原理是将地球变成一张平面图,在平面图上划分矩形区域,通过细分矩形区域来定位,具体算法可以参考

http://www.cnblogs.com/LBSer/p/3310455.html

http://www.cnblogs.com/dengxinglin/archive/2012/12/14/2817761.html


4,PHP.JAVA实现geohash

1),mongodb数据库支持geohash储存,如果不用该数据库,可以使用代码自己实现:

PHP版本:

<?php
/**
 * Geohash generation class
 * http://blog.dixo.net/downloads/
 *
 * This file copyright (C) 2008 Paul Dixon (paul@elphin.com)
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 3
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */



/**
* Encode and decode geohashes
*
*/
class Geohash
{
	private $coding="0123456789bcdefghjkmnpqrstuvwxyz";
	private $codingMap=array();
	
	public function Geohash()
	{
		//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
	*/
	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);
	}

	
	/**
	* Encode a hash from given lat and long
	*/
	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
	*/
	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
	*/
	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
	*/
	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);
	}
}






?>

JAVA版本:

import java.io.File;  
import java.io.FileInputStream;  
import java.util.BitSet;  
import java.util.HashMap;  
  
  
public class Geohash {  
  
    private static int numbits = 6 * 5;  
    final static char[] digits = { '0', '1', '2', '3', '4', '5', '6', '7', '8',  
            '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p',  
            'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };  
      
    final static HashMap<Character, Integer> lookup = new HashMap<Character, Integer>();  
    static {  
        int i = 0;  
        for (char c : digits)  
            lookup.put(c, i++);  
    }  
  
    public static void main(String[] args)  throws Exception{  
  
        System.out.println(new Geohash().encode(45, 125));  
              
    }  

    public double[] decode(String geohash) {  
        StringBuilder buffer = new StringBuilder();  
        for (char c : geohash.toCharArray()) {  
  
            int i = lookup.get(c) + 32;  
            buffer.append( Integer.toString(i, 2).substring(1) );  
        }  
          
        BitSet lonset = new BitSet();  
        BitSet latset = new BitSet();  
          
        //even bits  
        int j =0;  
        for (int i=0; i< numbits*2;i+=2) {  
            boolean isSet = false;  
            if ( i < buffer.length() )  
              isSet = buffer.charAt(i) == '1';  
            lonset.set(j++, isSet);  
        }  
          
        //odd bits  
        j=0;  
        for (int i=1; i< numbits*2;i+=2) {  
            boolean isSet = false;  
            if ( i < buffer.length() )  
              isSet = buffer.charAt(i) == '1';  
            latset.set(j++, isSet);  
        }  
          
        double lon = decode(lonset, -180, 180);  
        double lat = decode(latset, -90, 90);  
          
        return new double[] {lat, lon};       
    }  
      
    private double decode(BitSet bs, double floor, double ceiling) {  
        double mid = 0;  
        for (int i=0; i<bs.length(); i++) {  
            mid = (floor + ceiling) / 2;  
            if (bs.get(i))  
                floor = mid;  
            else  
                ceiling = mid;  
        }  
        return mid;  
    }  
      
      
    public String encode(double lat, double lon) {  
        BitSet latbits = getBits(lat, -90, 90);  
        BitSet lonbits = getBits(lon, -180, 180);  
        StringBuilder buffer = new StringBuilder();  
        for (int i = 0; i < numbits; i++) {  
            buffer.append( (lonbits.get(i))?'1':'0');  
            buffer.append( (latbits.get(i))?'1':'0');  
        }  
        return base32(Long.parseLong(buffer.toString(), 2));  
    }  
  
    private BitSet getBits(double lat, double floor, double ceiling) {  
        BitSet buffer = new BitSet(numbits);  
        for (int i = 0; i < numbits; i++) {  
            double mid = (floor + ceiling) / 2;  
            if (lat >= mid) {  
                buffer.set(i);  
                floor = mid;  
            } else {  
                ceiling = mid;  
            }  
        }  
        return buffer;  
    }  
  
    public static String base32(long i) {  
        char[] buf = new char[65];  
        int charPos = 64;  
        boolean negative = (i < 0);  
        if (!negative)  
            i = -i;  
        while (i <= -32) {  
            buf[charPos--] = digits[(int) (-(i % 32))];  
            i /= 32;  
        }  
        buf[charPos] = digits[(int) (-i)];  
  
        if (negative)  
            buf[--charPos] = '-';  
        return new String(buf, charPos, (65 - charPos));  
    }  
  
}

C#版本:

C#版本的geohash代
using System;

namespace sharonjl.utils
{
    public static class Geohash
    {
        #region Direction enum

        public enum Direction
        {
            Top = 0,
            Right = 1,
            Bottom = 2,
            Left = 3 
        }

        #endregion

        private const string Base32 = "0123456789bcdefghjkmnpqrstuvwxyz";
        private static readonly int[] Bits = new[] {16, 8, 4, 2, 1};

        private static readonly string[][] Neighbors = {
                                                           new[]
                                                               {
                                                                   "p0r21436x8zb9dcf5h7kjnmqesgutwvy", // Top
                                                                   "bc01fg45238967deuvhjyznpkmstqrwx", // Right
                                                                   "14365h7k9dcfesgujnmqp0r2twvyx8zb", // Bottom
                                                                   "238967debc01fg45kmstqrwxuvhjyznp", // Left
                                                               }, new[]
                                                                      {
                                                                          "bc01fg45238967deuvhjyznpkmstqrwx", // Top
                                                                          "p0r21436x8zb9dcf5h7kjnmqesgutwvy", // Right
                                                                          "238967debc01fg45kmstqrwxuvhjyznp", // Bottom
                                                                          "14365h7k9dcfesgujnmqp0r2twvyx8zb", // Left
                                                                      }
                                                       };

        private static readonly string[][] Borders = {
                                                         new[] {"prxz", "bcfguvyz", "028b", "0145hjnp"},
                                                         new[] {"bcfguvyz", "prxz", "0145hjnp", "028b"}
                                                     };

        public static String CalculateAdjacent(String hash, Direction direction)
        {
            hash = hash.ToLower();

            char lastChr = hash[hash.Length - 1];
            int type = hash.Length%2;
            var dir = (int) direction;
            string nHash = hash.Substring(0, hash.Length - 1);

            if (Borders[type][dir].IndexOf(lastChr) != -1)
            {
                nHash = CalculateAdjacent(nHash, (Direction) dir);
            }
            return nHash + Base32[Neighbors[type][dir].IndexOf(lastChr)];
        }

        public static void RefineInterval(ref double[] interval, int cd, int mask)
        {
            if ((cd & mask) != 0)
            {
                interval[0] = (interval[0] + interval[1])/2;
            }
            else
            {
                interval[1] = (interval[0] + interval[1])/2;
            }
        }

        public static double[] Decode(String geohash)
        {
            bool even = true;
            double[] lat = {-90.0, 90.0};
            double[] lon = {-180.0, 180.0};

            foreach (char c in geohash)
            {
                int cd = Base32.IndexOf(c);
                for (int j = 0; j < 5; j++)
                {
                    int mask = Bits[j];
                    if (even)
                    {
                        RefineInterval(ref lon, cd, mask);
                    }
                    else
                    {
                        RefineInterval(ref lat, cd, mask);
                    }
                    even = !even;
                }
            }

            return new[] {(lat[0] + lat[1])/2, (lon[0] + lon[1])/2};
        }

        public static String Encode(double latitude, double longitude, int precision = 12)
        {
            bool even = true;
            int bit = 0;
            int ch = 0;
            string geohash = "";

            double[] lat = {-90.0, 90.0};
            double[] lon = {-180.0, 180.0};

            if (precision < 1 || precision > 20) precision = 12;

            while (geohash.Length < precision)
            {
                double mid;

                if (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;
                }

                even = !even;
                if (bit < 4)
                    bit++;
                else
                {
                    geohash += Base32[ch];
                    bit = 0;
                    ch = 0;
                }
            }
            return geohash;
        }
    }
}

C#代码来自:https://github.com/sharonjl/geohash-net

其他版本可以参考:

http://www.cnblogs.com/dengxinglin/archive/2012/12/14/2817761.html   邓星林-GEOHASH算法原理和实现

2),测试(下一篇)

爱编程-编程爱好者经验分享平台

文章评论

  

版权所有 爱编程 © Copyright 2012. w2bc.com. All Rights Reserved.
闽ICP备12017094号-3