地图标记聚合算法

需要实现一个地图图标聚合算法, 最终功能类似 安居客 在地图搜索房源的功能. 当地图缩放级别较大时, 仅用一个地图标记显示该区域总数; 当地图缩小至一定级别时, 每条信息才可以显示为单独的图标.

自己拟了一套算法, 基本思想是, 以网格递归分割全部数据点, 直到网格大小达到阈值, 或者每个网格内都仅存在至多一个数据点. 然后根据递归层次 (即网格层次), 将全部数据点依该层次存入一个树型数据结构. 地图缩放时即根据该树型结构取出对应地图缩放层次要显示的数据点, 及聚合数量.
先上思路和伪代码:

定义

常量:
单次等分一边分母为 DIVIDER (方格 4 等分则 DIVIDER 为 2, 9 等分则 DIVIDER 为 3)
单元格可允许的最小边长为 MIN_LENGTH

已知条件:
经纬度点队列 list

变量:
覆盖所有点所需正方形区域边长为 area_length
覆盖所有点所需正方形区域 左下角 (lon1, lat1)
覆盖所有点所需正方形区域 右上角 (lon2, lat2)
分割的最小单元格边长为 grid_length
分割的最小单元格经度差 grid_lon
分割的最小单元格纬度差 grid_lat
分割层级数为 layer_count

函数:
dis(point1, point2) // 两点(经纬度)间距
lon2dis(lon) // 经度差转距离
lat2dis(lat) // 纬度差转距离
dis2lon(dis) // 距离转经度差
dis2lat(dis) // 距离转纬度差

数据结构:

point_layer {
    point       // 点的原始信息
    index_list  // 点的层级列表,层级由大到小降序排列 - [01, 22, 11]
}

index {
    x  // 某一层级内的 横坐标
    y  // 某一层级内的 纵坐标
}

算法步骤 (伪代码)

1. 遍历 list , 得到覆盖所有点的最小边界 (lon1, lat1) (lon2, lat2):

lon1 = lon2 = list.get(0).lon
lat1 = lat2 = list.get(0).lat
for (point in list); do
    lon1 = lon1 < point.lon ? lon1 : point.lon
    lat1 = lat1 < point.lat ? lat1 : point.lat
    lon2 = lon2 > point.lon ? lon2 : point.lon
    lat2 = lat2 > point.lat ? lat2 : point.lat
done

此边界应适当扩大.
点过少或者区域过小时以大数值扩大边界,点多时则以小数值扩大边界:

lon1 = lon1 - offset
lat1 = lat1 - offset
lon2 = lon2 + offset
lat2 = lat2 + offset

2. 确定 area_length 及 区域边界坐标 (左上角, 右下角)

x = lat2dis(lat2 - lat1)
y = lon2dis(lon2 - lon1)
area_length = x > y ? x : y

3. 根据 area_length 及 MIN_LENGTH 即可确定 grid_length 及 layer_count

layer_count = 1
grid_length = area_length
while (grid_length > MIN_LENGTH); do
    grid_length = grid_length / DIVIDER
    layer_count ++
done
grid_lon = dis2lon(grid_length)
grid_lat = dis2lat(grid_length)

4. 根据以上求出的各值, 遍历 list 逐个确定每个点所在的单元格编号.

编号规则可按从左到右, 从下到上顺序等,这里按网格二维坐标编码:

for (point in list); do
    lon_delta = point.lon - lon1  // 距左上角经度
    lat_delta = point.lat - lat1  // 距左上角纬度
    nx = lon_delta / grid_lon  // 整除取整,得到距左下角x轴格子数
    ny = lat_delta / grid_lat  // 整除取整,得到距左下角y轴格子数
    
    // 按层级为每个点做标记,从最小层级开始遍历
    pl = new point_layer()
    pl.point = point
    idx_x = nx
    idx_y = ny
    for (int i = 0; i < layer_count; i ++); do
        idx = new index()
        idx.x = idx_x % DIVIDER  // 取余得本层级内的x坐标
        idx.y = idx_y % DIVIDER  // 取余得本层级内的y坐标
        pl.index_list.add(idx)
        idx_x = idx.x / DIVIDER  // 取除为取得上个层级坐标做准备
        idx_y = idx.y / DIVIDER  // 取除为取得上个层级坐标做准备
    done
    
    pl_list.add(pl)
done

实现

下面开始方案落地. 虽然写的是 Android 程序, 但下面其实是纯 java 代码.

先定义一个标记抽象类(接口) IMarker:

