地理围栏算法解析（Geo-fencing）
地理围栏算法解析
http://www.cnblogs.com/LBSer/p/4471742.html
地理围栏（Geo-fencing）是LBS的一种应用，就是用一个虚拟的栅栏围出一个虚拟地理边界，当手机进入、离开某个特定地理区域，或在该区域内活动时，手机可以接收自动通知和警告。如下图所示，假设地图上有三个商场，当用户进入某个商场的时候，手机自动收到相应商场发送的优惠券push消息。地理围栏应用非常广泛，当今移动互联网主要app如美团、大众、手淘等都可看到其应用身影。
图1 地理围栏示意图
地理围栏的核心问题就是判断用户是否落在某多边形围栏内部。本文将介绍实际应用中常用的解决方法。
1 如何判断点在多边形内部
地理围栏一般是多边形，如何判断点在多边形内部呢？可以通过射线法来判断点是否在多边形内部。如下图所示，从该点出发沿着X轴画一条射线，依次判断该射线与每条边的交点，并统计交点个数，如果交点数为奇数，则在多边形内部（如图3个交点），如果焦点数是偶数，则在外部，射线法对凸和非凸多边形都适用，复杂度为O(N)，其它N是边数。源码可参考（http://alienryderflex.com/polygon/）
图2 射线法判断点在多边形内外
当地理围栏多边形数目较少时，我们可以依次遍历每一个多边形（暴力遍历法），然后用射线法进行判断，这样效率也很高。而当多边形数目较多时，比如有10万个多边形，这个时候需要执行10万次射线法，响应时间达到3.9秒，这在互联网应用几乎不可忍受。下表是本人的简单测试，多边形边数均为7。
表1 射线法性能测试
2 R树索引加速判断
暴力遍历法效率低下的原因是与每一个多边形都进行了射线法判断，因此我们的优化思路很直接，首先进行粗筛，找到符合条件的少量多边形，然后对粗筛后的多边形使用射线法判断，这样射线法的执行次数大大降低，效率也能大大提高。下面将介绍R树的解决思路。
1）外包矩形表示多边形
由于多边形形状各异，我们需要以一种统一的方式来对多边形进行近似，最简单的方式就是用最小外包矩形来表示多边形。
图3 最小外包矩形（MBR）表达多边形
2）对最小外包矩形建立R树索引
图4 对最小外包矩形进行R树索引
3）查询
a）首先通过R树迅速判断用户所在位置（粗红点）是否被外包矩形覆盖（图5，红色点代表用户所在位置）；
b）如果不被任何外包矩形覆盖则返回不在地理围栏多边形内；
c）如果被外包矩形覆盖则还需要进一步判断是否在此外包矩形的多边形内部，采用上文提到的射线法判断（图2）。
图5 R树查询示例
3 实践
线上某应用服务有30万个地理围栏多边形，通过在内存中构建R树索引，使得线上实时地理围栏查询平均响应时间在1ms以内，而暴力查询响应时间是9秒左右。
空间索引相关博文：
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
