高德地图之路线规划 多点路线规划路线最短原则排序算法

继续高德地图  

高德地图-自定义地图

高德地图-自定义导航

tsp最短路线原则和demo下载

继续写路线规划

上一篇写道多点路线规划 高德地图仅仅只会按照你给出的点的顺序进行路线规划 并不会智能的给你按照最近或者最快进行规划 举个例子 A B C D 四个点路线规划 A是起点 D是终点 B C 是途径点 加入你按照 A - B - C - D 的顺序给高德 那么高德返回给你的就是 A - B - C - D这个顺序 加入这时A - B - C - D 并不是最优的路线 是不是就萌币了

不要着急 下面我就是给你一个最优路线

说一下思路 以A - B - C - D 为例 

首先起点A 终点 D 不会变 我们不用管 

现在命名： 

AStartLat 起点纬度 ASP A的起点 

AStartLon 起点经度

BStartLat B起点纬度 BSP 

BStartLon B起点经度

CStartLat C起点纬度 CSP 

CStartLon C起点经度

BEndLat B终点纬度 BEP 

BEndLon B终点经度

CEndLat B终点纬度 CEP 

CEndLon B终点经度

简单做个用例图 

A —> B——>C—–>D 原顺序

A—–>B 10KM 

A—–>C 3KM

A—->C—->B—->D 排序后顺序

我们要做的就是 A —> B——>C—–>D 计算出每两个点的距离 然后比较大小 得到距离最近的点 并以这个点为起点 再次计算下一轮的最近的点 最后得到一个最短的路线 就是我们的最后的目的

好 下面上代码

// 排序所有途经点 

private List sortPoint(List sortList) { 

for (int no = 0; no < sortList.size()*2-1; no++) { 

if (no!=0){// 不是第一次 要判断添加终点 

for (int i = 1; i < startList.size(); i++) { 

for (int j = 1; j < sortList.size(); j++) { 

if (startList.get(i).getLlPoint()==sortList.get(j).getSrartPoint()&&startList.get(i).getLlPoint()!=sortList.get(j).getEndPoint()){ 

Point p = new Point(); 

p.setLlPoint(sortList.get(j).getEndPoint()); 

p.setDistance(0); 

startList.add(p); 

} 

} 

} 

}else {// 第一次 只添加所有起点 

for (int i = 0; i < sortList.size(); i++) { 

Point p = new Point(); 

p.setLlPoint(sortList.get(i).getSrartPoint()); 

p.setDistance(0); 

startList.add(p); 

} 

} 

for (int i = 0; i < startList.size()-1; i++) { 

for (int j = (i+1); j < startList.size(); j++) { 

if (i == 0){ 

startList.get(j).setDistance(DrivingRouteOverlay.calculateDistance(convertToLatLng(startList.get(i).getLlPoint()),convertToLatLng(startList.get(j).getLlPoint()))); 

} 

} 

} 

Collections.sort(startList, new Comparator() { 

@Override 

public int compare(Point o1, Point o2) { 

if (o1.getDistance()==o2.getDistance()){ 

return o1.getDistance(); 

}else { 

return o1.getDistance() - o2.getDistance(); 

} 

} 

}); 

for (int i = 0; i < startList.size(); i++) { 

for (int j = 0; j < startList.size(); j++) { 

if (i!=j){ 

if (startList.get(i).getLlPoint().getLatitude()==startList.get(j).getLlPoint().getLatitude()&&startList.get(i).getLlPoint().getLongitude()==startList.get(j).getLlPoint().getLongitude()){ 

startList.remove(j); 

} 

} 

} 

} 

}

return startList;

}

计算两点之间的距离 

public static int calculateDistance(LatLng start, LatLng end) { 

double x1 = start.longitude; 

double y1 = start.latitude; 

double x2 = end.longitude; 

double y2 = end.latitude; 

return calculateDistance(x1, y1, x2, y2); 

} 

// 根据经纬度计算两点的距离

public static int calculateDistance(double x1, double y1, double x2, double y2) {

    final double NF_pi = 0.01745329251994329; // 弧度 PI/180

    x1 *= NF_pi;

    y1 *= NF_pi;

    x2 *= NF_pi;

    y2 *= NF_pi;

    double sinx1 = Math.sin(x1);

    double siny1 = Math.sin(y1);

    double cosx1 = Math.cos(x1);

    double cosy1 = Math.cos(y1);

    double sinx2 = Math.sin(x2);

    double siny2 = Math.sin(y2);

    double cosx2 = Math.cos(x2);

    double cosy2 = Math.cos(y2);

    double[] v1 = new double[3];

    v1[0] = cosy1 * cosx1 - cosy2 * cosx2;

    v1[1] = cosy1 * sinx1 - cosy2 * sinx2;

    v1[2] = siny1 - siny2;

    double dist = Math.sqrt(v1[0] * v1[0] + v1[1] * v1[1] + v1[2] * v1[2]);

    return (int) (Math.asin(dist / 2) * 12742001.5798544);

}

算法有带点粗糙 感兴趣的可以继续优化方案  这个不但可以计算点的距离 还可以计算多路线规划 设置不同路线颜色等等 看你的需要

如有疑问 欢迎留言或私信