public interface IMarker {
    double getLatitude();
    double getLongitude();
}

定义为接口便于和具体的地图解耦. 因此这套算法即可以用于百度地图, 也可以用于高德, 腾讯等地图. 只需要继承相应地图的标记类, 然后再 implement 这个接口, 就可以应用这套算法了.

然后是最难写的, 节点树的数据结构:

package com.myapp.MapMarkerCluter;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * author: lx
 * date: 16-9-27
 */
public class IndexTree<K, T> {

    private HashMap<K, IndexTree<K, T>> children;
    private IndexTree<K, T> parent;
    private K index;
    private T data;

    private final Object mLock = new Object();

    public IndexTree(K index, T data) {
        this.index = index;
        this.data = data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public K getIndex() {
        return index;
    }

    public void setParent(IndexTree<K, T> parent) {
        this.parent = parent;
    }

    public IndexTree<K, T> putChild(K index, T data) {
        if (index == null) {
            throw new IllegalArgumentException("null index is not acceptable");
        }
        IndexTree<K, T> node = getChild(index);
        if (node != null) {
            node.data = data;
        } else {
            node = new IndexTree<>(index, data);
            node.parent = this;
            synchronized (mLock) {
                if (children == null) {
                    children = new HashMap<>();
                }
                children.put(node.index, node);
            }
        }
        return node;
    }

    public boolean putNodeByIndexList(List<K> indexList, T data) {
        int length;
        if (indexList == null || (length = indexList.size()) == 0) {
            throw new IllegalArgumentException("empty index is not acceptable");
        }
        if (!indexList.get(0).equals(index)) {
            return false;
        }
        if (indexList.size() == 1) {
            this.data = data;
        } else {
            IndexTree<K, T> parent = this;
            K idx;
            for (int i = 1; i < length; i ++) {
                idx = indexList.get(i);
                if (i == length - 1) {
                    // end of index, put data.
                    parent.putChild(idx, data);
                } else {
                    // way index. create if not exist.
                    IndexTree<K, T> node = parent.getChild(idx);
                    if (node == null) {
                        node = parent.putChild(idx, null);
                    }
                    parent = node;
                }
            }
        }
        return true;
    }

    public IndexTree<K, T> getParent() {
        return parent;
    }

    public IndexTree<K, T> getRoot() {
        IndexTree<K, T> node = this;
        while (node.parent != null) {
            node = node.parent;
        }
        return node;
    }

    public IndexTree<K, T> getChild(K index) {
        if (children == null) {
            return null;
        } else {
            return children.get(index);
        }
    }

    public IndexTree<K, T> getNodeByIndexList(List<K> indexList) {
        int length;
        if (indexList == null || (length = indexList.size()) == 0) {
            throw new IllegalArgumentException("empty index is not acceptable");
        }
        if (!indexList.get(0).equals(index)) {
            return null;
        }
        if (indexList.size() == 1) {
            return this;
        } else {
            IndexTree<K, T> node = this;
            K idx;
            for (int i = 1; i < length; i ++) {
                idx = indexList.get(i);
                node = node.getChild(idx);
                if (node == null) {
                    // search fail before reach index end, return null
                    return null;
                }
            }
            return node;
        }
    }

    public List<T> getChildDataList() {
        if (children == null) {
            return null;
        } else {
            ArrayList<T> list = new ArrayList<>(children.size());
            synchronized (mLock) {
                Iterator<IndexTree<K, T>> it = children.values().iterator();
                while (it.hasNext()) {
                    list.add(it.next().data);
                }
            }
            return list;
        }
    }

    public int getChildCount() {
        if (children == null) {
            return 0;
        } else {
            return children.size();
        }
    }

    public Iterator<IndexTree<K, T>> iterateChild() {
        if (children == null) {
            return null;
        } else {
            return children.values().iterator();
        }
    }

    public List<IndexTree<K, T>> getNodeListByLevel(int level) {
        LinkedList<IndexTree<K, T>> ret = new LinkedList<>();
        if (level <= 1) {
            ret.add(this);
            return ret;
        } else if (children == null || children.size() == 0) {
            return null;
        } else {
            synchronized (mLock) {
                Iterator<IndexTree<K, T>> it = children.values().iterator();
                while (it.hasNext()) {
                    List<IndexTree<K, T>> list = it.next().getNodeListByLevel(level - 1);
                    if (list != null) {
                        ret.addAll(list);
                    }
                }
            }
            return ret;
        }
    }

    @Override
    public String toString() {
        return index + "-" + (children == null ? 0 : children.size());
    }
}

此容器的各类查询 (取点, 取列表, 取数量) 基本都由递归实现, 基本就是为了实现上面伪代码逻辑而设计的树型结构.
水平实在有限, 对自己写出的这个泛型容器比较不满意: 基本就只能在这个场景下专用. 并且封装也不甚彻底, 很多逻辑本应在此实现, 但都放在了下面的 MarkerCluster 类中去实现了.

MarkerCluster 类似一个 manager, 即使用上面两个基础类 IMarker 及 IndexTree, 来实现最终的业务逻辑:

package com.myapp.MapMarkerCluter;

import com.fm1031.app.util.Log;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * author: lx
 * date: 16-9-26
 */
public class MarkerCluster {

