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

《在线地图的点聚合算法及现状.docx》由会员分享，可在线阅读，更多相关《在线地图的点聚合算法及现状.docx（10页珍藏版）》请在优知文库上搜索。

1、在线地图的点聚合算法及现状Viky2014目录一、概述1）什么是地图综合？地图综合所要解决的问题是把一个空间目标集合按照专题内容转换为一个最能代表该集合主要空间特征的更抽象的空间目标集合，并符号化该抽象后的空间目标集合，以最有效的方式传输地理空间知识.2）什么是点聚合？点聚合（pointc1.uster）,或又叫点聚类，是地图综合的其中一种方法，主要解决地图中点要素很多时候的表示困难的问题点聚合可以用少量的点或图标来表示地图中的所有点，让地图显示更清晰明朗.如所示.图I-在线地图的点聚合示意图3）本文关注的重点本文主要关注二维在线电子地图中点的聚合显示所用到的算法和目前的在线地图对点聚合显示的

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

3、含的原始点要索最大数量限制、聚合点间的距圈限制、点要素的权重、部分缩放级别是否该显示聚合点等.d）一般的点聚合（聚类）算法对在线地图点聚合虽适用（如K均值法等）,但需平衡运行效率和必要性，并且极少见这些豆杂方法应用实际的在线地图中.必要性目前在线地图的点聚合算法已有较成熟的应用不少在线地图均提供点聚合的功能及API.点聚合算法虽然相对简单，但却很实用，若缺少了，在线t也图则无法对大数据量的点要素进行较好的显示。对于在线地图的二次开发者来说，这也是一个十分重要的功能，例如要在地图上显示同一个站点中的多个传感器等，若缺少点聚合功能的支持，则是几乎无法辨别清楚地图上的这些传感器点要素.运行方式点聚合

4、的运算可以放在客户端（浏览器），也可以放在服务端运算（如Goog1.eMaps的融合表）完毕再传给客户端.表现形式在计算机上表现地点的点聚合方式多种多样，并无定论，聚合后的显示样式，不同缩放级别下是否显示不同图标或在以下列举几种常见的表现形式： 多个点聚合后还是点要素,换不同图标显示，或在图标中同时显示该聚合点所包含的原始点要素的数量，点击聚合点后，地图视图会自动切换到该聚合点所包含的所有点的最小包围盒地图范围中。 多个点聚合后还是点要素，换不同图标显示，或在图标中同时显示该聚合点所包含的原始点要素的数量，点击聚合点后，地图会弹出该聚合点的所聚合的所有点的位置信息，但并不缩放和移动地图. 多个

5、点聚合后是面要素，以颜色或数字表示所聚合的点的数量,点开后若单位面积内若依然包含较多点则继续显示面要素,若点较少则显示原始的点要索。此种方法较少见，常见于上述两种方法.第法本文关注的重点是在线地图点聚合算法的大致情况，而不是每个算法详细的运行效率和优劣情况.因此，以下对可搜到的在线地图点聚合算法进行简要列举：D基于网格的点聚合算法（Grid-basedC1.ustering）原理：将地图划分成指定尺寸的正方形（每个缩放级别不同尺寸），然后将落在对应格子中的点聚合至峻正方形中（正方形的中心），最终一个正方形内只显示一个点，并且点上显示该聚合点所包含的原始点的数量。优点：运算速度较快，每个原始点只

6、需计算一次，没有旦杂的距离计算.缺点：有时明明很相近的点，却仅仅因为网络的分界线而被逼分开在不同的聚合点中，此外，聚合点的位置采用的是该网格的中心，而非该网格的质心，这样聚合出来的点可能不能较精确反映原始点的信息。使用此苴法的在线地图：缺。以下是Goog1.e给出的一个基于距离的点聚合示意图：图2-基于网格的点聚合算法（聚合前）图3-基于网格的点聚合算法（聚合后）2）基于距离的点聚合弹法（Distance-basedC1.ustering）原理：根据点与点之间的距离进行聚合，对每个点进行迭代，若被迭代的点在某个已有聚合点的指定阈值的距离范围内用法这个点就聚合到该点,否则则新建一个聚合点,如此循

7、环,但聚合后的点的坐标依然是该聚合点创建时的第一个点的坐标位置.优点：聚合点较精确的反映了所包含的原始点要素的位置信息.缺点：需要计算点与点之间的距离，计算相对复杂。使用此算法的在线地图：缺.以下是Goog1.e给出的一个基于距离的点聚合示意图：图4-基于距离的点聚合算法（原始点要素）图5-基于距高的点聚合算法（聚合过程）图6-基于距图的点聚合算法（聚合结果）蓝1红2黄7、8绿3、4、6粉红5i三9表1基于距离的点聚合算法（聚合结果）3）基于方格和距离结合的点聚合算法（详细）原理：初始时没有田可已知聚合点，然后对每个点进行迭代，计算一个点的外包正方形，若此点的外包正方形与现有的聚合点的外包正方

