1.本公开涉及地理信息处理技术领域，具体涉及一种位置信息处理方法、装置、电子设备、介质及程序产品。
背景技术：2.位置信息服务是近年快速发展的服务，并且已成为目前应用与研究的热点。无论是公众用户还是行业用户，对于获得位置信息及其相关服务都有着广泛的需求。
3.基于位置的服务(location based services，lbs)利用各类型的定位技术来获取电子设备当前的所在位置，以便通过移动互联网向电子设备提供信息资源和其他服务。在很多lbs应用中，当获取到汽车、船舶等交通工具的位置信息时，需要知道交通工具位于哪个大区域内，例如汽车行驶于哪个省市，船舶停留于哪个岛屿的泊位。一个比较快速的办法是预计算好所有大区域内部的所有geohash值存储进数据库。geohash是一种地址编码方法，它能够把二维的空间经纬度数据编码成一个字符串。geohash用一个字符串表示经度和纬度两个坐标，其表示的并不是一个点，而是一个区域。换言之，每个geohash编码可以对应于一个geohash区块，该区块中包含多个地理位置点。
4.当地理区域形状不规则，边界顶点较多时，确定该地理区域内的geohash区块的计算复杂度会很高，当需要处理的地理区域较多时，计算效率会非常低下。
技术实现要素：5.为了解决相关技术中的问题，本公开实施例提供一种位置信息处理方法、装置、电子设备、介质及程序产品。
6.第一方面，本公开实施例提供了一种位置信息处理方法，包括：
7.获取指定地理区域边界顶点的位置信息；
8.根据所述指定地理区域边界顶点的位置信息，将所述指定地理区域划分为多个子区域；
9.根据所述子区域边界顶点的位置信息，确定多个区块；
10.根据所述区块与所述子区域的位置关系，确定所述区块与所述指定地理区域的位置关系。
11.根据本公开的实施例，所述根据所述指定地理区域边界顶点的位置信息，将所述指定地理区域划分为多个子区域，包括：
12.根据所述指定地理区域边界顶点的位置信息，使用耳切法将所述指定地理区域划分为多个三角形子区域。
13.根据本公开的实施例，所述根据所述指定地理区域边界顶点的位置信息，使用耳切法将所述指定地理区域划分为多个三角形子区域，包括：
14.根据所述指定地理区域边界顶点的位置信息，使用d-p算法删除所述指定地理区域边界顶点；
15.根据未删除的所述指定地理区域边界顶点的位置信息，得到精简的指定地理区域，使用耳切法将所述精简的指定地理区域划分为多个三角形子区域。
16.根据本公开的实施例，所述根据所述子区域边界顶点的位置信息，确定多个区块，包括：
17.根据所述子区域边界顶点的位置信息确定所述子区域的外包矩形；
18.根据所述外部矩形顶点的位置信息，确定所述多个区块，所述多个区块中的任一区块全部或部分位于所述外包矩形内。
19.根据本公开的实施例，每个所述区块是一个geohash编码区域。
20.根据本公开的实施例，所述根据所述区块与所述子区域的位置关系，确定所述区块与所述指定地理区域的位置关系，包括：
21.获取以所述区块的顶点为顶点并且经过所述子区域内的一点的射线与所述子区域的边界的交点数量；
22.根据所述交点数量确定所述区块与所述指定地理区域的位置关系。
23.根据本公开的实施例，所述根据所述交点数量确定所述区块与所述指定地理区域的位置关系，包括：
24.根据所述以所述区块的顶点为顶点并且经过所述子区域内的一点的射线与所述子区域的边界的交点数量，确定所述区块是否至少部分位于所述子区域内；
25.如果所述区块至少部分位于所述子区域内，则所述区块至少部分位于所述指定地理区域内。
26.根据本公开的实施例，针对所述多个子区域，并行地执行所述确定所述区块与所述指定地理区域的位置关系的操作。
27.第二方面，本公开实施例中提供了一种位置信息处理装置，包括：
28.获取模块，被配置为获取指定地理区域边界顶点的位置信息；
29.划分模块，被配置为根据所述指定地理区域边界顶点的位置信息，将所述指定地理区域划分为多个子区域；
30.第一确定模块，被配置为根据所述子区域边界顶点的位置信息，确定多个区块；
31.第二确定模块，被配置为根据所述区块与所述子区域的位置关系，确定所述区块与所述指定地理区域的位置关系。
32.根据本公开的实施例，所述根据所述指定地理区域边界顶点的位置信息，将所述指定地理区域划分为多个子区域，包括：
33.根据所述指定地理区域边界顶点的位置信息，使用耳切法将所述指定地理区域划分为多个三角形子区域。
34.根据本公开的实施例，所述根据所述指定地理区域边界顶点的位置信息，使用耳切法将所述指定地理区域划分为多个三角形子区域，包括：
35.根据所述指定地理区域边界顶点的位置信息，使用d-p算法删除所述指定地理区域边界顶点；
36.根据未删除的所述指定地理区域边界顶点的位置信息，得到精简的指定地理区域，使用耳切法将所述精简的指定地理区域划分为多个三角形子区域。
37.根据本公开的实施例，所述根据所述子区域边界顶点的位置信息，确定多个区块，
包括：
38.根据所述子区域边界顶点的位置信息确定所述子区域的外包矩形；
39.根据所述外部矩形顶点的位置信息，确定所述多个区块，所述多个区块中的任一区块全部或部分位于所述外包矩形内。
40.根据本公开的实施例，每个所述区块是一个geohash编码区域。
41.根据本公开的实施例，所述根据所述区块与所述子区域的位置关系，确定所述区块与所述指定地理区域的位置关系，包括：
42.获取以所述区块的顶点为顶点并且经过所述子区域内的一点的射线与所述子区域的边界的交点数量；
43.根据所述交点数量确定所述区块与所述指定地理区域的位置关系。
44.根据本公开的实施例，所述根据所述交点数量确定所述区块与所述指定地理区域的位置关系，包括：
45.根据所述以所述区块的顶点为顶点并且经过所述子区域内的一点的射线与所述子区域的边界的交点数量，确定所述区块是否至少部分位于所述子区域内；
46.如果所述区块至少部分位于所述子区域内，则所述区块至少部分位于所述指定地理区域内。
47.根据本公开的实施例，针对所述多个子区域，并行地执行所述确定所述区块与所述指定地理区域的位置关系的操作。
48.第三方面，本公开实施例提供了一种电子设备，包括存储器和处理器，其中，所述存储器用于存储一条或多条计算机指令，其中，所述一条或多条计算机指令被所述处理器执行以实现如第一方面任一项所述的方法。
49.第四方面，本公开实施例中提供了一种计算机可读存储介质，其上存储有计算机指令，该计算机指令被处理器执行时实现如第一方面所述的方法。
50.第五方面，本公开实施例中提供了一种计算机程序产品，包括计算机指令，该计算机指令被处理器执行时实现如第一方面所述的方法步骤。
51.根据本公开实施例提供的技术方案，根据本公开的实施例，将指定地理区域划分为多个子区域，分别确定区块与子区域的位置关系，进而确定区块与指定地理区域的位置关系，由于子区域的边界顶点数量远小于指定区域，显著降低了计算复杂度，提高了计算效率。
52.应当理解的是，以上的一般描述和后文的细节描述仅是示例性和解释性的，并不能限制本公开。
附图说明
53.结合附图，通过以下非限制性实施方式的详细描述，本公开的其它特征、目的和优点将变得更加明显。在附图中：
54.图1示出根据本公开的实施例的位置信息处理方法的流程图。
55.图2示出了d-p算法的原理。
56.图3a示出了根据本公开实施例，根据所述子区域边界顶点的位置信息确定多个区块的示意图。
57.图3b示出了根据本公开实施例，根据区块与子区域的位置关系确定区块与指定地理区域的位置关系的原理示意图。
58.图4示出了根据本公开实施例进行位置信息处理的流程图。
59.图5示出根据本公开的实施例的位置信息处理装置的结构框图。
60.图6示出根据本公开的实施例的电子设备的结构框图。
61.图7示出适于用来实现根据本公开实施例的方法的计算机系统的结构示意图。
具体实施方式
62.下文中，将参考附图详细描述本公开的示例性实施例，以使本领域技术人员可容易地实现它们。此外，为了清楚起见，在附图中省略了与描述示例性实施例无关的部分。
63.在本公开中，应理解，诸如“包括”或“具有”等的术语旨在指示本说明书中所公开的特征、数字、步骤、行为、部件、部分或其组合的存在，并且不欲排除一个或多个其他特征、数字、步骤、行为、部件、部分或其组合存在或被添加的可能性。
64.另外还需要说明的是，在不冲突的情况下，本公开中的实施例及实施例中的特征可以相互组合。下面将参考附图并结合实施例来详细说明本公开。
65.在本公开中，对用户信息或用户数据的获取均为经用户授权、确认，或由用户主动选择的操作。
66.如上所述，lbs利用各类型的定位技术来获取电子设备当前的所在位置，以便通过移动互联网向电子设备提供信息资源和其他服务。在很多lbs应用中，当获取到汽车、船舶等交通工具的位置信息时，需要知道交通工具位于哪个大区域内，例如汽车行驶于哪个省市，船舶停留于哪个岛屿的泊位。一个比较快速的办法是预计算好所有大区域内部的所有geohash值存储进数据库。geohash是一种地址编码方法，它能够把二维的空间经纬度数据编码成一个字符串。geohash用一个字符串表示经度和纬度两个坐标，其表示的并不是一个点，而是一个区域。换言之，每个geohash编码可以对应于一个geohash区块，该区块中包含多个地理位置点。
67.当地理区域形状不规则，边界顶点较多时，确定该地理区域内的geohash区块的计算复杂度会很高，当需要处理的地理区域较多时，计算效率会非常低下。
68.本公开提供了一种位置信息处理方法，包括：获取指定地理区域边界顶点的位置信息；根据所述指定地理区域边界顶点的位置信息，将所述指定地理区域划分为多个子区域；根据所述子区域边界顶点的位置信息，确定多个区块；根据所述区块与所述子区域的位置关系，确定所述区块与所述指定地理区域的位置关系。
69.根据本公开的实施例，将指定地理区域划分为多个子区域，分别确定区块与子区域的位置关系，进而确定区块与指定地理区域的位置关系，由于子区域的边界顶点数量远小于指定区域，显著降低了计算复杂度，提高了计算效率。
70.图1示出根据本公开的实施例的位置信息处理方法的流程图。如图1所示，所述位置信息处理方法包括以下步骤s101-s104：
71.在步骤s101中，获取指定地理区域边界顶点的位置信息；
72.在步骤s102中，根据所述指定地理区域边界顶点的位置信息，将所述指定地理区域划分为多个子区域；
73.在步骤s103中，根据所述子区域边界顶点的位置信息，确定多个区块；
74.在步骤s104中，根据所述区块与所述子区域的位置关系，确定所述区块与所述指定地理区域的位置关系。
75.根据本公开的实施例，指定地理区域可以是感兴趣的任意地理区域，例如岛屿、省、市、县、区，等等。指定地理区域的边界可以构成规则或不规则的多边形，所述边界可以具有多个顶点，根据指定地理区域边界顶点的位置信息，可以将指定地理区域划分为多个子区域。所述子区域的边界顶点数量少于所述指定区域的边界顶点数量，所述多个子区域的全集构成所述指定地理区域，所述多个子区域之间没有交集。
76.在确定所述多个子区域之后，可以确定全部位于所述子区域内部、或部分位于所述子区域内部(称为“与子区域相交”)、或位于所述子区域周围的多个区块，并确定所述区块与所述子区域的位置关系。由于所述子区域的边界顶点数量少于所述指定区域的边界顶点数量，因此子区域的大小和形状复杂度均低于指定区域，因此，确定上述区块与子区域的位置关系的计算复杂度相比于直接计算区块与指定地理区域的位置关系的计算复杂度显著降低，效率明显提升。
77.由于子区域是指定区域的一部分，因此，如果任一区块全部或部分位于子区域内，则该区块必然全部或部分位于所述指定区域内。另一方面，如果任一区块既不位于任一子区域内部也不与任一子区域相交，则认为该区块位于任一子区域外部，因此，该区块也位于指定区域外部。
78.根据本公开的实施例，所述根据所述指定地理区域边界顶点的位置信息，将所述指定地理区域划分为多个子区域，包括：根据所述指定地理区域边界顶点的位置信息，使用耳切法将所述指定地理区域划分为多个三角形子区域。
79.耳切法(ear clipping)在计算机图形学领域中，是将简单多边形转换成一组三角形集合的经典算法。简单多边形的耳朵，是指由连续顶点v0，v1，v2组成的内部不包含其他任意顶点的三角形。在计算机几何术语中，v0与v2之间的连线称之为多边形的对角线，点v1称之为耳尖。
80.耳切法的计算复杂度位o(n2),以下为其算法步骤:
81.1)将多边形使用双向链表存储，这样可以快速的移除耳朵。列表的构建复杂度是o(n)；
82.2)遍历顶点寻找耳朵。对于每一个顶点vi和围绕该顶点的三角形＜v
i-1
，vi，v
i+1
＞，测试其他顶点是否在当前三角形中，如果有一个顶点在三角形里面，则不是耳朵，只有没有顶点在当前三角形中时，才算是找到一个耳朵。一旦凸顶点和耳朵的链表构建成功，每次遍历都会移除一个耳朵。假设当前vi是个耳朵并且被移除掉，那么边结构的相邻点v
i-1
,v
i+1
则会发生变化，如果相邻点是凸顶点，那么依旧保持凸点，如果相邻点是个耳朵，那么当vi被移除后则不一定能保持耳朵的状态，如果相邻点是个凹点，那么它有可能变为一个凸点甚至是耳朵。因此当移除顶点vi后，如果相邻点是凸点，则必须遍历相关顶点，通过遍历查看是否包含其他点，来测试它是否是一个耳朵。
83.如果有n个耳朵，则每一次更新都会触发一个耳朵检测，每次过程中更新o(n)，所以移除耳朵的进程的复杂度是o(n2)。
84.通过耳切法，可以将指定区域分割为多个三角形子区域。
85.由于指定区域的边界可能非常不规则，因此，在进行耳切法之前，可以先将指定区域的边界简化，即减少其顶点数量。
86.根据本公开的实施例，所述根据所述指定地理区域边界顶点的位置信息，使用耳切法将所述指定地理区域划分为多个三角形子区域，包括：根据所述指定地理区域边界顶点的位置信息，使用d-p算法删除所述指定地理区域边界顶点；根据未删除的所述指定地理区域边界顶点的位置信息，得到精简的指定地理区域，使用耳切法将所述精简的指定地理区域划分为多个三角形子区域。
87.根据本公开的实施例，当指定地理区域的边界点较多时，如在一些省市的边界会出现较顶点较为密集的齿轮形的边界线。对边界数据进行压缩，能有效地提取出边界的特征点，幅度的减少无效顶点，简化算法计算复杂度。
88.douglas-peucker算法(简称d-p算法)考虑到了空间距离，被广泛应用于制图学和计算机图形学，被许多制图员认为是最精确的直线泛化算法之一。
89.图2示出了d-p算法的原理。
90.在指定曲线首尾的两点(分别称为锚点a1、漂浮点an)之间虚连一条直线，求出指定曲线上其余各点到该直线的投影距离，选其最大者与阀值相比较，若大于阀值，则离该直线投影距离最大的点保留作为分裂点an-p,否则将直线两端点间各点全部舍去。依据所保留的分裂点an-p，将指定曲线分成两部分(锚点a1到漂浮点/锚点an-p、漂浮点/锚点an-p到漂浮点an)处理，重复上述计算。在锚点a1到漂浮点/锚点an-p部分保留分裂点an-p-q，在漂浮点/锚点an-p到漂浮点an部分舍弃两端点之前的所有各点。
91.然后，根据保留的分裂点an-p-q，将锚点a1到漂浮点/锚点an-p部分分为两部分(锚点a1到漂浮点/锚点an-p-q、漂浮点/锚点an-p-q到漂浮点/锚点an-p-q)，重复上述操作。
92.假设指定地理区域有100个顶点，则可以将这100个顶点分为10组，每组包含相邻的10个顶点，针对每组分别执行d-p算法以压缩顶点数量，最后将经过d-p压缩后的10组顶点中未删除的顶点相连，得到精简的指定地理区域，再通过耳切法根据未删除的所述指定地理区域边界顶点的位置信息，得到精简的指定地理区域，使用耳切法将所述精简的指定地理区域划分为多个三角形子区域。
93.根据本公开的实施例，所述根据所述子区域边界顶点的位置信息，确定多个区块，包括：根据所述子区域边界顶点的位置信息确定所述子区域的外包矩形；根据所述外部矩形顶点的位置信息，确定所述多个区块，所述多个区块中的任一区块全部或部分位于所述外包矩形内。
94.图3a示出了根据本公开实施例，根据所述子区域边界顶点的位置信息确定多个区块的示意图。
95.如图3a所示，三角形为任一子区域的示例。由实线包围的矩形是子区域的外包矩形。虚线包围的正方形区域是区块，任一区块全部或部分位于所述外包矩形内。图3中总共示出了9*6＝54个区块。
96.根据本公开的实施例，可以根据实际需要进行区块划分，例如，每个所述区块是一个geohash编码区域。
97.根据本公开的实施例，所述根据所述区块与所述子区域的位置关系，确定所述区
块与所述指定地理区域的位置关系，包括：获取以所述区块的顶点为顶点并且经过所述子区域内的一点的射线与所述子区域的边界的交点数量；根据所述交点数量确定所述区块与所述指定地理区域的位置关系。
98.根据本公开的实施例，所述根据所述交点数量确定所述区块与所述指定地理区域的位置关系，包括：根据所述以所述区块的顶点为顶点并且经过所述子区域内的一点的射线与所述子区域的边界的交点数量，确定所述区块是否至少部分位于所述子区域内；如果所述区块至少部分位于所述子区域内，则所述区块至少部分位于所述指定地理区域内。
99.图3b示出了根据本公开实施例，根据区块与子区域的位置关系确定区块与指定地理区域的位置关系的原理示意图。
100.如图3b所示，p1是子区域内的一点。以区块b1的顶点q1为顶点且经过p1的射线与子区域的边界交点数量为两个，因此q1位于子区域外部。以此方式可以依次确定区块b1的四个顶点均位于子区域外部，因此，区块b1位于子区域外部。
101.类似地，可以确定区块b2和b3的顶点q2位于子区域内部。具体地，以顶点q2为顶点且经过p1的射线与子区域的边界交点数量为一个，因此q2位于子区域内部。对于任一区块而言，只要其有一个顶点位于子区域内部，则该区域至少部分位于所述子区域内。因此，区块b2和b3至少部分位于该子区域内，相应地，区块b2和b3至少部分位于指定地理区域内。
102.根据本公开的实施例，位于某个区域内，包括位于该区域的边界上的情况。
103.如果某个区块位于指定地理区域的所有子区域的外部，则该区块位于指定地理区域的外部。
104.根据本公开的实施例，针对所述多个子区域，并行地执行所确定所述区块与所述指定地理区域的位置关系的操作。
105.在将指定地理区域划分为多个子区域之后，可以针对多个子区域并行地执行所确定所述区块与所述指定地理区域的位置关系的操作。例如，可以使用mapreduce框架执行该操作。
106.mapreduce是一个并行计算与运行软件框架，它提供了一个庞大但设计精良的并行计算软件框架，能自动完成计算任务的并行化处理，自动划分计算数据和计算任务，在集群节点上自动分配和执行任务以及收集计算结果，将数据分布存储、数据通信、容错处理等并行计算涉及到的很多系统底层的复杂细节交由系统负责处理。
107.根据本公开的实施例，将使用耳切法切割出的多个三角形子区域作为输入，使用mapreduce框架进行并行化求解根据各三角形子区域确定的相应区块与指定地理区域的位置关系，将最后计算出的所有区块与指定地理区域的位置关系进行汇总去重，即得到最终的结果。所述最终结果显示了各个区块与所述指定地理区域的位置关系，例如任一区块至少部分位于该指定地理区域内部或位于该指定地理区域外部。
108.图4示出了根据本公开实施例进行位置信息处理的流程图。
109.如图4所示，首先获取指定地理区域边界顶点的位置信息，然后使用d-p算法对指定地理区域的边界形状进行精简，接下来，使用耳切法将精简的指定地理区域划分为多个三角形子区域。将使用耳切法切割出的多个三角形子区域作为输入，使用mapreduce框架进行并行化求解根据各三角形子区域确定的相应区块与指定地理区域的位置关系，将最后计算出的所有区块与指定地理区域的位置关系进行汇总去重，即得到最终的结果。
110.根据本公开的实施例，将形状复杂的指定地理区域划分为形状简单的子区域后进行并行处理，在显著减少计算复杂度的同时提高了计算效率。
111.图5示出根据本公开的实施例的位置信息处理装置的结构框图。其中，该装置可以通过软件、硬件或者两者的结合实现成为电子设备的部分或者全部。
112.如图5所示，所述位置信息处理装置500包括获取模块510、划分模块520、第一确定模块530、第二确定模块540。
113.获取模块510被配置为获取指定地理区域边界顶点的位置信息；
114.划分模块520被配置为根据所述指定地理区域边界顶点的位置信息，将所述指定地理区域划分为多个子区域；
115.第一确定模块530被配置为根据所述子区域边界顶点的位置信息，确定多个区块；
116.第二确定模块540被配置为根据所述区块与所述子区域的位置关系，确定所述区块与所述指定地理区域的位置关系。
117.根据本公开的实施例，所述根据所述指定地理区域边界顶点的位置信息，将所述指定地理区域划分为多个子区域，包括：
118.根据所述指定地理区域边界顶点的位置信息，使用耳切法将所述指定地理区域划分为多个三角形子区域。
119.根据本公开的实施例，所述根据所述指定地理区域边界顶点的位置信息，使用耳切法将所述指定地理区域划分为多个三角形子区域，包括：
120.根据所述指定地理区域边界顶点的位置信息，使用d-p算法删除所述指定地理区域边界顶点；
121.根据未删除的所述指定地理区域边界顶点的位置信息，得到精简的指定地理区域，使用耳切法将所述精简的指定地理区域划分为多个三角形子区域。
122.根据本公开的实施例，所述根据所述子区域边界顶点的位置信息，确定多个区块，包括：
123.根据所述子区域边界顶点的位置信息确定所述子区域的外包矩形；
124.根据所述外部矩形顶点的位置信息，确定所述多个区块，所述多个区块中的任一区块全部或部分位于所述外包矩形内。
125.根据本公开的实施例，每个所述区块是一个geohash编码区域。
126.根据本公开的实施例，所述根据所述区块与所述子区域的位置关系，确定所述区块与所述指定地理区域的位置关系，包括：
127.获取以所述区块的顶点为顶点并且经过所述子区域内的一点的射线与所述子区域的边界的交点数量；
128.根据所述交点数量确定所述区块与所述指定地理区域的位置关系。
129.根据本公开的实施例，所述根据所述交点数量确定所述区块与所述指定地理区域的位置关系，包括：
130.根据所述以所述区块的顶点为顶点并且经过所述子区域内的一点的射线与所述子区域的边界的交点数量，确定所述区块是否至少部分位于所述子区域内；
131.如果所述区块至少部分位于所述子区域内，则所述区块至少部分位于所述指定地理区域内。
132.根据本公开的实施例，针对所述多个子区域，并行地执行所述确定所述区块与所述指定地理区域的位置关系的操作。
133.本公开还公开了一种电子设备，图6示出根据本公开的实施例的电子设备的结构框图。
134.如图6所示，所述电子设备600包括存储器601和处理器602，其中，存储器601用于存储一条或多条计算机指令，其中，所述一条或多条计算机指令被所述处理器602执行以实现根据本公开的实施例的方法。
135.本公开实施例提供了一种位置信息处理方法，包括：
136.获取指定地理区域边界顶点的位置信息；
137.根据所述指定地理区域边界顶点的位置信息，将所述指定地理区域划分为多个子区域；
138.根据所述子区域边界顶点的位置信息，确定多个区块；
139.根据所述区块与所述子区域的位置关系，确定所述区块与所述指定地理区域的位置关系。
140.根据本公开的实施例，所述根据所述指定地理区域边界顶点的位置信息，将所述指定地理区域划分为多个子区域，包括：
141.根据所述指定地理区域边界顶点的位置信息，使用耳切法将所述指定地理区域划分为多个三角形子区域。
142.根据本公开的实施例，所述根据所述指定地理区域边界顶点的位置信息，使用耳切法将所述指定地理区域划分为多个三角形子区域，包括：
143.根据所述指定地理区域边界顶点的位置信息，使用d-p算法删除所述指定地理区域边界顶点；
144.根据未删除的所述指定地理区域边界顶点的位置信息，得到精简的指定地理区域，使用耳切法将所述精简的指定地理区域划分为多个三角形子区域。
145.根据本公开的实施例，所述根据所述子区域边界顶点的位置信息，确定多个区块，包括：
146.根据所述子区域边界顶点的位置信息确定所述子区域的外包矩形；
147.根据所述外部矩形顶点的位置信息，确定所述多个区块，所述多个区块中的任一区块全部或部分位于所述外包矩形内。
148.根据本公开的实施例，每个所述区块是一个geohash编码区域。
149.根据本公开的实施例，所述根据所述区块与所述子区域的位置关系，确定所述区块与所述指定地理区域的位置关系，包括：
150.获取以所述区块的顶点为顶点并且经过所述子区域内的一点的射线与所述子区域的边界的交点数量；
151.根据所述交点数量确定所述区块与所述指定地理区域的位置关系。
152.根据本公开的实施例，所述根据所述交点数量确定所述区块与所述指定地理区域的位置关系，包括：
153.根据所述以所述区块的顶点为顶点并且经过所述子区域内的一点的射线与所述子区域的边界的交点数量，确定所述区块是否至少部分位于所述子区域内；
154.如果所述区块至少部分位于所述子区域内，则所述区块至少部分位于所述指定地理区域内。
155.根据本公开的实施例，针对所述多个子区域，并行地执行所述确定所述区块与所述指定地理区域的位置关系的操作。
156.图7示出适于用来实现根据本公开实施例的方法的计算机系统的结构示意图。
157.如图7所示，计算机系统700包括处理单元701，其可以根据存储在只读存储器(rom)702中的程序或者从存储部分708加载到随机访问存储器(ram)703中的程序而执行上述实施例中的各种处理。在ram 703中，还存储有系统700操作所需的各种程序和数据。处理单元701、rom 702以及ram 703通过总线704彼此相连。输入/输出(i/o)接口705也连接至总线704。
158.以下部件连接至i/o接口705：包括键盘、鼠标等的输入部分706；包括诸如阴极射线管(crt)、液晶显示器(lcd)等以及扬声器等的输出部分707；包括硬盘等的存储部分708；以及包括诸如lan卡、调制解调器等的网络接口卡的通信部分709。通信部分709经由诸如因特网的网络执行通信处理。驱动器710也根据需要连接至i/o接口705。可拆卸介质711，诸如磁盘、光盘、磁光盘、半导体存储器等等，根据需要安装在驱动器710上，以便于从其上读出的计算机程序根据需要被安装入存储部分708。其中，所述处理单元701可实现为cpu、gpu、tpu、fpga、npu等处理单元。
159.特别地，根据本公开的实施例，上文描述的方法可以被实现为计算机软件程序。例如，本公开的实施例包括一种计算机程序产品，其包括计算机指令，该计算机指令被处理器执行时实现上文所述的方法步骤。在这样的实施例中，该计算机程序产品可以通过通信部分709从网络上被下载和安装，和/或从可拆卸介质711被安装。
160.附图中的流程图和框图，图示了按照本公开各种实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段或代码的一部分，所述模块、程序段或代码的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个接连地表示的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或操作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。
161.描述于本公开实施例中所涉及到的单元或模块可以通过软件的方式实现，也可以通过可编程硬件的方式来实现。所描述的单元或模块也可以设置在处理器中，这些单元或模块的名称在某种情况下并不构成对该单元或模块本身的限定。
162.作为另一方面，本公开还提供了一种计算机可读存储介质，该计算机可读存储介质可以是上述实施例中电子设备或计算机系统中所包含的计算机可读存储介质；也可以是单独存在，未装配入设备中的计算机可读存储介质。计算机可读存储介质存储有一个或者一个以上程序，所述程序被一个或者一个以上的处理器用来执行描述于本公开的方法。
163.以上描述仅为本公开的较佳实施例以及对所运用技术原理的说明。本领域技术人员应当理解，本公开中所涉及的发明范围，并不限于上述技术特征的特定组合而成的技术
方案，同时也应涵盖在不脱离所述发明构思的情况下，由上述技术特征或其等同特征进行任意组合而形成的其它技术方案。例如上述特征与本公开中公开的(但不限于)具有类似功能的技术特征进行互相替换而形成的技术方案。
技术特征：1.一种位置信息处理方法，包括：获取指定地理区域边界顶点的位置信息；根据所述指定地理区域边界顶点的位置信息，将所述指定地理区域划分为多个子区域；根据所述子区域边界顶点的位置信息，确定多个区块；根据所述区块与所述子区域的位置关系，确定所述区块与所述指定地理区域的位置关系。2.根据权利要求1所述的方法，其中，所述根据所述指定地理区域边界顶点的位置信息，将所述指定地理区域划分为多个子区域，包括：根据所述指定地理区域边界顶点的位置信息，使用耳切法将所述指定地理区域划分为多个三角形子区域。3.根据权利要求2所述的方法，其中，所述根据所述指定地理区域边界顶点的位置信息，使用耳切法将所述指定地理区域划分为多个三角形子区域，包括：根据所述指定地理区域边界顶点的位置信息，使用d-p算法删除所述指定地理区域边界顶点；根据未删除的所述指定地理区域边界顶点的位置信息，得到精简的指定地理区域，使用耳切法将所述精简的指定地理区域划分为多个三角形子区域。4.根据权利要求1所述的方法，其中，所述根据所述子区域边界顶点的位置信息，确定多个区块，包括：根据所述子区域边界顶点的位置信息确定所述子区域的外包矩形；根据所述外部矩形顶点的位置信息，确定所述多个区块，所述多个区块中的任一区块全部或部分位于所述外包矩形内。5.根据权利要求4所述的方法，其中，每个所述区块是一个geohash编码区域。6.根据权利要求1所述的方法，其中，所述根据所述区块与所述子区域的位置关系，确定所述区块与所述指定地理区域的位置关系，包括：获取以所述区块的顶点为顶点并且经过所述子区域内的一点的射线与所述子区域的边界的交点数量；根据所述交点数量确定所述区块与所述指定地理区域的位置关系。7.根据权利要求6所述的方法，其中，所述根据所述交点数量确定所述区块与所述指定地理区域的位置关系，包括：根据所述以所述区块的顶点为顶点并且经过所述子区域内的一点的射线与所述子区域的边界的交点数量，确定所述区块是否至少部分位于所述子区域内；如果所述区块至少部分位于所述子区域内，则所述区块至少部分位于所述指定地理区域内。8.根据权利要求1所述的方法，其中，针对所述多个子区域，并行地执行所述确定所述区块与所述指定地理区域的位置关系的操作。9.一种位置信息处理装置，包括：获取模块，被配置为获取指定地理区域边界顶点的位置信息；划分模块，被配置为根据所述指定地理区域边界顶点的位置信息，将所述指定地理区
域划分为多个子区域；第一确定模块，被配置为根据所述子区域边界顶点的位置信息，确定多个区块；第二确定模块，被配置为根据所述区块与所述子区域的位置关系，确定所述区块与所述指定地理区域的位置关系。10.一种电子设备，包括存储器和处理器；其中，所述存储器用于存储一条或多条计算机指令，其中，所述一条或多条计算机指令被所述处理器执行以实现权利要求1～8任一项所述的方法步骤。11.一种可读存储介质，其上存储有计算机指令，该计算机指令被处理器执行时实现权利要求1～8任一项所述的方法步骤。12.一种计算机程序产品，包括计算机指令，该计算机指令被处理器执行时实现权利要求1～8任一项所述的方法步骤。
技术总结本公开实施例公开了一种位置信息处理方法、装置、电子设备、介质及程序产品。所述位置信息处理方法，包括：获取指定地理区域边界顶点的位置信息；根据所述指定地理区域边界顶点的位置信息，将所述指定地理区域划分为多个子区域；根据所述子区域边界顶点的位置信息，确定多个区块；根据所述区块与所述子区域的位置关系，确定所述区块与所述指定地理区域的位置关系。关系。关系。
技术研发人员：柯有华
受保护的技术使用者：阿里云计算有限公司
技术研发日：2022.01.30
技术公布日：2022/7/5
