摘要：本篇文章已授權微信公眾號郭霖獨家發布老規矩先上圖最近沒有什么時間，后面項目再補上詳細說明百度地圖新增點聚合功能。百度地圖是把整個地球是按照一個平面來展開，并且通過墨卡托投影投射到坐標軸上面。上圖很明顯墨卡托投影把整張世界地圖投影成。

本篇文章已授權微信公眾號 guolin_blog （郭霖）獨家發布

老規矩先上圖
最近 沒有什么時間，后面項目再補上詳細說明

百度地圖SDK新增點聚合功能。通過該功能，可通過縮小地圖層級，將定義范圍內的多個標注點，聚合顯示成一個標注點，解決加載大量點要素到地圖上產生覆蓋現象的問題，并提高性能。

本demo 修改算法流程：

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

只加載屏幕范圍內的圖片

優化渲染邏輯
大大減少運算的時間（經過測試1W張不同經緯度的圖片 300-500ms 可以計算完畢）

講解點聚合功能，整個分析過程分為三部分：

1、如何添加點聚合功能到項目中；
2、整體結構分析；
3、核心算法分析。

一、添加點聚合功能

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

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

二、整體結構分析

先上一個思維導圖：

如上圖，點聚合有四個類
1、Cluster數據：主要是聚合后的數據類型
2、四叉樹：記錄初始范圍內的所有圖片并以四叉樹的數據結構組織。核心算法需要用到的數據結構，后面再講；
3、點聚合算法：基于四叉樹的核心算法。后面講；
4、Cluster管理：對外接口，通過調用核心算法實現點聚合功能、

整個功能的主要流程有兩條：
1、添加item：Cluster管理類添加item接口  算法類添加item接口：記錄所有的圖片信息  四叉樹類添加item接口：已四叉樹的結構記錄所有圖片信息
2、獲取聚合后的集合：Cluster管理類獲取聚合接口  算法類核心算法接口：通過核心算法獲取聚合后的集合

三、核心算法

首先要說一個概念：世界寬度。
百度地圖是把整個地球是按照一個平面來展開，并且通過墨卡托投影投射到xy坐標軸上面。上圖：

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

（其實確認來說是投影一個上下無限延伸的長方體，只是Y屬于[0,1]這個范圍已經足夠我們使用）上圖說明：

從上面看出 -85°的緯度對應Y坐標是1，那么-90°呢，你們自己可以去算一下，是+∞ （正無窮）。

至于為什么講這個，因為計算搜索范圍的時候，所有的經緯度都需要換算成Point 來計算，是不是很方便性，而且不易出錯。
真是感嘆偉人的強大！

附注

轉換的公式在下面這個類里面：

SphericalMercatorProjection.java

接下來說說如何通過四叉樹組織數據

四叉樹的基本思想是把空間遞歸劃分為不同層次的樹結構。它把已知的空間等分成四個相等的子空間，如此遞歸下去，直到滿足當層數目量超過50，或者層級數大于40則停止分割。示意圖如下：

OK，接下來說說具體流程

遍歷QuadItem,只加載屏幕內的點，生成四叉樹，方便搜索。

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

對上一次屏幕上的點QuadItem先進行處理；

根據MAX_DISTANCE_IN_DP及圖片位置計算出searchBounds;

通過四叉樹得到searchBounds內所有的圖片；

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

遍歷得到的圖片；

依次對得到的圖片進行處理，

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

重點源碼分析：

1.聚合觸發口
ClusterManager.java

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

        // 屏幕縮放范圍太小，不進行觸發聚合功能
        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;
     
        //算法運算，計算出聚合后結果集，并且addMarker 到屏幕上
        cluster(mapStatus.zoom,mapStatus.bound);
    }

對地圖進行手勢操作，都會進行觸發這個函數，并進行聚合操作

2.算法運算
NonHierarchicalDistanceBasedAlgorithm.java

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

這個函數有點多，不過在github 上面的demo 已經注釋滿滿，請移步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())) {
                //異步加載占時不添加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 這一個函數， 我們看一下實現：

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線程上添加圖片阻塞問題， 添加強大的 fresco 第三方加載庫，進行異步加載圖片，接下來看圖片下載完成后 執行setIconByCluster 函數：

//異步回調回來的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) {
     //如果該圖在屏幕上已經打了marker，那么替換icon即可，主要解決圖片重新加載閃爍問題    
              marker.setIcon(markerOptions.getIcon());
            } else {
            //打入新的Marker
                marker = mClusterManager.getClusterMarkerCollection().addMarker(markerOptions);
            }

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

總結：

重點源碼分析，基本上到這里結束。我們來擼一擼流程：

通過onMapStatusChangeFinish回調，去執行點聚合運算；

通過 getClusters把聚合后的結果集算出來；

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

備注：

更多細節請看源代碼，
喜歡去幫忙start一下，謝謝！

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