8、形不相交，则新建聚合点（区别于前面基于直接距离的算法,这里不是计算点与点间的距离，而是计算一个点的勺袍正方形，正方形的变长由用户指定或程序设置一个默认值），若相交，则把该点聚合到该聚合点中,若点与多个已知的聚合点的夕也正方形相交，则计算该点到到聚合点的距离,聚合到距离最近的聚合点中，如此循环，直到所有点都遍历完毕.每个缩放级别都重新遍历所有原始点要素.此方法可以算是基于方格与基于距离的算法的一个结合算法.优点：运算速度相对较快，每个原始点只需计算一次，可能会有点与点距离计算，聚合点较精确的反映了所包含的原始点要素的位置信息.缺点:速度不如完全基于方格的速度快等。使用此算法的在线地图:Goog1

9、.eMaps.以下是Goog1.e给出的一个基于方格距离的点聚合示；步骤示例：a）默认输入的数组的顺序是如所示的字母顺序.b）初始计算，从A开始出弋，此时并没有任何聚合点，则在A的位置生成一个聚合点（设为A1.）,A1.的位置与A相同.c）迭代到B,如所示，由于B的外包正方形与已有聚合点A1.的外包正方形相交，所以B应聚合到A1.中，新聚合后的聚合点的位置依然保持在A1.原来的位置（这主要是因为若采用A与B的质心会花费客户端较大的计算量，这在原始点要素数量较大时影响较大、d）迭代到C,由于C的外包正方形不与现有的聚合点A1.相文目前只有A1.一个聚合点），因此C需要新建一个新的聚合点（设为C1

10、.e）迭代到D,类似于B,D与A1.聚合，聚合后依然为A1.f）迭代到E,新的问题来了,E的勺徇正方形同时与A1.和C1.相交这时需判断E到A1.C1.的距离，并将E聚合到距离近的那个聚合点中,这里E到C1.更近，于是E聚合到了C1.中.g）剩下的如此迭代，直至完毕.图7-基于方格距离的点聚合算法（原始点要素）图8-基于方格距离的点聚合算法（聚合过程）图9-基于方格距离的点聚合算法（聚合结果）1 A、B、D2 UE3 F、G、J、I4 H表2基于方格距离的点聚合算法（聚合结果）图10-基于方格距离的点聚合算法（更高缩放级别的聚合结果）图I1.-基于方格距离的点聚合算法（缩放到只有一个聚合点的聚

11、合结果）4）基于距商和最少点数量限制的点鬃合算法原理：此算法相当于先执行完基于距离的点聚合算法，然后再进行一次聚合点的分解。每个聚合点成立的条件是所聚合的原始点要素的数量应大于程序默认或用户指定的最少数量限制，否则将解散这个聚合点。此方法层至不能算是一个独立的算法，因为此算法的前后相互独立，类比的，其实也可以建议一种基于网格和最少点数量限制的点聚合算法.优点：聚合后的显示相对精确，对显示的控制更灵活。缺点：运算速度相对较慢,因为本身基于距离的点聚合算法就弹是相对较慢了，再加上后期根据最少数量限制的阈值进行点聚合分解，速度更慢.使用此算法的在线地图:Open1.ayers（Open1.ayers

12、易一Hni的Javcript（。于懈蛔的BSD即啄布）,用泉在Web制城冏阪IBS*三I4以下是OPenIayerS官方Javascript源码的算法核心：c1.uster:function(event)if(!event|&if(reso1.ution!=|!()=reso1.ution;varc1.usters=;varfeature,c1.ustered,c1.uster;feature=i;ifc1.ustered=fa1.se;for(varj=J=0;-j)c1.uster=c1.ustersj;if(c1.uster,feature)(c1.uster,feature);c1.u

13、stered=true;break;)if(!c1.ustered)i)；)=true;=fa1.se;ifO)ifDvarc1.one=();c1.usters=;varcandidate;for(vari=0,Ien=;i1.en;+i)candidate=c1.onei;e1.se(candidate);)=true;Forc1.usteringtobehavewe1.1.,features=fa1.se;)=c1.usters;)ShouIdCIuster:function(c1.uster;feature)vardistance=(-,2)+(-.2)/)；return(distan

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

15、d):DBSCAN和OPTICS等d.基于模型的方法(ModeI-basedMethod):基于模型的方法为每个簇假定了一个模型,寻找数据对给定模型的最佳拟合在日后的在线地图的发展中，不排除由于新的其他需求而重新在其中使用上述这些额外的复杂算法。三、在线地图点聚合功能的实现情况目前来说,由于在线地图的点聚合算法在算法难度和实现难度上均不难,也基本能解决地图上大数据量点显示的问题,所以算法本身可能并不是大部分地图用户和地图开发者所关心的问题，他们最关心的可能是该地图是否支持点聚合显示功能，该地图的开放API是否可以调用点聚合功能等问题.因此,本文对目前一些常用在线地图的点聚合功能进行调查，并举其中的情况.Open1.ayers类型：开源的JaVaSCriPt库，用来在Web浏览器显示地图.是否支持点聚合显示：支持是否支持点聚合API调用：支持点聚合所用算法：基于距离和最少点数量的点聚合算法点聚合官方地址：点聚合功能实例：图示：图12-0Pen1.ayerS点聚合示例G