百度地图的聚合算法

这段百度算法的描述来自博客：https://blog.csdn.net/javine/article/details/51195014

总结如下：

百度地图把整个地球是按照一个平面来展开，把整个地球按照平面来展开之后，我们就能算出这个地球平面的宽度，也就是世界宽度。

计算公式是这样的：256*（zoom^2） == worldWidth

其中zoom就是地图的层级，我们缩放地图也是根据zoom的变化来判断是放大还是缩小的。这样可以把不利于计算的经纬度position转换成我们熟悉的二维坐标point。

而一个二维坐标中有若干个点，把它们按照一个给定的distance来进行分组。
迭代所有的QuadItem，以此QuadItem为中心画一个框框，框框里面的点就算是一个cluster簇，
也就是可以聚合成一个点的QuadItems。框框的大小就是我们定义的可以执行聚合的距离。
当然，这话其实并不准确，会有些点同时被好多个框框给框住，那就算距离最小的那个cluster里面的点。

/**
     *  cluster算法核心
     * @param zoom map的级别
     * @return
     */
    @Override
    public Set<? extends Cluster<T>> getClusters(double zoom) {
        final int discreteZoom = (int) zoom;
 
        final double zoomSpecificSpan = MAX_DISTANCE_AT_ZOOM / Math.pow(2, discreteZoom) / 256;//定义的可进行聚合的距离
 
        final Set<QuadItem<T>> visitedCandidates = new HashSet<QuadItem<T>>();  //遍历QuadItem时保存被遍历过的Item
        final Set<Cluster<T>> results = new HashSet<Cluster<T>>();  //保存要返回的cluster簇，每个cluster中包含若干个MyItem对象
        final Map<QuadItem<T>, Double> distanceToCluster = new HashMap<QuadItem<T>, Double>();  //Item --> 此Item与所属的cluster中心点的距离
        final Map<QuadItem<T>, mapapi.clusterutil.clustering.algo.StaticCluster<T>> itemToCluster =
                new HashMap<QuadItem<T>, mapapi.clusterutil.clustering.algo.StaticCluster<T>>(); //Item对象 --> 此Item所属的cluster
 
        synchronized (mQuadTree) {
            for (QuadItem<T> candidate : mItems) {<span style="white-space:pre">	</span>//遍历所有的QuadItem
                if (visitedCandidates.contains(candidate)) {<span style="white-space:pre">	</span>//如果此Item已经被别的cluster框住了，就不再处理它
                 
                    continue;
                }
 
                Bounds searchBounds = createBoundsFromSpan(candidate.getPoint(), zoomSpecificSpan);//这个就是我们说的，根据给定距离生成一个框框
                Collection<QuadItem<T>> clusterItems;
                // search 某边界范围内的clusterItems
                clusterItems = mQuadTree.search(searchBounds); //从quadTree中搜索出框框内的点
                if (clusterItems.size() == 1) {
                    // 如果只有一个点，那么这一个点就是一个cluster，QuadItem也实现了Cluster接口，也可以当作Cluster对象
                    results.add(candidate);
                    visitedCandidates.add(candidate);
                    distanceToCluster.put(candidate, 0d);
                    continue;<span style="white-space:pre">	</span>//并且结束此次循环
                }
                mapapi.clusterutil.clustering.algo.StaticCluster<T> cluster =
                        new mapapi.clusterutil.clustering.algo
                                .StaticCluster<T>(candidate.mClusterItem.getPosition());//如果搜索到多个点,那么就以此item为中心创建一个cluster
                results.add(cluster);
 
                for (QuadItem<T> clusterItem : clusterItems) {<span style="white-space:pre">	</span>//遍历所有框住的点
                    Double existingDistance = distanceToCluster.get(clusterItem);//获取此item与原来的cluster中心的距离(如果之前已经被其他cluster给框住了)
                    double distance = distanceSquared(clusterItem.getPoint(), candidate.getPoint());<span style="white-space:pre">	</span>//获取此item与现在这个cluster中心的距离
                    if (existingDistance != null) {
                        // 判断那个距离跟小
                        if (existingDistance < distance) {
                            continue;
                        }
                        //如果跟现在的cluster距离更近，则将此item从原来的cluster中移除
                        itemToCluster.get(clusterItem).remove(clusterItem.mClusterItem);
                    }
                    distanceToCluster.put(clusterItem, distance); //保存此item到cluster中心的距离
                    cluster.add(clusterItem.mClusterItem);<span style="white-space:pre">	</span>//将此item添加到cluster中
                    itemToCluster.put(clusterItem, cluster);<span style="white-space:pre">	</span>//建立item -- cluster 的map
                }
                visitedCandidates.addAll(clusterItems);//将所有框住过的点添加到已访问的List中。
            }
        }
        return results;
    }

