本发明公开了一种基于优先队列的客户端自适应地图矢量线简化方法及系统。本发明针对现有基于线简化的轨迹压缩方法依赖于人工设置的距离阈值，并且无法提前确定轨迹的压缩率的问题，通过使用优先队列来选择特征点，并且在算法运行过程中不断判断是否达到目标压缩率，减小了为达到目标压缩率而使用不同距离阈值重复压缩过程导致的不必要的计算开销。
1.基于优先队列的客户端自适应地图矢量线简化方法，其特征在于该方法的具体步骤是：步骤(1).输入矢量线集合polylines、地图比例尺scale、地图中心点经纬度(lon,lat)、客户端屏幕宽度方向上像素点width、客户端屏幕高度方向上像素点高height、客户端计算速度s、客户端可接受延迟时间t；
步骤(2).计算地图分辨率resolution，用于表示客户端屏幕上每个像素在实际地图上对应的实际地面距离；
步骤(4).计算矢量线简化比例ratio，包括以下步骤：步骤(4.1).计算矢量线集合polylines在地图显示区域内部分的数据大小m；
步骤(4.2).根据客户端可接受延迟时间t与客户端计算能力s计算出预期矢量线数据简化后的大小m′，从而得到矢量线简化比例ratio＝m′/m；
步骤(5).初始化优先队列Q；优先队列的底层数据结构为大顶堆，队列节点包含两个属性，分别为一个矢量线片段与该片段的分割点；所述分割点为矢量线片段上距离首尾位置点连线垂直距离最大的位置点；节点的优先级即为分割点距离其所属片段首尾连线的垂直距离；
步骤(6).取首尾位置点为特征点，判断特征点个数与位置点总个数比例是否达到目标简化比例ratio；若达到，则结束；所有特征点组成的矢量线为简化后的结果；否则执行步骤(7)；
步骤(7).取出优先队列头节点，在该节点的分割点处将矢量线片段划分为两段，同时将分割点标记为特征点；
将新构造出的两个优先队列节点加入优先队列，完成后返回至步骤(6)继续构建新的节点。
2.根据权利要求1所述的基于优先队列的客户端自适应地图矢量线简化方法，其特征在于：所述地图分辨率的计算如下：resolution＝0.0254/(sacle*96)；
其中，0.0254代表米与英寸之间的单位转换，即一英寸等于0.0254米，sacle代表地图分辨率与比例尺之间的关系。
3.根据权利要求1所述的基于优先队列的客户端自适应地图矢量线简化方法，其特征在于：所述的步骤(3)具体是：步骤(3.1).计算地图显示区域的东西方向距离x与南北方向距离y；
步骤(3.3).对于地图显示区域，计算客户端屏幕的四个角对应的经纬度点。
4.根据权利要求3所述的基于优先队列的客户端自适应地图矢量线简化方法，其特征在于：所述的步骤(3.2)具体是：利用步骤(1)中输入的地图中心点经纬度(lon,lat)和步骤(3.1)计算的地图显示区域的宽度x和高度y分别计算东西方向的最大经纬度点和最小经纬度点；以及南北方向上的最大经纬度点和最小经纬度点。
5.基于优先队列的客户端自适应地图矢量线简化系统，其特征在于，包括：数据输入模块，用于输入矢量线集合polylines、地图比例尺scale、地图中心点经纬度(lon,lat)、客户端屏幕宽度方向上像素点width、客户端屏幕高度方向上像素点高height、客户端计算速度s、客户端可接受延迟时间t；
地图分辨率resolution计算模块，用于计算地图分辨率resolution；
显示区域范围计算模块，用于计算客户端屏幕显示的区域范围；
矢量线简化比例ratio计算模块，用于计算矢量线简化比例ratio；
判断模块，用于判断特征点个数与位置点总个数比例是否达到目标简化比例ratio；
调整模块，用于对优先队列进行调整，以便判断模块再次判断；
所述矢量线简化比例ratio计算模块执行以下操作：计算矢量线集合polylines在地图显示区域内部分的数据大小m；
根据客户端可接受延迟时间t与客户端计算能力s计算出预期矢量线数据简化后的大小m′，从而得到矢量线简化比例ratio＝m′/m；
优先队列的底层数据结构设为大顶堆，队列节点设两个属性，分别为一个矢量线片段与该片段的分割点；
所述分割点为矢量线片段上距离首尾位置点连线垂直距离最大的位置点；节点的优先级即为分割点距离其所属片段首尾连线的垂直距离；
取出优先队列头节点，在该节点的分割点处将矢量线片段划分为两段，同时将分割点标记为特征点；
将新构造出的两个优先队列节点加入优先队列，完成后返回至判断模块。
基于优先队列的客户端自适应地图矢量线简化方法及系统
技术领域
[0001] 本发明属于地图数据渲染领域，具体涉及一种基于优先队列的客户端自适应地图矢量线简化方法及系统。
背景技术
[0002] 近年来，在线地图服务发展迅速，人们在日常生活中对于在线地图的使用也愈加频繁。地图数据渲染是在线地图服务的重要组成部分，渲染的速度与质量对用户的使用体验至关重要，地图数据中的覆盖物数据包含大量线类型矢量数据，如公路线路、公交线路、地铁线路等等；此类数据通常占据大量的存储空间，导致客户端的计算开销增大，对客户端的渲染造成很大压力，从而影响用户的体验。
[0003] 线类型的矢量数据通常表示为一组顺序相连的位置点，对位置点按顺序连接即可得到地图上显示的线类型覆盖物。为了加快客户端对线类型矢量数据的渲染速度，许多方法首先采用线简化方法对线类型矢量数据进行简化，减少位置点的个数，从而提高客户端渲染速度，减轻渲染压力。
[0004] 现有矢量线简化算法依赖于人工设置距离阈值，只有当简化过程结束后才能计算出简化比例。现有方法的不足之处在于：没有综合考虑客户端计算能力与用户可接受延迟时间；若距离阈值设置过大，则可能导致简化后的线与原始线差距过大，地图显示不够精细、用户视觉观感不佳；若距离阈值设置过小，则会导致简化后矢量线保留的位置点过多，增大客户端渲染压力，造成较大延迟，影响用户的使用体验。
发明内容
[0005] 本发明针对矢量线简化算法依赖于人工设置距离阈值、且无法综合考虑客户端计算能力与用户可接受延迟时间的问题，提出了一种基于优先队列的客户端自适应地图矢量线简化方法及系统。
[0006] 本发明首先根据屏幕的地图显示范围计算出矢量图形数据大小，再根据客户端计算能力与用户可接受延迟时间计算出矢量线简化比例，简化后的线类型覆盖物能够在用户可接受的延迟时间内渲染完成，最大限度地保证线覆盖物精细度。
[0007] 本发明的一方面提供了一种基于优先队列的客户端自适应地图矢量线简化方法，具体步骤是：
[0008] 步骤(1).输入矢量线集合polylines、地图比例尺scale、地图中心点经纬度(lon,lat)、客户端屏幕宽度方向上像素点width、客户端屏幕高度方向上像素点高height、客户端计算速度s、客户端可接受延迟时间t；
[0009] 步骤(2).计算地图分辨率resolution，用于表示客户端屏幕上每个像素在实际地图上对应的实际地面距离。
[0010] 步骤(3).计算客户端屏幕显示的区域范围；
[0011] 步骤(4).计算矢量线简化比例ratio，包括以下步骤：
[0012] 步骤(4.1).计算矢量线集合polylines在地图显示区域内部分的数据大小m；
[0013] 步骤(4.2).根据客户端可接受延迟时间t与客户端计算能力s计算出预期矢量线数据简化后的大小m′，从而得到矢量线简化比例ratio＝m′/m；
[0014] 步骤(5).初始化优先队列Q；优先队列的底层数据结构为大顶堆，队列节点包含两个属性，分别为一个矢量线片段与该片段的分割点。所述分割点为矢量线片段上距离首尾位置点连线垂直距离最大的位置点。节点的优先级即为分割点距离其所属片段首尾连线的垂直距离。
[0015] 步骤(6).取首尾位置点为特征点，判断特征点个数与位置点总个数比例是否达到目标简化比例ratio；若达到，则结束；所有特征点组成的矢量线为简化后的结果；否则执行步骤(7)；
[0016] 步骤(7).取出优先队列头节点，在该节点的分割点处将矢量线片段划分为两段，同时将分割点标记为特征点；
[0017] 为分割后得到的两段子片段分别构造优先队列节点；
[0018] 将新构造出的两个优先队列节点加入优先队列，完成后返回至步骤(6)继续构建新的节点。
[0019] 本发明的另一方面提供了一种基于优先队列的客户端自适应地图矢量线简化系统，包括：
[0020] 数据输入模块，用于输入矢量线集合polylines、地图比例尺scale、地图中心点经纬度(lon,lat)、客户端屏幕宽度方向上像素点width、客户端屏幕高度方向上像素点高height、客户端计算速度s、客户端可接受延迟时间t；
[0021] 地图分辨率resolution计算模块，用于计算地图分辨率resolution；
[0022] 显示区域范围计算模块，用于计算客户端屏幕显示的区域范围；
[0023] 矢量线简化比例ratio计算模块，用于计算矢量线简化比例ratio；
[0024] 初始化模块，用于初始化优先队列；
[0025] 判断模块，用于判断特征点个数与位置点总个数比例是否达到目标简化比例ratio；
[0026] 调整模块，用于对优先队列进行调整，以便判断模块再次判断。
[0027] 本发明相对于现有技术而言，具有以下有益效果：
[0028] 本针对用户在不同场景下的客户端计算能力和可接受延迟时间，可以以数值的方式在服务请求过程中发送给服务端，服务端实时为用户计算出当前请求的目标简化比例，然后在服务端完成优先队列的构建与矢量线的压缩过程，减少了服务器和客户端网络传输过程中的资源损耗，也避免了客户端进行适量线的二次处理，提升服务效率。最终实现地图矢量线数据的简化。本发明能够在满足用户可接受延迟时间的情况下，最大限度地完成地图上矢量数据的精细渲染。
附图说明
[0029] 图1.本发明方法流程图；
[0030] 图2.轨迹压缩过程示意图。
[0031] 图3.本发明系统结构示意图。
具体实施方式
[0032] 下面将结合附图以及实施例对本发明作进一步说明。
[0033] 为叙述方便，定义相关符号如下：
[0034] 位置点定义为p:(p.lon,p.lat,p.index)：其中p.lon为位置点经度，p.lat为位置点纬度，p.index为位置点索引。
[0035] 矢量线:Tr:p1→p2→p3→…→pn是一组按顺序排列的位置点组成的序列。
[0036] 矢量线片段Trsub:pa→pa+1→pa+2→…→pb,1≤a≤b≤n，为矢量线Tr的子线段。
[0037] 线简化比例ratio：简化后位置点个数与原矢量线位置点个数的比例，即压缩率。
[0038] 存在原始矢量线Tr:p1→p2→p3→…→pn，简化后的矢量线为Tr′:p1′→p′2→p′3→…→p′m。简化过程将原始矢量线上的部分位置点标记为特征点，即简化后的矢量线Tr′上的位置点也是原始矢量线上的位置点。简化比例ratio为位置点个数与原始矢量线位置点个数之比，
[0039] 优先队列Q上的节点Node包含两个属性，分别为一个矢量线片段TrNode与该片段的分割点psplit，其中分割点psplit为矢量线片段TrNode上距离起始位置点pstart与终止位置点pend连线垂直距离最大的位置点。节点的优先级即为分割点距离首尾位置点连线的垂直距离。
[0040] 本实施例提出了一种基于优先队列与客户端计算能力的自适应地图矢量线简化方法，方法的执行过程如图1所示。
[0041] 步骤(1).输入矢量线集合polylines、地图比例尺scale、地图中心点经纬度(lon,lat)、屏幕宽width(像素)、高height(像素)、客户端计算速度s、用户可接受延迟时间t。
[0042] 步骤(2).计算地图分辨率resolution，表示客户端屏幕上每个像素在实际地图上对应的实际地面距离(米)。
[0043] 地图分辨率与比例尺之间的关系如下：scale＝1:(resolution*PPI/0.0254)，经转换得地图分辨率的计算公式：resolution＝0.0254/(sacle*96)。
[0044] 其中，0.0254(m/inch)代表米与英寸之间的单位转换，即一英寸等于0.0254米，PPI代表屏幕上每英寸内像素的数量，默认是96。
[0045] 步骤(3).为了避免渲染用户不可见的矢量线造成的时间损耗，需要计算客户端屏幕显示的区域范围，包括以下步骤：
[0046] 步骤(3.1).计算地图显示区域的东西方向距离x与南北方向距离y，计算公式分别为x＝resolution*width，y＝resolution*height。
[0047] 步骤(3.2).计算地图显示地经纬度范围，利用步骤(1)中输入的地图中心点经纬度(lon,lat)和步骤(3.1)计算的地图显示区域的宽度x和高度y分别计算东西方向和南北方向上的最大经纬度点和最小经纬度点，具体计算过程如下：
[0048] lon′＝lon+d*sinα/[ARC*cos(lat)*2π/360]
[0049] lat′＝lat+d*cosα/(ARC*2′/360)
[0050] 其中α表示方位角，正北方向为0度，ARC表示赤道圆的平均半径，取值为6371.393*1000(米)。(lon′,lat′)表示需要根据已知距离(d表示所求未知点与中心点之间的距离)和中心点经纬度计算得到的未知点的经纬度。
[0051] 步骤(3.3).对于地图显示区域，只需要计算客户端屏幕的四个角对应的经纬度点即可。具体分为两个方向上的计算：
[0052] 在东西方向上，以中心点经纬度(lon,lat)和距离d＝x/2的条件下，分别以α＝90和α＝270代入步骤(3.2)的公式中得到经度边界lonleft和lonright；
[0053] 在南北方向上，以中心点经纬度(lon,lat)和距离d＝y/2的条件下，分别以α＝0和α＝180代入步骤(3.2)的公式中得到纬度边界latup和latdown。
[0054] 步骤(4).计算矢量线简化比例ratio，包括两个步骤：
[0055] 步骤(4.1).计算矢量线集合polylines在地图显示区域内部分的数据大小m，例如对于矢量线Tr:p1→p2→p3→…→pn有两种显示情况：
[0056] 一是整段矢量线都不在渲染的显示区域内，可以将此类矢量线删除。
[0057] 二是矢量线中的部分位置点不在显示区域内，即位置点的经纬度超出了步骤(3.3)计算的显示区域边界时，将超出区域的位置点删除，只保留矢量线的在显示区域内的部分。
[0058] 步骤(4.2).根据用户可接受延迟时间t与客户端计算能力s计算出预期矢量线数据简化后的大小m′，计算公式为：m′＝t*s。
[0059] 最后计算矢量线简化比例ratio＝m′/m。
[0060] 步骤(5).初始化优先队列Q；优先队列的底层数据结构为大顶堆，队列节点包含两个属性，分别为一个矢量线片段与该片段的分割点。分割点为矢量线片段上距离首尾位置点连线垂直距离最大的位置点。节点的优先级即为分割点距离其所属片段首尾连线的垂直距离。
[0061] 步骤(6).取首尾位置点为特征点，判断特征点个数与位置点总个数比例是否达到目标简化比例ratio；若达到，则结束，所有特征点组成的矢量线为简化后的结果；否则执行步骤(7)。
[0062] 步骤(7).首先取出优先队列头节点，在该节点的分割点处将矢量线片段划分为两段，同时将分割点标记为特征点。其次为分割后得到的两段子片段分别构造优先队列节点。最后，将新构造出的两个优先队列节点加入优先队列，完成后返回至步骤(6)继续构建新的节点。
[0063] 本实施例中一段矢量线Tr:p1→p2→p3→…→p10使用本方法的压缩过程如图2所示。设适量线比例ratio为0.5。按步骤(5)在首尾位置点p1和p10的连线上取垂直距离最大的位置点p6作为分割点，以轨迹段p1→p10和分割点p6构建优先队列的第一个节点，此时特征点个数和位置点总个数未达到目标简化比例，按步骤(7)，取出队列中第一个节点，构建两个新的节点，分别是以p1→p6为轨迹、p4为分割点的节点二和以p6→p10为轨迹、p8为分割点的节点三，继续按步骤(7)分别取出节点二和节点三后，此时总特征点和位置点包括p1、p4、p6、p8、p10，达到目标简化比例，结束压缩流程。
[0064] 如图3所示，本实施例还提供了一种系统，该系统用于执行上述方法，具体包括：
[0065] 数据输入模块，用于输入矢量线集合polylines、地图比例尺scale、地图中心点经纬度(lon,lat)、客户端屏幕宽度方向上像素点width、客户端屏幕高度方向上像素点高height、客户端计算速度s、客户端可接受延迟时间t；
[0066] 地图分辨率resolution计算模块，用于计算地图分辨率resolution；
[0067] 显示区域范围计算模块，用于计算客户端屏幕显示的区域范围；
[0068] 矢量线简化比例ratio计算模块，用于计算矢量线简化比例ratio；
[0069] 初始化模块，用于初始化优先队列；
[0070] 判断模块，用于判断特征点个数与位置点总个数比例是否达到目标简化比例ratio；
[0071] 调整模块，用于对优先队列进行调整，以便判断模块再次判断。
[0072] 以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到其各种变化或替换，这些都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应以所述权利要求的保护范围为准。
