基于GeoJSON-VT动态生成大规模GeoJSON文件的矢量瓦片

发表于 | 分类于 | | 本文总阅读量 次

本文主要内容来自Mapbox官方博客，感兴趣的童鞋可以点击此处浏览原文。

GeoJSON作为JSON在地理空间领域的扩展格式，已经在各类Web应用中广泛使用。对于少量数据而言，直接调用Leaflet、Openlayers等地图应用库的原生API进行渲染并不存在什么问题。但当数据量较大时，这种做法显然效率低下，对此不妨考虑采用矢量瓦片来解决问题。

下面是一个简单的例子。使用Mapbox GL JS可以在数秒内完成全美邮政边界的GeoJSON文件(106 MB)加载，该文件包含33,000多个Feature，涉及超过5,400,000个点。整个加载过程不需要依赖后台服务器，直接在浏览器中完成。

可以看到整个浏览体验是很平滑的，那么到底是如何实现的呢？

矢量瓦片

对于这么大的数据量，显然不可能对所有数据实现60 FPS的渲染，但实际上也没有必要这样做，因为：

  • 在较低层级上，并不需要将所有矢量细节完全表现出来
  • 在较高层级上，大部分数据实际上是处于屏幕以外的

为了满足各层级的浏览需要，一种优化策略是将GeoJSON分割为矢量瓦片。该项工作通常会使用服务器端的工具完成，比如Mapnik和PostGIS。

那么我们是否可以直接在浏览器中动态生成矢量瓦片？为了这个目标，Vladimir Agafonkin实现了一个JavaScript库——geojson-vt。

由于实际效果出奇的好，这个库也被进一步发扬光大了：

  • 它被用于Mapbox GL JS中的GeoJSON渲染工作
  • 它被移植为C++ 14版本，用于支持Mapbox Mobile在移动设备上的动态点线渲染
  • 它通过Node.js在服务器端也能有效运行，因此Mapbox团队也在利用该库的方法改进服务器端的数据处理流程

GeoJSON-VT工作原理

预处理

生成瓦片通常会涉及到很多计算密集的步骤：

  • 将地理坐标投影为屏幕坐标
  • 为每个缩放级别优化线面细节
  • 在特定级别上过滤掉微小细节
  • 将整个数据分割为各层级瓦片

GeoJSON-VT正是按照上述步骤顺序来工作的：先投影，再简化，最后分割瓦片。这样在生成各层级瓦片时，可避免许多重复操作。

那么第一步就是坐标投影，按照Web Mercator投影，将GeoJSON中的地理坐标投影至[0..1,0..1]范围。这样就可通过下面的公式得到屏幕坐标：
screen_x = [tile_size × (2^zoomx - tile_x)]
screen_y = [tile_size × (2^zoomy - tile_y)]

第二步则是数据简化，以便减少瓦片中的细节数量。这里采用的是Ramer-Douglas-Peucker simplification algorithm(某些地方称为RDP算法)，通过递归的方式查找一条折线中的重要点，舍弃不必要的细节。

Leaflet和simplify-js也是采用的该方法，但GeoJSON-VT并没有在查找完成后立即删除非必要点，而是给每个结点赋予了不同的权重，从而便于在不同层级上快速实现结点的包含或排除。

第三步是计算面积和长度，根据每个多边形的面积和每条折线的长度为其赋予相应的权值，从而在特定层级上过滤掉过于微小的几何要素。

最后一步，保存所有要素的包围盒，这样可以使分割操作更加高效。

瓦片分割

直接将整个GeoJSON文件分割为最细粒度的瓦片无疑是很慢的（可以参考这篇文章），那么为了快速完成瓦片分割，GeoJSON-VT采用的是由上至下、分而治之的方式：

  1. 将顶端的z0瓦片分割为4张z1瓦片；
  2. 将每张z1瓦片分割为4张z2瓦片；
  3. 递归上述步骤。

这样每级瓦片只需要分割其上一级瓦片中的要素即可，但这里还可以进一步优化。

最常用的多边形分割算法Sutherland-Hodgeman，如下图所示：

为了分割上一级瓦片，要用到图中红色轴平行线组成的4个半平面。而每一条轴平行线，都需要遍历上一次分割的所有点。

值得注意的是，每一张分割的瓦片并不正好是上一级瓦片的1/4，因为每张瓦片都需要保留一小块缓冲区解决渲染问题（比如Mapbox Studio Classic对每张512 pix瓦片在每个方向默认保存8 pix的缓冲区）。