    // 单次等分一边分母
    private int divider;
    // 单元格可允许的最小边长
    private int grid_min_length;

    private int area_length;
    private double lon1;
    private double lat1;
    private double lon2;
    private double lat2;
    private double grid_lon;
    private double grid_lat;
    private int grid_length;
    private int layer_count;

    private List<? extends IMarker> list;
    private IndexTree<Index, MarkerInfo> index_tree;

    public MarkerCluster(int divider, int gridMinLength) {
        this.divider = divider;
        this.grid_min_length = gridMinLength;
    }

    public boolean isValid() {
        return index_tree != null &&
                (index_tree.getChildCount() != 0 || index_tree.getData() != null);
    }

    public void reset() {
        list = null;
        index_tree = null;
    }

    public void cluster(List<? extends IMarker> markerList) {
        list = markerList;
        cluster();
    }

    public void cluster() {
        if (divider <= 0 || grid_min_length <= 0) {
            throw new IllegalStateException("pre condition not met !");
        }
        if (list == null || list.size() == 0) {
            Log.w("liuxu", "cluster with no data at all");
            return;
        }

        index_tree = new IndexTree<>(new Index(0, 0), null);

        lon1 = lon2 = list.get(0).getLongitude();
        lat1 = lat2 = list.get(0).getLatitude();
        for (int i = list.size() - 1; i >= 0; i --) {
            IMarker m = list.get(i);
            if (m.getLatitude() == 0 || m.getLongitude() == 0) {
                list.remove(m);
                continue;
            }
            lon1 = lon1 < m.getLongitude() ? lon1 : m.getLongitude();
            lat1 = lat1 < m.getLatitude() ? lat1 : m.getLatitude();
            lon2 = lon2 > m.getLongitude() ? lon2 : m.getLongitude();
            lat2 = lat2 > m.getLatitude() ? lat2 : m.getLatitude();
        }
        if (list.size() == 0) {
            // no valid marker in list, just return
            Log.w("liuxu", "cluster with no data at all");
            return;
        }
        {
            // enlarge area
            if (lat1 == lat2) {
                lat1 -= 0.05D;
                lat2 += 0.05D;
            }
            if (lon1 == lon2) {
                lon1 -= 0.05D;
                lon2 += 0.05D;
            }
            double d_lon = (lon2 - lon1) * divider / 2;
            double d_lat = (lat2 - lat1) * divider / 2;
            lon1 -= d_lon;
            lon2 += d_lon / 2;
            lat1 -= d_lat / 2;
            lat2 += d_lat / 2;
        }

        int x_delta = lat2dis(lat2 - lat1);
        int y_delta = lon2dis(lon2 - lon1);
        area_length = x_delta > y_delta ? x_delta : y_delta;

        layer_count = 1;
        grid_length = area_length;
        while (grid_length > grid_min_length) {
            grid_length = grid_length / divider;
            layer_count ++;
        }
        grid_lon = dis2lon(grid_length);
        grid_lat = dis2lat(grid_length);

        for (IMarker m : list) {
            List<Index> index_list = getIndexByLatLon(m.getLatitude(), m.getLongitude());
            IndexTree<Index, MarkerInfo> t = index_tree.getNodeByIndexList(index_list);
            if (t != null && t.getData() != null) {
                t.getData().addMarker(m);
            } else {
                MarkerInfo info = new MarkerInfo(m, index_list);
                index_tree.putNodeByIndexList(info.index_list, info);
            }
        }

        clusterData(index_tree);
    }

