一种基于地图缩放层级显示Top-k城市轨道交通站点的方法

摘要

本发明公开了一种基于地图缩放层级显示Top‑k城市轨道交通站点的方法，先获取当前屏幕范围内的所有POIs，再结合空间约束、分时客流量分析、是否为换乘站点三种约束，使用基于Skyline的Top‑k排序算法对过滤后的POIs进行排序，返回给用户k个当前可视范围内最具有代表性的POIs的队列。当地图尺度变化或用户拖动地图时，更新算法重新获取POIs并排序。步骤1：获取当前屏幕范围内地图上的所有POIs并筛选出所有的Skyline Point；步骤2：结合空间约束、分时客流量分析、是否为换乘站点三个约束对过滤后的POIs执行基于Skyline的Top‑k排序算法；步骤3：当地图尺度变化或地图中心点改变时，更新站点集合，重新执行算法，调整屏幕范围内所显示的POIs。

说明书

技术领域

本发明涉及一种基于不同的地图缩放层级显示Top-k城市轨道交通站点的方法。

背景技术

近60年来，随着中国经济的快速增长，我国的城市轨道交通建设得到了迅猛发展，也带动了国内基建技术的全面进步。为了满足城市便利性的需要，人们在电子地图上绘制轨道交通图层，将轨道线路及交通站点在地图上直观显示，乘客通过地图来完成定位、查找站点、安排及估计车程，大大提高了用户的乘车效率。面对大量的站点信息，如何能够对站点的空间信息进行合理的显示是建立轨道交通地图过程中的关键步骤。站点空间数据的视觉信息元素合理可视化、有效的需求是提高站点信息化服务水平的重要指标。现有的地图服务虽然可视化了各个站点的地理信息，但主要重点是在地图上为用户展示所有的结果，它在尺度变化时会发生站点图标相互遮挡的现象，用户识别不同的站点不方便，并且在尺度不变但用户拖动地图时不能动态地显示新的站点。为了最大程度地发挥轨道交通图作为城市公共交通系统的信息指南的作用，让乘客更直观地安排出行方案，本发明提出了一种基于地图缩放层级显示Top-k城市轨道交通站点的方法，该方法能够按照用户给出的中心点以及不同的尺度大小在地图上显示数目合理的更为重要的关键站点。

本发明在地图的不同尺度下，合理地展示用户浏览在线地图上某个区域的少量代表性POI(用k表示)。在用户当前区域的可视范围内，需要有效地选择个k个对象，为了避免一些重要的节点被忽略，结合空间约束、分时客流量分析、是否为换乘站点三个方面进行排序。空间多样性是通过已经选择POIs的方向对候选POIs中同一方向的点进行削弱，客流量分析比较站点间客流分布趋势的相似性，换乘站点的重要程度远大于普通站点，量化了POI的空间约束、分时客流量分析、是否为换乘站点之后，对所有的POI每个维的属性进行了归一化处理，即使其最大值和最小值均分别为1和0，便于结合三个约束的分值进行后续排序。使用基于Skyline的Top-k排序方法选取分值最高的k个POIs，通过组合属性得分为每个对象分配总得分，通过添加系数α、β符号将三个属性分值组合在一起，以来确定总得分最高的k个对象。然后定义效用函数，对POIs按照效用函数值进行Top-k排序。其中k的值可与屏幕的缩放尺度联系在一起，在不同的尺度范围下，设置不同的k值。当地图尺度变化或用户拖动地图时，就更新算法并为新图区域选择一组新的代表性对象，重新动态调整所显示的POIs。通过这种方法可筛选相对更重要的POIs，在保持地图中站点显示美观的前提下，也能合理满足用户需求。

发明内容

本发明的目的在于提供了一种基于地图缩放层级显示Top-k城市轨道交通站点的方法，结合空间约束、分时客流量分析、是否为换乘站点三种约束，使用基于Skyline的Top-k排序算法的对过滤后的POIs进行排序，仅显示当前可视范围内最具有代表性的k个POIs，返回给用户k个当前可视范围内最具有代表性的POIs的集合。当地图尺度变化或用户拖动地图时，更新算法重新获取POIs并排序。

