2. 浙江大学 地理信息科学研究所, 浙江 杭州 310027;
3. 浙江省第二测绘院, 浙江 杭州 310012
2. Department of Geographic Information Science, Zhejiang University, Hangzhou 310027, China;
3. The Second Surveying and Mapping Institute of Zhejiang Province, Hangzhou 310012, China
矢量数据是对现实空间世界中各类地理事物和现象进行抽象表达的一种空间数据结构，在地理信息系统中具有极其重要的作用.随着GIS应用和WebGIS的快速发展，矢量数据量不断增大，用户对系统的交互性要求也越来越高.矢量地图将矢量地理数据在前端绘制成不同要素，能够实现地图的动态交互，但矢量地图传输的是全部数据，当数据量较大或者网络速度较慢时，内存开销大，响应时间长，影响了地图服务的质量.目前，通用的互联网地图服务网站(Google地图、天地图、百度地图等)主要采用多级栅格与影像金字塔模型，通过在服务器端建立多分辨率层次模型，在不同显示层级预先生成地图瓦片来大幅减少数据访问量，减轻服务器负载和网络传输负担，提高地图生成、发布、显示和浏览的效率[1-3].
矢量瓦片技术将瓦片服务的高效与矢量地图的灵活结合在一起，使得矢量瓦片拥有切片优势的同时能够实现地图的交互显示.对于矢量瓦片技术，不少学者做了相应研究，ANTONIOU等[4]提出了矢量数据瓦片化方法.孙璐等[5]利用矢量瓦片技术，实现了全国路网等大规模矢量数据可视化.王亚平等[6]利用开源应用程序TileStache，得到适用于多源投影矢量地理数据的瓦片生成工具OTileTool.孙晨龙等[7]以矢量瓦片作为矢量数据的载体，利用金字塔思想，实现了基于LOD的矢量瓦片调度.以上学者均是基于金字塔模型，对每一层级按照均匀格网划分方式对地理坐标范围内的地图进行切分，构建矢量瓦片.然而，由于要素空间分布的不均匀性，矢量数据往往存在要素空间稠密度不一致的现象，例如人口分布，在人口稠密地区，每km2可能包含兆级数量的数据，而在稀疏地区数据可能很少甚至没有.采用均匀格网划分的方式，会导致每一层级矢量瓦片间数据量不均衡，客户端在请求瓦片数据时，数据量小的瓦片能够快速加载渲染，而数据量大的瓦片加载渲染慢，用户等待时间长，体验效果差.
综上所述，当前对矢量瓦片构建技术的相关研究普遍未考虑矢量数据空间分布不均匀对瓦片加载渲染的影响.针对此问题，本文提出了一种顾及要素分布特征的稠疏矢量瓦片优化构建方法，使得同一分辨率下的矢量瓦片数据量趋于均衡，以优化矢量地图瓦片的加载速度，提高渲染效率，获得更好的用户体验.
1 矢量瓦片瓦片是随着互联网地图服务不断发展以及高性能地图服务需求而出现的一种新型的面向可视化的地理空间数据表达方式[8].传统意义上的地图瓦片是指将基础地图按照既定的规则分割成一定单元大小的图片，这些图片即栅格瓦片，其本身不含空间数据内容，且样式固定.文献[4]所述的矢量瓦片与栅格瓦片类似，是将用于传输的矢量数据按照一定大小的数据单元进行切分，形成一定数量级的小数据单元进行传输，但与栅格瓦片不同的是，矢量瓦片的每个数据单元中包含的是该数据单元范围内的所有要素的信息.矢量瓦片不仅拥有瓦片地图高效的请求和传输，成熟的缓存、缩放比例技术的优势，而且具有矢量数据灵活的地图交互显示、自由的样式配色及快速的地图映射等特点.目前，在浏览器端，矢量瓦片正逐渐占据越来越重要的地位.
矢量瓦片数据需要一种合适的格式进行传输.目前，主要的地理信息交换格式有GeoJSON、SVG、GML、KML等.本文采用GeoJSON格式承载矢量瓦片数据，GeoJSON是基于JSON扩展的用于表示各种地理数据结构的数据格式，遵循OGC简单要素模型，可以对地理要素进行编码，较SVG、GML、KML等地理信息交换格式简洁，有利于地理数据的传输[9-10].GeoJSON使得矢量瓦片保留了原始矢量数据的全部空间和属性信息，客户端可以直接实现要素查询、动态符号渲染，甚至空间分析等复杂操作，减轻服务端矢量数据计算的压力.
2 空间数据的格网划分数据划分，又称为数据分簇(data declustering)，其目的是将一块完整的数据分割为相对小而独立的多块数据.数据划分策略的优劣将直接影响系统的吞吐能力和I/O性能.
空间数据广泛采用格网划分，即使用平行于数据空间坐标轴的分割线将数据空间划分成多个均匀或不均匀的子数据空间，并将空间数据集压缩到划分的格网空间中，从而生成一定数量的网格单元.空间格网划分的主要目的是将空间数据集离散化，用少数网格单元代表多数数据对象，从而降低处理的复杂度[11].空间格网划分的主要方法有：一维散列划分、采样划分、轮转划分，这类方法是利用Geohash编码、空间填充曲线(Z曲线、Hilbert曲线等)等技术对空间格网先降维后进行空间数据划分，在一定程度上满足了划分区域内要素对象的空间聚集性，保证了划分区域的数据量均衡.
瓦片地图采用的金字塔模型组织是一种多分辨率层次模型，如图 1所示，从金字塔底层至顶层，分辨率逐级降低，但表示的地图范围不变[12].金字塔模型每一分辨率层级都采用均匀格网划分结构对数据进行划分，每个网格单元的容积相等，即将地理坐标范围内的地图分割为大小相同(如128*128pixel，256*256pixel等)的正方形地图瓦片，这种划分方式的计算与索引方法简便快捷.
|
图 1 瓦片金字塔模型 Fig. 1 Tile-pyramid model |
矢量瓦片保留了空间要素的全部空间和属性信息，当空间要素分布不均匀时，采用均匀格网的划分方式，将会导致不同瓦片间存在较大的数据量差异，引起访问时负载不均衡，影响瓦片地图整体的加载渲染效率.此外，某些数据量大的瓦片易受到网络传输不确定性因素的干扰导致加载失败，这在一定程度上影响了用户的体验感.如图 2所示，数据分布不均匀时，采用均匀格网划分的方式，各矢量瓦片间较大的数据量差异导致了瓦片间的加载渲染存在较长的时间差，易于使用户产生数据已经加载完毕或者加载失败的错觉，影响用户的体验，而当数据分布均匀时，矢量瓦片间具有相对均衡的数据量，使得瓦片的加载速率几乎一致，加载渲染时间差异小，浏览显示效果更优.由此可知，在保证瓦片计算与索引简单便捷的同时，保证瓦片间的数据量均衡，将更能优化瓦片的加载渲染效率，提升用户体验.本文借鉴此思想，将矢量数据在纵向上按照瓦片金字塔模型进行分层，横向上根据子瓦片数据量的差异进行一次或多次四等分划分，如图 3所示，保证同一层级瓦片间的数据量相对均衡，从而实现矢量瓦片的加载均衡化，提升加载渲染效率，改善用户体验.
|
图 2 不同空间数据分布情况的矢量瓦片加载渲染对比 Fig. 2 Loading and rendering contrast of vector tiles with different spatial distribution data |
|
图 3 瓦片金字塔模型的横向切分 Fig. 3 Transverse segmentation of tile-pyramid model |
要素空间分布的情况直接影响矢量瓦片的数据量，针对矢量瓦片地图金字塔模型未考虑空间要素分布不均引起的矢量地图瓦片加载渲染效率差异和并发一致性问题，本文提出一种稠疏矢量瓦片的构建方法，即对金字塔每一层级，在空间要素密集区则格网密集，空间要素稀疏区则格网稀疏，如图 4所示.
|
图 4 稠疏矢量瓦片 Fig. 4 Dense-sparse vector tiles |
在稠疏矢量瓦片的构建过程中，既要保证瓦片对象间的空间邻近性，同时要保证瓦片间数据量大致均衡，因此，需要解决以下2个关键问题：(1) 确定数据划分的起始层级和每一层级中子格网划分的终止层级；(2) 对划分后生成的瓦片对象如何进行编码，保证瓦片的唯一性.其中，稠疏矢量瓦片构建过程中涉及的变量有：按照金字塔模型构建的矢量瓦片数据集D；D对应的最大层级号maxlevel；层级号i(0≤i≤maxlevel)；每一层级的瓦片数据集Di；Di的瓦片个数Num；Di中每个瓦片的数据量Qm(0＜m＜Num)；Di的初始数据量平均值Qi；Di中数据量最大的瓦片dmax；当前层级的瓦片数据划分前后的变异系数CVbefore和CVafter.
稠疏矢量瓦片构建过程中的初始层级与金字塔模型的层级一一对应，子格网由父格网进行一次或者多次四等分得到，每一层级中子瓦片划分的终止层级影响稠疏矢量瓦片构建的质量，过低则无法保证该层级中瓦片数据量的均衡，过高则造成不必要的过密划分.每一层级中子瓦片划分的终止层级可以通过比较瓦片数据量Qm与Qi，及比较划分前后的CVbefore与CVafter确定，比较方式如下：
(1) 若划分后Di中所有瓦片的Qm小于Qi，则当前划分层级为子瓦片的终止层级；
(2) 若划分后CVbefore小于CVafter，则CVbefore所处的层级为子瓦片的终止层级；
只要满足以上2个条件之一便可确定是否终止划分.此比较方式为迭代划分提供了依据.
对于生成的稠疏矢量瓦片对象，需要采用唯一的编码进行标识，本文采用Geohash编码方式对构建的稠疏矢量瓦片进行降维编码.Geohash编码是由GUSTAVO提出的一种全球性的基于经纬度的地理编码系统[13]，通过将经纬度转换为字符串实现地理编码，其核心思想是利用空间二分无限逼近方法，即将空间范围按照经度和纬度方向交替进行二分，直至划分后的空间精度满足要求，再通过Base32字符编码对划分的空间分区进行表述.具体算法如下：
(1) 空间二分.Geohash编码的对象是全球的经纬度坐标，因此，Geohash编码的空间范围为：纬度[-90°，90°]，经度[-180°，180°].空间划分方式是先将经度范围进行二分，左半部分范围编码为0，右半部分范围编码为1，再将纬度范围进行二分，下半部分范围编码为0，上半部分范围编码为1，空间范围被一分为四.2次划分后全球空间被划分为编码00、01、10、11四等份，划分后的编码是2次划分编码的拼接，第1位为经度范围编码，第2位为纬度范围编码.按照上述方式继续划分，对划分后每一空间区块进行空间二分，并追加编码.划分与编码过程如图 5所示，可知Geohash编码符合Z曲线编码的特性.
|
图 5 空间二分过程 Fig. 5 Space dichotomy process |
(2) Base32字符编码.Geohash编码采用0-9、b-z(去掉a、i、l、o，避免与数字混淆)这32个字符进行编码.
Geohash编码具有唯一性、递归性、空间包含性、空间邻近性等特点[14]，通过Geohash编码可提高瓦片查询检索的速度.根据Geohash核心思想，可知Geohash编码符合Z曲线编码的特性，可以按照Z曲线编码的计算方式计算Geohash二进制编码.因此本文通过Z曲线填充稠疏格网，计算对应格网的二进制编码值，如图 6所示.Geohash二进制编码的位数反映了空间划分的层级，位的具体数值则反映了数据的空间范围.
|
图 6 Z曲线填充 Fig. 6 Z space-filling curve |
稠疏矢量瓦片构建流程如图 7所示，其中流程中涉及的变量含义与上一节中所述相同.具体的构建步骤如下：
|
图 7 稠疏矢量瓦片构建流程 Fig. 7 Process of dense-parse vector tile generation |
(1) 计算空间数据集的空间范围，按照瓦片金字塔模型构建矢量瓦片，得到均匀划分的矢量瓦片数据集D；
(2) 瓦片划分从第0层级开始，即i为0；
(3) 判断i是否小于等于maxlevel，若是，则执行步骤(4)~(9)；否则执行步骤(10)；
(4) 计算第i层级的瓦片数据集Di的瓦片数据量初始平均值Qi；
(5) 计算Di中瓦片数据量大小的变异系数CVbefore；
(6) 选择Di中瓦片数据量最大的瓦片dmax，将其平均划分为四等分；
(7) 计算此时Di中瓦片数据量大小的变异系数CVafter.
(8) 判断CVbefore和CVafter的大小，若CVafter小于CVbefore且Di中存在瓦片的Qm不小于Qi，则重复上述步骤(5)~(8)；若CVafter大于CVbefore，则恢复dmax瓦片为未切分时的状态，直到CVbefore达到最小或者每份瓦片数据量都小于Qi时停止切分；
(9) 层级i加上1，执行步骤(3)；
(10) 完成稠疏矢量瓦片的构建.
4 实验与分析 4.1 实验数据及实验方法实验所用数据：以宁波市行政区划为空间范围，乡镇为基本单元，模拟了各个乡镇不同数据量级的随机点分布，共包含了783 440个点要素，如图 8所示.
|
图 8 实验数据 Fig. 8 Experimental data |
为进行对比分析，将实验数据按照2种方式进行划分：(1) 按照传统金字塔模型瓦片构建方式构建矢量瓦片.(2) 按照本文提出的稠疏矢量瓦片构建方式构建矢量瓦片.然后选取2种划方式对应的矢量瓦片结构的第8~13级瓦片为实验数据，每一层级瓦片的数据情况见表 1.
|
表 1 不同划分方式的矢量瓦片结果 Table 1 Results of the vector tiles generated by different methods |
记录和对比不同格网划分方式下矢量瓦片的加载显示时间.为了减少实验过程中网络及硬件状态产生的随机误差，矢量瓦片加载重复20次，将20次加载时间的平均值作为实验结果进行分析.
服务器硬件环境：处理器：Intel(R) Core(TM) i7-4790 CPU @ 3.60 GHz；内存：8 GB；操作系统：Window 7 64位.客户端硬件环境为：处理器：Intel(R) Core(TM)2 Duo CPU E4500 @ 2.20 GHz；内存：4 GB；操作系统：Windows 7 32位.
4.2 实验结果为验证本文提出的稠疏格网构建方法的有效性，首先对基于均匀格网划分方式构建的第8~13层级的瓦片进行加载实验，并将实验结果进行记录.在保证各层级请求中心点不变的前提下，对基于稠疏格网划分方式构建的第8~13层级的瓦片数据进行2组不同的实验，记录实验结果，并与基于均匀格网划分方式的实验结果进行对比.其中，实验1保证各层级请求的瓦片数据范围与均匀格网划分方式下各层级请求的瓦片数据范围一致，得到的实验结果如表 2所示；实验2保证瓦片请求的视窗范围与均匀格网划分方式实验的视窗范围一致，得到的实验结果如表 3所示.
|
|
表 2 同一空间范围内的矢量瓦片加载情况对比 Table 2 Performance of vector tiles loading in the same spatial scope |
|
|
表 3 同一视窗范围内的矢量瓦片加载情况对比 Table 3 Performance of tiles loading in the same web window |
从表 2中可以看出，稠疏矢量瓦片的请求数据量总体上略大于均匀矢量瓦片，但差异并不显著，这是由于GeoJSON格式包含一部分非要素属性信息，同一请求空间范围内稠疏矢量瓦片数量大于等于均匀矢量瓦片，从而引起稠疏矢量瓦片的请求数据量略大于均匀矢量瓦片；2种瓦片构建方式的瓦片请求绘制时间都随请求数据量的增加而增加，但采用本文提出的稠疏矢量瓦片的请求绘制时间优于均匀矢量瓦片的请求绘制时间.分析其原因，本文瓦片的请求绘制采用多线程方式，稠疏矢量瓦片各瓦片间的数据量均衡，使得瓦片请求绘制达到负载均衡，从而提升了瓦片的渲染效率.由表 2中的时间比可知，在8~11级，均匀矢量瓦片与稠疏矢量瓦片加载的时间比随着层级的增加而增大，而在11~13级，时间比随着层级的增加而减小，说明瓦片的划分粒度对稠疏瓦片的加载有影响，过小的粒度增加了瓦片的读取和加载时间.
表 2中2种划分方式下各层级请求的瓦片数据空间范围是一致的，如图 9所示，在视窗范围内请求基于均匀格网划分的瓦片(见图 9(a))为瓦片1~6，请求基于稠疏格网划分的瓦片为瓦片a~k和瓦片1~30.但实际应用中，往往是请求视窗范围内的瓦片，因此，请求基于稠疏格网划分的瓦片得到的应为瓦片1~30.由此可知，同一视窗范围内请求的稠疏矢量瓦片的数据范围小于等于均匀格网矢量瓦片，即采用稠疏矢量瓦片可在一定程度上减少瓦片请求的数据量.表 3即为同一视窗范围内2种划分方式下瓦片请求的实验结果.
|
图 9 视窗范围内2种矢量瓦片请求加载情况 Fig. 9 Performance of tiles loading in the web window |
由表 3知，采用稠疏格网划分方式构建的矢量瓦片可以减少瓦片加载的数据量，最高可减少近一半的数据量，数据量的减少程度与空间数据的实际分布情况有关.同时，采用稠疏格网构建矢量瓦片的方式能够大幅度缩短瓦片加载时间，最高可缩短一半时间.
图 10为同一份矢量数据采用不同划分方式构建的矢量瓦片加载对比图，展示了随着时间的变化，不同划分方式的矢量瓦片的加载情况.从图 10中可以看出，采用本文提出的稠疏格网划分方法构建的矢量瓦片在加载渲染时比均匀格网划分方式下构建的矢量瓦片更加平滑，所需时间更少，用户体验更佳.
|
图 10 稠疏矢量瓦片与均匀矢量瓦片加载对比 Fig. 10 Loading contrast between dense-sparse vector tiles and uniform divided tiles |
与传统的金字塔模型矢量瓦片构建方法相比，本文提出的顾及要素空间分布的矢量瓦片优化构建方法能够在保证金字塔模型多层次分辨率特性的同时，保证各层级矢量瓦片的数据量相对均衡化.并采用Geohash编码方式对生成的瓦片进行编码，维持了瓦片间的空间邻近性，提升了瓦片的索引效率.实验结果表明, 该方法能够保证数据访问时的负载相对均衡化，减少数据传输量，避免出现单个瓦片由于数据量过大造成瓦片加载慢甚至无法加载的现象.
本文提出的稠疏矢量瓦片的构建方法可提高瓦片加载渲染效率，提升用户体验感.在未来的研究中，对于非均衡数据量的矢量瓦片优化构建仍需深入探索.主要从两方面考虑：一方面是优化稠疏矢量瓦片的索引调度策略，由于稠疏矢量瓦片的构建对每一层级中的子瓦片进行了层次划分，金字塔模型的瓦片索引方式在一定程度上增加了矢量瓦片查询的复杂度，增加了瓦片调度消耗的时间；另一方面是在稠疏矢量瓦片生成过程中，结合制图综合理论及方法，考虑简化要素，以减少每一层级的数据量.
| [1] |
周侗, 龙毅. 我国近期移动地图与互联网地图发展综述[J].
地理信息与地理信息科学, 2012, 28(5): 1–5.
ZHOU T, LONG Y. Review about recently development of mobile map and internet map in China[J]. Geography and Geo-Information Science, 2012, 28(5): 1–5. |
| [2] |
苏旭明, 谭建成. WebGIS中瓦片地图关键技术研究[J].
北京测绘, 2012(2): 9–12.
SU X M, TAN J C. The research of key technologies for the tile map in WebGIS[J]. Beijing Surveying and Mapping, 2012(2): 9–12. |
| [3] |
朱光, 杨耀东. 静态多分辨率层次模型技术的研究与实践[J].
测绘通报, 2014(2): 55–58.
ZHU G, YANG Y D. Research and practice of static multi-resolution level model technology[J]. Bulletin of Surveying and Mapping, 2014(2): 55–58. |
| [4] | ANTONIOU V, MORELEY J, HAKLAY M. Tiled vectors:A method for vector transmission over the web[C]//International Symposium on Web & Wireless Geographical Information Systems.Heidelberg:Springer, 2009, 5886:56-71. |
| [5] |
孙璐, 陈荦, 刘露, 等. 一种面向服务器制图可视化的矢量数据多尺度组织方法[J].
计算机工程与科学, 2014, 36(2): 226–232.
SUN L, CHEN L, LIU L, et al. A muti-scale management method for visualization of vector data on server cluster[J]. Computer Engineering & Science, 2014, 36(2): 226–232. |
| [6] |
王亚平, 蒲英霞, 刘大伟, 等. 基于TileStache的多源投影矢量数据瓦片生成技术研究[J].
地理信息世界, 2015, 22(1): 77–81.
WANG Y P, PU Y X, LIU D W, et al. Research on the tile generation of multi-projections vector data based on TileStache[J]. Geomatics World, 2015, 22(1): 77–81. |
| [7] |
孙晨龙, 霍亮, 高泽辉. 基于矢量瓦片的矢量数据组织方法研究[J].
测绘与空间地理信息, 2016, 39(4): 122–124.
SUN C L, HUO L, GAO Z H. A method of vector data organization based on vector tile[J]. Geomatics & Spatial Information Technology, 2016, 39(4): 122–124. |
| [8] | SAMPLE J T, IOUP E. Tile-Based Geospatial Information System[M]. Berlin: Springer-Verlag, 2010. |
| [9] | BUTLER H, DALY M, DOYLE A, et al. The GeoJSON format specification[EB/OL].[2008-06-01].http://geojson.org/geojson-spec.html. |
| [10] |
陈德权. 基于GeoJSON的WFS实现方式[J].
测绘科学技术学报, 2011, 28(1): 66–69.
CHEN D Q. The realization of WFS based on GeoJSON[J]. Journal of Geomatics Science and Technology, 2011, 28(1): 66–69. |
| [11] |
黄明. 基于空间分区的空间聚类研究[D]. 武汉: 武汉大学, 2010.
HUANG M.The Research on Spatial Data Clustering based on Space Partition[D]. Wuhan:Wuhan University, 2010. http://cdmd.cnki.com.cn/Article/CDMD-10486-1011065961.htm |
| [12] |
郭宁, 吴秋云, 熊伟, 等. 大规模栅格数据集的瓦片金字塔快速构建方法[J].
地理信息世界, 2015, 22(6): 43–50.
GUO N, WU Q Y, XIONG W, et al. An efficient method of building tile-pyramid for massive raster dataset[J]. Geomatics World, 2015, 22(6): 43–50. |
| [13] | WIKIPEDIA.Geohash[EB/OL].[2015-06-06]. http://en.wikipedia.org/wiki/Geohash. |
| [14] |
侯志通. 条带状公路运营管理空间大数据降维组织及混合存储关键技术研究[D]. 杭州: 浙江大学, 2007.
HOU Z T.Research on Key Technologies of Dimension Reduction Storage and Hybrid Management for Striping spatial Big Data in Highway operation Management[D]. Hangzhou:Zhejiang University, 2007. http://cdmd.cnki.com.cn/Article/CDMD-10335-1015321851.htm |