    public List<Index> getIndexByLatLon(double lat, double lon) {
        ArrayList<Index> index_list = new ArrayList<>(layer_count);
        double lon_delta = lon - lon1;
        double lat_delta = lat - lat1;
        int nx = (int) (lon_delta / grid_lon);
        int ny = (int) (lat_delta / grid_lat);
        int idx_x = nx > 1 ? nx - 1 : 0;
        int idx_y = ny > 1 ? ny - 1 : 0;
        for (int i = 0; i < layer_count; i ++) {
            Index idx = new Index(idx_x % divider, idx_y % divider);
            idx_x = idx_x / divider;
            idx_y = idx_y / divider;
            index_list.add(0, idx);
        }
        return index_list;
    }

    public int getLevelByArea(
            double lat_bottom, double lon_left, double lat_top, double lon_right) {
        if (lat_bottom > lat2 || lat_top < lat1 || lon_left > lon2 || lon_right < lon1) {
            // out of range
            return 0;
        }
        if ((lat_top - lat_bottom) > 3 * (lat2 - lat1)) {
            return 0;
        }
        int dis_lat = lat2dis(lat_top - lat_bottom);
        int dis_lon = lon2dis(lon_right - lon_left);
        int dis = dis_lat < dis_lon ? dis_lat : dis_lon;
        int level = getLevelByDis(dis * 2 / 3) + 1;
        level = level < layer_count ? level : layer_count;
        //Log.d("liuxu", "getLevelByArea, level: " + level);
        return level;
    }

    public List<MarkerInfo> getMarkerListByLevel(int level) {
        List<IndexTree<Index, MarkerInfo>> nodeList = index_tree.getNodeListByLevel(level);
        if (nodeList != null && nodeList.size() != 0) {
            ArrayList<MarkerInfo> list = new ArrayList<>(nodeList.size());
            for (IndexTree<Index, MarkerInfo> n : nodeList) {
                list.add(n.getData());
            }
            return list;
        } else {
            return null;
        }
    }

    public List<MarkerInfo> getMarkerListByArea(
            double lat_bottom, double lon_left, double lat_top, double lon_right) {
        return getMarkerListByLevel(getLevelByArea(lat_bottom, lon_left, lat_top, lon_right));
    }

    public MarkerInfo clusterData(IndexTree<Index, MarkerInfo> index_tree) {
        int childCount = index_tree.getChildCount();
        if (childCount == 0) {
            return index_tree.getData();
        } else {
            MarkerInfo data = index_tree.getData();
            if (data == null) {
                int marker_count = 0;
                int center_x = divider / 2;
                int center_y = divider / 2;
                double offset = divider * divider;
                MarkerInfo childData = null;
                Iterator<IndexTree<Index, MarkerInfo>> it = index_tree.iterateChild();
                while (it != null && it.hasNext()) {
                    IndexTree<Index, MarkerInfo> tree = it.next();
                    marker_count += clusterData(tree).marker_count;
                    double f = Math.pow(tree.getIndex().x - center_x, 2) +
                            Math.pow(tree.getIndex().y - center_y, 2);
                    if (f < offset) {
                        offset = f;
                        childData = tree.getData();
                    }
                }
                if (childData != null) {
                    data = new MarkerInfo(
                            childData.marker,
                            childData.index_list.subList(0, childData.index_list.size() - 1));
                    data.marker_count = marker_count;
                    index_tree.setData(data);
                }
            }
            return data;
        }
    }

    public int getLevelByDis(int dis) {
        int level = layer_count;
        int d = grid_length;
        while (d < dis) {
            level --;
            d = d * divider;
        }
        return level > 0 ? level : 0;
    }

    public boolean isEndPointMarker(MarkerInfo marker) {
        if (marker == null || marker.getIndexList() == null) {
            return false;
        }
        return marker.getIndexList().size() == layer_count;
    }

    public List<IMarker> getEndPointDataList(MarkerInfo marker) {
        List<IMarker> list = new ArrayList<>();
        return getEndPointDataList(marker, list);
    }

    private List<IMarker> getEndPointDataList(MarkerInfo marker, List<IMarker> list) {
        if (list == null) {
            list = new ArrayList<>();
        }
        if (isEndPointMarker(marker)) {
            if (marker.getMarkerList() != null) {
                list.addAll(marker.getMarkerList());
            } else {
                list.add(marker.getMarker());
            }
            return list;
        } else {
            IndexTree<Index, MarkerInfo> node = index_tree.getNodeByIndexList(marker.getIndexList());
            List<MarkerInfo> childList = node.getChildDataList();
            for (MarkerInfo m : childList) {
                getEndPointDataList(m, list);
            }
            return list;
        }
    }

    // ===========================================
    // about index list

