在線地圖的點聚合算法及現(xiàn)狀

1、在線地圖的點聚合算法及現(xiàn)狀Viky2014目錄一、概述21)什么是地圖綜合？22)什么是點聚合？23)本文關(guān)注的重點2二、在線地圖點聚合的算法3特點3必要性3運行方式3表現(xiàn)形式3算法31)基于網(wǎng)格的點聚合算法（Grid-based Clustering）32)基于距離的點聚合算法（Distance-based Clustering）53)基于方格和距離結(jié)合的點聚合算法（詳細(xì)）74)基于距離和最少點數(shù)量限制的點聚合算法125)其他的可用于在線地圖點聚合的算法14三、在線地圖點聚合功能的實現(xiàn)情況14Openlayers14Google Maps15百度地圖16高德地圖17ESRI18騰訊地圖（原

2、搜索地圖）19天地圖20四、小結(jié)20參考文獻(xiàn)21一、 概述1) 什么是地圖綜合？地圖綜合所要解決的問題是把一個空間目標(biāo)集合按照專題內(nèi)容轉(zhuǎn)換為一個最能代表該集合主要空間特征的更抽象的空間目標(biāo)集合，并符號化該抽象后的空間目標(biāo)集合，以最有效的方式傳輸?shù)乩砜臻g知識。2) 什么是點聚合？點聚合（point cluster），或又叫點聚類，是地圖綜合的其中一種方法，主要解決地圖中點要素很多時候的表示困難的問題。點聚合可以用少量的點或圖標(biāo)來表示地圖中的所有點，讓地圖顯示更清晰明朗。如Error! Reference source not found.所示。圖 1 在線地圖的點聚合示意圖3) 本文關(guān)注的重點本

3、文主要關(guān)注二維在線電子地圖中點的聚合顯示所用到的算法和目前的在線地圖對點聚合顯示的支持情況。電子地圖中，通常會遇到在某個地區(qū)包含成千上萬個點要素的情況，若同時加載顯示在電子地圖中，會顯得很亂、覆蓋地圖底圖，也會占用大量系統(tǒng)資源，甚至引發(fā)瀏覽器的崩潰、卡頓，極大的影響用戶體驗，因此點聚合顯示是電子地圖十分需要的一項功能。目前的常見在線地圖（或其API）是否支持點聚合？若支持點聚合的算法是什么？是一個值得關(guān)注的問題。本文嘗試對這兩個問題進(jìn)行解答。二、 在線地圖點聚合的算法特點a) 數(shù)據(jù)相對簡單，只有點要素，點沒有形狀變化，因此沒有形狀對聚合影響。b) 沒有評價聚合精確度的唯一指標(biāo)，（不考慮運行速度

4、的情況下）不同的算法不同的顯示方式對用戶體驗影響并不會太大。c) 可能需考慮的方面：聚合點中包含的原始點要素最大數(shù)量限制、聚合點間的距離限制、點要素的權(quán)重、部分縮放級別是否該顯示聚合點等。d) 一般的點聚合（聚類）算法對在線地圖點聚合雖適用（如K均值法等），但需平衡運行效率和必要性，并且極少見這些復(fù)雜方法應(yīng)用實際的在線地圖中。必要性目前在線地圖的點聚合算法已有較成熟的應(yīng)用，不少在線地圖均提供點聚合的功能及API。點聚合算法雖然相對簡單，但卻很實用，若缺少了，在線地圖則無法對大數(shù)據(jù)量的點要素進(jìn)行較好的顯示。對于在線地圖的二次開發(fā)者來說，這也是一個十分重要的功能，例如要在地圖上顯示同一個站點中的多

5、個傳感器等，若缺少點聚合功能的支持，則是幾乎無法辨別清楚地圖上的這些傳感器點要素。運行方式點聚合的運算可以放在客戶端（瀏覽器），也可以放在服務(wù)端運算（如Google Maps的融合表）完畢再傳給客戶端。表現(xiàn)形式在計算機上表現(xiàn)地點的點聚合方式多種多樣，并無定論，聚合后的顯示樣式，不同縮放級別下是否顯示不同圖標(biāo)或在以下列舉幾種常見的表現(xiàn)形式：l 多個點聚合后還是點要素，換不同圖標(biāo)顯示，或在圖標(biāo)中同時顯示該聚合點所包含的原始點要素的數(shù)量，點擊聚合點后，地圖視圖會自動切換到該聚合點所包含的所有點的最小包圍盒地圖范圍中。l 多個點聚合后還是點要素，換不同圖標(biāo)顯示，或在圖標(biāo)中同時顯示該聚合點所包含的原始點

