利用Supercluster实现百万级点数据的实时聚类可视化

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

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

在线地图上浏览点数据最常见的应用需求之一，众多JS库(Leaflet、Openlayers、Mapbox、Mapzen、CARTO等等)都可以很轻松地实现。然而，但点数据规模达到一定程度后，直接对每个点进行渲染是不现实的，尤其是在点数据集达到百万级以上的时候。

Mapbox GL JS提供了point clustering功能，可使浏览器迅速完成400,000点数据的处理：

通过样式修改，还可将其转化为热力图表达：

在这项功能背后，是一个名为Supercluster的JavaScript聚类库，下面将该库的实现思路进行介绍。

层次贪心聚类

在某个特定缩放层级上，对点数据集进行聚类时，最直接的方法就是贪心聚类，流程如下：

  1. 选择点数据集中的任意一点；
  2. 以该点为中心，查找一定范围内的所有点；
  3. 通过上一步找到的邻近点生成一个点簇；
  4. 选择已生成点簇以外的某个点，重复上述步骤。

然而，在每一级地图上使用贪心聚类的代价太高，每变化一次缩放级别就得重新聚类一次，并且随着地图的放大，点簇的数目会呈指数级增长。

考虑到不同层级的点簇之间存在着关联，很自然地可以想到重复利用聚类结果。比如从18级到17级，可以将18级的聚类结果进行分组合并。随着地图的缩小，需要处理的点簇也会呈指数级下降，这样整个聚类过程就会快很多。

这种方法也就是层次贪心聚类，它已经被Dave Leaver实现为Leaflet.markercluster，Leaflet的常用插件之一。

尽管这种方法很简单，但已足够用来处理浏览器中的百万级点数据集了，也足以满足交互式地图浏览的需求。

点簇索引

当然，交互式地图中的层次贪心聚类实现依然存在两类代价高昂的操作：

  1. 查找一定范围内的所有点；
  2. 查找屏幕内的所有点簇。

范围查询最简单的实现方式就是遍历所有点，然后保存处于查询范围内的点。但是如果对每个潜在点簇进行查询，效率还是会很低。同样地，当用户拖拽或缩放屏幕时，也没有必要去遍历屏幕以外的点了。

为了使上述两类操作更加高效地完成，我们必须使用空间索引，将点数据集一次性地组织为特定的数据结构，之后就能实现任意数量的实时查询。

空间索引是许多算法必不可少的部分，所以已经出现许多JavaScript库实现了快速空间索引，比如RBush。

虽然在每个缩放级别都需要对点数据集建立一次索引，但是这样可以在任意缩放级别都实现实时查询与浏览。

聚类性能实验

下面是对400,000个点进行聚类的实验结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
399601 points prepared in 123ms
z16: indexed in 516ms clustered in 156ms 46805 clusters
z15: indexed in 53.4ms clustered in 40.8ms 20310 clusters
z14: indexed in 12.4ms clustered in 17.2ms 10632 clusters
z13: indexed in 7.9ms clustered in 12.9ms 6578 clusters
z12: indexed in 3.4ms clustered in 6.9ms 4514 clusters
z11: indexed in 2.4ms clustered in 3.4ms 3252 clusters
z10: indexed in 1.4ms clustered in 2.3ms 2329 clusters
 z9: indexed in 1ms clustered in 1.5ms 1608 clusters
 z8: indexed in 0.6ms clustered in 1.5ms 1083 clusters
 z7: indexed in 0.4ms clustered in 0.7ms 721 clusters
 z6: indexed in 0.2ms clustered in 0.4ms 421 clusters
 z5: indexed in 0.1ms clustered in 0.2ms 202 clusters
 z4: indexed in 0.1ms clustered in 0.1ms 82 clusters
 z3: indexed in 0ms clustered in 0ms 34 clusters
 z2: indexed in 0ms clustered in 0ms 14 clusters
 z1: indexed in 0ms clustered in 0ms 7 clusters
 z0: indexed in 0ms clustered in 0ms 3 clusters
total time: 972ms

Supercluster在1s内就完成了该数据集的聚类处理。而且使用Web Worker来完成该处理过程的话，不会影响主线程中的地图渲染过程。而当聚类完成后，任何范围查询都可以实时完成(1ms内)。

Supercluster使用方法

Supercluster API很简洁：

1
2
3
4
5
6
// cluster GeoJSON points
var index = supercluster({radius: 40, maxZoom: 16}).load(geojson.features);
// get GeoJSON clusters given a bounding box and zoom
var clusters = index.getClusters([-180, -85, 180, 85], 2);
// get a JSON vector tile in the same format as GeoJSON-VT
var tile = index.getTile(7, 523, 125);

由于Supercluster在Mapbox GL JS中表现出来的性能非常好，官方很大方地将其发布为一个独立的JavaScript库，以便于其它软件充分发挥该库的作用。

此外，也可以使用Node.js在服务器端进行聚类处理，然后通过Anand Thakker开发的vt-pbf module，将聚类结果转换为Mapbox矢量瓦片。

实际上，Supercluster也就300多行代码，是很好的学习素材。