本申请涉及按需服务，尤其涉及用于确定对象是否属于目标地理围栏的系统和方法。
背景技术：
随着互联网技术的发展，按需服务，例如，在线叫车服务和送货服务，开始在人们的日常生活中起着重要作用。按需服务平台的精细化管理有助于提高企业利润。例如，对于不同的服务区域，按需服务平台可以为在平台注册的服务提供者和/或服务请求者制定相应的营销策略。又例如，对于不同的服务区域，按需服务平台可以制定相应的调度策略以满足服务能力需求。按需服务的这种精细化管理依赖于用户位置信息的准确获取，例如，用户所属地理围栏的获取。因此，我们期望开发出能够准确高效地确定对象是否属于目标地理围栏的系统和方法。
技术实现要素：
本申请实施例之一提供了一种用于确定对象是否属于目标地理围栏的方法。所述方法包括：获取所述对象的地理位置对应的地理坐标；确定所述地理坐标对应的网格信息；基于所述网格信息，在第一网格数据库中索引所述网格；响应于所述索引的网格不在所述第一网格数据库中：确定所述对象不属于所述目标地理围栏；响应于所述索引的网格在所述第一网格数据库中：基于所述网格信息，在第二网格数据库中索引所述网格；响应于所述索引的网格不在所述第二网格数据库中：确定所述对象属于所述目标地理围栏；以及响应于所述索引的网格在所述第二网格数据库中：根据所述对象和局部围栏的关系，确定所述对象是否属于所述目标地理围栏。
本申请实施例之一提供了一种用于确定对象是否属于目标地理围栏的装置，包括至少一个处理器以及计算机可读存储介质，所述至少一个处理器用于执行所述计算机指令，以实现上述用于确定对象是否属于目标地理围栏的方法。
本申请实施例之一提供了一种计算机可读存储介质，所述存储介质存储计算机指令，当计算机读取存储介质中的计算机指令后，计算机执行上述用于确定对象是否属于目标地理围栏的方法。
本申请实施例之一提供了一种用于确定对象是否属于目标地理围栏的系统，所述系统包括获取模块、网格信息确定模块、索引模块和结果确定模块、第一网格数据库确定模块和第二网格数据库确定模块。其中，所述获取模块用于获取所述对象的地理位置对应的地理坐标；所述网格信息确定模块用于确定所述地理坐标对应的网格信息；所述索引模块用于基于所述网格信息，在第一网格数据库中索引所述网格；响应于所述索引的网格不在所述第一网格数据库中：所述结果确定模块用于确定所述对象不属于所述目标地理围栏；响应于所述索引的网格在所述第一网格数据库中：所述索引模块用于基于所述网格信息，在第二网格数据库中索引所述网格；响应于所述索引的网格不在所述第二网格数据库中：所述结果确定模块用于确定所述对象属于所述目标地理围栏；响应于所述索引的网格在所述第二网格数据库中：所述结果确定模块用于根据所述对象和局部围栏的关系，确定所述对象是否属于所述目标地理围栏；所述第一网格数据库确定模块用于建立所述第一网格数据库；以及所述第二网格数据库确定模块用于建立所述第二网格数据库。
本申请实施例之一提供了一种用于确定对象是否属于目标地理围栏的系统，所述系统包括用于存储指令的存储设备以及与所述存储设备进行通信的处理器。当所述处理器执行所述指令时，所述处理器触发所述系统执行：获取所述对象的地理位置对应的地理坐标；确定所述地理坐标对应的网格信息；基于所述网格信息，在第一网格数据库中索引所述网格；响应于所述索引的网格不在所述第一网格数据库中：确定所述对象不属于所述目标地理围栏；响应于所述索引的网格在所述第一网格数据库中：基于所述网格信息，在第二网格数据库中索引所述网格；响应于所述索引的网格不在所述第二网格数据库中：确定所述对象属于所述目标地理围栏；以及响应于所述索引的网格在所述第二网格数据库中：根据所述对象和局部围栏的关系，确定所述对象是否属于所述目标地理围栏。
在一些实施例中，可以建立所述第一数据库。其中，所述建立所述第一数据库进一步包括：获取所述目标地理围栏；获取所述目标地理围栏对应的至少两个网格，其中所述至少两个网格中的每一网格是具有多个顶点的多边形；将所述至少两个网格对应的数据编码成第一数据结构，所述第一数据结构包括所述至少两个网格的标识码和所述多个顶点的坐标；以及将所述编码的数据写入至少一个非暂时性存储介质。
在一些实施例中，可以建立所述第二网格数据库。其中，所述建立所述第二网格数据库进一步包括：获取所述至少两个网格中的一个及以上边界网格；基于所述一个及以上边界网格和所述目标地理围栏确定一个及以上局部地理围栏；将所述一个及以上边界网格对应的数据和所述一个及以上局部地理围栏对应的数据编码成第二数据结构，所述第二数据结构包括所述一个及以上边界网格的标识码、所述一个及以上局部地理围栏的标识码、所述一个及以上边界网格中的每一边界网格的顶点坐标、所述一个及以上局部地理围栏中的每一局部地理围栏的顶点坐标，其中，所述一个及以上局部地理围栏中的每一局部地理围栏的顶点包括所述边界网格和所述局部地理围栏的一个及以上交点；以及将所述编码的数据写入所述至少一个非暂时性存储介质。
在一些实施例中，对于所述一个及以上边界网格中的每一个边界网格：可以分别确定对应于所述边界网格的第一链表和对应于所述目标地理围栏的第二链表，其中，所述第一链表或第二链表中的每一节点分别对应于所述边界网格的一个顶点或所述目标地理围栏的一个顶点；可以确定所述边界网格和所述目标地理围栏的一个及以上交点；基于所述一个及以上交点更新所述第一链表和所述第二链表；以及基于所述更新的第一链表和第二链表确定所述一个及以上局部地理围栏。
在一些实施例中，对于确定所述一个及以上局部地理围栏中的每一个局部地理围栏：基于预设的遍历规则，遍历所述更新的第一链表和第二链表；确定所述边界网格和所述目标地理围栏的交集，所述交集包括所述边界网格和所述目标地理围栏的一个及以上交点；以及基于所述交集确定所述局部地理围栏。
在一些实施例中，所述预设的遍历规则与遍历起点、遍历方向和遍历转换顺序相关，其中，所述遍历起点包括所述边界网格的顶点且所述边界网格的顶点位于所述目标地理围栏的外部，或者所述目标地理围栏的顶点且所述目标地理围栏的顶点位于所述边界网格的外部；所述遍历方向包括顺时针方向或者逆时针方向；以及所述遍历转换顺序包括在遍历到第一个交点后每次遇到交点交替遍历所述更新的第一链表和第二链表。
在一些实施例中，如果以所述对象为端点的射线穿过奇数个所述局部地理围栏的边界，可以确定所述对象属于所述局部地理围栏；如果以所述对象为端点的射线穿过偶数个所述局部地理围栏的边界，可以确定所述对象不属于所述局部地理围栏。
在一些实施例中，可以确定与所述对象和所述局部地理围栏相关的回转数；如果所述回转数不等于零，确定所述对象属于所述局部地理围栏；以及如果所述回转数等于零，确定所述对象不属于所述局部地理围栏。
在一些实施例中，所述网格具有正六边形结构。
本发明的有益效果：(1)构建第一网格数据库和第二网格数据库，在第一网格数据库和第二网格数据库索引与对象相关的格子来确定对象和目标地理围栏的关系，能够减少计算量，提升检测效率，有效克服了直接用射线法在检测较大围栏或当围栏点数过大时，算法检测效率较低的问题。(2)本发明的系统和方法能够准确地判断对象和目标地理围栏的关系，针对不同的目标地理围栏制定相应的策略，有助于实现平台的精细化管理。
附图说明
本申请将以示例性实施例的方式进一步说明，这些示例性实施例将通过附图进行详细描述。这些实施例并非限制性的，在这些实施例中，相同的编号表示相同的结构，其中：
图1是根据本申请的一些实施例所示的示例性按需服务系统的示意图；
图2是用于实施本申请中公开的特定系统的示例性移动设备的框图；
图3是根据本申请的一些实施例所示的示例性计算设备的框图；
图4是根据本申请的一些实施例所示的示例性处理引擎的框图；
图5是根据本申请的一些实施例所示的示例性第一网格数据库确定模块的框图；
图6是根据本申请的一些实施例所示的示例性第二网格数据库确定模块的框图；
图7是根据本申请的一些实施例所示的用于确定对象是否属于目标地理围栏的示例性过程的流程图；
图8是根据本申请的一些实施例所示的用于建立第一网格数据库的示例性过程的流程图；
图9是根据本申请的一些实施例所示的目标地理围栏和一个或以上网格的关系的示意图；
图10是根据本申请的一些实施例所示的用于建立第二网格数据库的示例性过程的流程图；
图11是根据本申请的一些实施例所示的用于确定一个或以上局部地理围栏的示例性过程的流程图；
图12是根据本申请的一些实施例所示的用于确定局部围栏的示例性操作的示意图；
图13是根据本申请的一些实施例所示的示例性链表的示意图；
图14是根据本申请的一些实施例所示的用于确定局部围栏的示例性操作的示意图；
图15是根据本申请的一些实施例所示的对象不属于局部地理围栏示例性关系的示意图；以及
图16是根据本申请的一些实施例所示的对象属于局部地理围栏示例性关系的示意图。
具体实施方式
以下描述是为了使本领域的普通技术人员能够实施和利用本申请，并且该描述是在特定的应用场景及其要求的环境下提供的。对于本领域的普通技术人员来讲，显然可以对所披露的实施例作出各种改变，并且在不偏离本申请的原则和范围的情况下，本申请中所定义的普遍原则可以适用于其他实施例和应用场景。因此，本申请并不限于所描述的实施例，而应该被给予与权利要求一致的最广泛的范围。
本申请中所使用的术语仅用于描述特定的示例性实施例，并不限制本申请的范围。如本申请使用的单数形式“一”、“一个”及“该”可以同样包括复数形式，除非上下文明确提示例外情形。还应当理解的是，如在本申请说明书中，术语“包括”和/或“包含”仅提示存在所述特征、整体、步骤、操作、组件和/或部件，但并不排除存在或添加一个或以上其他特征、整体、步骤、操作、组件、部件和/或其组合的情况。
应当理解，本文使用的术语“系统”、“模块”和/或“块”是以升序区分不同级别的不同部件、组件、零件、部分或组合的一种方法。但是，如果这些术语达到同样的目的，则可能会被另一个术语所取代。
这里使用的术语“模块”或“块”是指体现在硬件或固件中的逻辑，或者是软件指令的集合。这里描述的模块或块可以实现为软件和/或硬件，并且可以存储在任何类型的非暂时性计算机可读介质或另一个存储设备中。在一些实施例中，可以编译软件模块/单元/块,并将其链接到可执行程序中。应当理解，软件模块可以从其他模块/单元/块或它们自身调用，和/或可以响应检测到的事件或中断来调用。计算机可读介质上可以提供用于在计算设备上执行的软件模块/单元/块(例如，如图3所示的处理器320)，例如光盘、数字视频盘、闪存驱动器、磁盘或任何其他有形介质，或者作为数字下载(原始文件以压缩或可安装的格式进行存储，需要在执行前进行安装、解压缩或解密)。这里的软件代码可以被部分的或全部的储存在执行操作的计算设备的存储设备中，并应用在计算设备的操作之中。软件指令可以嵌入固件中，例如电子可编程只读存储器(eprom)。还应当理解，硬件模块/单元/块可以包括在连接的逻辑组件中，例如门和触发器，和/或可以包括在可编程单元中，例如可编程门阵列或处理器。这里描述的模块/单元/块或计算设备功能可以作为软件模块/单元/块来实施，但是也可以用硬件或固件来实施。通常，这里描述的模块/单元/块指的是逻辑模块/单元/块，其可以与其他模块/单元/块组合，或者不考虑它们的物理组织或存储，将其划分成子模块/子单元/子块。该描述适用于系统，引擎或它们的一部分。
应当理解，当一个模块或块被称为“连接到”或“耦合到”另一模块或块时，它可以直接连接或耦合到另一模块、块、介入单元、或引擎，进行通信，除非上下文另有明确说明。在本申请中，术语“和/或”可以包括任何一个或以上相关所列条目或其组合。
在考虑了作为本申请一部分的附图的描述内容后，本申请的特征和特点以及操作方法、结构的相关元素的功能、各部分的组合、制造的经济性变得显而易见。然而，应当理解，附图仅仅是为了说明和描述的目的，并不旨在限制本申请的范围。应当理解的是，附图并不是按比例绘制的。
本申请中使用了流程图用来说明根据本申请的一些实施例的系统所执行的操作。应当理解的是，前面或下面操作不一定按照顺序来精确地执行。相反，可以按照倒序或同时处理各种步骤。同时，也可以将一个或以上其他操作添加到这些流程图中。也可以从流程图中删除一个或以上操作。
而且，本申请的系统或方法可以应用于任何其他种类的在线按需服务。例如，本申请的系统和方法可以应用于不同的运输系统，包括陆地、海洋、航空航天等或上述举例的任意组合。运输系统的车辆可以包括出租车、私家车、顺风车、公共汽车、火车、动车、高铁、地铁、船只、飞机、宇宙飞船、热气球、无人驾驶车辆、自行车、三轮车、摩托车等或其任意组合。本申请的系统或方法可以应用于出租车、司机服务、送货服务、拼车、公交服务、外卖服务、司机租用、车辆租赁、自行车共享服务、火车服务、地铁服务、班车服务、定位服务等。又例如，本申请的系统或方法可以应用于购物服务、学习服务、健身服务、金融服务、社交服务等。本申请的系统或方法的应用场景可以包括网页、浏览器插件、客户端、客户系统、内部分析系统、人工智能机器人等或其任意组合。
按需服务的对象可以是任何产品。在一些实施例中，产品可以是有形产品或非物质产品。有形产品可以包括食品、药品、商品、化学产品、电器、服装、汽车、房屋、奢侈品等或其任何组合。无形产品可以包括服务产品、金融产品、知识产品、互联网产品等或其任意组合。互联网产品可以包括个人主机产品、网站产品、移动互联网产品、商业主机产品、嵌入式产品等或其任意组合。移动互联网产品可以用于移动终端的软件、程序、系统等或其任意组合。移动终端可以包括平板计算机、笔记本电脑、移动电话、个人数字助理(pda)、智能手表、pos设备、车载计算机、车载电视、可穿戴设备等或其任意组合。例如，产品可以是在计算机或移动电话上使用的任一软件和/或应用。该软件和/或应用程序可以与社交、购物、交通、娱乐、学习、投资等或上述举例的任意组合相关。在一些实施例中，与运输相关的软件及/或应用程序可以包括出行软件和/或应用程序、车辆调度软件和/或应用程序、地图软件和/或应用程序等。在车辆调度软件和/或应用程序中，车辆可以包括马、马车、人力车(例如，独轮车、自行车、三轮车等)、汽车(例如，出租车、公共汽车、私人汽车等)、火车、地铁、船舶、飞行器(例如，飞机、直升机、航天飞机、火箭、热气球等)或其任意组合。
在本申请中，术语“用户”表示可以请求服务、预定服务、提供服务或协助提供服务的个体、实体或工具。在本申请中，术语“用户”和“用户终端”可以互换使用。
本申请涉及的系统和方法能够高效地确定对象是否属于目标地理围栏。例如，所述系统可以构建用于对地球表面建模的离散全局网格系统(dggs)。在dggs中，地球表面被划分为至少两个网格。所述系统可以确定所述对象地理坐标对应的网格标识码(这里也称为网格id)。在一些实施例中，所述系统可以在第一网格数据库中索引所述网格id。如果在第一网格数据库中没有索引到所述网格id，则所述对象不属于目标地理围栏。如果在第一网格数据库中索引到所述网格id，则所述系统进一步在第二网格数据库中索引所述网格id。如果在第二网格数据库中没有索引到所述网格id，则所述对象属于目标地理围栏。如果在第二网格数据库中索引到所述网格id，则所述系统还需要基于所述对象和局部地理围栏的关系来进一步确定所述对象是否属于目标地理围栏。例如，所述系统可以基于射线法确定所述对象和局部地理围栏的关系。在确定对象是否属于目标地理围栏过程中，相比于传统的算法，比如，射线法，本申请可以减少计算量来提升计算效率。例如，所述目标地理围栏被化分为一个或以上内部网格和一个或以上边界网格。假设目标地理围栏的形状为n多边形，其包括m个边界网格。在一些实施例中，如果所述对象在内部网格中，计算复杂度可以等于ο(1)。在一些实施例中，如果对象在边界网格中，计算复杂度可以等于ο(n/m)。在一些实施例中，如果对象不在目标地理围栏中，即对象既不在内部网格也不在边界网格中，计算复杂度可以等于ο(1)。在一些实施例中，单纯用射线法检测的计算复杂度等于ο(n)。
以在线运输服务(例如，叫车服务)为例，所述系统可用于确定服务请求者和/或服务提供者在某个时刻所属的地理围栏。在一些实施例中，所述系统可以制定与所述地理围栏相对应的营销策略。在一些实施例中，所述系统可以制定与所述地理围栏相对应的安全策略。在一些实施例中，所述系统可以确定在所述地理围栏内的服务能力，并基于所述服务能力制定调度策略。
图1是根据一些实施例所示的示例性按需服务系统的示意图。例如，按需服务系统100可以是用于运输服务的在线按需服务系统(如出租车呼叫、司机服务、送货服务、拼车、巴士服务、外送服务、代驾服务、租用车辆、火车服务、地铁服务、班车服务)、购物服务、健身服务、学习服务、金融服务等。
按需服务系统100可以包括服务器110、网络120、一个或以上用户终端(例如，一个或以上乘客终端130、司机终端140)和存储设备150。
服务器110可以包含处理引擎112。应当注意的是，图1所示的按需服务系统100仅仅是示例，并非旨在限制。在一些实施例中，按需服务系统100可以包括乘客终端130或司机终端140。在一些实施例中，按需服务系统100可以获取对象的位置(例如，与乘客终端130相关的乘客、与司机终端140相关的司机、车辆、兴趣点(poi)等)，并根据对象的位置确定对象是否属于目标地理围栏。在一些实施例中，按需服务系统100可以确定与对象所属的目标地理围栏相对应的营销策略(例如，定价策略、优惠策略)。在一些实施例中，对于运输服务，按需服务系统100可以确定用于不同地理围栏的安全策略，例如，当车辆超出预定目标地理围栏时，按需服务系统100可以警示乘客。
在一些实施例中，服务器110可以是单个服务器，也可以是服务器组。所述服务器组可以是集中式的、也可以是分布式的(例如，服务器110可以是分布式的系统)。在一些实施例中，服务器110可以是本地的、也可以是远程的。例如，服务器110可以通过网络120访问存储在一个或以上用户终端(例如，一个或以上乘客终端130和司机终端140)和/或存储设备150中的信息和/或数据。又例如，服务器110可以直接连接到一个或以上用户终端(例如，一个或以上乘客终端130、司机终端140)和/或存储设备150以访问存储的信息和/或数据。在一些实施例中，服务器110可以在云平台上实施。仅作为示例，所述云平台可以包括私有云、公共云、混合云、社区云、分布云、内部云、多云等或其任意组合。在一些实施例中，服务器110可以在具有如图3所示的一个或以上组件的计算设备300上实施。
在一些实施例中，服务器110可以包括处理引擎112。处理引擎112可以处理与一个或以上对象有关的信息和/或数据。在一些实施例中，处理引擎112可以获取对象的位置(例如，与乘客终端130相关的乘客、与司机终端140相关的司机、车辆、兴趣点(poi)等)，并根据对象的位置确定对象是否属于目标地理围栏。在一些实施例中，处理引擎112可以确定与所述对象的目标地理围栏相对应的营销策略(例如，定价策略、优惠策略)。在一些实施例中，对于运输服务，处理引擎112可以确定用于不同地理围栏的安全策略，例如，当车辆超出预定的目标地理围栏时，处理引擎112可以警示乘客。在一些实施例中，处理引擎112可以包括一个或以上处理引擎(例如，单芯片处理引擎或多芯片处理引擎)。仅作为示例，处理引擎112可以包括中央处理单元(cpu)、特定应用集成电路(asic)、特定应用指令集处理器(asip)、图形处理单元(gpu)、物理处理单元(ppu)、数字信号处理器(dsp)、现场可程序门阵列(fpga)、可程序逻辑装置(pld)、控制器、微控制器单元、精简指令集计算机(risc)、微处理器等或其任意组合。
网络120可以促进信息和/或数据的交换。在一些实施例中，按需服务系统100中的一个或以上组件(例如，服务器110、一个或以上乘客终端130、一个或以上司机终端140或存储设备150)可以通过网络120将信息和/或数据发送到按需服务系统100中的其他组件。例如，服务器110可以通过网络120从乘客终端130获取/得到服务请求。又例如，服务器110可以直接或经由网络120从存储器150接收与一个或以上对象有关的信息。又例如，服务器110可以经由网络120从乘客终端130和/或司机终端140接收与一个或以上对象有关的信息。在一些实施例中，网络120可以是任意形式的有线网络或无线网络，或其任意组合。仅作为示例，网络120可以包括电缆网络、有线网络、光纤网络、远程通信网络、内部网络、互联网、局域网络(lan)、广域网络(wan)、无线局域网络(wlan)、城域网(man)、公共开关电话网络(pstn)、蓝牙网络、zigbee网络、近场通讯(nfc)网络等或上述举例的任意组合。在一些实施例中，网络120可以包括一个或以上网络接入点。例如，网络120可以包括有线或无线网络接入点，如基站和/或网络交换点120-1、120-2、…，通过所述接入点，按需服务系统100的一个或以上部件可以连接到网络120以交换数据和/或信息。
在一些实施例中，乘客终端130可以包括移动设备130-1、平板计算机130-2、笔记本电脑130-3、车载设备130-4等或其任意组合。在一些实施例中，移动设备130-1可以包括智能家居设备、可穿戴设备、智能移动设备、虚拟现实设备、增强现实设备等或其任意组合。在一些实施例中，智能家居设备可以包括智能照明设备、智能电器控制设备、智能监控设备、智能电视、智能摄像机、对讲机等或其任意组合。在一些实施例中，该可穿戴设备可包括智能手环、智能鞋袜、智能眼镜、智能头盔、智能手表、智能衣服、智能背包、智能配件等或其任意组合。在一些实施例中，智能移动设备可以包括智能电话、个人数字助理(pda)、游戏设备、导航设备、销售点(pos)机等或其任意组合。在一些实施例中，虚拟现实设备和/或增强型虚拟现实设备可以包括虚拟现实头盔、虚拟现实眼镜、虚拟现实眼罩、增强现实头盔、增强现实眼镜、增强现实眼罩等或其任意组合。例如，虚拟现实装置和/或增强实境装置可以包括googleglass、oculusrift、hololens或gearvr等。在一些实施例中，机动车辆130-4内置设备包括车载计算机或车载电视等。在一些实施例中，乘客终端130可以是具有定位技术的设备，用于定位服务请求者和/或乘客终端130的位置。
在一些实施例中，司机终端140可以与乘客终端130类似或相同的设备。在一些实施例中，司机终端140可以是具有用来确定司机或者司机终端140位置的定位技术的设备。在一些实施例中，乘客终端130和/或司机终端140可以与一个或多个其他定位设备通信以确定请求者、乘客终端130、司机，和/或司机终端140的位置。在一些实施例中，乘客终端130和/或司机终端140可以将所述定位信息发送至服务器110。
存储设备150可以存储数据和/或指令。例如，所述数据可以涉及对象的定位信息、一个或以上地理围栏，将地球划分为一个或以上网格的模型、服务订单等或其组合。在一些实施例中，存储设备150可以存储从一个或以上用户终端(例如，一个或以上乘客终端130、司机终端140)获取的数据。在一些实施例中，存储设备150可以存储供服务器110执行或使用的数据和/或指令，以实现本申请描述的示例性方法。在一些实施例中，存储设备150可以包括大容量存储器、可移动存储器、易失性读写存储器、只读存储器(rom)等或其任意组合。示例性的大容量储存器可以包括磁盘、光盘、固态磁盘等。示例性可移动存储器可以包括闪存驱动器、软盘、光盘、存储卡、压缩盘、磁带等。示例性易失性读写存储器可以包括随机存取内存(ram)。示例性ram可包括动态随机存取存储器(dram)、双倍数据速率同步动态随机存取存储器(ddrsdram)、静态随机存取存储器(sram)、晶闸管随机存取存储器(t-ram)和零电容随机存取存储器(z-ram)等。示例性只读存储器可以包括掩模型只读存储器(mrom)、可编程只读存储器(prom)、可擦除可编程只读存储器(perom)、电可擦除可编程只读存储器(eeprom)、光盘只读存储器(cd-rom)和数字多功能磁盘只读存储器等。在一些实施例中，存储设备150可以在云平台上实施。仅作为示例，所述云平台可以包括私有云、公共云、混合云、社区云、分布云、内部云、多云等或其任意组合。
在一些实施例中，存储设备150可以连接到网络120，以与按需服务系统100中的一个或以上组件(例如，服务器110、一个或以上用户终端等)通信。按需服务系统100中的一个或以上组件可以经由网络120访问存储设备150中存储的数据和/或指令。在一些实施例中，存储器150可以直接与按需服务系统100中的一个或以上部件(例如，服务器110、一个或以上乘客终端等)连接或通信。在一些实施例中，存储设备150可以是服务器110的一部分。
在一些实施例中，按需服务系统100中的一个或以上组件(例如，服务器110、一个或以上用户终端等)可以被许可访问存储设备150。在一些实施例中，当满足一个或以上条件时，按需服务系统100的一个或以上组件可以读取和/或修改与服务请求者，司机和/或公众相关的信息。例如，在完成服务后，服务器110可以读取和/或修改一个或以上用户的信息。应当注意的是，按需服务系统100仅仅是提供了用于确定对象是否属于目标地理围栏、确定营销策略和/或确定安全策略的处理引擎112的应用的示例。处理引擎112可以在一个或以上其他系统(例如，地理信息系统(arcgis)、传输管理系统、对象跟踪系统等)上实现。处理引擎112和按需服务系统100的上述描述是出于说明的目的而提供的，并不旨在限制本申请的范围。
图2是用于实现本申请中公开的特定系统的示例性移动设备的框图。在一些实施例中，用于显示和传送与位置有关信息的用户终端设备可以是移动设备200。移动设备200可以包括但不限于智能手机、平板电脑、音乐播放器、便携式游戏机、gps接收器、可穿戴计算设备(例如眼镜、手表等)等。移动设备200可以包括一个或以上中央处理单元(cpu)240、一个或以上图形处理单元(gpu)230、显示器220、存储器260、通信单元210、存储单元290、以及一个或以上输入/输出(i/o)设备250。此外，移动设备200还可以是包括但不限于系统总线或控制器(图2中未示出)的任何其他合适的组件。如图2所示，移动操作系统270(例如ios、android、windowsphone等)和一个或以上应用程序280可以从存储单元290加载到存储器260并由cpu240实现。应用程序280可以包括浏览器或其他移动应用程序，以用于接收和处理与用户在移动设备200中输入查询(例如，位置名称)有关的信息。乘客/司机可以通过系统i/o设备250获取与一个或以上搜索结果有关的信息，并将该信息提供给服务器110和/或按需服务系统100的其他模块或单元(例如，网络120)。
为了实现上述各种模块、单元及其功能，计算机硬件平台可以用作一个或以上元件的硬件平台(例如，图1-16描述的服务器110和/或图中描述的按需服务系统100的其他部分)。这类计算机的硬件元素，操作系统和程序语言在自然界中是常见的，可以假定本领域技术人员对这些技术都足够熟悉，能够利用这里描述的技术提供按需服务所需要的信息。具有用户界面的计算机可以用作个人计算机(pc)，或其他类型的工作站或终端设备。在正确编程之后，具有用户界面的计算机可以用作服务器。可以认为本领域普通技术人员熟悉这种类型的计算机设备的这种结构，程序或一般操作。因此，没有针对附图描述额外的解释。
图3是根据本申请的一些实施例所示的可以在其上实施服务器110、一个或以上用户终端(例如，一个或以上乘客终端130、司机终端140)的计算设备的示例性硬件和软件组件的框图。计算设备300可以被配置用于执行本申请中公开的服务器110、乘客终端130和司机终端140的一个或以上功能。例如，处理引擎112可以在计算设备300上实现并被配置为实现本申请中所披露的处理引擎112的功能。
计算设备300可以是通用计算机或专用计算机，二者均可以用来实现本申请的按需服务系统100。计算设备300可以用来实现本申请所描述的按需服务系统100的任意组件。例如，处理引擎112可以在计算设备上通过其硬件、软件程序、固件或其组合实现。为了方便起见，图中仅示出了一台计算机，但是本申请描述的与检索服务有关的计算机功能可以在多个类似平台上以分布式方式实现，以分担处理负载。
例如，计算设备300可以包括连接到与之连接的网络的通信(com)端口350，以便于数据通信。计算设备300还可以包括处理器320用来执行程序指令，处理器320可以以一个或以上处理器的形式存在。示例性的计算机平台可以包括一个内部通信总线310、不同形式的程序内存和数据存储器，例如，磁盘370、和只读存储器(rom)330或随机存取内存(ram)340，用于存储由计算机处理和/或传输的各种各样的数据文件。示例性的计算机平台也包括存储在rom330、ram340和/或由处理器320执行的其他类型的非暂时性存储介质。本申请的方法和/或流程可以以程序指令的方式实现。计算设备300还包括输入/输出组件360，用来支持计算机和其他组件之间进行输入/输出。计算设备300也可以通过网络通信接收编程和数据。
计算设备300还可以包括与硬盘通信的硬盘控制器、与小键盘/键盘通信的小键盘/键盘控制器、与串行接口设备通讯的串行接口设备控制器、与并行接口设备通讯的并行接口控制器、与显示器通讯的显示器控制器等或其任意组合。
仅仅是为了说明，计算设备300中仅示例性绘制了一个cpu和/或处理器。然而，需要注意的是，本申请中的计算设备300可以包括多个cpu和/或处理器，因此本申请中描述的由一个cpu和/或处理器实现的操作和/或方法也可以共同地或独立地由多个cpu和/或处理器实现。例如，如果在本申请中，计算设备300的cpu和/或处理器执行操作a和操作b，则应该理解操作a和操作b也可以由两个不同的cpu和/或处理器共同执行，或者在计算设备300中单独地执行(例如，第一处理器执行操作a、第二处理器执行操作b、或者第一和第二处理器共同执行操作a和b)。
图4是根据本申请的一些实施例所示的示例性处理引擎的框图。在一些实施例中，处理引擎112可以与计算机可读存储器(例如，存储设备150、用户终端(例如，乘客终端130、司机终端140等))通信并且可以执行存储在计算机可读存储介质中的指令。处理引擎112可以包括获取模块402、网格信息确定模块404、索引模块406、结果确定模块408、第一网格确定模块410，和第二网格确定模块412。
获取模块402可以获取对象的地理位置对应的地理坐标。所述对象可以是在地球上的由有机和/或无机物质构成的有生命或没有生命的任何组合物。例如，所述对象可以是使用按需服务系统100的服务提供者(例如，司机)或服务请求者(例如，乘客)。又例如，所述对象可以是用于通过使用按需服务系统100提供运输服务的工具(例如，车辆、共享单车)。又例如，所述对象可以是建筑物。在一些实施例中，对象的地理位置对应的地理坐标可以包括对象所在位置的经度和纬度坐标。
在一些实施例中，获取模块402可以从按需服务系统100的一个或以上组件获取所述对象的地理坐标。在一些实施例中，所述对象可以与具有定位功能的设备相关，获取模块402可以从所述设备获取地理坐标。例如，获取模块402可以利用安装在与对象相关的便携式设备上的gps接收器(例如，乘客终端130、司机终端140等)来获取地理坐标。获取模块402可以连续地或周期性地从所述设备获取对象的地理坐标。
网格信息确定模块404可以确定与地理坐标相对应的网格信息。在一些实施例中，网格信息确定模块402可以通过使用离散全局网格系统(dggs)来确定与地理坐标相对应的网格信息。网格可以指dggs中的离散全局网格。网格信息可以包括网格的唯一标识码、与网格所代表的区域相关的地理数据等。在一些实施例中，网格信息确定模块404可以构建dggs，并将dggs存储在存储器(例如，存储设备150或存储器290)中。基于dggs，网格信息确定模块404可以确定对应于对象的地理坐标的网格id。
索引模块406可以在第一网格数据库中基于网格信息来索引网格。更具体地，索引模块406可以基于网格id在第一网格数据库中索引网格。第一网格数据库可以由第一网格数据库确定模块410建立。第一网格数据库可以包括第一数据结构，所述第一数据结构可以指示至少两个网格对应的数据。在第一网格数据库中，所述至少两个网格与目标地理围栏相关。
在一些实施例中，索引模块406可以确定第一网格数据库是否包括索引网格id。例如，索引模块406可以生成指示索引网格不在第一网格数据库中的第一否定结果。又例如，索引模块406可以生成指示索引网格在第一网格数据库中的第一肯定结果。响应于指示所述索引网格不在第一网格数据库的第一否定结果，索引模块406可以将第一否定结果发送到结果确定模块408。结果确定模块408可以确定所述对象不属于目标地理围栏。响应于指示所述索引网格在第一网格数据库的第一肯定结果，索引模块406进一步在第二网格数据库中根据网格信息索引网格。第二网格数据库可以由第二网格数据库确定模块412建立。第二网格数据库可以包括第二数据结构，所述第二数据结构指示与划分目标地理围栏的至少两个网格中的一个或以上边界网格相对应的数据。第二网格数据库记录与边界网格相关的信息，例如，边界网格id、局部地理围栏id等。关于建立第二网格数据库的更多描述可以在本申请的其他地方找到(例如，图10及其描述)。
索引模块406可以基于网格id来索引第二网格数据库中的网格。索引模块406可以确定第二网格数据库是否包括索引网格id。例如，索引模块406可以生成指示索引网格不在第二网格数据库的第二否定结果。又例如，索引模块406可以产生指示索引网格在第二数据库的第二肯定结果。索引模块406可以将第二否定结果和/或第二肯定结果发送到结果确定模块408。响应于指示所述索引网格不在第二网格数据库的第二否定结果，结果确定模块408可以确定所述对象属于目标地理围栏。响应于指示所述索引网格在第二网格数据库的第二肯定结果，结果确定模块408可以基于所述对象和局部地理围栏的关系来确定所述对象是否属于目标地理围栏。所述局部地理围栏可以是边界网格与目标地理围栏重叠的区域。
在一些实施例中，结果确定模块408可以基于射线法确定所述对象和局部地理围栏的关系。例如，结果确定模块408可以确定端点为所述对象的射线。如果所述射线穿过奇数个局部地理围栏的边界，则结果确定模块408可以确定所述对象属于局部地理围栏。如果所述射线穿过偶数个局部地理围栏的边界，则结果确定模块408可以确定所述对象不属于局部地理围栏。
在一些实施例中，结果确定模块408可以基于回转数算法确定所述对象和局部地理围栏的关系。结果确定模块408可以确定与所述对象和局部地理围栏相关的回转数。如果回转数不等于零(或非零)，则结果确定模块408可以确定所述对象属于局部地理围栏。如果回转数等于零，则结果确定模块408可以确定对象不属于局部地理围栏。
第一网格数据库确定模块410可以建立第一网格数据库。在一些实施例中，第一网格数据库确定模块410还可以包括目标地理围栏获取单元502、网格获取单元504、第一编码单元506和第一写入单元508，如图5所示。目标地理围栏获取单元502可以获取目标地理围栏。目标地理围栏可以指示感兴趣的区域(roi)，例如城市、区域、县、社区等。网格获取单元504可以获取所述目标地理围栏对应的至少两个网格。例如，目标地理围栏可以通过dggs划分为所述至少两个网格。网格获取单元504可以从dggs获取所述至少两个网格。所述至少两个网格可以包括一个或以上内部网格和一个或以上边界网格。内部网格完全落在目标地理围栏内，而边界网格部分地、不完全地落入目标地理围栏内，例如，如图9所示、边界网格904和内部网格906。第一编码单元506可以将对应于至少两个网格的数据编码成第一数据结构。第一数据结构可包括至少两个网格的标识码、以及网格的至少两个顶点的坐标、或其任何组合。第一数据结构可以是各种各样的，例如b树结构、b 树结构、静默表、链表等。第一写入单元508可以将编码的数据写入至少一个非暂时性存储介质中以建立第一网格数据库。例如，所述至少一个非暂时性存储介质可以包括按需服务系统100的存储设备150和/或存储器290。又例如，所述至少一个非暂时性存储介质可以包括与按需服务系统100分开的外部存储设备。关于建立第一网格数据库的更多描述可以在本申请的其他地方找到(例如，图8及其描述)。
第二网格数据库确定模块412可以建立第二网格数据库。在一些实施例中，第二网格数据库确定模块412还可以包括边界网格获取单元602、局部地理围栏确定单元604、第二编码单元606和第二写入单元608，如图6所示。边界网格获取单元602可以从对应于目标地理围栏的至少两个网格获取一个或以上边界网格。例如，网格获取单元504可以获取目标地理围栏对应的至少两个网格。所述至少两个网格可以包括一个或以上内部网格和一个或以上边界网格。边界网格获取单元602可以从网格获取单元504获取一个或以上边界网格。局部地理围栏确定单元604可以基于一个或以上边界网格和目标地理围栏来确定一个或以上局部地理围栏。例如，对于一个或以上边界网格中的每一个边界网格，局部地理围栏确定单元604可以确定对应于边界网格的第一链表，例如，对应于边界网格1202(如图12所示)的第一链表1302(如图13所示)。局部地理围栏确定单元604可以确定对应于目标地理围栏1204(图12中所示)的第二链表1304(如图13所示)。第一链表或第二链表可以包括至少两个节点。所述节点可以包括至少一个数据元素，例如，所述边界网格或目标地理围栏的编号的顶点。在一些实施例中，第一链表和第二链表可以是双向循环链表。局部地理围栏确定单元604可以确定边界网格和目标地理围栏的一个或以上交点。局部地理围栏确定单元604可以基于所述一个或以上交点更新第一链表和第二链表。局部地理围栏确定单元604可以基于更新的第一链表和更新的第二链表来确定一个或以上局部地理围栏。关于确定一个或以上局部地理围栏的更多描述可以在本申请的其他地方找到(例如，图11及其描述)。
第二编码单元606可以将对应于一个或以上边界网格和一个或以上局部地理围栏的数据编码到第二数据结构中。第二数据结构可以包括一个或以上边界网格的标识码、一个或以上局部围栏的标识码、一个或以上边界网格的顶点坐标、以及一个或以上局部地理围栏的每一个局部地理围栏的顶点坐标等或其任何组合。第二数据结构可以是各种各样的，例如b树结构、b 树结构、静默表、链表等。
第二写入单元608可以将编码数据写入至少一个非暂时性存储介质中以建立第二网格数据库。例如，至少一个非暂时性存储介质可以包括按需服务系统100的存储设备150和/或存储器290。又例如，所述至少一个非暂时性存储介质可以包括与按需服务系统100分开的外部存储设备。
应当注意，以上关于处理引擎112的描述是出于说明的目的而提供的，并非旨在限制本申请的范围。本领域技术人员能够理解，本申请所披露的内容可以出现多种变型和改进。但是，那些变化与修改不会脱离本申请的范围。在一些实施例中，处理引擎112可包括一个或以上其他模块。例如，处理引擎112可以包括存储模块，用于存储由处理引擎112中的模块生成的数据。在一些实施例中，任意两个模块可以合幷成一模块，以及任意一个模块可以被拆分成两个或者多个单元。
图7是根据本申请的一些实施例所示的用于确定对象是否属于目标地理围栏的示例性过程的流程图。在一些实施例中，所述用于确定对象是否属于目标地理围栏的过程700可以在按需服务系统100中实施，如图1所示。例如，过程700可以在用户终端(例如，乘客终端130、司机终端140)和/或服务器110中实施。过程700还可以作为存储设备150中存储的一个或以上指令来实施，并由处理引擎112调用和/或执行。以下所示过程的操作仅出于说明的目的。在一些实施例中，过程700在实施时可以添加一个或以上本申请未描述的额外操作，和/或删减一个或以上此处所描述的操作。另外，如图7所示的过程700的操作顺序和下面描述的不是限制性的。
在702中，处理器(例如，处理引擎112中的获取模块402)可以获取对象的地理位置对应的地理坐标。所述对象可以是在地球上的有机和/或无机物质构成的有生命或没有生命的任何组合物。例如，所述对象可以是使用按需服务系统100的服务提供者(例如，司机)或服务请求者(例如，乘客)。又例如，所述对象可以是用于通过使用按需服务系统100提供运输服务的工具(例如，车辆、共享单车)。又例如，所述对象可以是建筑物。在一些实施例中，对象的地理位置对应的地理坐标可以包括对象所在的位置的经度和纬度坐标。
在一些实施例中，处理器可以从按需服务系统100的一个或以上组件获取所述对象的地理坐标。在一些实施例中，所述对象可以与具有定位功能的设备相关，处理器可以从所述设备获取地理坐标。例如，获取模块402可以利用安装在与对象(例如，乘客终端130、司机终端140等)相关的便携式设备上的gps接收器获取地理坐标。处理器可以连续或定期从设备中来获取对象的地理坐标。可选地，具有定位功能的设备可以连续地或周期性地经由网络120将对象的地理坐标发送到存储器(例如，存储设备150、存储器290)。处理器可以访问所述存储器，并检索所述对象在不同时间点的地理坐标。
在704中，处理器(例如，处理引擎112的网格信息确定模块404)可以确定与地理坐标相对应的网格信息。
在一些实施例中，处理器可以通过使用离散全局网格系统(dggs)来确定与地理坐标相对应的网格信息。在一些实施例中，网格可以指dggs中的离散全局网格。所述网格信息可以包括网格的唯一标识码，与网格所代表的区域相关的地理数据等。dggs可用于对地球表面建模。对于本领域普通技术人员而言，dggs包括一系列离散的全局网格。每个离散的全局网格表示地球表面的一个分区/区域。离散的全局网格可以用作构建地理空间数据结构的几何基础。在dggs中，可以为离散的全局网格分配唯一标识码(id)。离散的全局网格id可以指示与网格所代表的区域相关的地理数据。
在一些实施例中，处理器可以构建dggs并将dggs存储在存储器(例如，存储设备150或存储器290)中。例如，处理器可以将地球模拟为多面体。代表地球的多面体可以具有任何形状，例如，四面体、立方体、八面体、二十面体、十二面体等。在一些实施例中，代表地球的多面体可以是具有八个面的八面体，其具有基本相同的尺寸和形状。所述八面体具有六个顶点。在地理坐标系中，所述六个顶点的经度坐标和纬度坐标可以是(0,90)、(0,-90)、(0,0)、(90,0)、(-90,0)和(180,0)。所述八面体具有八个面，分别对应于地球表面的八个相等部分。八个面中的每一个面可以代表地球表面的八个相等部分中的一个部分。在一些实施例中，处理器可以将多面体的每个面分成至少两个网格(或多个单元)。每个网格都有一个形状，如六边形、菱形、正方形、矩形、三角形等。在一些实施例中，所述至少两个网格可以由相同的尺寸和形状构成。在一些实施例中，所述至少两个网格可以由不同的尺寸和形状构成。在优选的实施例中，所述至少两个网格中的每个网格可以具有相同的正六边形形状。
在一些实施例中，处理器可以对至少两个网格执行细化操作。细化操作可以用于细化多面体的一个或以上面(例如，八面体)，以便提供具有相对较高分辨率的至少两个网格。处理器可以为每个网格分配一个唯一标识码。dggs可以包括全球唯一网格/单元索引。基于dggs，处理器可以确定对象的地理坐标对应的网格id。
在一些实施例中，处理器可以基于地理坐标确定对象的地理位置在多面体的相应面上的第一投影坐标。例如，处理器可以将地理坐标转换为球坐标。处理器可以将球坐标转换为笛卡尔坐标。处理器可以将笛卡尔坐标转换为第一投影坐标。在一些实施例中，处理器可以确定最接近对象的地理位置的第一投影坐标的目标中心点。处理器可以基于多面体的相应面上的目标中心点的投影坐标来确定与对象相关的网格id。网格id可以作为字符串，例如，ol2f0i1234j5678。所述网格id可以指示与dggs中的对象相关的信息。以网格id“ol2f0i1234j5678”为例，其中“o”表示多面体是八面体，“l2”表示细化级别为2，“f0”表示相应面的标识码八面体的数值为0，“i1234j5678”指的是目标中心点的投影坐标为(12.34,56.78)。关于构建dggs和/或确定与dggs中的对象相关的网格id的实施例的更多描述可以在例如国际申请pct/cn2018/090034中找到，其内容在此引入。
在一些实施例中，处理器可以通过使用商用dggs来确定网格id，例如，pyxisdigitalearthdggs。例如，网格信息确定模块404可以通过连接到按需服务系统100和dggs的应用程序接口(api)来调用dggs。可以将所述对象的地理坐标输入到dggs，网格信息确定模块404可以获取与所述地理坐标相对应的网格id。
在706中，处理器(例如，处理引擎112的索引模块406)可以基于网格信息在第一网格数据库中索引网格。更具体地，处理器可以基于网格id在第一网格数据库中索引网格。处理器可以确定第一网格数据库是否包括索引的网格id。例如，索引模块406可以生成指示所述索引网格不在第一网格数据库的第一否定结果。又例如，索引模块406可以生成指示所述索引网格在第一网格数据库的第一肯定结果。
在一些实施例中，第一网格数据库可以存储在按需服务系统100的存储器(例如，存储设备150或存储器290)中。在一些实施例中，第一网格数据库可以存储在与按需服务系统100分开的外部存储器中。索引模块406可以访问第一网格数据库以索引网格。
第一网格数据库可以包括第一数据结构，所述第一数据结构指示对应于至少两个网格的数据。在第一网格数据库中，所述至少两个网格与目标地理围栏相关。对于本领域普通技术人员而言，所述地理围栏可以指真实地理区域的虚拟周界。所述地理围栏对应于特定的地理区域。所述地理围栏也可以动态生成。例如，所述地理围栏是位于某点位置半径范围内的区域。又例如，所述地理围栏是一组预定义的边界(例如学区或邻域边界)。在一些实施例中，目标地理围栏可以指示感兴趣的区域(roi)，例如城市、区域、县、社区等。在dggs中，目标地理围栏可以划分为至少两个正六边形网格。所述至少两个正六边形网格可以包括一个或以上内部网格和一个或以上边界网格。内部网格完全落在目标地理围栏内，而边界网格部分地、不完全地落入目标地理围栏内。如图9所示，让多边形区域为目标地理围栏902，目标地理围栏902可以划分为至少两个网格，其包括一个内部网格906和多个边界网格904。关于建立第一网格数据库的更多描述可以在本申请的其他地方找到(例如，图8及其描述)。
响应于所述索引网格不在第一网格数据库的第一否定结果，处理器可以执行操作712。处理器(例如，处理引擎112的结果确定模块408)可以确定对象不属于目标地理围栏。
响应于所述索引网格在第一网格数据库的第一肯定结果，处理器可以执行操作708。在708中，处理器(例如，处理引擎112的索引模块406)可以基于网格信息在第二网格数据库中索引网格。更具体地，处理器可以基于网格id在第二网格数据库中索引网格。处理器可以确定第二网格数据库是否包括索引网格id。例如，索引模块406可以生成指示所述索引网格不在第二网格数据库的第二否定结果。又例如，索引模块406可以产生指示索引网格在第二网格数据库的第二肯定结果。
在一些实施例中，第二网格数据库可以存储在按需服务系统100的存储器(例如，存储设备150或存储器290)中。在一些实施例中，第二网格数据库可以存储在与按需服务系统100分开的外部存储器中。索引模块406可以访问第二网格数据库以索引网格。
第二网格数据库可以包括第二数据结构，所述第二数据结构指示与划分目标地理围栏的至少两个网格中的一个或以上边界网格相对应的数据。如图9所示，目标地理围栏902可以被划分为至少两个网格，其包括一个内部网格906和多个边界网格904。第二网格数据库记录与边界网格相关的信息，例如边界网格id、局部地理围栏id等。关于建立第二网格数据库的更多描述可以在本申请的其他地方找到(例如，图10及其描述)。
响应于所述索引网格不在第二网格数据库的第二否定结果，处理器可以执行操作714。处理器(例如，处理引擎112的结果确定模块408)可以确定对象属于目标地理围栏。换句话说，所述对象处于目标地理围栏的一个内部网格对应的区域中。
响应于所述索引网格在第二网格数据库的第二肯定结果，处理器可以执行操作710。在710中，处理器(例如，处理引擎112的结果确定模块408)可以根据对象和局部地理围栏的关系来确定对象是否属于目标地理围栏。局部地理围栏可以指边界网格与目标地理围栏重叠的区域。例如，如图12所示，假设三角形abc为边界网格1202、假设正方形1234为目标地理围栏1204、多边形区域nabm可以被指定为边界网格1202与目标地理围栏1204重叠的局部地理围栏。如图14所示，边界网格1402与目标地理围栏1404重叠，形成局部地理围栏1406和1408(即图14中c所示的暗区)。
虽然所述对象处于某个边界网格中，例如，所述对象在第二网格数据库中对应的网格id，但所述对象可能并不总是属于包括所述边界网格的目标地理围栏。应当理解的是，边界网格的至少一部分位于目标地理围栏中，而边界网格的其他部分不在目标地理围栏中。位于目标地理围栏中的边界网格的至少一部分被指定为至少一个局部地理围栏。如果所述对象位于局部地理围栏，所述对象属于目标地理围栏。然而，如果所述对象不在局部地理围栏中，所述对象可能不属于目标地理围栏。因此，为了确定对象是否属于目标地理围栏，处理器可能需要确定对象与局部地理围栏的关系。
在一些实施例中，第二网格数据库可以包括与一个或以上局部地理围栏有关的信息，例如，局部地理围栏id、局部地理围栏的顶点坐标等。所述处理器可以通过检索第二网格数据库来确定包含在与所述对象相关的边界网格中的一个或以上局部地理围栏。处理器可以确定所述对象与每一个局部地理围栏的关系。例如，假设所述对象在边界网格a中，结果确定模块408可以基于第二网格数据库确定边界网格a包括两个局部地理围栏，l1和l2。对于两个局部地理围栏中的每一个，处理器可以确定所述对象和每一个局部地理围栏的关系。
在一些实施例中，处理器可以基于射线法确定对象和局部地理围栏的关系。更具体地，所述对象可以被抽象为一个给定点。结果确定模块408可以确定一条以所述对象为端点的射线。射线的方向可以指向局部地理围栏的具有多边形形状的边界。例如，所述射线的方向可以垂直于多边形局部地理围栏的边界(例如，距离射线端点最近的边界)。在一些实施例中，如果射线穿过奇数个局部地理围栏的边界，如3、5、7等，处理器可以确定所述对象属于该局部地理围栏。如果射线穿过偶数个局部地理围栏的边界，例如2、4、6等，处理器可以确定所述对象不属于该局部地理围栏。
仅用于说明，图15为例证对象不属于局部地理围栏的关系的示意图，图16为例证对象属于局部地理围栏的关系的示意图。如图15所示，多边形区域1502表示局部地理围栏、点1504表示对象、射线1506是其端点为1504的射线。所述对象位于局部地理围栏的区域之外。在这种情况下，射线1506穿过局部地理围栏1502的四个边界，相应地产生了射线1506和边界的四个交点，例如交点1508。如果以所述对象为端点的射线穿过偶数个局部地理围栏的边界，则指示所述对象不属于该局部地理围栏。如图16所示，多边形区域1602表示局部地理围栏、点1604表示对象、射线1606是其端点为1604的射线。所述对象位于局部地理围栏的区域内。在这种情况下，射线1606穿过局部地理围栏1602的五个边界，相应地产生了射线1606和边界的五个交点，例如交点1608。如果以对象为端点的射线穿过奇数个局部地理围栏的边界，则指示所述对象属于该局部地理围栏。在一些实施例中，如果以对象为端点的射线穿过局部地理围栏的边界，所述对象在局部地理围栏的边界上，即对象也属于该局部地理围栏。
在一些实施例中，处理器可以基于回转数算法确定对象和局部地理围栏的关系。在多边形中，回转数指的是多边形边界围绕给定点缠绕的次数。回转数取决于多边形边界缠绕给定点的方向。例如，如果方向是逆时针方向，则回转数为正。如果方向是顺时针方向，则回转数为负数。基于所述回转数算法，处理器可以确定与对象和局部地理围栏相关的回转数。例如，所述对象可以被抽象为一个给定点、所述局部地理围栏为多边形，结果确定模块408可以确定由多边形顶点和给定点依次形成的所有夹度，并将多边形的每个边界(或边缘)和给顶点所形成的所有夹角相加来确定回转数。如果回转数不等于零(或非零)，处理器可以确定对象属于该局部地理围栏。如果回转数等于零，处理器可以确定对象不属于该局部地理围栏。
在一些实施例中，响应于确定所述对象属于目标地理围栏，处理器可以针对所述对象(例如，服务请求者或服务提供者)自定义营销策略。例如，当处理器监控到服务提供者和/或服务请求者位于通过dggs预定义的目标地理围栏中，比如，所述预定义的目标地理围栏对应于北京市海淀区，处理器可以发送向服务请求者终端和/或服务提供者终端上发送显示广告信息的指令，以显示广告信息。所述广告信息可以通过各种形式显示，比如，消息、图像、视频或音频等。在一些实施例中，所述广告信息可以包括与按需服务相关的定价策略和/或优惠策略。例如，如果在目标地理围栏对应的区域中存在大量的服务请求，则可以将按需服务的服务奖励调高，这可以鼓励更多的服务提供者提供按需服务。处理器可以将包含服务奖励的广告信息发送给目标地理围栏中的服务提供者。又例如，假设第三方企业希望将目标广告发送给特定区域中的服务请求者或服务提供者，则可以将该特定区域预先定义为目标地理围栏，处理器可以监控位于目标地理围栏对应区域中的服务请求者或服务提供者。当在目标地理围栏对应区域内出现服务请求者或服务提供者时，处理器可以将第三方企业的广告信息发送给所述服务请求者或服务提供者。
在一些实施例中，响应于确定所述对象属于目标地理围栏，处理器可以针对对象(例如，服务请求者或服务提供者)自定义安全策略。对于诸如叫车服务之类的运输服务，通过按需服务系统100获取上车位置和下车位置，可以预定义包括下车位置的目标地理围栏。在预计的到达时间(eta)之后，如果处理器监控服务提供者不在目标地理围栏的区域内，或远离目标地理围栏的区域，处理器可以向服务请求者发送安全警报信息。
在一些实施例中，处理器可以确定与过程700相关的按需服务平台的服务能力。仅仅为了说明，处理器可以获取至少两个服务提供者的地理坐标。处理器可以通过使用dggs确定与地理坐标相对应的网格信息(例如，网格id)。对于每个网格id，处理器可以在第一网格数据库中索引网格id。第一个数据库可以记录划分目标地理围栏的所有网格。处理器可以识别第一网格数据库中包含的第一网格id。处理器可以在第二网格数据库中索引每一个第一网格id。第二网格数据库可以记录划分目标地理围栏的所有网格的一个或以上边界网格。处理器可以确定第二网格数据库中未包含的第二网格id，并计数对应于第二网格id的服务提供者的数量。处理器可以确定第二网格数据库中包含的第三网格id。对于与每一个第三网格id相关的至少一个局部地理围栏，处理器可以确定属于所述至少一个局部地理围栏的服务提供者。处理器可以根据第二网格id对应的服务提供者的数量和属于所述至少一个局部地理围栏的服务提供者的数量，来确定目标地理围栏对应区域中的服务提供者的总数。处理器可以进一步根据总数来确定目标地理围栏对应区域中的服务能力。在一些实施例中，处理器可以在地图上显示所述服务能力。在一些实施例中，处理器可以基于所述服务能力确定调度策略。例如，如果服务能力低于目标地理围栏对应区域的阈值，处理器可以将更多服务提供者调度到目标地理围栏的区域。
应该注意的是，上述仅出于说明性目的而提供，并不旨在限制本申请的范围。对于本领域的普通技术人员而言，根据本申请的教导可以做出多种变化和修改。例如，第一网格数据库和第二网格数据库可以分别存储在不同的存储器中。又例如，第一网格数据库和第二网格数据库可以存储在同一存储器(例如，存储设备150或存储器290)中。然而，这些变化和修改不会背离本申请的范围。
图8是根据本申请的一些实施例所示的用于建立第一网格数据库的示例性过程的流程图。在一些实施例中，所述用于确定第一网格数据库的过程800可以在按需服务系统100中实施，如图1所示。例如，过程800可以在用户终端(例如，乘客终端130、司机终端140)和/或服务器110中实施。过程800还可以作为存储设备150中存储的一个或以上指令来实施，并由处理引擎112调用和/或执行。以下所示过程的操作仅出于说明的目的。在一些实施例中，过程800在实施时可以添加一个或以上本申请未描述的额外操作，和/或删减一个或以上此处所描述的操作。另外，如图8所示和下面描述的过程800的操作的顺序不是限制性的。
在802中，处理器(例如，第一网格确定模块410中的目标地理围栏获取单元502)可以获取目标地理围栏。目标地理围栏可以指示感兴趣的区域(roi)，例如城市、区域、县、社区等。
在一些实施例中，可以通过按需服务系统100构建目标地理围栏。例如，按需服务系统100的用户可以指定特定地理区域(例如，北京市海淀区)作为roi，并构建与roi对应的目标地理围栏。通常，地理区域具有不规则的形状，例如多边形，那么目标地理围栏相应地具有不规则的形状。注意，目标地理围栏的形状可以是各种各样的，例如不规则形状或规则形状，这取决于相应roi的形状。
在804中，处理器(例如，第一网格确定模块410中的网格获取单元504)可以获取对应于目标地理围栏的至少两个网格。例如，网格获取单元504可以从在按需服务平台上实施的dggs上获取所述至少两个网格。
在一些实施例中，目标地理围栏可以通过dggs划分为至少两个网格。所述至少两个网格每一个网格可以是离散的全局网格(或单元)。每个网格可以包括具有至少两个顶点的多边形。如这里所使用的，每个网格可以具有相同的正六边形形状，例如，图9中所示的网格904和906，或者图14中所示的网格1402。然而，在一些实施例中，网格的形状可以是各种各样的，例如三角形、正方形、矩形等。所述至少两个网格可以具有相同的尺寸和形状。所述至少两个网格也可以具有不同的尺寸和形状。
在一些实施例中，所述至少两个网格可以包括一个或以上内部网格和一个或以上边界网格。所述内部网格的整个部分包括在目标地理围栏中，例如，图9中所示的内部网格906。所述边界网格的至少一部分包括在目标地理围栏中，例如，图9中所示的边界网格904。如这里所使用的，包括在目标地理围栏中的边界网格的至少一部分可以用于构建局部地理围栏。
仅用于说明，图9是根据本申请的一些实施例所示的目标地理围栏和一个或以上网格的关系的示意图。如图9所示，处理器可以将roi(即，粗体多边形)指定为目标地理围栏902。根据dggs，目标地理围栏902被划分为八个六边形网格，包括七个边界网格和一个内部网格906。边界网格904表示七个边界网格中的一个。
在806中，处理器(例如，第一网格确定模块410的第一编码单元506)可以将对应于所述至少两个网格的数据编码成第一数据结构。第一数据结构可以包括所述至少两个网格的标识码，以及至少两个顶点的坐标等或其任何组合。在一些实施例中，第一数据结构可以是键值对(key-value)的形式。键可以指示网格id。键可以指向一个或以上的值。键可以指示与网格id对应的网格的顶点的坐标。在一些实施例中，坐标可以指示所述至少两个顶点中的每一个顶点的纬度和经度坐标。仅仅为了说明，第一编码单元506可以基于消息摘要算法(md5)为至少两个网格中的每一个网格生成唯一标识码(或id)。网格id可以指向与网格id对应的网格的坐标。应当理解的是，第一数据结构可以是各种各样的，例如b树结构、b 树结构、静默表、链表等。这些变化均在本申请的保护范围内。
在808中，处理器(例如，第一网格确定模块410中的第一写入单元508)可以将编码数据写入至少一个非暂时性存储介质中，以建立第一网格数据库。例如，所述至少一个非暂时性存储介质可以包括按需服务系统100的存储设备150和/或存储器290。又例如，所述至少一个非暂时性存储介质可以包括与按需服务系统100分开的外部存储设备。
应该注意的是，上述仅出于说明性目的而提供，并不旨在限制本申请的范围。对于本领域的普通技术人员而言，根据本申请的教导可以做出多种变化和修改。例如，第一网格数据库还可以存储在与按需服务系统100分开的外部存储介质中。又例如，第一网格数据库可以根据dggs中不同的目标地理围栏进行更新。然而，变化和修改不会背离本申请的范围。
图10是根据本申请的一些实施例所示的用于建立第二网格数据库的示例性过程的流程图。在一些实施例中，所述用于确定第二网格数据库的过程1000可以在按需服务系统100中实施，如图1所示。例如，过程1000可以在用户终端(例如，乘客终端130、司机终端140)和/或服务器110中实施。过程1000还可以作为存储设备150中存储的一个或以上指令来实施，并由处理引擎112调用和/或执行。以下所示过程的操作仅出于说明的目的。在一些实施例中，过程1000在实施时可以添加一个或以上本申请未描述的额外操作，和/或删减一个或以上此处所描述的操作。另外，如图10所示和下面描述的过程1000的操作的顺序不是限制性的。
在1002中，处理器(例如，第二网格确定模块412的边界网格获取单元602)可以从对应于目标地理围栏的至少两个网格中获取一个或以上边界网格。在一些实施例中，网格获取单元504可以获取对应于目标地理围栏的至少两个网格，如图8的804所述。所述至少两个网格可以包括一个或以上内部网格和一个或以上边界网格。边界网格获取单元602可以从网格获取单元504获取所述一个或以上边界网格。
在1004中，处理器(例如，第二网格确定模块412的局部地理围栏确定单元604)可以基于一个或以上边界网格和目标地理围栏来确定一个或以上局部地理围栏。所述局部地理围栏可以是边界网格与目标地理围栏重叠的区域。
在一些实施例中，对于一个或以上边界网格中的每一个边界网格，处理器可以确定对应于所述边界网格的第一链表，例如，对应于边界网格1202(如图12所示)的第一链表1302(如图13所示)。处理器可以确定对应于目标地理围栏1204(如图12所示)的第二链表1304(如图13所示)。在第一链表中，每个节点对应于边界网格的一个顶点，所述节点由图13所示的矩形框表示。类似于第一链表，在第二链表中，每个节点对应于目标地理围栏的一个顶点。处理器可以确定边界网格和目标地理围栏的一个或以上交点，例如，点a(1)、点b、点m和点n，如图12所示。处理器可以基于一个或以上交点来更新第一链表和第二链表，例如，更新的第一链表1306和更新的第二链表1308，如图13所示。处理器可以根据更新的第一链表和更新的第二链表确定所述一个或以上局部地理围栏。关于确定一个或以上局部地理围栏的更多描述可以在本申请的其他地方找到(例如，图11-14及其描述)。
在1006中，处理器(例如，第二网格确定模块412的第二编码单元606)可以将对应于一个或以上边界网格和一个或以上局部地理围栏的数据编码成第二数据结构。第二数据结构可以包括一个或以上边界网格的标识码、一个或以上局部围栏的标识码、一个或以上边界网格的每一个边界网格的顶点坐标、以及一个或以上局部地理围栏的每一个局部地理围栏的顶点坐标等或其任何组合。在一些实施例中，第二数据结构可以是以键值(key-value)的形式表示。键指向一个或以上的值。例如，键可以指示边界网格id，键可以指向多个值，比如，边界网格的顶点坐标和对应于所述边界网格的一个或以上局部地理围栏的顶点坐标。在一些实施例中，所述坐标可以指示顶点的纬度和经度坐标。
在一些实施例中，第二编码单元606可以从第一编码单元506获取一个或以上边界网格的标识码。所述一个或以上边界网格的标识码可以与第一网格数据库的标识码一致。例如，假设边界网格a的标识码在第一网格数据库中是“ol2f0i1234j5678”，因此边界网格a的标识码也可以是第二网格数据库中的“ol2f0i1234j5678”。在一些实施例中，第二编码单元606可以基于消息摘要算法(md5)为一个或以上局部地理围栏中的每一个局部地理围栏生成唯一标识码。边界网格id可以指向相应边界网格的顶点坐标。局部地理围栏id可以指向对应于局部地理围栏的顶点坐标。类似于第一数据结构，第二数据结构可以是各种各样的，例如b树结构、b 树结构、静默表、链表等。这些变化均在本申请的保护范围内。
在1008中，处理器(例如，第二网格确定模块412的第二写入单元608)可以将编码数据写入到至少一个非暂时性存储介质中，以建立第二网格数据库。例如，所述至少一个非暂时性存储介质可以包括按需服务系统100的存储设备150和/或存储器290。又例如，所述至少一个非暂时性存储介质可以包括与按需服务系统100分开的外部存储设备。在一些实施例中，第一网格数据库和第二网格数据库可以集成到单个非暂时性存储介质(例如，存储设备150)。
应该注意的是，上述仅出于说明性目的而提供，并不旨在限制本申请的范围。对于本领域的普通技术人员来说，根据本申请的教导可以做出多种变化和修改。例如，第二网格数据库可以存储在与按需服务系统100分开的外部存储介质中。又例如，第二网格数据库可以根据dggs中不同的目标地理围栏进行更新。然而，变化和修改不会背离本申请的范围。
图11是根据本申请的一些实施例所示的确定一个或以上局部地理围栏的示例性过程的流程图。在一些实施例中，用于确定一个或以上局部地理围栏的过程1100可以在按需服务系统100中实施，如图1所示。例如，过程1100可以在用户终端(例如，乘客终端130、司机终端140)和/或服务器110中实施。过程1100还可以作为存储设备150中存储的一个或以上指令来实施，并由处理引擎112调用和/或执行。以下所示过程的操作仅出于说明的目的。在一些实施例中，过程1100在实施时可以添加一个或以上本申请未描述的额外操作，和/或删减一个或以上此处所描述的操作。另外，如图11所示和下面描述的过程1100的操作的顺序不是限制性的。
在1102中，处理器(例如，第二网格确定模块412的局部地理围栏确定单元604)可以分别确定对应于边界网格的第一链表和对应于目标地理围栏的第二链表。第一链表或第二链表可以包括至少两个节点。所述节点可以包括至少一个数据元素，例如，边界网格或目标地理围栏的编号顶点。所述数据元素可以指向下一个节点。仅仅为了说明，如图12和图13所示，假设三角区域表示边界网格1202、正方形区域表示目标地理围栏1204。边界网格1202的每个顶点可以编号为唯一字符，例如a、b、c。目标地理围栏1204的每个顶点可以编号为唯一字符，例如1、2、3和4。编号1和a是相同的顶点。局部地理围栏确定单元604可以确定对应于边界网格1202的第一链表1302，以及对应于目标地理围栏1204的第二链表1304。所述节点可以由矩形框来表示，并对应于一个顶点。在第一链表1302和第二链表1304中，节点的顺序可以是相同的。例如，第一链表1302或第二链表1304的节点均是逆时针排序的。在一些实施例中，相应顶点的坐标可以通过索引节点来获取。
在一些实施例中，第一链表或第二第一链表的类型可以包括单链表、双链表、圆形链表、双向循环链表等或其任何组合。如本文所用，第一链表和第二第一链表是双向循环链表。双向循环链表中的每个节点指向列表中的下一个节点和前一个节点。在双向循环链表中，处理器容易在列表的开头或结尾处添加或删除节点，即使在列表的中间也是如此。
在1104中，处理器(例如，第二网格确定模块412的局部地理围栏确定单元604)可以确定边界网格和目标地理围栏的一个或以上交点。
在一些实施例中，处理器可以分别遍历边界网格和目标地理围栏的每个边界(或边缘)。应当理解的是，在数学中，每个边界可以由至少两个离散数据点表示。每个数据点可以指示边界中的地理点的坐标。如果在边界网格和目标地理围栏的边界中存在相同的数据点，则处理器可以指定所述相同的数据点为交点。如图12所示，点a(或1)，点m和点n是边界网格1202和目标地理围栏1204的交点。类似地，处理器可以确定边界网格和目标地理围栏的所有边界的一个或以上的交点。
在1106中，处理器(例如，第二网格确定模块412的局部地理围栏确定单元604)可以基于一个或以上交点更新第一链表和第二链表。
在一些实施例中，由于第一链表1302和第二链表1304是双向循环链表，处理器可以容易地将一个或以上交点添加到原始链表以进行更新。例如，局部地理围栏确定单元604可以确定更新的第一链表1306和更新的第二链表1308。
仅用于说明，表1例证了更新第一链表和第二链表的示例性操作。
表1
如表1所示，边界网格1202和目标地理围栏1204的边界交点可以被添加到原始链表(例如，第一链表1302和第二链表1304)。例如，对于表1中的编号2，在边界ab和边界12中有三个交点，即点b、点a和点1。事实上，点a和点1是相同的点，它们可以用1(a)或a(1)表示。将交点添加到第一链表1302，即a->b->b->c->1(a)。将交点可以添加到第二链表1304，即1->b->2->3->4->1(a)。对于表1中的编号2，可以将边界ab和41中的交点添加到先前更新的第一链表和先前更新的链表。类似地操作，处理器可以遍历与边界网格和目标地理围栏相关的每个相交的边界，并将交点添加到相应的链表。处理器可以确定目标第一链表和目标第二链表，例如，更新的第一链表1302和更新的链表1304。在一些实施例中，可以将添加到第一链表或第二链表的交点进行标记，用于区别交点和顶点。例如，对于链表，a->b->b->c->1(a)，第一个b是交点，而第二个b是顶点。处理器可以自动识别链表中标记的交点。
在1108中，处理器(例如，第二网格确定模块412的局部地理围栏确定单元604)可以基于更新的第一链表和更新的第二链表来确定一个或以上局部地理围栏。
在一些实施例中，为了确定一个或以上局部地理围栏中的每一个局部地理围栏，处理器可以基于预设的遍历规则来遍历更新的第一链表和更新的第二链表。处理器可以确定边界网格和目标地理围栏的交集。所述交集包括边界网格和目标地理围栏的一个或以上的交点。处理器可以根据所述交集确定局部地理围栏。
在一些实施例中，预设的遍历规则可以与遍历起点、遍历方向或遍历转换顺序相关。所述遍历起点可以包括位于目标地理围栏之外的边界网格的顶点或位于边界网格之外的目标地理围栏的顶点。例如，如图12所示，顶点c可以被指定为遍历起点，因为边界网格1202的顶点c在目标地理围栏1204之外。又如图12所示，顶点2、3或4可以指定为遍历起点，因为目标地理围栏1204的这些顶点位于边界网格1202之外。遍历方向可以包括顺时针方向或逆时针方向。遍历转换顺序可以包括在遍历到第一个交点后每次遇到交点交替遍历所述更新的第一链表和第二链表。
仅仅为了说明，局部地理围栏确定单元604在预设的遍历规则上遍历更新的第一链表1302和更新的第二链表1304。假设顶点c作为遍历起点。首先，局部地理围栏确定单元604逆时针遍历链表1302。局部地理围栏确定单元604遇到第一交点n，并将其放入交集。局部地理围栏确定单元604继续沿逆时针方向遍历更新的第一链表1302，并遇到第二交点1(a)。第二交叉点1(a)可以被放到交集中。然后跳到链表1304并逆时针遍历，局部地理围栏确定单元604遇到第三交点1(a)。因为第三交点与第二交点相同，所以第三交点1(a)不会被重复放入交集中。跳到链表1302并逆时针遍历，局部地理围栏确定单元604遇到第四交点1(a)。因为第四交点与第二交点相同，所以第四交点1(a)不会被重复放入交集中。跳到链表1304并逆时针遍历，局部地理围栏确定单元604遇到第五交点1(a)。因为第五交点与第二交点相同，所以第五交点1(a)不会被重复放入交集中。跳到链表1302并逆时针遍历，局部地理围栏确定单元604遇到第六点，即顶点a。因为第六点不是交点，所以局部地理围栏确定单元604可以继续遍历链表1302。局部地理围栏确定单元604遇到第七交点b。第七交点b可以被放入交集中。跳到链表1304并进行遍历，局部地理围栏确定单元604遇到第八交点b。因为第八交点与第七交点相同，所以第八交点b不会重复放入交集中。跳到链表1302并进行遍历，局部地理围栏确定单元604遇到第九点，即顶点b。因为第九点不是交点，所以局部地理围栏确定单元604可以继续遍历链表1302。局部地理围栏确定单元604遇到第十交点m，并将第十交点放入交集中。跳到链表1304并进行遍历，局部地理围栏确定单元604遇到第十一交点n。因为第十一交点与遍历起点(即，第一交点n)相同，所以局部地理围栏确定单元604可以终止遍历。注意，在遍历的过程中，一旦局部地理围栏确定单元604遇到遍历起点，就可以终止遍历。最后，可以确定所述交集。所述交集包括交点n、1a、b和m，即{n，1a，b，m}。可以基于交集来构建边界网格1302和目标地理围栏1304的多边形局部地理围栏nabm。
仅用于说明，图14是根据本申请的一些实施例所示的用于确定局部围栏的示例性操作的示意图。局部地理围栏确定单元604可以分别对边界网格1402和目标地理围栏1404的顶点进行编号，如图14中的a所示。局部地理围栏确定单元604可以确定包括边界网格1402的顶点的第一链表，并确定包括目标地理围栏1404顶点的第二链表。如图14的b所示，局部地理围栏确定单元604可以确定目标地理围栏1402和边界网格1404的交点，并对交点进行编号。局部地理围栏确定单元604可以基于编号的交点更新第一链表和第二链表。参考上述遍历过程，如图14中的c所示，局部地理围栏确定单元604可以确定目标地理围栏1402和边界网格1404的局部地理围栏，即局部地理围栏1406和1408。
上文已对基本概念做了描述，显然，对于阅读此申请后的本领域的普通技术人员来说，上述发明披露仅作为示例，并不构成对本申请的限制。虽然此处并未明确说明，但本领域的普通技术人员可能会对本申请进行各种修改、改进和修正。该类修改、改进和修正在本申请中被建议，所以该类修改、改进、修正仍属于本申请示范实施例的精神和范围。
同时，本申请使用了特定术语来描述本申请的实施例。例如“一个实施例”、“一实施例”、和/或“一些实施例”意指与本申请至少一个实施例相关的某一特征、结构或特性。因此，应当强调并注意的是，本说明书中在不同位置两次或以上提及的“一实施例”或“一个实施例”或“一替代性实施例”并不一定是指同一实施例。此外，本申请的一个或以上实施例中的某些特征、结构或特点可以进行适当的组合。
此外，本领域的普通技术人员可以理解，本申请的各方面可以通过若干具有可专利性的种类或情况进行说明和描述，包括任何新的和有用的工序、机器、产品或物质的组合，或对其任何新的和有用的改进。相应地，本申请的各个方面可以完全由硬件执行、可以完全由软件(包括固体、常驻软件、微码等)执行、也可以由硬件和软件组合执行。以上硬件或软件均可被称为“单元”、“模块”或“系统”。此外，本申请的各方面可以采取体现在一个或以上计算机可读介质中的计算机程序产品的形式，其中计算机可读程序编码包含在其中。
计算机可读信号介质可能包含一个内含有计算机程序代码的传播数据信号，例如在基带上或作为载波的一部分。此类传播信号可以有多种形式，包括电磁形式、光形式等或任何合适的组合形式。计算机可读信号介质可以是除计算机可读存储介质之外的任何计算机可读介质，该介质可以通过连接至一个指令执行系统、装置或设备以实现通信、传播或传输供使用的程序。位于计算机可读信号介质上的程序代码可以通过任何合适的介质进行传播，包括无线电、电缆、光纤电缆、rf等，或任何上述介质的组合。
本申请各方面操作所需的计算机程序码可以用一种或多种程序语言的任意组合编写，包括面向对象程序设计，如java、scala、smalltalk、eiffel、jade、emerald、c 、c#、vb.net、python或类似的常规程序编程语言，如"c"编程语言，visualbasic、fortran2003、perl、cobol2002、php、abap，动态编程语言如python、ruby和groovy或其它编程语言。该程序代码可以完全在用户计算机上运行、或作为独立的软件包在用户计算机上运行、或部分在用户计算机上运行部分在远程计算机运行、或完全在远程计算机或服务器上运行。在后种情况下，远程计算机可以通过任何网络形式与用户计算机连接，比如局域网(lan)或广域网(wan)，或连接至外部计算机(例如通过因特网)，或在云计算环境中，或作为服务使用如软件即服务(saas)。
此外，除非权利要求中明确说明，本申请所述处理元素和序列的顺序、数字字母的使用、或其他名称的使用，并非用于限定本申请流程和方法的顺序。尽管上述披露中通过各种示例讨论了一些目前认为有用的发明实施例，但应当理解的是，该类细节仅起到说明的目的，附加的权利要求并不仅限于披露的实施例，相反，权利要求旨在覆盖所有符合本申请实施例实质和范围的修正和等价组合。例如，虽然以上所描述的系统组件可以通过硬件设备实现，但是也可以只通过软件的解决方案得以实现，如在现有的服务器或移动设备上安装所描述的系统。
同理，应当注意的是，为了简化本申请披露的表述，从而帮助对一个或以上发明实施例的理解，前文对本申请实施例的描述中，有时会将多种特征归并至一个实施例、附图或对其的描述中。但是，这种披露方法并不意味着本申请对象所需要的特征比权利要求中提及的特征多。实际上，实施例的特征要少于上述披露的单个实施例的全部特征。
1.一种用于确定对象是否属于目标地理围栏的方法，其特征在于，所述方法包括：
获取所述对象的地理位置对应的地理坐标；
确定所述地理坐标对应的网格信息；
基于所述网格信息，在第一网格数据库中索引所述网格；
响应于所述索引的网格不在所述第一网格数据库中：
确定所述对象不属于所述目标地理围栏；
响应于所述索引的网格在所述第一网格数据库中：
基于所述网格信息，在第二网格数据库中索引所述网格；
响应于所述索引的网格不在所述第二网格数据库中：
确定所述对象属于所述目标地理围栏；以及
响应于所述索引的网格在所述第二网格数据库中：
根据所述对象和局部围栏的关系，确定所述对象是否属于所述目标地理围栏。
2.根据权利要求1所述的方法，其特征在于，所述方法还包括：建立所述第一网格数据库，其中，
所述建立所述第一网格数据库进一步包括：
获取所述目标地理围栏；
获取所述目标地理围栏对应的至少两个网格，其中所述至少两个网格中的每一网格是具有多个顶点的多边形；
将所述至少两个网格对应的数据编码成第一数据结构，所述第一数据结构包括所述至少两个网格的标识码和所述多个顶点的坐标；以及
将所述编码的数据写入至少一个非暂时性存储介质。
3.根据权利要求2所述的方法，其特征在于，所述方法进一步包括：建立所述第二网格数据库，其中，
所述建立所述第二网格数据库进一步包括：
获取所述至少两个网格中的一个及以上边界网格；
基于所述一个及以上边界网格和所述目标地理围栏确定一个及以上局部地理围栏；
将所述一个及以上边界网格对应的数据和所述一个及以上局部地理围栏对应的数据编码成第二数据结构，所述第二数据结构包括所述一个及以上边界网格的标识码、所述一个及以上局部地理围栏的标识码、所述一个及以上边界网格中的每一边界网格的顶点坐标、所述一个及以上局部地理围栏中的每一局部地理围栏的顶点坐标，其中，所述一个及以上局部地理围栏中的每一局部地理围栏的顶点包括所述边界网格和所述局部地理围栏的一个及以上交点；以及
将所述编码的数据写入所述至少一个非暂时性存储介质。
4.根据权利要求3所述的方法，其特征在于，所述基于所述一个及以上边界网格和所述目标地理围栏确定一个及以上局部地理围栏包括：
对于所述一个及以上边界网格中的每一个边界网格：
分别确定对应于所述边界网格的第一链表和对应于所述目标地理围栏的第二链表，其中，所述第一链表或第二链表中的每一节点分别对应于所述边界网格的一个顶点或所述目标地理围栏的一个顶点；
确定所述边界网格和所述目标地理围栏的一个及以上交点；
基于所述一个及以上交点更新所述第一链表和所述第二链表；以及
基于所述更新的第一链表和第二链表确定所述一个及以上局部地理围栏。
5.根据权利要求4所述的方法，其特征在于，所述基于所述更新的第一链表和第二链表确定所述一个及以上局部地理围栏包括：
对于确定所述一个及以上局部地理围栏中的每一个局部地理围栏：
基于预设的遍历规则，遍历所述更新的第一链表和第二链表；
确定所述边界网格和所述目标地理围栏的交集，所述交集包括所述边界网格和所述目标地理围栏的一个及以上交点；以及
基于所述交集确定所述局部地理围栏。
6.根据权利要求5所述的方法，其特征在于，所述预设的遍历规则与遍历起点、遍历方向和遍历转换顺序相关，其中，
所述遍历起点包括所述边界网格的顶点且所述边界网格的顶点位于所述目标地理围栏的外部，或者所述目标地理围栏的顶点且所述目标地理围栏的顶点位于所述边界网格的外部；
所述遍历方向包括顺时针方向或者逆时针方向；以及
所述遍历转换顺序包括在遍历到第一个交点后每次遇到交点交替遍历所述更新的第一链表和第二链表。
7.根据权利要求4所述的方法，其特征在于，所述第一链表和第二链表是双向循环链表。
8.根据权利要求1的所述方法，其特征在于，所述根据所述对象和局部围栏的关系确定所述对象是否属于所述目标地理围栏包括：
如果以所述对象为端点的射线穿过奇数个所述局部地理围栏的边界，确定所述对象属于所述局部地理围栏；以及
如果以所述对象为端点的射线穿过偶数个所述局部地理围栏的边界，确定所述对象不属于所述局部地理围栏。
9.根据权利要求1所述的方法，其特征在于，所述根据所述对象和局部围栏的关系确定所述对象是否属于所述目标地理围栏进一步包括：
确定与所述对象和所述局部地理围栏相关的回转数；
如果所述回转数不等于零，确定所述对象属于所述局部地理围栏；以及
如果所述回转数等于零，确定所述对象不属于所述局部地理围栏。
10.根据权利要求1所述的方法，其特征在于，所述网格具有正六边形结构。
11.一种用于确定对象是否属于目标地理围栏的装置，其特征在于，包括至少一个处理器以及计算机可读存储介质，其中，
所述计算机可读存储介质用于存储计算机指令；
所述至少一个处理器用于执行所述计算机指令以实现如权利要求1-10中任意一项所述的方法。
12.一种计算机可读存储介质，其特征在于，所述存储介质存储计算机指令，当计算机读取所述存储介质中的计算机指令后，计算机运行如权利要求1-10中任意一项所述的方法。
13.一种用于确定对象是否属于目标地理围栏的系统，其特征在于，所述系统包括获取模块、网格信息确定模块、索引模块和结果确定模块、第一网格数据库确定模块和第二网格数据库确定模块，其中，
所述获取模块用于获取所述对象的地理位置对应的地理坐标；
所述网格信息确定模块用于确定所述地理坐标对应的网格信息；
所述索引模块用于基于所述网格信息，在第一网格数据库中索引所述网格；
响应于所述索引的网格不在所述第一网格数据库中：
所述结果确定模块用于确定所述对象不属于所述目标地理围栏；
响应于所述索引的网格在所述第一网格数据库中：
所述索引模块用于基于所述网格信息，在第二网格数据库中索引所述网格；
响应于所述索引的网格不在所述第二网格数据库中：
所述结果确定模块用于确定所述对象属于所述目标地理围栏；以及
响应于所述索引的网格在所述第二网格数据库中：
所述结果确定模块用于根据所述对象和局部围栏的关系，确定所述对象是否属于所述目标地理围栏；
所述第一网格数据库确定模块用于建立所述第一网格数据库；以及
所述第二网格数据库确定模块用于建立所述第二网格数据库。
14.根据权利要求13所述的系统，其特征在于，所述第一网格数据库确定模块进一步包括目标地理围栏获取单元、网格获取单元、第一编码单元和第一写入单元，其中，
为了建立所述第一网格数据库：
所述目标地理围栏获取单元用于获取所述目标地理围栏；
所述网格获取单元用于获取所述目标地理围栏对应的至少两个网格，所述至少两个网格中的每一网格是具有多个顶点的多边形；
所述第一编码单元用于将所述至少两个网格对应的数据编码成第一数据结构，所述第一数据结构包括所述至少两个网格的标识码和所述多个顶点的坐标；以及
所述第一写入单元用于将所述编码的数据写入至少一个非暂时性存储介质。
15.根据权利要求14所述的系统，其特征在于，所述第二网格数据库确定模块进一步包括边界网格获取单元、局部地理围栏确定单元、第二编码单元和第二写入单元，其中，
为了建立所述第二网格数据库：
所述边界网格获取单元用于获取所述至少两个网格中的一个及以上边界网格；
所述局部地理围栏确定单元用于基于所述一个及以上边界网格和所述目标地理围栏确定一个及以上局部地理围栏；
所述第二编码单元用于将所述一个及以上边界网格对应的数据和所述一个及以上局部地理围栏对应的数据编码成第二数据结构，所述第二数据结构包括所述一个及以上边界网格的标识码、所述一个及以上局部地理围栏的标识码、所述一个及以上边界网格中的每一边界网格的顶点坐标、所述一个及以上局部地理围栏中的每一局部地理围栏的顶点坐标，其中，所述一个及以上局部地理围栏中的每一局部地理围栏的顶点包括所述边界网格和所述局部地理围栏的一个及以上交点；以及
所述第二写入单元用于将所述编码的数据写入所述至少一个非暂时性存储介质。
16.根据权利要求15所述的系统，其特征在于，所述局部地理围栏确定单元进一步用于：
对于所述一个及以上边界网格中的每一个边界网格：
分别确定对应于所述边界网格的第一链表和对应于所述目标地理围栏的第二链表，其中，所述第一链表或第二链表中的每一节点分别对应于所述边界网格的一个顶点或所述目标地理围栏的一个顶点；
确定所述边界网格和所述目标地理围栏的一个及以上交点；
基于所述一个及以上交点更新所述第一链表和所述第二链表；以及
基于所述更新的第一链表和第二链表确定所述一个及以上局部地理围栏。
17.根据权利要求16所述的系统，其特征在于，所述局部地理围栏确定单元进一步用于：
对于确定所述一个及以上局部地理围栏中的每一个局部地理围栏：
基于预设的遍历规则，遍历所述更新的第一链表和第二链表；
确定所述边界网格和所述目标地理围栏的交集，所述交集包括所述边界网格和所述目标地理围栏的一个及以上交点；以及
基于所述交集确定所述局部地理围栏。
18.根据权利要求17所述的系统，其特征在于，所述预设的遍历规则与遍历起点、遍历方向和遍历转换顺序相关，其中，
所述遍历起点包括所述边界网格的顶点且所述边界网格的顶点位于所述目标地理围栏的外部，或者所述目标地理围栏的顶点且所述目标地理围栏的顶点位于所述边界网格的外部；
所述遍历方向包括顺时针方向或者逆时针方向；以及
所述遍历转换顺序包括在遍历到第一个交点后每次遇到交点交替遍历所述更新的第一链表和第二链表。
19.根据权利要求16-18所述的系统，其特征在于，所述第一链表和第二链表是双向循环链表。
20.根据权利要求13所述的系统，其特征在于，所述结果确定模块进一步用于：
如果以所述对象为端点的射线穿过奇数个所述局部地理围栏的边界，确定所述对象属于所述局部地理围栏；以及
如果以所述对象为端点的射线穿过偶数个所述局部地理围栏的边界，确定所述对象不属于所述局部地理围栏。
21.根据权利要求13所述的系统，其特征在于，所述结果确定模块进一步用于：
确定与所述对象和所述局部地理围栏相关的回转数；
如果所述回转数不等于零，确定所述对象属于所述局部地理围栏；以及
如果所述回转数等于零，确定所述对象不属于所述局部地理围栏。
22.根据权利要求13所述的系统，其特征在于，所述网格具有正六边形结构。
技术总结