地理围栏：如何判断一个点是否在多边形内部？

地理围栏（Geo-fencing）是LBS的一种应用。简单地说，就是用一个虚拟的栅栏围出一个虚拟地理边界，当用户进入或者离开某个特定区域，就会触发相应的互动。

如下图所示的三个商场，当用户进入其中某个商场的时候，服务器就会将对应商场的优惠券消息推送到用户。

在公共交通领域，地理围栏常用于公交车辆的报站。对于每个站点，事先预设一个地理围栏，当车辆进入站点区域后，车辆自动报站。该技术同样可以用来记录公交车辆的到站和离站时间。

那么我们如何判断一个点是否在多边形的内部呢？这是地理围栏的核心问题。本文将介绍实际应用中常用的解决方法。

射线法

顾名思义，就是通过绘制射线来判断点是否在多边形内部。

如下图所示，以待判断的点为端点绘制一条水平射线，并统计其与围栏各边的交点个数。如果交点数为奇数，则该点在多边形内部（如图2中为3个交点）；如果为偶数，则该点在多边形外部。

射线法对凸和非凸多边形都适用，复杂度为O(N)，其中 N 是边数。源码可参考网页：http://alienryderflex.com/polygon/。

需要判断的多边形多怎么办？

对于少量的多边形，直接采用射线法即可，响应时间在可接受的范围之内。但是当多边形较多时，比如有 10 万个多边形，就需要执行 10 万次判断，响应时间达到 3.9 秒，这在互联网应用几乎不可忍受。下表是一个简单的测试（多边形边数均为7）。

表 1   射线法性能测试

针对这种现象，优化思路很直接：通过一定的方法（效率肯定要比射线法高）快速筛选，去掉容易判断的，对于剩下的无法判断的调用射线法判断，从而降低射线法的执行次数，提高整体效率。

怎么粗筛呢？对于一维数据我们常常使用索引的方法，比如通过B树索引找到某一个范围区间段，然后对此范围区间段进行遍历查找，对于二维空间数据常常使用空间索引的方法，比如通过R树找到范围区间内的多边形，然后对此范围内的多边形进行精确判断。

下面介绍最常使用的空间索引R树的解决思路。

1. 外包矩形表示多边形

由于多边形形状各异，我们需要以一种统一的方式来对多边形进行近似，最简单的方式就是用最小外包矩形来表示多边形。

2. 对最小外包矩形建立R树索引

3. 查询

• 首先通过R树迅速判断用户所在位置（粗红点）是否被外包矩形覆盖（图5，红色点代表用户所在位置；R树平均查询复杂度为O(Log(N))，N为多边形个数）；
• 如果不被任何外包矩形覆盖则返回不在地理围栏多边形内；
• 如果被外包矩形覆盖则还需要进一步判断是否在此外包矩形的多边形内部，采用上文提到的射线法判断（图2）。

多边形边数较多怎么办？

大多数应用的地理围栏多边形都比较简单，但有时也会遇到一些特别复杂的多边形，比如单个多边形的边数就超过十几万条，这时候对此复杂多边形执行一次射线法也非常耗时。

如何提高对复杂多边形执行射线法的计算效率呢？同样使用R树索引！笔者在实际应用中对边数较多（如超过 1 万）的多边形的边再单独进行R树索引，具体如图 6 所示，首先对多边形的每条边构建最小外包矩形，然后在这些最小外包矩形基础上构建 R 树索引（R树索引上的外包矩形未画出），这样射线法求交点的时候首先通过R树判断射线是否与外包矩形相交，最后对 R 树粗筛后的边进行精确求交判断，时间复杂度从 O(N) 降到 O(Log(N))，大大提高了计算效率。

实践

某线上应用服务有 30 万个地理围栏多边形，通过在内存中构建 R 树索引，使得线上实时地理围栏查询平均响应时间在 1ms 以内，而暴力查询响应时间是 9 秒左右。

R 树相关源码的下载链接附后，有 Python、Java、Javascript、C# 多个版本。

来源：伯乐在线>>地理围栏算法解析

打赏

微信

支付宝

用 微信 扫描二维码打赏

用 支付宝 扫描二维码打赏

相关下载