摘要：本篇文章已授權(quán)微信公眾號(hào)郭霖獨(dú)家發(fā)布老規(guī)矩先上圖最近沒(méi)有什么時(shí)間，后面項(xiàng)目再補(bǔ)上詳細(xì)說(shuō)明百度地圖新增點(diǎn)聚合功能。百度地圖是把整個(gè)地球是按照一個(gè)平面來(lái)展開(kāi)，并且通過(guò)墨卡托投影投射到坐標(biāo)軸上面。上圖很明顯墨卡托投影把整張世界地圖投影成。

本篇文章已授權(quán)微信公眾號(hào) guolin_blog （郭霖）獨(dú)家發(fā)布

老規(guī)矩先上圖
最近 沒(méi)有什么時(shí)間，后面項(xiàng)目再補(bǔ)上詳細(xì)說(shuō)明

百度地圖SDK新增點(diǎn)聚合功能。通過(guò)該功能，可通過(guò)縮小地圖層級(jí)，將定義范圍內(nèi)的多個(gè)標(biāo)注點(diǎn)，聚合顯示成一個(gè)標(biāo)注點(diǎn)，解決加載大量點(diǎn)要素到地圖上產(chǎn)生覆蓋現(xiàn)象的問(wèn)題，并提高性能。

本demo 修改算法流程：

加入異步添加屏幕上圖片，

只加載屏幕范圍內(nèi)的圖片

優(yōu)化渲染邏輯
大大減少運(yùn)算的時(shí)間（經(jīng)過(guò)測(cè)試1W張不同經(jīng)緯度的圖片 300-500ms 可以計(jì)算完畢）

講解點(diǎn)聚合功能，整個(gè)分析過(guò)程分為三部分：

1、如何添加點(diǎn)聚合功能到項(xiàng)目中；
2、整體結(jié)構(gòu)分析；
3、核心算法分析。

一、添加點(diǎn)聚合功能

如官網(wǎng)所示，添加點(diǎn)聚合的方法分為三步：
1、聲明點(diǎn)聚合管理類(lèi)為全局變量，并初始化。核心代碼如下圖：

MarkerOptions opts = new MarkerOptions().position(cluster.getPosition())
            .icon(BitmapDescriptorFactory.fromBitmap(XX));
Marker marker = (Marker) mMap.addOverlay(opts);

二、整體結(jié)構(gòu)分析

先上一個(gè)思維導(dǎo)圖：

如上圖，點(diǎn)聚合有四個(gè)類(lèi)
1、Cluster數(shù)據(jù)：主要是聚合后的數(shù)據(jù)類(lèi)型
2、四叉樹(shù)：記錄初始范圍內(nèi)的所有圖片并以四叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)組織。核心算法需要用到的數(shù)據(jù)結(jié)構(gòu)，后面再講；
3、點(diǎn)聚合算法：基于四叉樹(shù)的核心算法。后面講；
4、Cluster管理：對(duì)外接口，通過(guò)調(diào)用核心算法實(shí)現(xiàn)點(diǎn)聚合功能、

整個(gè)功能的主要流程有兩條：
1、添加item：Cluster管理類(lèi)添加item接口  算法類(lèi)添加item接口：記錄所有的圖片信息  四叉樹(shù)類(lèi)添加item接口：已四叉樹(shù)的結(jié)構(gòu)記錄所有圖片信息
2、獲取聚合后的集合：Cluster管理類(lèi)獲取聚合接口  算法類(lèi)核心算法接口：通過(guò)核心算法獲取聚合后的集合

三、核心算法

首先要說(shuō)一個(gè)概念：世界寬度。
百度地圖是把整個(gè)地球是按照一個(gè)平面來(lái)展開(kāi)，并且通過(guò)墨卡托投影投射到xy坐標(biāo)軸上面。上圖：

很明顯墨卡托投影把整張世界地圖投影成
X∈ [0,1] ; Y∈ [0,1]。
的一個(gè)正方型區(qū)域。
X 表示的是經(jīng)度，Y表示的是緯度。

（其實(shí)確認(rèn)來(lái)說(shuō)是投影一個(gè)上下無(wú)限延伸的長(zhǎng)方體，只是Y屬于[0,1]這個(gè)范圍已經(jīng)足夠我們使用）上圖說(shuō)明：

