最新版本541200007

doum

4 小时以前 d8b9d884967f502caac58d723e57931d0356fa11

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
package com.doumee.core.tsp;
 
/**
 * 聚类分组
 */
import com.doumee.core.utils.Constants;
import com.doumee.dao.admin.request.SketchCateModel;
import com.doumee.dao.business.model.JkSketchCustomer;
import com.doumee.service.business.impl.JkSketchServiceImpl;
 
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
 
public class Clustering {
    public static  List<SketchCateModel>  clusterPoints(List<JkSketchCustomer> points, double threshold) {
 
        List<SketchCateModel> clusters = new ArrayList<>();
        boolean[] visited = new boolean[points.size()];
        int index =0;
        for (int i = 0; i < points.size(); i++) {
            if (!visited[i]) {
                List<JkSketchCustomer> cluster = new ArrayList<>();
                dfs(points, visited, cluster, i, threshold);
                SketchCateModel sketchCateModel = new SketchCateModel();
                sketchCateModel.setCustomerList(cluster);
                sketchCateModel.setId(index);
                sketchCateModel.setStartPoint(cluster.get(0));
                for (JkSketchCustomer c : cluster){
                    sketchCateModel.setTotalNum(Constants.formatBigdecimal(sketchCateModel.getTotalNum()).add(Constants.formatBigdecimal(c.getTotalNum())));
                }
                sketchCateModel.setTotalCustomer(cluster.size());
                clusters.add(sketchCateModel);
            }
        }
        // 打印每个聚类的点
        for (int i = 0; i < clusters.size(); i++) {
            System.out.println("Cluster " + (i + 1) + ": " + clusters.get(i).getStartPoint().getName()+ ": " + clusters.get(i).getCustomerList().size());
        }
        return  clusters;
    }
    public static double distanceTo(JkSketchCustomer self, JkSketchCustomer other) {
        List<DistanceMapParam> distanceMapParamList  =JkSketchServiceImpl.getListFromJsonStr(self.getDistanceJson());
        DistanceMapParam param = JkSketchServiceImpl.getParamByCustomerIds( other.getId(),distanceMapParamList);
        if(param!=null && param.getDistance()!=0){//如果之前已经获取过
          return (param.getDistance());
        }
        return DistanceCalculator.calculateDistance(Constants.formatBigdecimal(self.getLatitude()).doubleValue()
                ,Constants.formatBigdecimal(self.getLongitude()).doubleValue()
                ,Constants.formatBigdecimal(other.getLatitude()).doubleValue()
                ,Constants.formatBigdecimal(other.getLongitude()).doubleValue());
    }
    private static void dfs(List<JkSketchCustomer> points, boolean[] visited, List<JkSketchCustomer> cluster, int startIndex, double threshold) {
        visited[startIndex] = true;
        cluster.add(points.get(startIndex));
        JkSketchCustomer startPoint = points.get(startIndex);
 
        for (int i = 0; i < points.size(); i++) {
            if (!visited[i]) {
                double distance = distanceTo(startPoint,points.get(i));
                if (distance <= threshold) {
                    dfs(points, visited, cluster, i, threshold); // 递归添加到聚类中
                }
            }
        }
    }
 
    /**
     * 117°40′～118°44′、北纬30°19′～31°34′
     * @param args
     */
    public static void main(String[] args) {
        List<JkSketchCustomer> points = new ArrayList<>();
        for (int i = 0; i <3000; i++) {
            JkSketchCustomer a = new JkSketchCustomer();
            a.setLatitude(new BigDecimal(30.19d+(30.54d-30.19d)*Math.random()));
            a.setLongitude(new BigDecimal(117.40+(117.74d-117.40d)*Math.random()));
            a.setName("客户"+i);
            points.add(a);
        }
 
        double threshold = 1000; // 设置距离阈值，超过这个距离就不属于同一聚类。
        clusterPoints(points, threshold);
    }
}