在线地图的点聚合算法及现状

1、在线地图的点聚合算法及现状Viky2014目录一、概述21)什么是地图综合？22)什么是点聚合？23)本文关注的重点2二、在线地图点聚合的算法3特点3必要性3运行方式3表现形式3算法31)基于网格的点聚合算法（Grid-based Clustering）32)基于距离的点聚合算法（Distance-based Clustering）53)基于方格和距离结合的点聚合算法（详细）74)基于距离和最少点数量限制的点聚合算法125)其他的可用于在线地图点聚合的算法14三、在线地图点聚合功能的实现情况14Openlayers14Google Maps15百度地图16高德地图17ESRI18腾讯地图（原

2、搜索地图）19天地图20四、小结20参考文献21一、 概述1) 什么是地图综合？地图综合所要解决的问题是把一个空间目标集合按照专题内容转换为一个最能代表该集合主要空间特征的更抽象的空间目标集合，并符号化该抽象后的空间目标集合，以最有效的方式传输地理空间知识。2) 什么是点聚合？点聚合（point cluster），或又叫点聚类，是地图综合的其中一种方法，主要解决地图中点要素很多时候的表示困难的问题。点聚合可以用少量的点或图标来表示地图中的所有点，让地图显示更清晰明朗。如Error! Reference source not found.所示。图 1 在线地图的点聚合示意图3) 本文关注的重点本

3、文主要关注二维在线电子地图中点的聚合显示所用到的算法和目前的在线地图对点聚合显示的支持情况。电子地图中，通常会遇到在某个地区包含成千上万个点要素的情况，若同时加载显示在电子地图中，会显得很乱、覆盖地图底图，也会占用大量系统资源，甚至引发浏览器的崩溃、卡顿，极大的影响用户体验，因此点聚合显示是电子地图十分需要的一项功能。目前的常见在线地图（或其API）是否支持点聚合？若支持点聚合的算法是什么？是一个值得关注的问题。本文尝试对这两个问题进行解答。二、 在线地图点聚合的算法特点a) 数据相对简单，只有点要素，点没有形状变化，因此没有形状对聚合影响。b) 没有评价聚合精确度的唯一指标，（不考虑运行速度

4、的情况下）不同的算法不同的显示方式对用户体验影响并不会太大。c) 可能需考虑的方面：聚合点中包含的原始点要素最大数量限制、聚合点间的距离限制、点要素的权重、部分缩放级别是否该显示聚合点等。d) 一般的点聚合（聚类）算法对在线地图点聚合虽适用（如K均值法等），但需平衡运行效率和必要性，并且极少见这些复杂方法应用实际的在线地图中。必要性目前在线地图的点聚合算法已有较成熟的应用，不少在线地图均提供点聚合的功能及API。点聚合算法虽然相对简单，但却很实用，若缺少了，在线地图则无法对大数据量的点要素进行较好的显示。对于在线地图的二次开发者来说，这也是一个十分重要的功能，例如要在地图上显示同一个站点中的多

5、个传感器等，若缺少点聚合功能的支持，则是几乎无法辨别清楚地图上的这些传感器点要素。运行方式点聚合的运算可以放在客户端（浏览器），也可以放在服务端运算（如Google Maps的融合表）完毕再传给客户端。表现形式在计算机上表现地点的点聚合方式多种多样，并无定论，聚合后的显示样式，不同缩放级别下是否显示不同图标或在以下列举几种常见的表现形式：l 多个点聚合后还是点要素，换不同图标显示，或在图标中同时显示该聚合点所包含的原始点要素的数量，点击聚合点后，地图视图会自动切换到该聚合点所包含的所有点的最小包围盒地图范围中。l 多个点聚合后还是点要素，换不同图标显示，或在图标中同时显示该聚合点所包含的原始点