從上面看出 -85°的緯度對(duì)應(yīng)Y坐標(biāo)是1，那么-90°呢，你們自己可以去算一下，是+∞ （正無(wú)窮）。

至于為什么講這個(gè)，因?yàn)橛?jì)算搜索范圍的時(shí)候，所有的經(jīng)緯度都需要換算成Point 來(lái)計(jì)算，是不是很方便性，而且不易出錯(cuò)。
真是感嘆偉人的強(qiáng)大！

附注

轉(zhuǎn)換的公式在下面這個(gè)類(lèi)里面：

SphericalMercatorProjection.java

接下來(lái)說(shuō)說(shuō)如何通過(guò)四叉樹(shù)組織數(shù)據(jù)

四叉樹(shù)的基本思想是把空間遞歸劃分為不同層次的樹(shù)結(jié)構(gòu)。它把已知的空間等分成四個(gè)相等的子空間，如此遞歸下去，直到滿(mǎn)足當(dāng)層數(shù)目量超過(guò)50，或者層級(jí)數(shù)大于40則停止分割。示意圖如下：

OK，接下來(lái)說(shuō)說(shuō)具體流程

遍歷QuadItem,只加載屏幕內(nèi)的點(diǎn)，生成四叉樹(shù)，方便搜索。

如果圖片已被visitedCandidate記錄，則continue下面步驟，直到需要處理的圖片沒(méi)有被visitedCandidates記錄；

對(duì)上一次屏幕上的點(diǎn)QuadItem先進(jìn)行處理；

根據(jù)MAX_DISTANCE_IN_DP及圖片位置計(jì)算出searchBounds;

通過(guò)四叉樹(shù)得到searchBounds內(nèi)所有的圖片；

如果圖片數(shù)量為1，記錄并跳到步驟2；

遍歷得到的圖片；

依次對(duì)得到的圖片進(jìn)行處理，

如果圖片到中心點(diǎn)的距離比distanceToCluster（此圖片與包含此圖片的前cluster的距離）小，把圖片加入結(jié)果集，并移除前Cluster擁有該圖片的引用，并記錄此次更小的距離，跳步驟8繼續(xù)遍歷剩余項(xiàng)。

重點(diǎn)源碼分析：

1.聚合觸發(fā)口
ClusterManager.java

@Override
    public void onMapStatusChangeFinish(MapStatus mapStatus) {
        if (mRenderer instanceof BaiduMap.OnMapStatusChangeListener) {
            ((BaiduMap.OnMapStatusChangeListener) mRenderer).onMapStatusChange(mapStatus);
        }

        // 屏幕縮放范圍太小，不進(jìn)行觸發(fā)聚合功能
        if (mPreviousCameraPosition != null
                && Math.abs((int) mPreviousCameraPosition.zoom - (int) mapStatus.zoom) < 1
                && mPreviousCameraPosition.target.latitude == mapStatus.target.latitude
                && mPreviousCameraPosition.target.longitude == mapStatus.target.longitude) {
            return;
        }
       //記錄
        mPreviousCameraPosition = mapStatus;
     
        //算法運(yùn)算，計(jì)算出聚合后結(jié)果集，并且addMarker 到屏幕上
        cluster(mapStatus.zoom,mapStatus.bound);
    }

對(duì)地圖進(jìn)行手勢(shì)操作，都會(huì)進(jìn)行觸發(fā)這個(gè)函數(shù)，并進(jìn)行聚合操作

2.算法運(yùn)算
NonHierarchicalDistanceBasedAlgorithm.java

@Override
    public Set> getClusters(double zoom, LatLngBounds visibleBounds) {
    ...
    }

這個(gè)函數(shù)有點(diǎn)多，不過(guò)在github 上面的demo 已經(jīng)注釋滿(mǎn)滿(mǎn)，請(qǐng)移步github 查看。

3.渲染UI(addMarker) 
class DefaultClusterRenderer {
    class CreateMarkerTask {
       ...
    }
}

