基于空间密度约束的GPS数据LOD模型构建方法
摘 要：为解决GPS轨迹数据动态可视化效率低下问题，本文通过引入LOD（Level Of Detail，LOD）技术从海量轨迹中提取能够代表原始数据的空间特征点，保留原有空间分布特征，压缩数据量。现有LOD模型构建算法虽压缩了数据量，但时间复杂度高，不能显著提高可视化效率。本文提出了一种基于四叉树的点LOD构建算法。实验表明：本文提出的点LOD算法与基于Voronoi图的点LOD算法相比，具有时间复杂度低，LOD构建速度快，无符号压盖等优点。
关键词：动态可视化；GPS轨迹；LOD
中图分类号：TP274 文献标识码：A
Abstract：To address the challenge to visualization of GPS trajectory data，this paper integrates Level Of Detail（LOD）technology into GPS data visualization in order to improve visualization efficiency while maintaining visualization quality.Although the existing LOD algorithms compress the quantity of GPS Data，it cannot significantly improve the visualization efficiency because of high time complexity.This paper proposes a quadtree-based point LOD algorithm.Experiments shows that the quadtree-based point LOD algorithm has lower time complexity，higher performance and better visualization quality than the widely used Voronoi-based LOD algorithm.
Keywords：online visualization；GPS trajectory；LOD
1 引言（Introduction）
随着空间定位技术的成熟发展，可用于记录位置信息的设备越来越普及，手机、平板等移动终端及汽车大都内嵌了GPS芯片或安装了GPS接收机，这些设备每天产生大量的GPS轨迹数据[1]。GPS轨迹数据富含运动主体的群体分布特征，其动态可视化有助于用户快速直观地理解分析这些特征[2，3]。以出租车为例，出租车GPS数据动态可视化，可直观反映出租车群体的空间分布变化情况。GPS轨迹数据作为一种高动态性的时空序列数据，与传统静态空间数据相比，具有海量、更新速度快、时空密集度高等特点。因此，如何高效、准确地可视化GPS轨迹数据，使用户能够快速直观地获取GPS轨迹蕴含的信息，是GPS数据可视化研究中亟待解决的问题。
2 常见LOD算法综述（Summary of common LOD algorithm）
为解决GPS轨迹数据动态可视化效率低下问题，本文通过引入LOD技术从海量轨迹中提取能够代表原始数据的空间特征点，缩短数据传输时间，以提高可视化效率。目前，国内外针对LOD技术在电子地图显示中的研究取得了一些显著成果。对于点状要素LOD可视化研究，文献[4]重点研究了电子地图显示中点状要素LOD模型的建立，提出了一種基于Voronoi图和Delaunay三角网综合相关因素影响建立点状要素LOD模型的算法，实现了不同比例尺下都能得到尽量合理的地图外观。文献[5]结合聚类方法，在Voronoi图的基础上提取聚类中心点，同时利用层次Voronoi图结构逐步细化地表达聚类中心点，进而实现点群由繁到简的综合。文献[6]针对聚集分布的点群，借助凸壳算法形成多层嵌套，以反映点群的逐层分布特征。
无论是Voronoi图法还是凸壳法，都存在这样一个问题：算法时间复杂度高。这对于大数据可视化来说，虽进行了数据抽稀，缩短了前端可视化时间，但由于服务器端计算量大、耗时久，导致操作延时长、用户体验差等问题。因此，针对大数据量的点群可视化需要一种更为快速的LOD模型构建算法。
3 基于空间密度约束的LOD模型构建方法（A LOD construction method for GPS trajectory data with constraints in spatial density）
基于空间密度约束的点状要素LOD模型构建算法借鉴了四叉树的思想，逻辑上分为两步，即空间划分与编码。空间划分是将空间区域分别沿经度方向和纬度方向递归中分，终止条件与比例尺有关。编码是把划分后的格网都赋予一个唯一的编码。
3.1 空间划分与编码
空间划分是对可视化区域的范围沿经纬度方向不断地交替进行二分，每四次二分作为一个层次，即两次四叉划分作为一个层次。用0和1表示每次二分产生的区域，即当沿纬度方向进行二分时，上面区域的编码为1，下面区域的编码为0；当沿经度方向进行二分时，右侧区域的编码为1，左侧区域的编码为0；进而，每四次二分的二进制编码转换为16进制编码，即为某一层网格的编码，如图1所示。16进制编码由数字0—9和英文小写字母a—f组成。
经过编码之后，空间每块区域都对应唯一的一个编码，且同一区域内的点要素具有相同的编码。编码具有这样一个特性：字符串越短，代表空间范围越大，且具有包含关系，比如编码为ab的区域包含编码为abc的区域。基于此特性，字符串编码就代表着空间的金字塔结构，即LOD。基于空间划分的LOD模型如图2所示。
3.2 空间划分阈值
本文提出的点LOD模型构建算法是一个递归划分的过程，递归划分并不是无限进行，当格网被划分到一定大小就应该终止划分。本文提出的点状要素LOD的构建基本思想是在当前比例尺下，一个可视化符号所覆盖的区域内的点群要素只显示一个，因此空间划分的终止条件与可视化符号大小和比例尺有关。设可视化符号宽度为d，当前比例尺为1：x，则屏幕长度对应地图上的实际距离是z，且1：x=d：z。z即为格网划分的阈值。因此，空间划分的终止条件为格网宽度小于等于z。阈值z与比例尺的关系公式如下：
纸质地图上人眼能够分辨两点之间的距离最小为0.1mm[7]，因此可视化符号最小不应该小于0.1mm，即d>=0.1mm，且根据点形状的不同，此值还应适当增大。当已知可视化符号d，则空间划分的终止阈值就可由公式（1）得出。
4 实验过程与结果分析（Experiment process result analysis）
目前点要素化简的算法有凸壳化简法、相关系数控制法、重力模型法和Voronoi图法，且大都只适用于居民地综合[8-12]。仅基于Voronoi图的简化算法应用范围较为广泛，除了针对居民地，还可以针对其他呈点状分布的地物要素[8]。因此，本文以适用性最高的Voronoi图法作为对比对象，比较两种算法的抽稀效率和可视化效果。
4.1 实验方法
本文设计了一个基于B/S架构GPS数据可视化系统，系统架构如图3所示。实验以武汉市出租车GPS数据为可视化对象，数据量大小约200MB。从服务器响应时间、数据传输时间、可视化时间和可视化效果这四个指标进行评价，其中可视化效果指数据抽稀之后仍能反映点状要素空间分布特征，且可视化符号无压盖。实验环境见表1。基于空间密度约束的点LOD算法空间划分阈值等于可视化符号的宽度，为4mm。
4.2 实验结果与分析
实验统计不同比例尺下服务器响应时间、数据传输时间、可视化时间这三个指标，并绘制条形图，即图4、图5、图6。从图4中可以看出，本文算法效率明显高于基于Voronoi图点LOD算法。实验表明，基于Voronoi图的点LOD算法会导致可视化页面易出现无响应情形。
如图5和图6所示，对于数据传输时间和可视化时间这两个指标，本文提出的点LOD算法比基于Voronoi图的点LOD算法均占优。数据传输时间和可视化时间与点数正相关，说明区域一定的条件下，本文算法可以抽稀更多的点。
对于可视化效果这一指标并无量化数据，对比分析图7、图8、图9可以发现两种构建LOD的算法均可以减缓符号压盖现象，同时保持点群空间分布特征。但基于Voronoi图的点LOD算法本身的原因，在点群稀疏的地方也会进行抽稀，这不满足GPS数据动态可视化需求。
综上所述，本文提出的基于空间密度约束的点LOD模型构建算法顾及点状要素空间分布特征的同时，大大减小了算法时间复杂度，进而提高了可视化效率，比基于Voronoi图的点LOD算法更优。
5 结论（Conclusion）
针对GPS轨迹数据动态可视化效率低下问题，本文将LOD技术引入可视化系统中。根据比例尺自适应地数据抽稀，保留数据原有空间分布特征的同时，提高了可视化效率。鉴于现有针对点状要素LOD算法时间复杂度高，本文结合四叉树的特点，提出了基于空间密度约束的LOD模型构建
算法。该算法与适用性高的基于Voronoi图LOD算法相比，时间复杂度低，减少数据量的同时，缩短了服务器响应时间，从而提高了GPS轨迹数据动态可视化效率。
参考文献（References）
[1] Mao Y，Zhong H，Qi H，et al.An Adaptive Trajectory Clustering Method Based on Grid and Density in Mobile Pattern Analysis[J].Sensors，2017，17（9）：2013.
[2] Cai L，Zhou Y，Liang Y，et al.Research and Application of GPS Trajectory Data Visualization[J].Annals of Data Science，2017（4）：1-15.
[3] Liu Y，Kang C，Gao S，et al.Understanding intra-urban trip patterns from taxi trajectory data[J].Journal of Geographical Systems，2012，14（4）：463-483.
[4] 賈奋励，宋国民.电子地图显示中点状要素LOD模型的建立[J].测绘学院学报，2002（01）：62-64.
[5] 李佳田，康顺，罗富丽.利用层次Voronoi图进行点群综合[J].测绘学报，2014（12）：1300-1306.
[6] 毋河海.凸壳原理在点群目标综合中的应用[J].测绘工程，1997（01）：1-6.
[7] Hans-Uli Feldmann.Cartographic Generalisation-Topographic Maps[M].Swiss：Swiss Society of Cartography，2005.
[8] 闫浩文，王家耀.基于Voronoi图的点群目标普适综合算法[J].中国图象图形学报，2005（05）：633-636.
[9] Kreveld M J V，Oostrum R W V，Snoeyink J.Efficient Settlement Selection for Interactive Display[J].In Proc.Auto-Carto 13：ACSM/ASPRS Annual Convention Technical Papers， 1997：287-296.
[10] Sadahiro Y.Cluster Perception in the Distribution of Point Objects[J].Cartographica the International Journal for Geographic Information & Geovisualization，1997（03）：49-62.
[11] 李雯静，李少宁，龙毅，等.利用重力模型进行GIS点群选取[J].武汉大学学报（信息科学版），2013，38（8）：945-949.
[12] 艾廷华，刘耀林.保持空间分布特征的群点化简方法[J].测绘学报，2002，31（2）：175-181.
作者简介：
孙泽昌（1990-），男，硕士，助理工程师.研究领域：GIS与铁路选线.
关键词：动态可视化；GPS轨迹；LOD
中图分类号：TP274 文献标识码：A
Abstract：To address the challenge to visualization of GPS trajectory data，this paper integrates Level Of Detail（LOD）technology into GPS data visualization in order to improve visualization efficiency while maintaining visualization quality.Although the existing LOD algorithms compress the quantity of GPS Data，it cannot significantly improve the visualization efficiency because of high time complexity.This paper proposes a quadtree-based point LOD algorithm.Experiments shows that the quadtree-based point LOD algorithm has lower time complexity，higher performance and better visualization quality than the widely used Voronoi-based LOD algorithm.
Keywords：online visualization；GPS trajectory；LOD
1 引言（Introduction）
随着空间定位技术的成熟发展，可用于记录位置信息的设备越来越普及，手机、平板等移动终端及汽车大都内嵌了GPS芯片或安装了GPS接收机，这些设备每天产生大量的GPS轨迹数据[1]。GPS轨迹数据富含运动主体的群体分布特征，其动态可视化有助于用户快速直观地理解分析这些特征[2，3]。以出租车为例，出租车GPS数据动态可视化，可直观反映出租车群体的空间分布变化情况。GPS轨迹数据作为一种高动态性的时空序列数据，与传统静态空间数据相比，具有海量、更新速度快、时空密集度高等特点。因此，如何高效、准确地可视化GPS轨迹数据，使用户能够快速直观地获取GPS轨迹蕴含的信息，是GPS数据可视化研究中亟待解决的问题。
2 常见LOD算法综述（Summary of common LOD algorithm）
为解决GPS轨迹数据动态可视化效率低下问题，本文通过引入LOD技术从海量轨迹中提取能够代表原始数据的空间特征点，缩短数据传输时间，以提高可视化效率。目前，国内外针对LOD技术在电子地图显示中的研究取得了一些显著成果。对于点状要素LOD可视化研究，文献[4]重点研究了电子地图显示中点状要素LOD模型的建立，提出了一種基于Voronoi图和Delaunay三角网综合相关因素影响建立点状要素LOD模型的算法，实现了不同比例尺下都能得到尽量合理的地图外观。文献[5]结合聚类方法，在Voronoi图的基础上提取聚类中心点，同时利用层次Voronoi图结构逐步细化地表达聚类中心点，进而实现点群由繁到简的综合。文献[6]针对聚集分布的点群，借助凸壳算法形成多层嵌套，以反映点群的逐层分布特征。
无论是Voronoi图法还是凸壳法，都存在这样一个问题：算法时间复杂度高。这对于大数据可视化来说，虽进行了数据抽稀，缩短了前端可视化时间，但由于服务器端计算量大、耗时久，导致操作延时长、用户体验差等问题。因此，针对大数据量的点群可视化需要一种更为快速的LOD模型构建算法。
3 基于空间密度约束的LOD模型构建方法（A LOD construction method for GPS trajectory data with constraints in spatial density）
基于空间密度约束的点状要素LOD模型构建算法借鉴了四叉树的思想，逻辑上分为两步，即空间划分与编码。空间划分是将空间区域分别沿经度方向和纬度方向递归中分，终止条件与比例尺有关。编码是把划分后的格网都赋予一个唯一的编码。
3.1 空间划分与编码
空间划分是对可视化区域的范围沿经纬度方向不断地交替进行二分，每四次二分作为一个层次，即两次四叉划分作为一个层次。用0和1表示每次二分产生的区域，即当沿纬度方向进行二分时，上面区域的编码为1，下面区域的编码为0；当沿经度方向进行二分时，右侧区域的编码为1，左侧区域的编码为0；进而，每四次二分的二进制编码转换为16进制编码，即为某一层网格的编码，如图1所示。16进制编码由数字0—9和英文小写字母a—f组成。
经过编码之后，空间每块区域都对应唯一的一个编码，且同一区域内的点要素具有相同的编码。编码具有这样一个特性：字符串越短，代表空间范围越大，且具有包含关系，比如编码为ab的区域包含编码为abc的区域。基于此特性，字符串编码就代表着空间的金字塔结构，即LOD。基于空间划分的LOD模型如图2所示。
3.2 空间划分阈值
本文提出的点LOD模型构建算法是一个递归划分的过程，递归划分并不是无限进行，当格网被划分到一定大小就应该终止划分。本文提出的点状要素LOD的构建基本思想是在当前比例尺下，一个可视化符号所覆盖的区域内的点群要素只显示一个，因此空间划分的终止条件与可视化符号大小和比例尺有关。设可视化符号宽度为d，当前比例尺为1：x，则屏幕长度对应地图上的实际距离是z，且1：x=d：z。z即为格网划分的阈值。因此，空间划分的终止条件为格网宽度小于等于z。阈值z与比例尺的关系公式如下：
纸质地图上人眼能够分辨两点之间的距离最小为0.1mm[7]，因此可视化符号最小不应该小于0.1mm，即d>=0.1mm，且根据点形状的不同，此值还应适当增大。当已知可视化符号d，则空间划分的终止阈值就可由公式（1）得出。
4 实验过程与结果分析（Experiment process result analysis）
目前点要素化简的算法有凸壳化简法、相关系数控制法、重力模型法和Voronoi图法，且大都只适用于居民地综合[8-12]。仅基于Voronoi图的简化算法应用范围较为广泛，除了针对居民地，还可以针对其他呈点状分布的地物要素[8]。因此，本文以适用性最高的Voronoi图法作为对比对象，比较两种算法的抽稀效率和可视化效果。
4.1 实验方法
本文设计了一个基于B/S架构GPS数据可视化系统，系统架构如图3所示。实验以武汉市出租车GPS数据为可视化对象，数据量大小约200MB。从服务器响应时间、数据传输时间、可视化时间和可视化效果这四个指标进行评价，其中可视化效果指数据抽稀之后仍能反映点状要素空间分布特征，且可视化符号无压盖。实验环境见表1。基于空间密度约束的点LOD算法空间划分阈值等于可视化符号的宽度，为4mm。
4.2 实验结果与分析
实验统计不同比例尺下服务器响应时间、数据传输时间、可视化时间这三个指标，并绘制条形图，即图4、图5、图6。从图4中可以看出，本文算法效率明显高于基于Voronoi图点LOD算法。实验表明，基于Voronoi图的点LOD算法会导致可视化页面易出现无响应情形。
如图5和图6所示，对于数据传输时间和可视化时间这两个指标，本文提出的点LOD算法比基于Voronoi图的点LOD算法均占优。数据传输时间和可视化时间与点数正相关，说明区域一定的条件下，本文算法可以抽稀更多的点。
对于可视化效果这一指标并无量化数据，对比分析图7、图8、图9可以发现两种构建LOD的算法均可以减缓符号压盖现象，同时保持点群空间分布特征。但基于Voronoi图的点LOD算法本身的原因，在点群稀疏的地方也会进行抽稀，这不满足GPS数据动态可视化需求。
综上所述，本文提出的基于空间密度约束的点LOD模型构建算法顾及点状要素空间分布特征的同时，大大减小了算法时间复杂度，进而提高了可视化效率，比基于Voronoi图的点LOD算法更优。
5 结论（Conclusion）
针对GPS轨迹数据动态可视化效率低下问题，本文将LOD技术引入可视化系统中。根据比例尺自适应地数据抽稀，保留数据原有空间分布特征的同时，提高了可视化效率。鉴于现有针对点状要素LOD算法时间复杂度高，本文结合四叉树的特点，提出了基于空间密度约束的LOD模型构建
算法。该算法与适用性高的基于Voronoi图LOD算法相比，时间复杂度低，减少数据量的同时，缩短了服务器响应时间，从而提高了GPS轨迹数据动态可视化效率。
参考文献（References）
[1] Mao Y，Zhong H，Qi H，et al.An Adaptive Trajectory Clustering Method Based on Grid and Density in Mobile Pattern Analysis[J].Sensors，2017，17（9）：2013.
[2] Cai L，Zhou Y，Liang Y，et al.Research and Application of GPS Trajectory Data Visualization[J].Annals of Data Science，2017（4）：1-15.
[3] Liu Y，Kang C，Gao S，et al.Understanding intra-urban trip patterns from taxi trajectory data[J].Journal of Geographical Systems，2012，14（4）：463-483.
[4] 賈奋励，宋国民.电子地图显示中点状要素LOD模型的建立[J].测绘学院学报，2002（01）：62-64.
[5] 李佳田，康顺，罗富丽.利用层次Voronoi图进行点群综合[J].测绘学报，2014（12）：1300-1306.
[6] 毋河海.凸壳原理在点群目标综合中的应用[J].测绘工程，1997（01）：1-6.
[7] Hans-Uli Feldmann.Cartographic Generalisation-Topographic Maps[M].Swiss：Swiss Society of Cartography，2005.
[8] 闫浩文，王家耀.基于Voronoi图的点群目标普适综合算法[J].中国图象图形学报，2005（05）：633-636.
[9] Kreveld M J V，Oostrum R W V，Snoeyink J.Efficient Settlement Selection for Interactive Display[J].In Proc.Auto-Carto 13：ACSM/ASPRS Annual Convention Technical Papers， 1997：287-296.
[10] Sadahiro Y.Cluster Perception in the Distribution of Point Objects[J].Cartographica the International Journal for Geographic Information & Geovisualization，1997（03）：49-62.
[11] 李雯静，李少宁，龙毅，等.利用重力模型进行GIS点群选取[J].武汉大学学报（信息科学版），2013，38（8）：945-949.
[12] 艾廷华，刘耀林.保持空间分布特征的群点化简方法[J].测绘学报，2002，31（2）：175-181.
作者简介：
孙泽昌（1990-），男，硕士，助理工程师.研究领域：GIS与铁路选线.