6、要素的数量，点击聚合点后，地图会弹出该聚合点的所聚合的所有点的位置信息，但并不缩放和移动地图。l 多个点聚合后是面要素，以颜色或数字表示所聚合的点的数量，点开后若单位面积内若依然包含较多点则继续显示面要素，若点较少则显示原始的点要素。此种方法较少见，常见于上述两种方法。算法本文关注的重点是在线地图点聚合算法的大致情况，而不是每个算法详细的运行效率和优劣情况。因此，以下对可搜到的在线地图点聚合算法进行简要列举：1) 基于网格的点聚合算法（Grid-based Clustering）原理：将地图划分成指定尺寸的正方形（每个缩放级别不同尺寸），然后将落在对应格子中的点聚合到该正方形中（正方形的中心）

7、，最终一个正方形内只显示一个点，并且点上显示该聚合点所包含的原始点的数量。优点：运算速度较快，每个原始点只需计算一次，没有复杂的距离计算。缺点：有时明明很相近的点，却仅仅因为网络的分界线而被逼分开在不同的聚合点中，此外，聚合点的位置采用的是该网格的中心，而非该网格的质心，这样聚合出来的点可能不能较精确反映原始点的信息。使用此算法的在线地图：缺。以下是Google给出的一个基于距离的点聚合示意图：图 2 基于网格的点聚合算法（聚合前）图 3 基于网格的点聚合算法（聚合后）2) 基于距离的点聚合算法（Distance-based Clustering）原理：根据点与点之间的距离进行聚合，对每个点进

8、行迭代，若被迭代的点在某个已有聚合点的指定阈值的距离范围内，那么这个点就聚合到该点，否则则新建一个聚合点，如此循环，但聚合后的点的坐标依然是该聚合点创建时的第一个点的坐标位置。优点：聚合点较精确的反映了所包含的原始点要素的位置信息。缺点：需要计算点与点之间的距离，计算相对复杂。使用此算法的在线地图：缺。以下是Google给出的一个基于距离的点聚合示意图：图 4 基于距离的点聚合算法（原始点要素）图 5 基于距离的点聚合算法（聚合过程）图 6 基于距离的点聚合算法（聚合结果）聚合点（Cluster）原始点要素（Markers）蓝1红2黄7、8绿3、4、6粉红5浅绿9表 1基于距离的点聚合算法（聚

9、合结果）3) 基于方格和距离结合的点聚合算法（详细）原理：初始时没有任何已知聚合点，然后对每个点进行迭代，计算一个点的外包正方形，若此点的外包正方形与现有的聚合点的外包正方形不相交，则新建聚合点（区别于前面基于直接距离的算法，这里不是计算点与点间的距离，而是计算一个点的外包正方形，正方形的变长由用户指定或程序设置一个默认值），若相交，则把该点聚合到该聚合点中，若点与多个已知的聚合点的外包正方形相交，则计算该点到到聚合点的距离，聚合到距离最近的聚合点中，如此循环，直到所有点都遍历完毕。每个缩放级别都重新遍历所有原始点要素。此方法可以算是基于方格与基于距离的算法的一个结合算法。优点：运算速度相对较

10、快，每个原始点只需计算一次，可能会有点与点距离计算，聚合点较精确的反映了所包含的原始点要素的位置信息。缺点：速度不如完全基于方格的速度快等。使用此算法的在线地图：Google Maps。以下是Google给出的一个基于方格距离的点聚合示意图：步骤示例：a) 默认输入的数组的顺序是如Error! Reference source not found.所示的字母顺序。b) 初始计算，从A开始迭代，此时并没有任何聚合点，则在A的位置生成一个聚合点（设为A1），A1的位置与A相同。c) 迭代到B，如Error! Reference source not found.所示，由于B的外包正方形与已有聚合点