    public static List<Index> getCommonIndexList(List<Index> index1, List<Index> index2) {
        if (index1 == null || index2 == null) {
            return null;
        }
        int size1 = index1.size();
        int size2 = index2.size();
        int size = size1 < size2 ? size1 : size2;
        if (size == 0) {
            return null;
        }
        ArrayList<Index> list = new ArrayList<>(size);
        for (int i = 0; i < size; i ++) {
            Index idx1 = index1.get(i);
            Index idx2 = index2.get(i);
            if (idx1.equals(idx2)) {
                list.add(idx1);
            } else {
                break;
            }
        }
        return list;
    }

    public static boolean containsIndexList(List<Index> list1, List<Index> list2) {
        if (list1 == null || list2 == null) {
            return false;
        }
        if (list1.size() < list2.size()) {
            return false;
        }
        for (int i = 0; i < list1.size(); i ++) {
            if (!list1.get(i).equals(list2.get(i))) {
                return false;
            }
        }
        return true;
    }

    public static boolean equalsIndexList(List<Index> list1, List<Index> list2) {
        if (list1 == null || list2 == null) {
            return false;
        }
        if (list1.size() != list2.size()) {
            return false;
        }
        for (int i = 0; i < list1.size(); i ++) {
            if (!list1.get(i).equals(list2.get(i))) {
                return false;
            }
        }
        return true;
    }

    private Comparator<Index> index_comparator = new Comparator<Index>() {
        @Override
        public int compare(Index lhs, Index rhs) {
            if (lhs.x < rhs.x) {
                return -1;
            } else if (lhs.y < rhs.y) {
                return 1;
            } else {
                return 0;
            }
        }
    };


    // =========================================


    public static int lon2dis(double lon) {
        return (int) Math.abs(lon * 111 * 1000);
    }

    public static int lat2dis(double lat) {
        return (int) Math.abs(lat * 111 * 1000);
    }

    public static double dis2lon(int dis) {
        return Math.abs((double) dis / 1000 / 111);
    }

    public static double dis2lat(int dis) {
        return Math.abs((double) dis / 1000 / 111);
    }

    public static String indexList2string(List<Index> list) {
        if (list == null || list.size() == 0) return null;
        StringBuilder sb = new StringBuilder();
        for (Index idx : list) {
            sb.append("[").append(idx.x).append(",").append(idx.y).append("]");
        }
        return sb.toString();
    }


    // =========================================


    public static class Index {
        int x;
        int y;

        public Index(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object that) {
            if (this == that) return true;
            if (that == null) return false;
            if (!(that instanceof Index)) return false;
            Index index = (Index) that;
            return (this.x == index.x && this.y == index.y);
        }

        @Override
        public int hashCode() {
            return 31 * x + y;
        }

        @Override
        public String toString() {
            return "[" + x + "," + y + "]";
        }
    }

    public static class MarkerInfo {
        IMarker marker;
        List<IMarker> marker_list;
        List<Index> index_list;
        int marker_count;

        public MarkerInfo(IMarker marker, List<Index> index_list) {
            this.marker = marker;
            this.index_list = index_list;
            this.marker_count = 1;
        }

        public void addMarker(IMarker marker) {
            if (marker_list == null) {
                marker_list = new LinkedList<>();
                if (this.marker != null) {
                    marker_list.add(this.marker);
                }
            }
            marker_list.add(marker);
            marker_count = marker_list.size();
        }

        public IMarker getMarker() {
            return marker;
        }

        public List<IMarker> getMarkerList() {
            return marker_list;
        }

        public boolean isMarkerListEmpty() {
            return marker_list != null && marker_list.size() != 0;
        }

        public int getMarkerCount() {
            return marker_count;
        }

        public List<Index> getIndexList() {
            return index_list;
        }

        public String getIndexListString() {
            return indexList2string(index_list);
        }

        @Override
        public String toString() {
            return getIndexListString() + getMarkerCount();
        }
    }

}

后记

该模块与具体地图完全解耦, 百度, 高德, 腾讯 地图都能用.
不说效率如何, 起码最终功能是实现了. 但算法实现水平确实弱了点, 很多地方写的不满意.
可优化的东西也很多, 比如: 目前递归等分是按正方形进行的, 如果给出的数据点的列表分布趋于正方形, 则该算法效率尚可; 如果数据点列表分布在一个窄带内, 则有很大优化余地; 如果数据点列表在较大范围内较稀疏, 则效率很差.
这套东西运行一年倒也没出什么错误, 后续就是新需求赶新需求, 也就没心思去优化这东西了. 各位大牛轻喷~.