private void perform(MarkerModifier markerModifier) {
            // Don"t show small clusters. Render the markers inside, instead.
            markRemoveAndAddLock.lock();
            //真正添加Marker 的地方

            Marker marker = mClusterToMarker.get(cluster);
            if (marker == null || (marker != null
                    && mMarkerToCluster.get(marker).getSize() != cluster.getSize())) {
                //異步加載占時(shí)不添加Marker
                Integer size = onReadyAddCluster.get(cluster);
                if (size == null || size != cluster.getSize()) {
                    onReadyAddCluster.put(cluster,cluster.getSize());
                    onBeforeClusterRendered(cluster, new MarkerOptions()
                            .position(cluster.getPosition()));

                }
            }
            markRemoveAndAddLock.unlock();
            newClusters.add(cluster);

        }

主要添加圖片的是onBeforeClusterRendered 這一個(gè)函數(shù)， 我們看一下實(shí)現(xiàn)：

public class PersonRenderer extends DefaultClusterRenderer {
  DataSource> target = cancleMap1.get(cluster);
        if(target != null) {
            target.close();
            cancleMap1.remove(target);
        }


        final LocalPictrue person = cluster.getItems().iterator().next();

        ImageRequest imageRequest = ImageRequestBuilder
                .newBuilderWithSource(Uri.fromFile(new File(person.path)))
                .setProgressiveRenderingEnabled(false)
                .setResizeOptions(new ResizeOptions(50, 50))
                .setPostprocessor(new BadgViewPostprocessor(mContext,cluster))
                .build();

        ImagePipeline imagePipeline = Fresco.getImagePipeline();
        DataSource> dataSource =
                imagePipeline.fetchDecodedImage(imageRequest,mContext);

        dataSource.subscribe(new BaseBitmapDataSubscriber() {

            @Override
            public void onNewResultImpl(@Nullable Bitmap bitmap) {
                // You can use the bitmap in only limited ways
                // No need to do any cleanup.
                if(bitmap != null && !bitmap.isRecycled()) {
                    //you can use bitmap here
                    setIconByCluster(person.path,cluster,
                            markerOptions.icon(BitmapDescriptorFactory.fromBitmap(bitmap)));
                }
                cancleMap1.remove(cluster);
            }

            @Override
            public void onFailureImpl(DataSource dataSource) {
                // No cleanup required here.
                System.out.println("shibai");
            }

        }, UiThreadImmediateExecutorService.getInstance());

        cancleMap1.put(cluster, dataSource);

}

很明顯我這邊解決了 baiduMap 在UI線(xiàn)程上添加圖片阻塞問(wèn)題， 添加強(qiáng)大的 fresco 第三方加載庫(kù)，進(jìn)行異步加載圖片，接下來(lái)看圖片下載完成后 執(zhí)行setIconByCluster 函數(shù)：

//異步回調(diào)回來(lái)的icon ，需要
    public void setIconByCluster(String path, Cluster cluster, MarkerOptions markerOptions) {
        markRemoveAndAddLock.lock();
        Integer size = onReadyAddCluster.get(cluster);
        if (size != null && cluster.getSize() == size) {
            Marker marker = mClusterToMarker.get(cluster);
            if (marker != null) {
     //如果該圖在屏幕上已經(jīng)打了marker，那么替換icon即可，主要解決圖片重新加載閃爍問(wèn)題    
              marker.setIcon(markerOptions.getIcon());
            } else {
            //打入新的Marker
                marker = mClusterManager.getClusterMarkerCollection().addMarker(markerOptions);
            }

            mMarkerToCluster.put(marker, cluster);
            mClusterToMarker.put(cluster, marker);
        }
        markRemoveAndAddLock.unlock();
    }

總結(jié)：

重點(diǎn)源碼分析，基本上到這里結(jié)束。我們來(lái)擼一擼流程：

通過(guò)onMapStatusChangeFinish回調(diào)，去執(zhí)行點(diǎn)聚合運(yùn)算；

通過(guò) getClusters把聚合后的結(jié)果集算出來(lái)；

通過(guò)CreateMarkerTask.perform() 把 marker打到屏幕上。

備注：

更多細(xì)節(jié)請(qǐng)看源代碼，
喜歡去幫忙start一下，謝謝！

github：
[https://github.com/zhangchaoj...