11、A1的外包正方形相交，所以B应聚合到A1中，新聚合后的聚合点的位置依然保持在A1原来的位置（这主要是因为若采用A与B的质心会花费客户端较大的计算量，这在原始点要素数量较大时影响较大）。d) 迭代到C，由于C的外包正方形不与现有的聚合点A1相交（目前只有A1一个聚合点），因此C需要新建一个新的聚合点（设为C1）。e) 迭代到D，类似于B，D与A1聚合，聚合后依然为A1。f) 迭代到E，新的问题来了，E的外包正方形同时与A1和C1相交，这时需判断E到A1、C1的距离，并将E聚合到距离近的那个聚合点中，这里E到C1更近，于是E聚合到了C1中。g) 剩下的如此迭代，直至完毕。图 7 基于方格距离的点聚

12、合算法（原始点要素）图 8 基于方格距离的点聚合算法（聚合过程）图 9 基于方格距离的点聚合算法（聚合结果）聚合点（Cluster）原始点要素（Markers）1A、B、D2C、E3F、G、J、I4H表 2基于方格距离的点聚合算法（聚合结果）图 10 基于方格距离的点聚合算法（更高缩放级别的聚合结果）图 11 基于方格距离的点聚合算法（缩放到只有一个聚合点的聚合结果）4) 基于距离和最少点数量限制的点聚合算法原理：此算法相当于先执行完基于距离的点聚合算法，然后再进行一次聚合点的分解。每个聚合点成立的条件是所聚合的原始点要素的数量应大于程序默认或用户指定的最少数量限制，否则将解散这个聚合点。此方

13、法甚至不能算是一个独立的算法，因为此算法的前后相互独立，类比的，其实也可以建议一种“基于网格和最少点数量限制”的点聚合算法。优点：聚合后的显示相对精确，对显示的控制更灵活。缺点：运算速度相对较慢，因为本身基于距离的点聚合算法就已经是相对较慢了，再加上后期根据最少数量限制的阈值进行点聚合分解，速度更慢。使用此算法的在线地图：Openlayers（Openlayers是一个开源的Javascript库（基于修改过的BSD许可发布），用来在Web浏览器显示地图【维基百科】）。以下是Openlayers官方Javascript源码的算法核心：cluster: function(event) if(!e

14、vent | event.zoomChanged) & this.features) var resolution = this.layer.map.getResolution(); if(resolution != this.resolution | !this.clustersExist() this.resolution = resolution; var clusters = ; var feature, clustered, cluster; for(var i=0; i=0; -j) cluster = clustersj; if(this.shouldCluster(cluste

15、r, feature) this.addToCluster(cluster, feature); clustered = true; break; if(!clustered) clusters.push(this.createCluster(this.featuresi); this.clustering = true; this.layer.removeAllFeatures(); this.clustering = false; if(clusters.length 0) if(this.threshold 1) var clone = clusters.slice(); cluster

16、s = ; var candidate; for(var i=0, len=clone.length; ilen; +i) candidate = clonei; if(candidate.attributes.count this.threshold) Atotype.push.apply(clusters, candidate.cluster); else clusters.push(candidate); this.clustering = true; / A legitimate feature addition could occur during this / ad

17、dFeatures call. For clustering to behave well, features / should be removed from a layer before requesting a new batch. this.layer.addFeatures(clusters); this.clustering = false; this.clusters = clusters; ,shouldCluster: function(cluster, feature) var cc = cluster.geometry.getBounds().getCenterLonLa

18、t(); var fc = feature.geometry.getBounds().getCenterLonLat(); var distance = ( Math.sqrt( Math.pow(cc.lon - fc.lon), 2) + Math.pow(cc.lat - fc.lat), 2) ) / this.resolution ); return (distance = this.distance);,摘自（2014.01.06）：/openlayers/openlayers/blob/master/lib/OpenLayers/Strategy

19、/Cluster.js5) 其他的可用于在线地图点聚合的算法一般的点聚合（聚类）算法对在线地图点聚合均适用（如K均值法等），但考虑运行效率和必要性的问题，因此，这里在不作运行效率、应用的在线地图等的评价。普通的遥感和GIS的图像聚类方法其实也可以应用在在线地图的点聚合中，由于运行的效率不高、实现容易程度难和必要性的不充分等原因可能并不适合实际运行，这里仅列举一些常见的遥感和GIS聚类方法：a. 启发式的方法：k-平均值(k- means)和k-中心点(k- medoids)等b. 层次方法(Hierarchy method): 对给定数据对象集合进行层次的分解 c. 基于密度的方法(Densi

20、ty-based method)：DBSCAN和OPTICS等d. 基于模型的方法(Model-based Method): 基于模型的方法为每个簇假定了一个模型, 寻找数据对给定模型的最佳拟合在日后的在线地图的发展中，不排除由于新的其他需求而重新在其中使用上述这些额外的复杂算法。三、 在线地图点聚合功能的实现情况目前来说，由于在线地图的点聚合算法在算法难度和实现难度上均不难，也基本能解决地图上大数据量点显示的问题，所以算法本身可能并不是大部分地图用户和地图开发者所关心的问题，他们最关心的可能是该地图是否支持点聚合显示功能，该地图的开放API是否可以调用点聚合功能等问题。因此，本文对目前一些常