6、要素的數(shù)量，點擊聚合點后，地圖會彈出該聚合點的所聚合的所有點的位置信息，但并不縮放和移動地圖。l 多個點聚合后是面要素，以顏色或數(shù)字表示所聚合的點的數(shù)量，點開后若單位面積內(nèi)若依然包含較多點則繼續(xù)顯示面要素，若點較少則顯示原始的點要素。此種方法較少見，常見于上述兩種方法。算法本文關(guān)注的重點是在線地圖點聚合算法的大致情況，而不是每個算法詳細(xì)的運行效率和優(yōu)劣情況。因此，以下對可搜到的在線地圖點聚合算法進(jìn)行簡要列舉：1) 基于網(wǎng)格的點聚合算法（Grid-based Clustering）原理：將地圖劃分成指定尺寸的正方形（每個縮放級別不同尺寸），然后將落在對應(yīng)格子中的點聚合到該正方形中（正方形的中心）

7、，最終一個正方形內(nèi)只顯示一個點，并且點上顯示該聚合點所包含的原始點的數(shù)量。優(yōu)點：運算速度較快，每個原始點只需計算一次，沒有復(fù)雜的距離計算。缺點：有時明明很相近的點，卻僅僅因為網(wǎng)絡(luò)的分界線而被逼分開在不同的聚合點中，此外，聚合點的位置采用的是該網(wǎng)格的中心，而非該網(wǎng)格的質(zhì)心，這樣聚合出來的點可能不能較精確反映原始點的信息。使用此算法的在線地圖：缺。以下是Google給出的一個基于距離的點聚合示意圖：圖 2 基于網(wǎng)格的點聚合算法（聚合前）圖 3 基于網(wǎng)格的點聚合算法（聚合后）2) 基于距離的點聚合算法（Distance-based Clustering）原理：根據(jù)點與點之間的距離進(jìn)行聚合，對每個點進(jìn)

8、行迭代，若被迭代的點在某個已有聚合點的指定閾值的距離范圍內(nèi)，那么這個點就聚合到該點，否則則新建一個聚合點，如此循環(huán)，但聚合后的點的坐標(biāo)依然是該聚合點創(chuàng)建時的第一個點的坐標(biāo)位置。優(yōu)點：聚合點較精確的反映了所包含的原始點要素的位置信息。缺點：需要計算點與點之間的距離，計算相對復(fù)雜。使用此算法的在線地圖：缺。以下是Google給出的一個基于距離的點聚合示意圖：圖 4 基于距離的點聚合算法（原始點要素）圖 5 基于距離的點聚合算法（聚合過程）圖 6 基于距離的點聚合算法（聚合結(jié)果）聚合點（Cluster）原始點要素（Markers）藍(lán)1紅2黃7、8綠3、4、6粉紅5淺綠9表 1基于距離的點聚合算法（聚

9、合結(jié)果）3) 基于方格和距離結(jié)合的點聚合算法（詳細(xì)）原理：初始時沒有任何已知聚合點，然后對每個點進(jìn)行迭代，計算一個點的外包正方形，若此點的外包正方形與現(xiàn)有的聚合點的外包正方形不相交，則新建聚合點（區(qū)別于前面基于直接距離的算法，這里不是計算點與點間的距離，而是計算一個點的外包正方形，正方形的變長由用戶指定或程序設(shè)置一個默認(rèn)值），若相交，則把該點聚合到該聚合點中，若點與多個已知的聚合點的外包正方形相交，則計算該點到到聚合點的距離，聚合到距離最近的聚合點中，如此循環(huán)，直到所有點都遍歷完畢。每個縮放級別都重新遍歷所有原始點要素。此方法可以算是基于方格與基于距離的算法的一個結(jié)合算法。優(yōu)點：運算速度相對較

10、快，每個原始點只需計算一次，可能會有點與點距離計算，聚合點較精確的反映了所包含的原始點要素的位置信息。缺點：速度不如完全基于方格的速度快等。使用此算法的在線地圖：Google Maps。以下是Google給出的一個基于方格距離的點聚合示意圖：步驟示例：a) 默認(rèn)輸入的數(shù)組的順序是如Error! Reference source not found.所示的字母順序。b) 初始計算，從A開始迭代，此時并沒有任何聚合點，則在A的位置生成一個聚合點（設(shè)為A1），A1的位置與A相同。c) 迭代到B，如Error! Reference source not found.所示，由于B的外包正方形與已有聚合點

11、A1的外包正方形相交，所以B應(yīng)聚合到A1中，新聚合后的聚合點的位置依然保持在A1原來的位置（這主要是因為若采用A與B的質(zhì)心會花費客戶端較大的計算量，這在原始點要素數(shù)量較大時影響較大）。d) 迭代到C，由于C的外包正方形不與現(xiàn)有的聚合點A1相交（目前只有A1一個聚合點），因此C需要新建一個新的聚合點（設(shè)為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 基于方格距離的點聚合算法（聚合結(jié)果）聚合點（Cluster）原始點要素（Markers）1A、B、D2C、E3F、G、J、I4H表 2基于方格距離的點聚合算法（聚合結(jié)果）圖 10 基于方格距離的點聚合算法（更高縮放級別的聚合結(jié)果）圖 11 基于方格距離的點聚合算法（縮放到只有一個聚合點的聚合結(jié)果）4) 基于距離和最少點數(shù)量限制的點聚合算法原理：此算法相當(dāng)于先執(zhí)行完基于距離的點聚合算法，然后再進(jìn)行一次聚合點的分解。每個聚合點成立的條件是所聚合的原始點要素的數(shù)量應(yīng)大于程序默認(rèn)或用戶指定的最少數(shù)量限制，否則將解散這個聚合點。此方