简化版的地图聚合算法

百度上面的聚合算法，基本上可以满足百分之九十九的需求。但是，经过测试，在一个很小的区域中密集聚合了1w个以上的点时，在android手机上就会出现内存溢出的情况。所以这时候就需要一个简单并且运算量较小的算法。

地图坐标化

虽然上面的算法不符合我们的要求，但是我们仍然可以获得一个思路，就是把地球展开成一个平面，将经纬度转换成我们熟识的xy二维坐标轴。

但是，为了节省移动端宝贵的内存和运算量，我们完全不需要建立整个世界的坐标系，而只需要建立我们手机屏幕所显示出来的地图的坐标系。如下图所示：

这样的建立坐标系以后，我们将屏幕的左下角看作0点，那么屏幕中任何一个点的相对坐标就是这个点的经纬度减去屏幕左下角那个点的经纬度。

点的聚合

在百度的算法中，可以看作会比较每两个点直接的距离。这样的话，画出来的聚合图虽然好看，但在数据量很大时，效率就比较低下。

所以我们如果对聚合的速度要求很高，但是聚合的效果要求不高的话。可以做这样一个处理。
我们将x轴分割为n份，y轴分割成m份。这样的话整个地图就会被分割成一个个的小方格，我们只需要计算每个方格中的包含的gps点数，即可。这样就完成了一个最基本的聚合。

例如在上图中，我们将地图分割成了n*m份，天津所在的这个小方格内的聚合度就1，其他地方聚合度就是0。

如果这个时候我们在天津所在的这个方格内，再加一个点，这个方格的聚合度就变成了2。

现在点的数目增加多一点

我们来分割一下，横向三格，纵向6格

这样分割以后，出来的聚合效果就是