假设上一级瓦片中包含n个要素，那么分割4张瓦片的耗时大约是：
4 × (n + 1/2n + 1/4n + 1/4n) = 8n

那么这里Vladimir Agafonkin对半平面分割算法做了简单的修改，使得两条轴平行线之间的分割一次性完成：分割“条带”。这样就可以先利用垂直方向的条带将上一级瓦片分割为两部分，然后再利用水平方向的条带将子瓦片分割出来。

这样耗时就会变成：
n + n + 4 × 1/2n = 4n

于是相比原先的分割过程，效率变为2倍。

最后，在预处理阶段保存的要素包围盒也能派上用场了。在较低层级上，如果要素包围盒在当前瓦片内，则完全保留，否则直接跳过。这样就无需再对每个点的权重进行遍历了，整个处理过程又将进一步加快。

动态分割

要实现无延迟的动态瓦片生成，一般会考虑将所有矢量瓦片缓存，从而能够在请求时立即提供服务。对于小数据量没有问题，但当数据量较大时，内存将无法满足需要。仅仅是第15级，就有4^15=~1,000,000,000张瓦片，对于浏览器而言是难以处理的。

既然无法分割到最细粒度，那么还是可以考虑分割到一个中间状态，当后续请求到来时，能够在不可察觉的延迟内完成瓦片分割。GeoJSON-VT通过以下方式来实现该目标：

  1. 刚开始，将瓦片分割至特定层级，后续分割工作将以按需分割的形式完成；
  2. 在初始分割的过程中，记录每张瓦片所包含的点数目，当某张瓦片的点数目低于阈值（默认设为100,000个点）时，则停止初始分割；
  3. 当放大至某张瓦片的过程中，GeoJSON-VT在每一级仅将1张瓦片分割为4张子瓦片，并将分割结果缓存。

根据原作者的测试情况，他发现初始分割设置在第5级或者100k点的阈值是比较好的，这样初始分割相对够快，同时后续分割几乎是立即完成。

当然，在上述算法的每一步都需要将内存使用最小化：

  1. 原始矢量数据仅在最低层级保存，一旦放大至下一级则只保存简化数据，这样当分割的瓦片越多时内存不需要将指数级增长的瓦片数据全部保留；
  2. 所有的递归操作都通过迭代算法清空，数据简化和瓦片分割都是基于数据队列实现，当某个几何数据不再需要时就不会一直占据内存空间；
  3. 处于(0..1,0..1)中的投影坐标仅在按需分割时转换为屏幕坐标，这样在分割瓦片时不需要将所有瓦片的坐标都进行转换，从而节省内存空间；
  4. 当瓦片完全处于某多边形内部的时候，则不再进行分割，因为不论层级再如何变化，父瓦片与子瓦片均完全一致，没有区别。

调试与性能分析

为便于调试和优化GeoJSON-VT，作者写了一个调试页面，将GeoJSON文件拖拽至页面，GeoJSON-VT便将开始处理：

该API库还提供了带有2个日志级别的debug选项，配置后会进行性能计时和日志记录。上图展示的是Level 1记录，Level 2会输出每个分割瓦片的信息，从而帮助追踪性能瓶颈和代码可能存在的问题。

平滑渲染

尽管GeoJSON-VT已经很快了，加载和处理大规模GeoJSON数据依然会消耗很长的CPU时间。通常浏览器会在同一个线程中处理UI更新和用户交互，于是当JavaScript进行重负荷计算时，页面会冻结，不再接受用户输入。为了避免数据载入与处理导致的延迟和冻结，Mapbox GL JS调用了Web Workers，允许后台执行计算密集的任务而不干扰主线程。

另外还有一个问题，就是web worker与主线程之间的数据交换，通常会涉及内存数据的复制，也会导致主线程冻结。为了避免该瓶颈，Mapbox GL JS利用了HTML5的特性——Transferable Objects。如果将数据组织为typed arrays，就可以“零复制”实现线程间数据的瞬间交换。上述两个方式使得Mapbox GL JS实现了大规模矢量瓦片的平滑渲染。

使用GeoJSON-VT

如果使用的是基于Mapbox GL JS的工具（包括GL JS或Mapbox Mobile），那么实际上就已经在用GeoJSON-VT了。

当然，对于其他应用，也可以手动借助API进行使用：

1
2
3
var tileIndex = geojsonvt(data);
...
var tile = tileIndex.getTile(z, x, y);

输出的结果就是矢量瓦片，可以轻松完成渲染。