21、用在线地图的点聚合功能进行调查，并列举其中的情况。Openlayers类型：开源的Javascript库，用来在Web浏览器显示地图。是否支持点聚合显示：支持是否支持点聚合API调用：支持点聚合所用算法：基于距离和最少点数量的点聚合算法点聚合官方地址：/docs/files/OpenLayers/Strategy/Cluster-js.html/releases/OpenLayers-2.13.1/examples/strategy-cluster-extended.htmlhttps:/githu

22、/openlayers/openlayers/blob/master/lib/OpenLayers/Strategy/Cluster.js点聚合功能实例：/dev/examples/strategy-cluster-threshold.html 图示：图 12 Openlayers点聚合示例Google Maps 类型：在线地图是否支持点聚合显示：支持是否支持点聚合API调用：支持点聚合所用算法：基于方格和距离结合的点聚合算法。算法开源。点聚合官方地址：/maps/articles/too

23、manymarkers点聚合功能实例：/svn/trunk/markerclusterer/1.0/examples/advanced_example.html图示：图 13 Google Maps点聚合示例特殊功能：Google Maps支持服务端的点聚合功能（将点聚合的算法运算转移到服务器端，运行完毕后再将聚合后的结果传到客户端中），Google通过FusionTablesLayer（融合表，链接）和KmlLayer两种服务端的方式。基于融合表的一个在线示例：http:/gmaps-samples-v3.g

24、/svn/trunk/fusiontables/cycletrails.html。百度地图类型：在线地图是否支持点聚合显示：支持是否支持点聚合API调用：支持点聚合所用算法：基于方格和距离结合的点聚合算法，支持是否将聚合点的位置放置在被聚合的点的质心或第一个被聚合的点中，支持指定在何种级别才显示点或聚合点，支持限制最少聚合点数量。算法开源。点聚合官方地址：/library/MarkerClusterer/1.2/docs/symbols/BMapLib.MarkerClusterer.html点聚合功能实例：http:/d

25、/map/jsdemo.htm#c1_4图示：图 14 百度地图点聚合示例高德地图类型：在线地图是否支持点聚合显示：支持是否支持点聚合API调用：支持点聚合所用算法：与百度地图基本一致。点聚合官方地址：/Javascript/reference/plugin#AMap.MarkerClusterer点聚合功能实例：/javascript/example/num/0509图示：图 15 高德地图点聚合示例ESRI类型：地图API（如Javascript、Flex、Silverli

26、ght等）是否支持点聚合显示：支持是否支持点聚合API调用：支持点聚合所用算法：同时支持基于网格的和基于点权重，等。点聚合官方地址：（Flex）/en/flex/api-reference/（Flex）/en/help/flex-viewer/concepts/index.html#/01mz点聚合功能实例：/en/flex/sample-code/clustering.htm图示：图 16 ESRI的FLex API地图点聚合示例腾讯地图（原 搜搜地图）类型：在线地图是否支持点聚合显示：不支持是否支持点聚合API调用：不支持关于不支持的相关地址和说明：