一种基于地图缩放层级显示Top-k城市轨道交通站点的方法，该方法的实现步骤如下：

步骤1：获取当前屏幕范围内地图上的所有POIs并筛选出所有的Skyline Point。

步骤1.1：收集并整理站点数据集。数据集中含有站点名称，依次对站点名进行编号1…i...n，:其中编号从1开始，pi代表站点集合的第i个站点，n为站点的总个数。

步骤1.2：根据结合当前尺度以及用户的中心点位置，对当前可视范围内的POIs进行筛选，对每个pi执行Skyline Point判断算法，删除所有被支配的POIs，保留SkylinePoint，留下的兴趣点组成Skyline Point集合。

步骤2：结合空间约束、分时客流量分析、是否为换乘站点三个方面对过滤后的POIs执行基于Skyline的Top-k排序算法。

步骤2.1：通过以下公式计算候选站点的空间多样性：

其中，l＝|eQue|表示已经提取了POIs的个数，pi是候选POIs队列pois中任意的POI，pj表示已提取队列eQue中的任意POI；s表示初始的屏幕中心点，dis(,)表示两个位置点的欧氏距离。其值域为(0,1]。

步骤2.2：采用欧氏距离的思想，采用以下公式计算两个站点pi和pj的进站客流差异：

其中f

根据站点进站客流量的相似度，量化出客流量约束，其值域为(0,1)，如下述公式所示：

步骤2.3：换乘站点，参数量化为1(trans＝1)，非换乘站点，量化为0(trans＝0)。

步骤2.4：在Skyline Point集合的基础上，进行Top-k排序。先判断队列eQue中的元素个数是否小于k，成立则通过组合属性得分为每个对象分配总得分，通过添加系数α、β符号将三个属性分值组合在一起，以来确定总得分最高的k个对象。然后定义效用函数，对POIs按照效用函数值进行Top-k排序。在可视范围内提取POIs的公式为：

pi.Div＝α*pi.Divpas+β*pi.Divspa+(1-α-β)*pi.trans (5)

函数分数最高的加入队列eQue。

步骤3：当地图尺度变化或地图中心点改变时，更新站点集合，重新执行算法，调整所显示的POIs。

综上，对POIs中的三个约束计算得分加入已提取POIs队列eQue，从候选队列pois中选出k个得分最高的POI加入队列eQue，所以选出top-k POIs的过程为：

1)获取当前屏幕范围内的所有POIs，个数为n，定义参数i＝0；

2)当i

3)执行算法判断pi是否为Skyline Point，算法有两个输出，0和1，分别代表不是Skyline Point和是Skyline Point；

4)当算法输出为0，转5)，否则转6)；

5)在POIs集合中删除pi，n-＝1；

6)i+＝1；

7)初始化队列pois为空，取三个属性值之和最大的Skyline Point为top-1加入队列，l＝1；

8)当l

9)计算pois队列中各个pi与eQue队列pj中的空间多样性；

10)计算pois队列中各个pi与eQue队列pj中的客流量相似度并归一化；

11)获取标志各个pi是否为换成站点的trans值；

12)计算候选队列pois中每一个POIs得分，并将候选队列中POIs按照分数从高到低排序，依次将前k个POIs加入队列eQue中，返回队列eQue

13)继续判断l

14)提取队列eQue中的top-kPOIs；

15)判断是否有尺度变化或用户拖动地图的中心点变化，如果有，转1)，否则结束；

与现有技术相比较，本发明具有如下有益效果：

1)使轨道交通站点的地图服务在尺度变化时不发生遮挡，在不同的尺度下，展示合理数目的地铁站，且所显示地铁站的文字标签之间不会出现任何重叠。

2)在尺度不变但中心点变化时可以动态地显示新的站点，有效提高了用户体验。

附图说明

图1为本发明的实施流程图。

具体实施方式

下面结合相关附图对本发明进行解释和阐述：

