基于道路网眼层次结构划分的POI简化并行计算方法

摘要

本发明公开了一种基于道路网眼层次结构划分的POI简化并行计算方法，以提高POI简化计算的效率。首先构建道路层次结构与网眼初始区域，按照道路的等级依次划分网眼区域，建立道路网眼的层次结构，在此基础上，使用道路网眼对POI空间分割，将海量的POI划分到一个一个道路网眼中，降低问题求解的复杂度；按照计算节点的数目与道路网眼的层次结构，划分POI数据，将数据分配到计算节点上，进而对POI进行并行简化。本发明采用道路网眼来划分POI数据，将道路网对POI的影响考虑到其数据划分过程中，可以更好的保持简化后POI的专题信息与拓扑信息。

说明书

技术领域

本发明涉及一种矢量数据划分方法，可以实现对POI(Points of Interest)数据进行高效的划分，技术应用领域为POI简化并行计算。

背景技术

POI，兴趣点，涵盖了餐饮、娱乐、金融机构、旅游景点、地标建筑、加油站、停车场等人们日常生活中最为经常的基础信息，POI数据的准确性，属性的丰富程度、表达的清晰度及其实时显示效率都将影响移动地图的质量与可用性。但当前POI表达存在许多问题，特别是在用户搜索特定信息时，由于查询结果数据量较大，会造成POI的重叠、压盖等，进而影响用户对地理空间的认知，降低地图的可用性。

地图综合是解决该问题的一个可行方案，但是目前针对POI综合的算子、算法还较少，而点要素综合研究已开展了几十年，已有许多成熟算法，可借鉴点综合的方法来处理POI数据。点的简化算子是基于点的空间属性从原始点集中选择子集，可以较好的保持POI的专题信息与拓扑信息，适合用于解决当前POI表达存在的问题。但现有的简化算法效率普遍不高，不能满足海量POI实时表达的需求。将这些算法与高性能计算技术结合，提高算法执行的效率，将为该问题的解决提供一种可行的技术方案。

发明内容

本发明的目的是提供一种道路网眼层次结构约束下的POI数据划分方法，以提高POI简化计算的效率。首先构建道路层次结构与网眼初始区域，按照道路的等级依次划分网眼区域，建立道路网眼的层次结构，在此基础上，使用道路网眼对POI空间分割，将海量的POI划分到一个一个道路网眼中，降低问题求解的复杂度。按照计算节点的数目与道路网眼的层次结构，划分POI数据，将数据分配到计算节点上，进而对POI进行并行简化，提高POI简化计算的效率。

本发明的技术解决方案为：基于道路网眼层次结构划分的POI简化并行计算方法，其所用的基本变量如表1所示。

表1基于道路网眼层次结构分解算法变量描述

本发明的步骤如下：

(1)根据数据特征与集群可用节点数目，计算划分过程中所用的变量：N、K、N_A、N_D、N_U。

(2)道路网眼层次结构构建，道路网层次网眼的构建就是对道路网所在区域进行区域的层次划分，道路的重要性等级将影响分割过程与结果，高级别的道路首先对区域进行粗分，低等级道路在粗分的基础上进一步对区域进行分割，由于道路重要性等级的差异，使得封闭区域具有层次特征，这样的封闭区域就是道路网眼。包含两个基本步骤：a)构建最大封闭区域边界，针对POI数据划分的道路网眼层次结构中最大封闭区域即是最初的网眼，其与传统的道路网眼层次结构不同，该最大封闭区域为POI数据的最小外接矩形；b)依次选取等级、长度、连通度最高的道路，对网眼进行分割，逐步构建网眼层次结构。

(3)道路网眼与POI数据匹配。遍历道路网眼与POI数据，判断POI与道路网眼的空间关系，如果道路网眼包含POI，则将该POI加入到当前道路网眼的POI集合中，计算每个网眼中POI的数目。

(4)从最底层网眼开始划分计算，设当前网眼的序号为i，其包含的点数为Ni，如果Ni＜N_D，执行步骤5；如果Ni＞N_U，执行步骤6；如果N_D＜Ni，且Ni≤N_U，执行步骤7。

(5)将其相邻网眼加入当前划分区域，继续执行步骤4，直到网眼i的所有兄弟网眼都参与划分，如果此时Ni＜N_D，则将当前网眼i及其兄弟节点合并到其父节点的兄弟节点中，并将这些网眼作为独立的划分单元，再从其新的兄弟节点开始，按照步骤4继续划分直到所有网眼都被划分。

