GIS地图点汇聚及空间搜索算法Java实现样例_java经纬度聚合

背景

当需要在GIS地图上显示的点数据量比较大时，会考虑将多个点汇聚成一个点展示；汇聚后图标上显示一个数字，以表示当前汇聚点包含了多少个原始数据对象。用户可以鼠标点击这些汇聚点查看单个原始数据的详细信息。

GIS数据汇聚展示可以让地图呈现更简洁，美观(如果所有点展开，地图缩小时显示得密密麻麻)。另外更重要的一点是可以提升地图渲染的效率。

方案分析

汇聚算法与地图的放大级别(zoom size)，以及当前屏幕窗口边界范围有关。当地图缩小时，数据需要汇聚，地图放大时数据需要展开。经纬度落在屏幕边界范围外的数据不需要展示，这样可以减少加载的数据量，提升性能（坏处是拖动地图时需要重新加载数据, 实测几十万点的情况下延迟两到三秒，还可以接受）。

有两种实现方式：一种是采用空间搜索算法，在地图视窗变化时根据地图放大层级，搜索半径范围的点汇聚在一起；另一种是将屏幕范围内的地图区域划分多个网格，落到同一个网格类的点汇聚在一起(网格大小根据不同的放大层级指定)。

前一种方案实现复杂，地图放大和缩小时点数据汇聚和展开的效果很平滑。后一种画网格的方式实现比较简单，但效果比较差，数据量，位置分布，离群值都会影响汇聚效果。

汇聚算法只能解决点数据的汇聚，如果地图上同时有线数据，与点相连的；处理不好就会出现放大或者缩小时点与线脱节的情况，很影响呈现效果。这种情况通过画网格的方式是解决不了的。

