地理围栏算法解析(Geo-fencing)

2024-05-25 01:58

本文主要是介绍地理围栏算法解析(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树索引加速判断

       暴力遍历法效率低下的原因是与每一个多边形都进行了射线法判断,如果能减少射线法的调用次数性能就能提升。因此我们的优化思路很直接,首先通过粗筛的方法快速找到符合条件的少量多边形,然后对粗筛后的多边形使用射线法判断,这样射线法的执行次数大大降低,效率也能大大提高。怎么粗筛呢?对于一维数据我们常常使用索引的方法,比如通过B树索引找到某一个范围区间段,然后对此范围区间段进行遍历查找,对于二维空间数据常常使用空间索引的方法,比如通过R树找到范围区间内的多边形,然后对此范围内的多边形进行精确判断,下面介绍最常使用的空间索引R树的解决思路。

       1)外包矩形表示多边形

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

图3 最小外包矩形(MBR)表达多边形

 

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

 

图4 对最小外包矩形进行R树索引

 

        3)查询

          a)首先通过R树迅速判断用户所在位置(粗红点)是否被外包矩形覆盖(图5,红色点代表用户所在位置;R树平均查询复杂度为O(Log(N)),N为多边形个数);

          b)如果不被任何外包矩形覆盖则返回不在地理围栏多边形内;

          c)如果被外包矩形覆盖则还需要进一步判断是否在此外包矩形的多边形内部,采用上文提到的射线法判断(图2)。

图5 R树查询示例

3 多边形边数较多怎么办

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

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

图6 对多边形的边进行R树索引

4 实践

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

      

5 R树相关源码

https://pypi.python.org/pypi/Rtree/ (Python)

http://jsi.sourceforge.net/ (Java)

https://github.com/leaflet-extras/RTree (Javascript)

http://sourceforge.net/p/cspatialindexrt/code/HEAD/tree/ (C#)

这篇关于地理围栏算法解析(Geo-fencing)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1000156

相关文章

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

使用Python实现批量访问URL并解析XML响应功能

《使用Python实现批量访问URL并解析XML响应功能》在现代Web开发和数据抓取中,批量访问URL并解析响应内容是一个常见的需求,本文将详细介绍如何使用Python实现批量访问URL并解析XML响... 目录引言1. 背景与需求2. 工具方法实现2.1 单URL访问与解析代码实现代码说明2.2 示例调用

SSID究竟是什么? WiFi网络名称及工作方式解析

《SSID究竟是什么?WiFi网络名称及工作方式解析》SID可以看作是无线网络的名称,类似于有线网络中的网络名称或者路由器的名称,在无线网络中,设备通过SSID来识别和连接到特定的无线网络... 当提到 Wi-Fi 网络时,就避不开「SSID」这个术语。简单来说,SSID 就是 Wi-Fi 网络的名称。比如

SpringCloud配置动态更新原理解析

《SpringCloud配置动态更新原理解析》在微服务架构的浩瀚星海中,服务配置的动态更新如同魔法一般,能够让应用在不重启的情况下,实时响应配置的变更,SpringCloud作为微服务架构中的佼佼者,... 目录一、SpringBoot、Cloud配置的读取二、SpringCloud配置动态刷新三、更新@R

使用Java解析JSON数据并提取特定字段的实现步骤(以提取mailNo为例)

《使用Java解析JSON数据并提取特定字段的实现步骤(以提取mailNo为例)》在现代软件开发中,处理JSON数据是一项非常常见的任务,无论是从API接口获取数据,还是将数据存储为JSON格式,解析... 目录1. 背景介绍1.1 jsON简介1.2 实际案例2. 准备工作2.1 环境搭建2.1.1 添加

在C#中合并和解析相对路径方式

《在C#中合并和解析相对路径方式》Path类提供了几个用于操作文件路径的静态方法,其中包括Combine方法和GetFullPath方法,Combine方法将两个路径合并在一起,但不会解析包含相对元素... 目录C#合并和解析相对路径System.IO.Path类幸运的是总结C#合并和解析相对路径对于 C

Java解析JSON的六种方案

《Java解析JSON的六种方案》这篇文章介绍了6种JSON解析方案,包括Jackson、Gson、FastJSON、JsonPath、、手动解析,分别阐述了它们的功能特点、代码示例、高级功能、优缺点... 目录前言1. 使用 Jackson:业界标配功能特点代码示例高级功能优缺点2. 使用 Gson:轻量

Java如何接收并解析HL7协议数据

《Java如何接收并解析HL7协议数据》文章主要介绍了HL7协议及其在医疗行业中的应用,详细描述了如何配置环境、接收和解析数据,以及与前端进行交互的实现方法,文章还分享了使用7Edit工具进行调试的经... 目录一、前言二、正文1、环境配置2、数据接收:HL7Monitor3、数据解析:HL7Busines

python解析HTML并提取span标签中的文本

《python解析HTML并提取span标签中的文本》在网页开发和数据抓取过程中,我们经常需要从HTML页面中提取信息,尤其是span元素中的文本,span标签是一个行内元素,通常用于包装一小段文本或... 目录一、安装相关依赖二、html 页面结构三、使用 BeautifulSoup javascript

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库,完全使用 Python 语言编写,它对 XPath表达式提供了良好的支 持,因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块,该模块专门用来解析 HTML/XML 文档,下面来介绍一下 lxml 库