在線地圖的點聚合算法和現狀

/在線地圖的點聚合算法及現狀Viky2014目錄一、概述21>什么是地圖綜合？22>什么是點聚合？23>本文關注的重點2二、在線地圖點聚合的算法3特點3必要性3運行方式3表現形式3算法31>基于網格的點聚合算法〔Grid-basedClustering32>基于距離的點聚合算法〔Distance-basedClustering53>基于方格和距離結合的點聚合算法〔詳細74>基于距離和最少點數量限制的點聚合算法125>其他的可用于在線地圖點聚合的算法14三、在線地圖點聚合功能的實現情況14Openlayers14GoogleMaps15百度地圖16高德地圖17ESRI18騰訊地圖〔原搜索地圖19天地圖20四、小結20參考文獻21概述什么是地圖綜合？地圖綜合所要解決的問題是把一個空間目標集合按照專題內容轉換為一個最能代表該集合主要空間特征的更抽象的空間目標集合.并符號化該抽象后的空間目標集合.以最有效的方式傳輸地理空間知識。什么是點聚合？點聚合〔pointcluster.或又叫點聚類.是地圖綜合的其中一種方法.主要解決地圖中點要素很多時候的表示困難的問題。點聚合可以用少量的點或圖標來表示地圖中的所有點.讓地圖顯示更清晰明朗。如REF_Ref376811161\h圖1所示。圖SEQ圖\*ARABIC1–在線地圖的點聚合示意圖本文關注的重點本文主要關注二維在線電子地圖中點的聚合顯示所用到的算法和目前的在線地圖對點聚合顯示的支持情況。電子地圖中.通常會遇到在某個地區(qū)包含成千上萬個點要素的情況.若同時加載顯示在電子地圖中.會顯得很亂、覆蓋地圖底圖.也會占用大量系統(tǒng)資源.甚至引發(fā)瀏覽器的崩潰、卡頓.極大的影響用戶體驗.因此點聚合顯示是電子地圖十分需要的一項功能。目前的常見在線地圖〔或其API是否支持點聚合？若支持點聚合的算法是什么？是一個值得關注的問題。本文嘗試對這兩個問題進行解答。在線地圖點聚合的算法特點數據相對簡單.只有點要素.點沒有形狀變化.因此沒有形狀對聚合影響。沒有評價聚合精確度的唯一指標.〔不考慮運行速度的情況下不同的算法不同的顯示方式對用戶體驗影響并不會太大。可能需考慮的方面：聚合點中包含的原始點要素最大數量限制、聚合點間的距離限制、點要素的權重、部分縮放級別是否該顯示聚合點等。一般的點聚合〔聚類算法對在線地圖點聚合雖適用〔如K均值法等.但需平衡運行效率和必要性.并且極少見這些復雜方法應用實際的在線地圖中。必要性目前在線地圖的點聚合算法已有較成熟的應用.不少在線地圖均提供點聚合的功能及API。點聚合算法雖然相對簡單.但卻很實用.若缺少了.在線地圖則無法對大數據量的點要素進行較好的顯示。對于在線地圖的二次開發(fā)者來說.這也是一個十分重要的功能.例如要在地圖上顯示同一個站點中的多個傳感器等.若缺少點聚合功能的支持.則是幾乎無法辨別清楚地圖上的這些傳感器點要素。運行方式點聚合的運算可以放在客戶端〔瀏覽器.也可以放在服務端運算〔如GoogleMaps的融合表完畢再傳給客戶端。表現形式在計算機上表現地點的點聚合方式多種多樣.并無定論.聚合后的顯示樣式.不同縮放級別下是否顯示不同圖標或在以下列舉幾種常見的表現形式：多個點聚合后還是點要素.換不同圖標顯示.或在圖標中同時顯示該聚合點所包含的原始點要素的數量.點擊聚合點后.地圖視圖會自動切換到該聚合點所包含的所有點的最小包圍盒地圖范圍中。多個點聚合后還是點要素.換不同圖標顯示.或在圖標中同時顯示該聚合點所包含的原始點要素的數量.點擊聚合點后.地圖會彈出該聚合點的所聚合的所有點的位置信息.但并不縮放和移動地圖。多個點聚合后是面要素.以顏色或數字表示所聚合的點的數量.點開后若單位面積內若依然包含較多點則繼續(xù)顯示面要素.若點較少則顯示原始的點要素。此種方法較少見.常見于上述兩種方法。算法本文關注的重點是在線地圖點聚合算法的大致情況.而不是每個算法詳細的運行效率和優(yōu)劣情況。因此.以下對可搜到的在線地圖點聚合算法進行簡要列舉：基于網格的點聚合算法〔Grid-basedClustering原理：將地圖劃分成指定尺寸的正方形〔每個縮放級別不同尺寸.然后將落在對應格子中的點聚合到該正方形中〔正方形的中心.最終一個正方形內只顯示一個點.并且點上顯示該聚合點所包含的原始點的數量。優(yōu)點：運算速度較快.每個原始點只需計算一次.沒有復雜的距離計算。缺點：有時明明很相近的點.卻僅僅因為網絡的分界線而被逼分開在不同的聚合點中.此外.聚合點的位置采用的是該網格的中心.而非該網格的質心.這樣聚合出來的點可能不能較精確反映原始點的信息。使用此算法的在線地圖：缺。以下是Google給出的一個基于距離的點聚合示意圖：圖SEQ圖\*ARABIC2–基于網格的點聚合算法〔聚合前圖SEQ圖\*ARABIC3–基于網格的點聚合算法〔聚合后基于距離的點聚合算法〔Distance-basedClustering原理：根據點與點之間的距離進行聚合.對每個點進行迭代.若被迭代的點在某個已有聚合點的指定閾值的距離范圍內.那么這個點就聚合到該點.否則則新建一個聚合點.如此循環(huán).但聚合后的點的坐標依然是該聚合點創(chuàng)建時的第一個點的坐標位置。優(yōu)點：聚合點較精確的反映了所包含的原始點要素的位置信息。缺點：需要計算點與點之間的距離.計算相對復雜。使用此算法的在線地圖：缺。以下是Google給出的一個基于距離的點聚合示意圖：圖SEQ圖\*ARABIC4–基于距離的點聚合算法〔原始點要素圖SEQ圖\*ARABIC5–基于距離的點聚合算法〔聚合過程圖SEQ圖\*ARABIC6–基于距離的點聚合算法〔聚合結果藍1紅2黃7、8綠3、4、6粉紅5淺綠9表SEQ表\*ARABIC1基于距離的點聚合算法〔聚合結果基于方格和距離結合的點聚合算法〔詳細原理：初始時沒有任何已知聚合點.然后對每個點進行迭代.計算一個點的外包正方形.若此點的外包正方形與現有的聚合點的外包正方形不相交.則新建聚合點〔區(qū)別于前面基于直接距離的算法.這里不是計算點與點間的距離.而是計算一個點的外包正方形.正方形的變長由用戶指定或程序設置一個默認值.若相交.則把該點聚合到該聚合點中.若點與多個已知的聚合點的外包正方形相交.則計算該點到到聚合點的距離.聚合到距離最近的聚合點中.如此循環(huán).直到所有點都遍歷完畢。每個縮放級別都重新遍歷所有原始點要素。此方法可以算是基于方格與基于距離的算法的一個結合算法。優(yōu)點：運算速度相對較快.每個原始點只需計算一次.可能會有點與點距離計算.聚合點較精確的反映了所包含的原始點要素的位置信息。缺點：速度不如完全基于方格的速度快等。使用此算法的在線地圖：GoogleMaps。以下是Google給出的一個基于方格距離的點聚合示意圖：步驟示例：默認輸入的數組的順序是如REF_Ref376784540\h圖7–基于方格距離的點聚合算法〔原始點要素所示的字母順序。初始計算.從A開始迭代.此時并沒有任何聚合點.則在A的位置生成一個聚合點〔設為A1.A1的位置與A相同。迭代到B.如REF_Ref376784647\h圖8所示.由于B的外包正方形與已有聚合點A1的外包正方形相交.所以B應聚合到A1中.新聚合后的聚合點的位置依然保持在A1原來的位置〔這主要是因為若采用A與B的質心會花費客戶端較大的計算量.這在原始點要素數量較大時影響較大。迭代到C.由于C的外包正方形不與現有的聚合點A1相交〔目前只有A1一個聚合點.因此C需要新建一個新的聚合點〔設為C1。迭代到D.類似于B.D與A1聚合.聚合后依然為A1。迭代到E.新的問題來了.E的外包正方形同時與A1和C1相交.這時需判斷E到A1、C1的距離.并將E聚合到距離近的那個聚合點中.這里E到C1更近.于是E聚合到了C1中。剩下的如此迭代.直至完畢。圖SEQ圖\*ARABIC7–基于方格距離的點聚合算法〔原始點要素圖SEQ圖\*ARABIC8–基于方格距離的點聚合算法〔聚合過程圖SEQ圖\*ARABIC9–基于方格距離的點聚合算法〔聚合結果1A、B、D2C、E3F、G、J、I4H表SEQ表\*ARABIC2基于方格距離的點聚合算法〔聚合結果圖SEQ圖\*ARABIC10–基于方格距離的點聚合算法〔更高縮放級別的聚合結果圖SEQ圖\*ARABIC11–基于方格距離的點聚合算法〔縮放到只有一個聚合點的聚合結果基于距離和最少點數量限制的點聚合算法原理：此算法相當于先執(zhí)行完基于距離的點聚合算法.然后再進行一次聚合點的分解。每個聚合點成立的條件是所聚合的原始點要素的數量應大于程序默認或用戶指定的最少數量限制.否則將解散這個聚合點。此方法甚至不能算是一個獨立的算法.因為此算法的前后相互獨立.類比的.其實也可以建議一種"基于網格和最少點數量限制"的點聚合算法。優(yōu)點：聚合后的顯示相對精確.對顯示的控制更靈活。缺點：運算速度相對較慢.因為本身基于距離的點聚合算法就已經是相對較慢了.再加上后期根據最少數量限制的閾值進行點聚合分解.速度更慢。使用此算法的在線地圖：Openlayers〔Openlayers是一個開源的Javascript庫〔基于修改過的BSD許可發(fā)布.用來在Web瀏覽器顯示地圖[維基百科]。以下是Openlayers官方Javascript源碼的算法核心：………cluster:function<event>{if<<!event||event.zoomChanged>&&this.features>{varresolution=this.layer.map.getResolution<>;if<resolution!=this.resolution||!this.clustersExist<>>{this.resolution=resolution;varclusters=[];varfeature,clustered,cluster;for<vari=0;i<this.features.length;++i>{feature=this.features[i];if<feature.geometry>{clustered=false;for<varj=clusters.length-1;j>=0;--j>{cluster=clusters[j];if<this.shouldCluster<cluster,feature>>{this.addToCluster<cluster,feature>;clustered=true;break;}}if<!clustered>{clusters.push<this.createCluster<this.features[i]>>;}}}this.clustering=true;this.layer.removeAllFeatures<>;this.clustering=false;if<clusters.length>0>{if<this.threshold>1>{varclone=clusters.slice<>;clusters=[];varcandidate;for<vari=0,len=clone.length;i<len;++i>{candidate=clone[i];if<candidate.attributes.count<this.threshold>{Atotype.push.apply<clusters,candidate.cluster>;}else{clusters.push<candidate>;}}}this.clustering=true;//Alegitimatefeatureadditioncouldoccurduringthis//addFeaturescall.Forclusteringtobehavewell,features//shouldberemovedfromalayerbeforerequestinganewbatch.this.layer.addFeatures<clusters>;this.clustering=false;}this.clusters=clusters;}}},………shouldCluster:function<cluster,feature>{varcc=cluster.geometry.getBounds<>.getCenterLonLat<>;varfc=feature.geometry.getBounds<>.getCenterLonLat<>;vardistance=<Math.sqrt<Math.pow<<cc.lon-fc.lon>,2>+Math.pow<<cc.lat-fc.lat>,2>>/this.resolution>;return<distance<=this.distance>;},………：/openlayers/openlayers/blob/master/lib/OpenLayers/Strategy/Cluster.js其他的可用于在線地圖點聚合的算法一般的點聚合〔聚類算法對在線地圖點聚合均適用〔如K均值法等.但考慮運行效率和必要性的問題.因此.這里在不作運行效率、應用的在線地圖等的評價。普通的遙感和GIS的圖像聚類方法其實也可以應用在在線地圖的點聚合中.由于運行的效率不高、實現容易程度難和必要性的不充分等原因可能并不適合實際運行.這里僅列舉一些常見的遙感和GIS聚類方法：啟發(fā)式的方法：k-平均值<k-means>和k-中心點<k-medoids>等層次方法<Hierarchymethod>:對給定數據對象集合進行層次的分解基于密度的方法<Density-basedmethod>：DBSCAN和OPTICS等基于模型的方法<Model-basedMethod>:基于模型的方法為每個簇假定了一個模型,尋找數據對給定模型的最佳擬合在日后的在線地圖的發(fā)展中.不排除由于新的其他需求而重新在其中使用上述這些額外的復雜算法。在線地圖點聚合功能的實現情況目前來說.由于在線地圖的點聚合算法在算法難度和實現難度上均不難.也基本能解決地圖上大數據量點顯示的問題.所以算法本身可能并不是大部分地圖用戶和地圖開發(fā)者所關心的問題.他們最關心的可能是該地圖是否支持點聚合顯示功能.該地圖的開放API是否可以調用點聚合功能等問題。因此.本文對目前一些常用在線地圖的點聚合功能進行調查.并列舉其中的情況。Openlayers類型：開源的Javascript庫.用來在Web瀏覽器顯示地圖。是否支持點聚合顯示：支持是否支持點聚合API調用：支持點聚合所用算法：基于距離和最少點數量的點聚合算法點聚合官方地址：/openlayers/openlayers/blob/master/lib/OpenLayers/Strategy/Cluster.js點聚合功能實例：/dev/examples/strategy-cluster-threshold.html圖示：圖SEQ圖\*ARABIC12–Openlayers點聚合示例GoogleMaps類型：在線地圖是否支持點聚合顯示：支持是否支持點聚合API調用：支持點聚合所用算法：基于方格和距離結合的點聚合算法。算法開源。點聚合官方地址：點聚合功能實例：圖示：圖SEQ圖\*ARABIC13–GoogleMaps點聚合示例特殊功能：GoogleMaps支持服務端的點聚合功能〔將點聚合的算法運算轉移到服務器端.運行完畢后再將聚合后的結果傳到客戶端中.Google通過FusionTablesLayer〔融合表.鏈接和KmlLayer兩種服務端的方式?；谌诤媳淼囊粋€在線示例：。百度地圖類型：在線地圖是否支持點聚合顯示：支持是否支持點聚合API調用：支持點聚合所用算法：基于方格和距離結合的點聚合算法.支持是否將聚合點的位置放置在被聚合的點的質心或第一個被聚合的點中.支持指定在何種級別才顯示點或聚合點.支持限制最少聚合點數量。算法開源。點聚合官方地址：點聚合功能實例：/map/jsdemo.htm#c1_4圖示：圖SEQ圖\*ARABIC14–百度地圖點聚合示例高德地圖類型：在線地圖是否支持點聚合顯示：支持是否支持點聚合API調用：支持點聚合所用算法：與百度地圖基本一致。點聚合官方地址：/Javascript/reference/plugin#AMap.MarkerClusterer點聚合功能實例：圖示：圖SEQ圖\*ARABIC15–高德地圖點聚合示例ESRI類型：地圖API〔如Javascript、Flex、Silverlight等是否支持點聚合顯示：支