基于空间搜索的方案，有成熟的开源组件SuperCluster(https://github.com/mapbox/supercluster)可用，实测效果也非常好。在使用的过程中发现有性能瓶颈(不是组件本身的算法瓶颈)，由于SuperCluster组件用JS开发的，在前端应用。这就要求后端一次把所有的点数据传到前端，数据量大时传输时间很长。

为解决数据传输性能的问题，需要把汇聚算法放在后台实现，参考SuperCluster的实现逻辑，用Java代码重写了一遍(JSuperCluster)。数据在后台汇聚后再传到前台，10几万个点汇聚后通常只有只百个点。传输数据量减小后，性能得到很大提升。

样例代码

代码目录结构

定义算法基础模型

1. 汇聚模型基础类定义-应用层模型从该类派生

package com.elon.jsc.model;

import lombok.Data;
import java.io.Serializable;

/**
 * 汇聚模型基础类定义。所有需要调用汇聚算法的模型从该类派生。
 *
 * @author elon
 * @version 1.0 2019-03-15
 */
@Data
public class AggregationModelBase implements Serializable {

    private static final long serialVersionUID = 4951392595928922035L;

    /**
     * 对象唯一ID(应用层定义，可以是数据库中对象的自增ID或者其它唯一标识)。
     */
    private int id = -1;

    /**
     * 经度
     */
    private double longitude = 0;

    /**
     * 维度
     */
    private double latitude = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

2. 汇聚算法参数模型定义-最大放大层级根据地图支持的规格而定

package com.elon.jsc.model;

import lombok.Data;

import java.io.Serializable;

/**
 * 汇聚算法参数模型定义
 */
@Data
public class JClusterOption implements Serializable {

    private static final long serialVersionUID = -7916591464862026234L;

    /**
     * 生成聚合数据的最小地图放大层级
     */
    private int minZoom = 0;

    /**
     * 生成数据的最大地图放大层级
     */
    private int maxZoom = 16;

    /**
     * 聚合半径(单位：像素)
     */
    private int radius = 40;

    /**
     * 瓦片大小
     */
    private int extent = 512;

    /**
     * KD-Tree的叶子节点数量
     */
    private int nodeSize = 64;

    private Object reduce = null;

    private Object initial = null;

    private Object map = null;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

3. KD树单点对象模型定义

package com.elon.jsc.model;

import lombok.Data;

import java.io.Serializable;

/**
 * KD树单点对象模型定义。应用层的单个GIS点在计算前转换为该模型。
 *
 * @author elon
 */
@Data
public class JKDNode implements Serializable {

    private static final long serialVersionUID = -7134737233652288121L;

    /**
     * 对象索引ID(算法对数量重新编号后的id)
     */
    private int id = -1;

    /**
     * 父节点ID
     */
    private int parentId = 1;

    /**
     * 地图放大级别
     */
    private int zoom = Integer.MAX_VALUE;

    /**
     * 聚合点的数量
     */
    private int numPoints = 0;

    /**
     * 对象属性
     */
    private Object properties = null;

    /**
     * 对象原始ID，记录应用层汇聚模型的ID值
     */
    private int orignalId = -1;

    /**
     * X坐标
     */
    private double x = 0;

    /**
     * Y坐标
     */
    private double y = 0;

    private int index = -1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

4. 聚合节点模型定义

package com.elon.jsc.model;

import lombok.Data;

import java.io.Serializable;

/**
 * 聚合节点模型定义。
 *
 * @author elon
 * @version 1.0 2019-03-15
 */
@Data
public class JClusterNode <T extends AggregationModelBase> implements Serializable {

    private static final long serialVersionUID = -5358622773451333438L;
    /**
     * 是否聚合对象
     */
    private boolean isCluster = false;

    /**
     * 聚合点的ID
     */
    private int clusterId = -1;

    /**
     * 聚合点数量
     */
    private int pointCount = 0;

    /**
     * 聚合点的X坐标
     */
    private double x = 0;

    /**
     * Y坐标
     */
    private double y = 0;

    /**
     * 聚合点为单点时存储应用层的对象模型。
     */
    private T data = null;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

定义算法底层使用的K-D树

1. K-D树模型定义

将GIS对象放到K-D Tree, 以支持后续的快速搜索。

package com.elon.jsc.kdbush;

import com.elon.jsc.model.JKDNode;

import java.util.Arrays;
import java.util.List;

/**
 * K-D树模型定义，用于GIS点汇聚时空间搜索。根据开源软件KDBush的JS代码翻译而来。
 *
 * @author elon
 * @version 1.0 2019-03-15
 */
public class JKDBush {

    /**
     * KD树节点数量
     */
    private int nodeSize = 64;

    /**
     * 节点列表
     */
    private List<JKDNode> points = null;

    /**
     * 节点ID列表(从0开始新分配的ID)
     */
    private List<Integer> ids = null;

    /**
     * 节点坐标列表(同一个点的X和Y存储在相邻的位置)
     */
    private List<Double> coords = null;

    /**
     * 构造函数。根据传入的KDNode模型初始化数据。
     *
     * @param points KDNode对象模型
     */
    public JKDBush(List<JKDNode> points){
        this.points = points;

        // 分配ID和坐标的存储空间(坐标存储X和Y, 需要两倍的空间)
        ids = Arrays.asList(new Integer[points.size()]);
        coords = Arrays.asList(new Double[points.size() * 2]);

        // 初始化数据
        for (int i = 0; i < points.size(); ++i){
            ids.set(i, i);

            // 偶数位存储X坐标, 奇数位存储Y坐标
            coords.set(2 * i, points.get(i).getX());
            coords.set(2 * i + 1, points.get(i).getY());
        }

        // 排序以支持快速搜索
        new JKDSort(nodeSize, ids, coords).sort(0, ids.size() - 1, 0);
    }

    public List<Integer> range(double minX, double minY, double maxX, double maxY) {
        return new JKDRange(nodeSize, ids, coords).range(minX, minY, maxX, maxY);
    }

    public List<Integer> within(double x, double y, double r) {
        return new JKDWithin(nodeSize, ids, coords).within(x, y, r);
    }

    public int getNodeSize() {
        return nodeSize;
    }

    public void setNodeSize(int nodeSize) {
        this.nodeSize = nodeSize;
    }

    public List<JKDNode> getPoints() {
        return points;
    }

    public void setPoints(List<JKDNode> points) {
        this.points = points;
    }

    public List<Integer> getIds() {
        return ids;
    }

    public void setIds(List<Integer> ids) {
        this.ids = ids;
    }

    public List<Double> getCoords() {
        return coords;
    }

    public void setCoords(List<Double> coords) {
        this.coords = coords;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

2. KD树排序

package com.elon.jsc.kdbush;

import java.util.List;

/**
 * KD树排序
 */
public class JKDSort {

    /**
     * 节点数量
     */
    private int nodeSize;

    /**
     * 节点ID列表
     */
    private List<Integer> ids = null;

    /**
     * 节点坐标列表
     */
    private List<Double> coords = null;

    /**
     * 构造方法
     */
    public JKDSort(int nodeSize, List<Integer> ids, List<Double> coords) {
        this.nodeSize = nodeSize;
        this.ids = ids;
        this.coords = coords;
    }

    /**
     * 数据排序
     *
     * @param left
     * @param right
     * @param depth
     */
    public void sort(int left, int right, int depth) {
        if (right - left <= nodeSize) {
            return;
        }

        // 计算中间节点的位置
        int m = (left + right) / 2;

        // 以中间节点排序
        select(m, left, right, depth % 2);

        // 递归处理左右子树
        sort(left, m - 1, depth + 1);
        sort(m + 1, right, depth + 1);
    }

    /**
     * 排序使左子树的点小于右子树的点。
     *
     * @param k
     * @param left
     * @param right
     * @param depth
     */
    private void select(int k, int left, int right, int depth) {

        while (right > left) {
            if (right - left > 600) {
                int n = right - left + 1;
                int m = k - left + 1;
                double z = Math.log(n);
                double s = 0.5 * Math.exp(2 * z / 3);
                double sd = 0.5 * Math.sqrt(z * s * (n - s) / n) * (m - n / 2 < 0 ? -1 : 1);
                int newLeft = (int) Math.max(left, Math.floor(k - m * s / n + sd));
                int newRight = (int) Math.min(right, Math.floor(k + (n - m) * s / n + sd));
                select(k, newLeft, newRight, depth);
            }

            double t = coords.get(2 * k + depth);
            int i = left;
            int j = right;

            swapItem(left, k);
            if (coords.get(2 * right + depth) > t){
                swapItem(left, right);
            }

            while (i < j) {
                swapItem(i, j);
                i++;
                j--;

                while (coords.get(2 * i + depth) < t) {
                    i++;
                }
                while (coords.get(2 * j + depth) > t) {
                    j--;
                }
            }

            if (Double.compare(coords.get(2 * left + depth), t) == 0) {
                swapItem(left, j);
            } else {
                j++;
                swapItem(j, right);
            }

            if (j <= k) {
                left = j + 1;
            }
            if (k <= j) {
                right = j - 1;
            }

        }
    }

    private void swapItem(int i, int j){
        swapInt(ids, i, j);
        swapDouble(coords, 2 * i, 2 * j);
        swapDouble(coords, 2 * i + 1, 2 * j +1);
    }

    private void swapInt(List<Integer> arr, int i, int j) {
        int tmp = arr.get(i);
        arr.set(i, arr.get(j));
        arr.set(j, tmp);
    }

    private void swapDouble(List<Double> arr, int i, int j) {
        double tmp = arr.get(i);
        arr.set(i, arr.get(j));
        arr.set(j, tmp);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

3. KD-Tree空间范围查询

package com.elon.jsc.kdbush;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * KD-Tree空间范围查询
 */
public class JKDRange {

    /**
     * KD树节点数量
     */
    private int nodeSize;

    /**
     * 节点ID列表
     */
    private List<Integer> ids = null;

    /**
     * 节点坐标列表
     */
    private List<Double> coords = null;

    public JKDRange(int nodeSize, List<Integer> ids, List<Double> coords) {
        this.nodeSize = nodeSize;
        this.ids = ids;
        this.coords = coords;
    }

    /**
     * 查询矩形范围内的点，过滤不在屏幕范围内的对象。
     *
     * @param minX
     * @param minY
     * @param maxX
     * @param maxY
     * @return
     */
    public List<Integer> range(double minX, double minY, double maxX, double maxY) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        stack.push(ids.size() - 1);
        stack.push(0);

        List<Integer> result = new ArrayList<>();

        // 递归搜索KD-Tree上指定范围内的元素。
        while (!stack.isEmpty()) {
            int axis = stack.pop();
            int right = stack.pop();
            int left = stack.pop();

            if (right - left <= nodeSize) {
                for (int i = left; i <= right; i++) {
                    double x = coords.get(2 * i);
                    double y = coords.get(2 * i + 1);
                    if (x >= minX && x <= maxX && y >= minY && y <= maxY) {
                        result.add(ids.get(i));
                    }
                }

                continue;
            }

            int m = (left + right) >> 1;

            // 如果中间节点在范围内，加入结果集。
            double x = coords.get(2 * m);
            double y = coords.get(2 * m + 1);
            if (x >= minX && x <= maxX && y >= minY && y <= maxY){
                result.add(ids.get(m));
            }

            int nextAxis = (axis + 1) % 2;

            if (axis == 0? minX <= x : minY <= y) {
                stack.push(left);
                stack.push(m - 1);
                stack.push(nextAxis);
            }

            if (axis == 0 ? maxX >= x : maxY >= y) {
                stack.push(m + 1);
                stack.push(right);
                stack.push(nextAxis);
            }
        }

        return result;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

4. 按搜索半径查询KD-Tree的数据

package com.elon.jsc.kdbush;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 按搜索半径查询KD-Tree的数据
 */
public class JKDWithin {
    /**
     * KD树节点数量
     */
    private int nodeSize;

    /**
     * 节点ID列表
     */
    private List<Integer> ids = null;

    /**
     * 节点坐标列表
     */
    private List<Double> coords = null;

    public JKDWithin(int nodeSize, List<Integer> ids, List<Double> coords) {
        this.nodeSize = nodeSize;
        this.ids = ids;
        this.coords = coords;
    }

    /**
     * 搜索半径范围内的点。
     *
     * @param qx
     * @param qy
     * @param r
     * @return
     */
    public List<Integer> within(double qx, double qy, double r) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        stack.push(ids.size() - 1);
        stack.push(0);

        List<Integer> result = new ArrayList<>();
        double r2 = r * r;

        // 在KD-Tree上搜索半径范围内的数据
        while (!stack.isEmpty()) {
            int axis = stack.pop();
            int right = stack.pop();
            int left = stack.pop();

            if (right - left <= nodeSize) {
                for (int i = left; i <= right; i++) {
                    if (sqDist(coords.get(2 * i), coords.get(2 * i + 1), qx, qy) <= r2) {
                        result.add(ids.get(i));
                    }
                }

                continue;
            }

            int m = (left + right) >> 1;

            double x = coords.get(2 * m);
            double y = coords.get(2 * m + 1);
            if (sqDist(x, y, qx, qy) <= r2) {
                result.add(ids.get(m));
            }

            int nextAxis = (axis + 1) % 2;

            if (axis == 0 ? qx - r <= x : qy - r <= y) {
                stack.push(left);
                stack.push(m - 1);
                stack.push(nextAxis);
            }

            if (axis == 0 ? qx + r >= x : qy + r >= y) {
                stack.push(m + 1);
                stack.push(right);
                stack.push(nextAxis);
            }
        }

        return result;
    }

    private double sqDist(double ax, double ay, double bx, double by) {
        double dx = ax -bx;
        double dy = ay -by;

        return dx * dx + dy * dy;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

SuperCluster汇聚主类-提供给应用层调用的接口

package com.elon.jsc.supercluster;

import com.elon.jsc.kdbush.JKDBush;
import com.elon.jsc.model.AggregationModelBase;
import com.elon.jsc.model.JClusterNode;
import com.elon.jsc.model.JClusterOption;
import com.elon.jsc.model.JKDNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * SuperCluster汇聚类。
 */
public class JSuperCluster<T extends AggregationModelBase> {
    /**
     * 汇聚算法参数
     */
    private JClusterOption option = null;

    /**
     * K-D树
     */
    private List<JKDBush> trees = null;

    /**
     * 参数汇聚的点数据列表
     */
    private List<T> points = null;

    public JSuperCluster(JClusterOption option) {
        this.option = option;
        this.trees = Arrays.asList(new JKDBush[option.getMaxZoom() + 2]);
    }

    /**
     * 加载数据，生成KD树。
     * @param points
     */
    public void load(List<T> points) {
        this.points = points;

        // 构建聚合点数据
        List<JKDNode> clusters = new ArrayList<>();
        for (int i = 0; i < this.points.size(); i++) {
            if (points.get(i) == null) {
                continue;
            }

            clusters.add(createPointCluster(points.get(i), i));
        }
        trees.set(option.getMaxZoom() + 1, new JKDBush(clusters));

        // 逐层构建每一级的汇聚节点
        for (int z = option.getMaxZoom(); z >= option.getMinZoom(); z--) {
            List<JKDNode> clustersList = buildCluster(clusters, z);

            trees.set(z, new JKDBush(clustersList));
            clusters = clustersList;
        }
    }

    private JKDNode createPointCluster(T p, int id) {
        JKDNode node = new JKDNode();
        node.setId(id);

        node.setX(lngX(p.getLongitude()));
        node.setY(latY(p.getLatitude()));
        node.setParentId(-1);
        node.setZoom(Integer.MAX_VALUE);
        node.setOrignalId(p.getId());
        node.setIndex(id);

        return node;
    }

    /**
     * 获取聚簇对象。
     * @param bbox
     * @param zoom
     * @return
     */
    public List<JClusterNode<T>> getClusters(List<Double> bbox, int zoom) {
        double minLng = ((bbox.get(0) + 180) % 360 + 360) % 360 - 180;
        double minLat = Math.max(-90, Math.min(90, bbox.get(1)));
        double maxLng = bbox.get(2) == 180 ? 180 : ((bbox.get(2) + 180) % 360 + 360) % 360 -180;
        double maxLat = Math.max(-90, Math.min(90, bbox.get(3)));

        if (bbox.get(2) - bbox.get(0) >= 360) {
            minLng = -180;
            maxLng = 180;
        } else if (minLng > maxLng) {
            List<Double> easternBBox = new ArrayList<>();
            easternBBox.add(minLng);
            easternBBox.add(minLat);
            easternBBox.add(180.0);
            easternBBox.add(maxLat);
            List<JClusterNode<T>> easternHem = getClusters(easternBBox, zoom);

            List<Double> westernBBox = new ArrayList<>();
            westernBBox.add(-180.0);
            westernBBox.add(minLat);
            westernBBox.add(maxLng);
            westernBBox.add(maxLat);
            List<JClusterNode<T>> westernHem = getClusters(westernBBox, zoom);

            easternHem.addAll(westernHem);

            return easternHem;
        }

        JKDBush tree = trees.get(limitZoom(zoom));
        List<Integer> ids = tree.range(lngX(minLng), latY(maxLat), lngX(maxLng), latY(minLat));
        List<JClusterNode<T>> clusters = new ArrayList<>();

        for (int id : ids) {
            JKDNode c = tree.getPoints().get(id);
            if (c.getNumPoints() > 0) {
                JClusterNode<T> cn = new JClusterNode<>();
                cn.setCluster(true);
                cn.setClusterId(c.getId());
                cn.setPointCount(c.getNumPoints());
                cn.setX(xLng(c.getX()));
                cn.setY(yLat(c.getY()));
                clusters.add(cn);
            } else {
                T vo = points.get(c.getIndex());
                JClusterNode<T> cn = new JClusterNode<>();
                cn.setClusterId(vo.getId());
                cn.setX(xLng(c.getX()));
                cn.setY(yLat(c.getY()));
                cn.setData(vo);
                clusters.add(cn);
            }
        }

        return clusters;
    }

    /**
     * 获取聚簇节点下所有叶子节点。
     *
     * @param clusterId
     * @return
     */
    public List<T> getLeaves(int clusterId) {
        int limit = Integer.MAX_VALUE;
        int offset = 0;

        List<T> leaves = new ArrayList<>();
        appendLeaves(leaves, clusterId, limit, offset, 0);

        return leaves;
    }

    /**
     * 构建聚簇对象。
     * @param points
     * @param zoom
     * @return
     */
    private List<JKDNode> buildCluster(List<JKDNode> points, int zoom) {
        List<JKDNode> clusters = new ArrayList<>();
        double r = option.getRadius() / (option.getExtent() * Math.pow(2, zoom));

        for (int i = 0; i < points.size(); i++) {
            JKDNode p = points.get(i);
            if (p.getZoom() <= zoom) {
                continue;
            }

            p.setZoom(zoom);

            // 找到所有临近的节点做汇聚
            JKDBush tree = trees.get(zoom + 1);
            List<Integer> neighborIds = tree.within(p.getX(), p.getY(), r);

            int numPoints = (p.getNumPoints() != 0) ? p.getNumPoints() : 1;
            double wx = p.getX() * numPoints;
            double wy = p.getY() * numPoints;

            // cluster id中包含的zoom和原始对象ID的信息
            int id = (i << 5) + (zoom + 1);

            for (int neighborId : neighborIds) {
                JKDNode b = tree.getPoints().get(neighborId);

                // 过滤掉已处理过的邻居节点
                if (b.getZoom() <= zoom) {
                    continue;
                }

                b.setZoom(zoom);
                int numPoints2 = (b.getNumPoints() != 0) ? b.getNumPoints() : 1;
                wx += b.getX() * numPoints2;
                wy += b.getY() * numPoints2;

                numPoints += numPoints2;
                b.setParentId(id);
            }

            if (numPoints == 1) {
                clusters.add(p);
            } else {
                p.setParentId(id);
                clusters.add(createCluster(wx / numPoints, wy / numPoints, id, numPoints, null));
            }
        }

        return clusters;
    }

    /**
     * 获取聚簇节点下的子节点。
     *
     * @param clusterId
     * @return
     */
    private List<JClusterNode<T>> getChildren(int clusterId) {
        int originId = clusterId >> 5;
        int originZoom = clusterId % 32;

        List<JClusterNode<T>> children = new ArrayList<>();

        JKDBush index = this.trees.get(originZoom);
        if (index == null) {
            return children;
        }

        JKDNode origin = index.getPoints().get(originId);
        if (origin == null) {
            return children;
        }

        double r = option.getRadius() / (option.getExtent() * Math.pow(2, originZoom - 1));
        List<Integer> ids = index.within(origin.getX(), origin.getY(), r);

        for (int id : ids) {
            JKDNode c = index.getPoints().get(id);
            if (c.getParentId() == clusterId) {
                if (c.getNumPoints() > 0) {
                    JClusterNode<T> cn = new JClusterNode<>();
                    cn.setCluster(true);
                    cn.setClusterId(c.getId());
                    cn.setPointCount(c.getNumPoints());
                    cn.setX(c.getX());
                    cn.setY(c.getY());
                    children.add(cn);
                } else {
                    T vo = points.get(c.getIndex());
                    JClusterNode<T> cn = new JClusterNode<>();
                    cn.setClusterId(vo.getId());
                    cn.setX(vo.getLongitude());
                    cn.setY(vo.getLatitude());
                    cn.setData(vo);
                    children.add(cn);
                }
            }
        }

        return children;
    }

    /**
     * 添加叶子节点。
     *
     * @param result
     * @param clusterId
     * @param limit
     * @param offset
     * @param skipped
     * @return
     */
    private int appendLeaves(List<T> result, int clusterId, int limit, int offset, int skipped) {
       List<JClusterNode<T>> children = getChildren(clusterId);

       for (JClusterNode<T> child : children) {
           if (child.isCluster()) {
               if (skipped + child.getPointCount() <= offset) {
                   // 跳过整个聚簇节点
                   skipped += child.getPointCount();
               } else {
                   skipped = appendLeaves(result, child.getClusterId(), limit, offset, skipped);
               }
           } else if (skipped < offset) {
               skipped++;
           } else {
               result.add(child.getData());
           }

           if (result.size() == limit) {
               break;
           }
       }

       return skipped;
    }

    private  int limitZoom(int z) {
        return  Math.max(option.getMinZoom(), Math.min(z, option.getMaxZoom() + 1));
    }

    /**
     * 将经度转成墨卡托坐标
     * @param lng
     * @return
     */
    private double lngX(double lng) {
        return lng / 360 + 0.5;
    }

    private double latY(double lat) {
        double sin = Math.sin(lat * Math.PI / 180);
        double y = (0.5 - 0.25 * Math.log((1 + sin) / (1 - sin)) / Math.PI);
        return y < 0 ? 0 : y > 1 ? 1 : y;
    }

    /**
     * 墨卡托坐标转经度。
     * @return
     */
    private double xLng(double x) {
        return (x - 0.5) * 360;
    }

    private double yLat(double y) {
        double y2 = (180 - y * 360) * Math.PI / 180;
        return 360 * Math.atan(Math.exp(y2)) / Math.PI - 90;
    }

    /**
     * 构建聚合节点。
     *
     * @return
     */
    private JKDNode createCluster(double x, double y, int id, int numPoints, Object properties) {
       JKDNode cp = new JKDNode();
       cp.setId(id);
       cp.setX(x);
       cp.setY(y);
       cp.setParentId(-1);
       cp.setNumPoints(numPoints);
       cp.setProperties(properties);

       return cp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349

测试代码

从汇聚基类派生应用层模型

package com.elon.jsc.model;

public class AppModelTest extends AggregationModelBase {

    private String remark = "";

    public String getRemark() {
        return remark;
    }

    public void setRemark(String remark) {
        this.remark = remark;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

构造数据测试

package com.elon.jsc;
import com.alibaba.fastjson.JSONObject;
import com.elon.jsc.model.AppModelTest;
import com.elon.jsc.model.JClusterNode;
import com.elon.jsc.model.JClusterOption;
import com.elon.jsc.supercluster.JSuperCluster;
import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;
import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;

import java.util.ArrayList;
import java.util.List;

/**
 * 应用启动类
 */
@SpringBootApplication
public class StartupSuperCluster {

    private static Logger logger = LogManager.getLogger(StartupSuperCluster.class);

    public static void main(String[] args){
        SpringApplication.run(StartupSuperCluster.class, args);
        logger.info("Start up Java Super Cluster Success!");

        // 测试点的汇聚
        List<AppModelTest> testDataList = new ArrayList<>();
        AppModelTest test1 = new AppModelTest();
        test1.setId(1);
        test1.setLongitude(112.97362);
        test1.setLatitude(27.83088);
        testDataList.add(test1);

        AppModelTest test2 = new AppModelTest();
        test2.setId(2);
        test2.setLongitude(112.98363);
        test2.setLatitude(27.84087);
        testDataList.add(test2);

        JClusterOption option = new JClusterOption();

        JSuperCluster jsc = new JSuperCluster<AppModelTest>(option);
        jsc.load(testDataList);

        List<Double> bbox = new ArrayList<>();
        bbox.add(112.6675);
        bbox.add(27.76451);
        bbox.add(113.13648);
        bbox.add(27.95462);
        List<JClusterNode<AppModelTest>> resultList = jsc.getClusters(bbox, 3);

        System.out.println("汇聚结果:" + JSONObject.toJSONString(resultList));

        System.out.println("显示聚簇点下的叶子节点：");
        for (JClusterNode<AppModelTest> c : resultList) {
            if (c.isCluster()) {
                System.out.println("汇聚节点ID：" + c.getClusterId());
                System.out.println("叶子节点：" + JSONObject.toJSONString(jsc.getLeaves(c.getClusterId())));
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

getClusters方法的第一个参数bbox是当前屏幕的边界(左上角、右下角坐标)；第二个参数取当前地图的放大级别。

运行结果

设置地图放大层级是12时，两个点展开显示：

设置地图放大级别是3时，两个点合并成一个点显示：

GitHub源码路径：https://github.com/ylforever/elon-javasupercluster