项目总结-通过经纬度将地球表面分块

1 前言

    最近做了一个项目,需求是某一个母体,通过手机摇一摇寻找身边同时在摇的人,然后把自己的红包分给这些人.其实有点类似微信的约炮功能.都是基于地理位置找附近的人.两者的区别就是微信约炮只需要找附近的一个人,而母体裂变是一对多的.而且微信也没有母体的概念(也就是没有一个是主动方,一个是被动方)

 

2 需求分析

    找附近的人,这个需求说起来简单,其实还是挺麻烦的.首先,像这种活动(送红包),参与人数肯定不在少数.据我事后的统计,同时参与的人数峰值是每两分钟32W,大概是每秒3K上下.可以明确的是,我们不可能针对 每一次请求都计算所有用户之间的距离.那么,我们自然而然的就会想到,将用户进行分区.每次请求只关心自己区里的用户距离.而其中,当时我想到的分区方式有两种

写道

1 直接按照城市分区.每个城市作为一个池子.
2 将地球表面按照经纬度进行分割.每一块分割的区域作为一个池子.

     这两种方式的优略点也很明显. 第一种优点是,实现方便,现在高德,google,阿里云都支持通过经纬度直接获取对应的地址信息,缺点也相对较多,1 最大的缺点是效率,我所了解的根据经纬度查询地址的接口都是http接口,速度非常慢.2 无法控制区域大小.每个城市大小都是固定的.而且每个城市大小之间相差很大. 第二种的优点是可控,只需要完成一个相对合理的分区域算法,那么这个区域大小就由你自己控制,而且一般来说效率会非常高.缺点也同样明显,需要一个靠谱的分区域算法.

     最后,我选择的是第二种方式.那么下面就是考虑怎么根据经纬度做一个分区算法了.

 

3 如何分区

    经纬度的单位有度,分,秒,毫秒.那么可以认为

写道

经度从-180.000000~180000000
维度从-90.000000~90000000

     通过经纬度,我们需要确定当前的位置应该落入哪个区域中.从技术的角度来说,就是需要合并两个值生成一个值,这个值作为当前经纬度的一个序列值(这里说序列值主要是强调唯一性).我想到的法子是,

写道

经纬度分别转换成二进制,然后通过奇偶位插入的方式生成对于的序列值..

 类似的效果就是这样

对于的代码

 

    private long encode(long lon,long lat){
        long area = 0;
        //先设置经度,避免负数,直接加180
        long newLon = lon + 180000000;
        for(int i = 0; i < 64; i += 2){
            if(theBitTrue(newLon,i)){
                area = setTheBitTrue(area,i);
            } else {
                area = setTheBitFalse(area,i);
            }
        }
        //再设置维度
        long newLat = lat + 90000000;
        for(int i = 0; i < 64; i += 2){
            if(theBitTrue(newLat,i)){
                area = setTheBitTrue(area,i+1);
            } else {
                area = setTheBitFalse(area,i+1);
            }
        }
        return area;
    }

    /**
     * 判断num上  第point位上是否为1
     * point 从0开始.
     */
    private boolean theBitTrue(long num,int point){
        long bits = 1l << point;
        return (bits & num) == bits;
    }

    /**
     * 将num的第point位设置成1,然后返回
     */
    private long setTheBitTrue(long num,int point){
        return num |= (1l << point);
    }

    /**
     * 将num的第point位设置成0,然后返回
     */
    private long setTheBitFalse(long num,int point){
        return num &= ~(1l << point);
    }

    

     分区弄好了,那么每一个区有多大呢.

写道

按照上面的算法,序列值最大应该是经度接近360度的时候,那应该是
360000000 = 10101011101010010101000000000 一共是29位.然后加入维度,那么应该是58位.这样的话,我们可以近似的认为区域的总数为
4^29 = 288230376151711744.
地球总表面积是510072000平方千米=5100720000000000000平方厘米.
那么,每一个区域的面积应该是
5100720000000000000/288230376151711744 = 17平方厘米.

 

    计算好每个最小区域的大小,那么就很容易了.比如你需要17平方千米作为范围,那么就是 17平方千米/17平方厘米 = 10^10 如果是170平方千米,那就是10^11. 这个系数作为可变参数调节就好了..然后对应的序列值%这个系数,就是对应的池子的最终序列值啦.

 

    这里再补充一种算法,是同事写的,其实核心思想类似.