具体代码

   mBaiduMap.setOnMapStatusChangeListener(new BaiduMap.OnMapStatusChangeListener() {
            @Override
            public void onMapStatusChangeStart(MapStatus mapStatus) {

            }

            @Override
            public void onMapStatusChangeStart(MapStatus mapStatus, int i) {

            }

            @Override
            public void onMapStatusChange(MapStatus mapStatus) {

            }

            @Override
            public void onMapStatusChangeFinish(MapStatus mapStatus) {
                try{
                    //清楚地图上的marker
                    mBaiduMap.clear();

                    //左上角经纬度
                    Point pt = new Point();
                    pt.x = 0;
                    pt.y = 0;
                    LatLng llLeftTop = mBaiduMap.getProjection().fromScreenLocation(pt);

                    //右下角经纬度
                    Point pty = new Point();
                    pty.x = mMapView.getWidth();
                    pty.y = mMapView.getHeight();
                    LatLng llRightBottom = mBaiduMap.getProjection().fromScreenLocation(pty);

                    //屏幕中显示的经度的长度和纬度的长度
                    double mapWidth = llRightBottom.longitude - llLeftTop.longitude;
                    double mapHeight = llLeftTop.latitude - llRightBottom.latitude;

                    //将屏幕中地图分割的横向 格子数和 纵向格子数
                    int widthSize = 10;
                    int heightSize = 20;

                    //计算每个格子的经纬度的长度
                    double unitWidth = mapWidth / widthSize;
                    double unitHeight = mapHeight / heightSize;

                    //用来保存每个格子里面的点的数量
                    int[] pointSize = new int[widthSize * heightSize];

                    //计算每个分隔点内gps点的数量
                    for (MyItem b : myItemList) {
                        LatLng latLng=b.getPosition();
                        //如果点在显示范围内
                        if (latLng.longitude > llLeftTop.longitude &&
                                latLng.longitude < llRightBottom.longitude &&
                                latLng.latitude > llRightBottom.latitude &&
                                latLng.latitude < llLeftTop.latitude) {

                            //计算每个点，相对于左下角的经纬度
                            double relativeX = latLng.longitude - llLeftTop.longitude;
                            double relativeY = latLng.latitude - llRightBottom.latitude;

                            //计算出这个点，处于哪个格子
                            int x = (int) Math.floor(relativeX / unitWidth);
                            int y = (int) Math.floor(relativeY / unitHeight);

                            if (x < 0 || y < 0) {
                                // LogUtil.e("relativeX:" + relativeX + "---------relativeY:" + relativeY);
                            }

                            pointSize[y * widthSize + x] = pointSize[y * widthSize + x] + 1;
                        }


                    }

                    List<OverlayOptions> options = new ArrayList<OverlayOptions>();
                    //设置坐标点
                    BitmapDescriptor bitmap;

                    //绘制每个格子和格子里点的数量
                    for (int y = 0; y < heightSize; y++) {
                        for (int x = 0; x < widthSize; x++) {
                            double lng = llLeftTop.longitude + x * unitWidth;
                            double lat = llRightBottom.latitude + y * unitHeight;

                            //如果格子里点的数量为0 ，则不绘制
                            if (pointSize[y * widthSize + x] == 0) {
                                continue;
                            }

                            TextView textView = new TextView(MarkerClusterDemo.this);
                            textView.setBackgroundColor(getResources().getColor(android.R.color.holo_red_light));
                            textView.setText(pointSize[y * widthSize + x] + "");
                            bitmap = BitmapDescriptorFactory.fromView(textView);

                            LatLng point = new LatLng(lat, lng);
                            OverlayOptions option1 = new MarkerOptions()
                                    .position(point)
                                    .icon(bitmap);
                            options.add(option1);
                        }
                    }

                    //在地图上批量添加
                    mBaiduMap.addOverlays(options);
                }catch (Exception e){
                    e.printStackTrace();
                }

            }

最近项目中遇到用高德制作地图，针对聚合的效果，将一下实现的一些思路。
高德的聚合使用的是AMap.MarkerClusterer，详细的参数设置和说明，可以参考官网的api，这边只根据自己的需求，贴上部分代码

效果：https://kaixin51.github.io/other/cluster.html

需求：在很小的层级时，需要聚合元素，显示这个图标中有多少个元素，单一元素的时候显示该元素，并根据是否预警设置闪烁的效果。
其中高德的闪烁效果实现大致有以下几种方式
1.用Marker的content 自定义一个闪烁效果
2.直接一个gif的图片做闪烁小狗
3.一个定时器自主控制闪烁
4.canvasLayer 去设计一个闪烁图层
这边打算用Marker的content属性来实现，因为聚合图层返回的对象就是一个个的Marker，所以考虑到方案的简便性还是选择了content

下面贴上代码

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
    <script type="text/javascript"
            src="https://webapi.amap.com/maps?v=2.0&key=你自己的高德key&plugin=AMap.GeoJSON"></script>
    <script type="text/javascript" src="js/jquery.3.5.1.js"></script>
</head>
<body>
<div id="map" style="width: 100%;height:500px;"></div>
</body>
<script>
    var map = new AMap.Map('map', {
        zoom: 16,//级别
        center: [119.9494600, 29.3449200],//中心点坐标
        viewMode: '2D'//使用3D视图
    });


    let clusterLayer;

    $.ajax({
        url: 'json/pool.json', //这里就是一组接口返回的数据对象，{status:0,message:[{longitude:121,latitude:31,projectName:'项目名称'}]}
        type: 'get',
        dataType: 'json',
        success: function (result) {
            if (result.status === 0) {
                let markers = [];
                result.message.forEach(element => {
                    if (element.longitude && element.latitude) {
                        markers.push({
                            lnglat: [element.longitude, element.latitude], // 点的经纬度
                            weight: 1, //权重高的将作为聚合的中心点
                            entity: element
                        })
                    }
                })
                let icon = 'image/三角形.png'
                let markerClusterOption = {
                    gridSize: 100,// 聚合像素
                    maxZoom: 16, //当大到该层级后不再聚合
                    renderClusterMarker: function (data) { // 聚合点样式设置
                        data.marker.setIcon(icon)
                        if (data.count > 1) {
                            data.marker.setLabel({
                                content: data.count,
                                direction: "right",
                                // 在 direction 基础上的偏移量
                                offset: [-20, -30]
                            })
                        }
                        return data.marker
                    },
                    renderMarker: function (data) { // 非聚合点样式
                        // 高德聚合图层中  非聚合点默认 setAnchor：top-left offset并不是（0,0）而是根据图片设置了一个特定的偏移，出现定位点不准确，请自行根据图片调整offset
                        data.marker.setIcon(icon)
                        if (data.data[0].entity.projectName === '测试1') {
                            // console.log(data.marker)
                            data.marker.setAnchor('top-left') // Anchor和offset 最好设置一下，不然点不在对应的位置，出现偏移
                            data.marker.setOffset(new AMap.Pixel(0, -16))
                            data.marker.setContent('<div class="marker-route"><div class="marker-title">' + data.data[0].entity.projectName + '</div><div><img class="breath_light" src="' + icon + '"/></div></div>')
                            console.log(data.marker)
                        } else {
                            data.marker.setAnchor('top-left') // Anchor和offset 最好设置一下，不然点不在对应的位置，出现偏移
                            data.marker.setOffset(new AMap.Pixel(0, 0))
                            data.marker.setLabel({
                                content: data.data[0].entity.projectName,
                                direction: "right",
                                // 在 direction 基础上的偏移量
                                offset: [-20, -30]
                            })
                        }

                        data.marker.setExtData(data.data[0].entity)
                        return data.marker
                    }
                }
                map.plugin(["AMap.MarkerClusterer"], function () {
                    clusterLayer = new AMap.MarkerClusterer(map, markers, markerClusterOption);
                });
                // var marker = new AMap.Marker({
                //     position: new AMap.LngLat(120.0830600, 29.2075300),
                //     icon: 'image/三角形.png'
                // })
                // marker.setLabel({
                //     content: '测试',
                //     direction: "right",
                //     // 在 direction 基础上的偏移量
                //     offset: [-20, -30]
                // })
                // marker.setMap(map)
                // console.log(marker)
            }
        }
    })
</script>
<style>
    .amap-marker-label {
        border: none !important;
        background-color: inherit !important;
        color: black;
    }

    .marker-title {
        color: black;
        width: 100px;
        height: 20px;
        top:-32px;
        font-size: 12px;
        /*right:-40px;*/
        /*position: absolute;*/
    }

    .breath_light {
        opacity: 0.1; /* 不透明度 */
        overflow: hidden; /* 背景色 */
        /* margin: 25% auto; */ /* 外边距 */

        /* IE10、Firefox and Opera，IE9以及更早的版本不支持 */
        animation-name: breath; /* 动画名称 */
        animation-duration: 700ms; /* 动画时长3秒 */
        animation-timing-function: ease-in-out; /* 动画速度曲线：以低速开始和结束 */
        animation-iteration-count: infinite; /* 播放次数：无限 */

        /* Safari and Chrome */
        -webkit-animation-name: breath; /* 动画名称 */
        -webkit-animation-duration: 700ms; /* 动画时长3秒 */
        -webkit-animation-timing-function: ease-in-out; /* 动画速度曲线：以低速开始和结束 */
        -webkit-animation-iteration-count: infinite; /* 播放次数：无限 */
    }

    @keyframes breath {
        from {
            opacity: 0.1;
        }
        /* 动画开始时的不透明度 */
        50% {
            opacity: 1;
        }
        /* 动画50% 时的不透明度 */
        to {
            opacity: 0.1;
        }
        /* 动画结束时的不透明度 */
    }

    @-webkit-keyframes breath {
        from {
            opacity: 0.1;
        }
        /* 动画开始时的不透明度 */
        50% {
            opacity: 1;
        }
        /* 动画50% 时的不透明度 */
        to {
            opacity: 0.1;
        }
        /* 动画结束时的不透明度 */
    }
</style>
</html>