13、法甚至不能算是一個獨立的算法，因為此算法的前后相互獨立，類比的，其實也可以建議一種“基于網(wǎng)格和最少點數(shù)量限制”的點聚合算法。優(yōu)點：聚合后的顯示相對精確，對顯示的控制更靈活。缺點：運算速度相對較慢，因為本身基于距離的點聚合算法就已經(jīng)是相對較慢了，再加上后期根據(jù)最少數(shù)量限制的閾值進(jìn)行點聚合分解，速度更慢。使用此算法的在線地圖：Openlayers（Openlayers是一個開源的Javascript庫（基于修改過的BSD許可發(fā)布），用來在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均值法等），但考慮運行效率和必要性的問題，因此，這里在不作運行效率、應(yīng)用的在線地圖等的評價。普通的遙感和GIS的圖像聚類方法其實也可以應(yīng)用在在線地圖的點聚合中，由于運行的效率不高、實現(xiàn)容易程度難和必要性的不充分等原因可能并不適合實際運行，這里僅列舉一些常見的遙感和GIS聚類方法：a. 啟發(fā)式的方法：k-平均值(k- means)和k-中心點(k- medoids)等b. 層次方法(Hierarchy method): 對給定數(shù)據(jù)對象集合進(jìn)行層次的分解 c. 基于密度的方法(Densi

20、ty-based method)：DBSCAN和OPTICS等d. 基于模型的方法(Model-based Method): 基于模型的方法為每個簇假定了一個模型, 尋找數(shù)據(jù)對給定模型的最佳擬合在日后的在線地圖的發(fā)展中，不排除由于新的其他需求而重新在其中使用上述這些額外的復(fù)雜算法。三、 在線地圖點聚合功能的實現(xiàn)情況目前來說，由于在線地圖的點聚合算法在算法難度和實現(xiàn)難度上均不難，也基本能解決地圖上大數(shù)據(jù)量點顯示的問題，所以算法本身可能并不是大部分地圖用戶和地圖開發(fā)者所關(guān)心的問題，他們最關(guān)心的可能是該地圖是否支持點聚合顯示功能，該地圖的開放API是否可以調(diào)用點聚合功能等問題。因此，本文對目前一些常

21、用在線地圖的點聚合功能進(jìn)行調(diào)查，并列舉其中的情況。Openlayers類型：開源的Javascript庫，用來在Web瀏覽器顯示地圖。是否支持點聚合顯示：支持是否支持點聚合API調(diào)用：支持點聚合所用算法：基于距離和最少點數(shù)量的點聚合算法點聚合官方地址：/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調(diào)用：支持點聚合所用算法：基于方格和距離結(jié)合的點聚合算法。算法開源。點聚合官方地址：/maps/articles/too

23、manymarkers點聚合功能實例：/svn/trunk/markerclusterer/1.0/examples/advanced_example.html圖示：圖 13 Google Maps點聚合示例特殊功能：Google Maps支持服務(wù)端的點聚合功能（將點聚合的算法運算轉(zhuǎn)移到服務(wù)器端，運行完畢后再將聚合后的結(jié)果傳到客戶端中），Google通過FusionTablesLayer（融合表，鏈接）和KmlLayer兩種服務(wù)端的方式?；谌诤媳淼囊粋€在線示例：http:/gmaps-samples-v3.g

24、/svn/trunk/fusiontables/cycletrails.html。百度地圖類型：在線地圖是否支持點聚合顯示：支持是否支持點聚合API調(diào)用：支持點聚合所用算法：基于方格和距離結(jié)合的點聚合算法，支持是否將聚合點的位置放置在被聚合的點的質(zhì)心或第一個被聚合的點中，支持指定在何種級別才顯示點或聚合點，支持限制最少聚合點數(shù)量。算法開源。點聚合官方地址：/library/MarkerClusterer/1.2/docs/symbols/BMapLib.MarkerClusterer.html點聚合功能實例：http:/d

25、/map/jsdemo.htm#c1_4圖示：圖 14 百度地圖點聚合示例高德地圖類型：在線地圖是否支持點聚合顯示：支持是否支持點聚合API調(diào)用：支持點聚合所用算法：與百度地圖基本一致。點聚合官方地址：/Javascript/reference/plugin#AMap.MarkerClusterer點聚合功能實例：/javascript/example/num/0509圖示：圖 15 高德地圖點聚合示例ESRI類型：地圖API（如Javascript、Flex、Silverli

26、ght等）是否支持點聚合顯示：支持是否支持點聚合API調(diào)用：支持點聚合所用算法：同時支持基于網(wǎng)格的和基于點權(quán)重，等。點聚合官方地址：（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調(diào)用：不支持關(guān)于不支持的相關(guān)地址和說明：