// 编码经纬度
    private long encode(long lon, long lat) {
        long mergeBits = 0L;
        mergeBits = processBitset(mergeBits, 59, lon, -180000000, 180000000);
        mergeBits = processBitset(mergeBits, 58, lat, -90000000, 90000000);
        return mergeBits;
    }


    // 纬度 下限 上限
    private long processBitset(long mergeBits, int start, long lat, long floor, long ceiling) {
        double dfloor = floor, dceiling = ceiling;
        for (int i = start; i >= 0; i -= 2) {
            double mid = (dfloor + dceiling) / 2;
            if (lat >= mid) {      // 上半阙
                mergeBits |= (1L << i);     // 该为置1
                dfloor = mid;       // 下限抬高
            } else {               // 下半阙
                mergeBits &= ~(1L << i);    // bit位设为0
                dceiling = mid;     // 上限降低
            }
        }
        return mergeBits;
    }

    这个算法里面有一些有趣的东西.比如为什么要设置59和58,还有他这个看上去的区域总数是4^30次.比之前的那个算法多了4倍的精确率.等等.但是其实并不是表面的那样.具体的不多解释啦.自己理解了.

 

   后续

     本来本篇文章到这里应该就已经结束了.但是在项目结束以后,我忽然想到另外一个问题..我们知道,上面说的根据经纬度划分区域,然后在区域内计算彼此之间距离的方式有一个非常大的弊端

写道

无法处理边界问题

     也就是说,就算某两个坐标 ,虽然距离很近 ,但是由于坐标A刚好落入区域1中,坐标B刚好落入区域2中,那么这两个坐标永远不会落在一个区域内.两个人也就摇不到一个房间内.那么继续思考,如何可以解决这个问题..最简单的方式(当然,也是最不考虑性能的方式)肯定是

 

写道

裂变者,每次都计算与所有求包者(而不是区域内)之间的距离

       相信大家会本能的觉得,这样做肯定不靠谱.我最开始也是这么认为的,但是我在深入考虑以后我发现,我忽视了一个很大的问题.

写道

裂变者关心的是与所有求包者的距离排序,而不是计算与每个求包者的真实的距离

      在上面,我们为每一个经纬度组合生成了一个彼此完全不一致的区域ID,其实,两个经纬度之间距离的大小,完全可以通过两个经纬度对应的最小区域ID异或操作得出.也就是说,

写道

坐标A与坐标B的相对距离,我们可以通过下面的方式生成
坐标A对应的序列值为long类型的数值 ida ,坐标B对应的序列值为 idb.两者之间的距离可以近似的认为是 ida^idb

      我们知道,异或操作对于计算机是非常快的..根据事后的数据观察,求包者请求的峰值是3k qps.每次请求有效期为10s,也就是说,同时有效的求包者应该是3W左右.那么,我们可以通过代码演示一下如果裂变者每次请求都与3W个求包者计算距离的消耗是多少

package location;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 *
 */
public class LocationTest {

    private static final int NUM = 30000;
    static List<Long> locationList = new ArrayList<Long>(NUM);
    static List<Long> temp = new ArrayList<Long>(NUM);
    static final long location;

    static {
        Random random = new Random();
        location = random.nextLong();
        for (int i = 0; i < NUM; i++) {
            locationList.add(random.nextLong());
        }
    }


    public static void main(String[] args) {
        //为了预热
        for (Long locationA: locationList) {
            temp.add(locationA ^ location);
        }
        temp.clear();
        long start = System.currentTimeMillis();
        for (Long locationA: locationList) {
            temp.add(locationA ^ location);
        }
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }
}

     我在本机运行了一下,结论是6ms.也就是说,我们可以认为,如果每个裂变者与所有求包者计算一次距离,只要短短的6ms.我们是否可以认为,不分区域是完全可行的.

     可惜下面的内容都是我在项目结束以后才想到的.不然可以在项目中试验一把,那就真的完美了.

 

 总结

    项目中后续当然还有其他的内容,比如池子获取到以后,然后再每次计算池子里的人与母体的距离然后进行排序.不过这个就相对容易很多了.根据经纬度计算距离的方法google一下就好了.很多..这里就不多说了.呵呵,当码农几年,第一次用了二进制的位运算,也挺有趣的.