本发明使用2013年6月至7月北京市轨道交通AFC刷卡记录统计站点进出客流量记录,爬取高德地图北京市地铁站点信息数据，POI包含的主要信息有名称，经度，纬度等。假设在地图在标尺为1.5公里，即比例尺为1厘米:1.5千米时，以平乐园地铁站为中心点，在地图上可视范围内的所有地铁站有平乐园，九龙山，北工大西门，国贸，劲松等21个地铁站，n＝21，其中有换乘站点九龙山，大望路，国贸等7个。假设在标尺为1.5公里的情况下，k＝6。

步骤1：执行Skyline Point判断算法判断每个pi是否为Skyline Point，该算法返回数据集中不受任何其他点支配的点的子集，点p＝(p[1]，p[2]，...，p[d])控制另一个点q＝(q[1]，q[2]，...，q[d])p[i]≤q[i](对于1≤i≤d)，并且至少存在一个维j，使得p[j]

步骤2:取三个属性值之和最大的Skyline Point，即国贸站为top-1，此时eQue队列中只有国贸这个POI，队列pois有除了国贸以外的7个POIs。

在分辨率为720*1280的屏幕上，中心点坐标s<360,640>，n个地铁站的坐标分别为：平乐园:p1<360,640>,欢乐谷景区:p2<662,1022>,九龙山:p3<360，488>，化工:p4<597，732>，国贸:p5<205，280>，大望路:p6<360，280>，双井:p7<205，488>，十里河:p8<205，754>。

步骤2.1:根据公式(1)计算空间多样性，此时eQue队列中只有国贸这个POI，即：

dis(p5,s)＝391.95,dis(p1,s)＝0,dis(p5,p1)＝391.95,由公式求得Div(p1)＝1。

dis(p5,s)＝391.95,dis(p2,s)＝486.96,dis(p5,p2)＝871.44,由公式求得Div(p2)＝0.99。

dis(p5,s)＝391.95,dis(p3,s)＝152,dis(p5,p3)＝259.40,由公式求得Div(p3)＝0.48。

dis(p5,s)＝391.95,dis(p4,s)＝254.23,dis(p5,p4)＝481.73,由公式求得Div(p4)＝0.74。

dis(p5,s)＝391.95,dis(p6,s)＝360,dis(p6,p5)＝155,由公式求得Div(p6)＝0.21。

dis(p5,s)＝391.95,dis(p7,s)＝217.09,dis(p5,p7)＝208,由公式求得Div(p7)＝0.37。

dis(p5,s)＝391.95,dis(p8,s)＝192.41,dis(p5,p8)＝474,由公式求得Div(p8)＝0.81。

步骤2.2:使用2013年6月至7月北京市轨道交通AFC刷卡记录，根据公式(2)计算所有站点pi和p5的进站客流差异，根据公式(3)计算站点pi和p6的时间感知客流量的相似度，公式(4)量化出客流量约束，其值域为(0,1)。Div(p1)＝0.41，Div(p2)＝0.58，Div(p3)＝0.70，Div(p4)＝0.51，Div(p6)＝0.78，Div(p7)＝0.64，Div(p8)＝0.60，

步骤2.3：换乘站点九龙山，国贸，大望路，双井，十里河trans＝1，非换乘站点欢乐谷景区,平乐园，化工trans＝0。

步骤2.4:根据公式(5)，赋予参数α，β值，求得函数分值，按分值进行大小排序，当α＝0.4，β＝0.4时求得：

P1.Div＝α*1+β*0.41+(1-α-β)*0＝0.564

P2.Div＝α*0.99+β*0.58+(1-α-β)*0＝0.628

P3.Div＝α*0.48+β*0.70+(1-α-β)*1＝0.672

P4.Div＝α*0.74+β*0.51+(1-α-β)*0＝0.5

P6.Div＝α*0.21+β*0.78+(1-α-β)*1＝0.596

P7.Div＝α*0.37+β*0.64+(1-α-β)*1＝0.604

P8.Div＝α*0.81+β*0.60+(1-α-β)*1＝0.764

按照从高到底排序，可得top-2为十里河，加入队列eQue，在eQue元素个数小于6时，循环步骤2，直至l＝6，得到最终的top-k排名如下

国贸，十里河，大望路，欢乐谷景区，十里河，平乐园

步骤3：当用户平行拖动地图或尺度大小发生改变时，更新站点集合，重新执行算法。