(6)将最后加入的网眼节点分解，如果当前网眼由其本身数据和其它网眼数据点组成，那么在分解时，分解其本身包含的数据，而不分解其他网眼数据，通过分解网眼，使得当前分配数据块i的节点数目Ni＝N_A，将其分配给一个计算节点，然后从被分解的网眼的剩余部分开始继续执行步骤4。

(7)将上述符合划分要求的网眼打包为一个数据块，转到步骤4继续执行，直到当前所有网眼都被分配，结束划分过程。

(8)按照已知的节点数目，创建一定的线程数目，将划分后的数据，依次分配给各个线程。

(9)并行简化POI，返回结果。

本发明较之现有技术有以下优点：

(1)目前的POI综合都是从单要素的角度出发，只对POI简化，不考虑其它要素对POI的影响，本发明将道路网对POI的影响考虑到其数据划分过程中，可以更好的保持简化后POI的专题信息与拓扑信息。

(2)传统的数据划分方法未考虑到简化算法的特征，需要进程、线程之间的协作，本发明采用道路网眼来划分POI数据。路网天然地将地图分为不同的区域，而POI都在路网的某一网眼中，网眼之间的POI被道路隔绝，其在空间与语义上都相互独立，降低了问题的求解空间，并以网眼为计算单元，减少了节点间的通信，提高了POI简化计算的效率。

附图说明

图1为本发明的基本流程图。

图2为使用本发明对某地区POI划分的结果图，其中图(a)为原始数据图，图(b)为2节点划分结果图，图(c)为4节点划分结果图，图(d)为6节点划分结果图，图(e)为8节点划分结果图。

图3为使用本发明与未使用本发明算法执行效率的对比图。

具体实施方式

结合图1所示的流程图，以4个计算节点为例，对某地区的道路网与POI数据进行划分、以及并行简化计算(其中道路数据包含69条道路，POI数据包含12006个点)，说明本发明的具体实施方法：

1、主线程读取道路与POI数据，计算各个数据划分各个参数N，K，N_A，N_U，N_D，N＝12006，K＝4，N_A＝3001，N_U＝2801，N_D＝3201。

2、主线程计算POI的最小外接矩形框，初始化道路数据，根据道路的等级、长度、连通度构建道路层次结构数据结构为Road＜道路ID，道路层次ID，Box＞，计算道路的最小外接矩形框，该最小外接矩形就是最初的网眼，其数据结构为Cell＜ID，POISet，PointSet，Box，POISum＞，其中POISet为其所含POI集合，PointSet为构成其本身的点集合，Box为最小外接矩形框，POISum为包含POI的总数目。

3、从级别最高的道路层次开始，依次使用道路Road对当前所有网眼进行划分，先计算道路的最小外接矩形框与网眼最小外接矩形框的空间关系，如果它们相交则继续计算道路与网眼的空间关系，计算其交点，根据其交点位置，计算划分后网眼的PointSet与Box，逐步建立道路网眼的层次结构。

4、从道路网眼最左侧的叶子节点开始，依次计算叶子节点与POI数据的关系，建立POI与网眼的空间关联关系，如果POI被该网眼包含就将该点加入到网眼的POISet集合中，计算各个网眼中POI的总数POISum。

5、主线程根据当前的节点数目，从道路网眼最左侧的叶子节点开始，判断网眼POISum与N_A，N_U，N_D的关系，如果小于N_U则就使用符合该情况的数据分配策略；如果大于N_U，而且小于N_D就使用分配策略，将这些数据打包分配到一个数据块(数据块的结构体为Block＜CellsSet，POINum，POISet＞)；如果大于N_D就使用拆分的分配策略，将特定的节点划分为两个节点，直到所有网眼都被分配。下面就某些特殊情况进行说明，假设当前节点i的数据量为3000，则直接将其分配给一个节点，继续对未分配的节点进行划分，如果加入节点j后数据量超出了划分上限，优先将j分为两个子集，其中一个子集划分到当前节点，另一个子集划分到另外一个节点。

在主线程中创建4个子线程，依次将Block[0]、Block[1]、Block[2]、Block[3]分配给这4个线程，各个线程依次处理Block，对数据块中的POISet进行简化，直到所有线程都处理完成，将Block中的POISet返回给主线程，完成计算。

图2为数据划分实验结果图，图中设定K为2、4、6、8的结果，给出了每个道路网眼所属于的节点号，分析了其负载均衡，如表2所示，分析可知划分结果满足了负载均衡的要求。

表2道路网眼层次结构划分结果统计表

图3给出了使用该数据划分方式的“圆”增长算法的执行，效率由图可知其加速比随着节点数目的增加而增加，并达到了超线性的增加，说明该方法可大大提高算法的执行效率。