您的位置: 首页  >  文章  >  android百度地图开发--自定义最短路径搜索图层

android百度地图开发--自定义最短路径搜索图层

分类: 文章 • 2024-03-23 15:28:16

原文：http://blog.****.net/wb7931021/article/details/38958957

由于需要，需要在百度地图的基础上实现小范围（例如校园，景区等地）内的详细最短路径导航，百度地图无法实现，因此通过SQLite数据库自行添加地点坐标信息，然后通过Dijkstra算法实现了两地点间的最短路径搜索。

 

直接上代码：

首先是定义的一个节点雷：Side.java

用于存放以及获取节点信息

[java] view plain copy
  1. package com.xjdx.suanfa;  
  2.   
  3. public class Side {  
  4.     private int preNode; //前驱节点  
  5.     private int nextNode;//后继节点  
  6.     private int weight;//权重  
  7.       
  8.     public Side(int preNode,int nextNode,int weight){  
  9.         this.preNode = preNode;  
  10.         this.nextNode = nextNode;  
  11.         this.weight = weight;  
  12.     }  
  13.       
  14.     public int getPreNode(){  
  15.         return this.preNode;  
  16.     }  
  17.       
  18.     public void setPreNode(int preNode){  
  19.         this.preNode = preNode;  
  20.     }  
  21.       
  22.     public int getNextNode(){  
  23.         return this.nextNode;  
  24.     }  
  25.       
  26.     public void setNextNode(int nextNode){  
  27.         this.nextNode = nextNode;  
  28.     }  
  29.       
  30.     public int getWeight(){  
  31.         return this.weight;  
  32.     }  
  33.       
  34.     public void setWeight(int weight){  
  35.         this.weight = weight;  
  36.     }  
  37.       
  38. }  

 

然后是一个用于存储以及获取最短路径类：MinShortPath.java

[java] view plain copy
  1. package com.xjdx.suanfa;  
  2.   
  3. import java.util.ArrayList;  
  4.   
  5. public class MinShortPath {  
  6.     private ArrayList<Integer> nodeList;//最短路径集  
  7.     private int weight;//最短路径  
  8.       
  9.     public MinShortPath(int node){  
  10.         nodeList = new ArrayList<Integer>();  
  11.         nodeList.add(node);  
  12.         weight = -1;  
  13.     }  
  14.       
  15.     public ArrayList<Integer> getNodeList(){  
  16.         return nodeList;  
  17.     }  
  18.       
  19.     public void setNodeList(ArrayList<Integer> nodeList){  
  20.         this.nodeList = nodeList;  
  21.     }  
  22.       
  23.     public void addNode(int node){  
  24.         if(nodeList == null){  
  25.             nodeList = new ArrayList<Integer>();  
  26.         }  
  27.         nodeList.add(0,node);  
  28.     }  
  29.       
  30.     public int getLastNode(){  
  31.         int size = nodeList.size();  
  32.         return nodeList.get(size-1);  
  33.     }  
  34.       
  35.     public int getWeight(){  
  36.         return weight;  
  37.     }  
  38.       
  39.     public void setWeight(int weight){  
  40.         this.weight = weight;  
  41.     }  
  42.       
  43.     public void outputPath(){  
  44.         outputPath(-1);  
  45.     }  
  46.       
  47.     public void outputPath(int srcNode){  
  48.         String result = "[";  
  49.         if(srcNode != -1){  
  50.             nodeList.add(srcNode);  
  51.         }  
  52.         for(int i=0;i<nodeList.size();i++){  
  53.             result += "" + nodeList.get(i);  
  54.             if(i<nodeList.size()-1){  
  55.                 result += ",";  
  56.             }  
  57.         }  
  58.         result +="]:"+weight;  
  59.         System.out.println(result);  
  60.     }  
  61.       
  62.     public void addWeight(int w){  
  63.         if(weight == -1){  
  64.             weight = w;  
  65.         }  
  66.         else{  
  67.             weight += w;  
  68.         }  
  69.     }  
  70. }  


最后是主类linjiejuzhen.java

通过邻接矩阵实现

[java] view plain copy
  1. package com.xjdx.xxxy;  
  2.   
  3. import java.io.File;  
  4. import java.io.FileOutputStream;  
  5. import java.io.IOException;  
  6. import java.io.InputStream;  
  7. import java.io.OutputStream;  
  8. import java.util.ArrayList;  
  9. import java.util.HashMap;  
  10. import java.util.List;  
  11. import java.util.Map;  
  12.   
  13. import com.xjdx.suanfa.MinShortPath;  
  14. import com.xjdx.suanfa.Side;  
  15.   
  16. import android.app.Activity;  
  17. import android.database.Cursor;  
  18. import android.database.SQLException;  
  19. import android.database.sqlite.SQLiteDatabase;  
  20. import android.os.Bundle;  
  21. import android.widget.TextView;  
  22. import android.widget.Toast;  
  23.   
  24. public class linjiejuzhen extends Activity {  
  25.     TextView textView = null;  
  26.     int col, row = 0;  
  27.     private static final String DB_PATH = "/data/data/com.xjdx.xxxy/databases/";  
  28.     private static final String DB_NAME = "PLACE";  
  29.     static ArrayList<Side> map = null;  
  30.     static ArrayList<Integer> redAgg = null;  
  31.     static ArrayList<Integer> blueAgg = null;  
  32.     static Side[] parents = null;  
  33.   
  34.     @Override  
  35.     protected void onCreate(Bundle savedInstanceState) {  
  36.         // TODO Auto-generated method stub  
  37.         super.onCreate(savedInstanceState);  
  38.         super.setContentView(R.layout.linjiejuzhen);  
  39.   
  40.         if ((new File(DB_PATH + DB_NAME)).exists() == false) { // 如 SQLite  
  41.             // 数据库文件不存在，再检查一下 database 目录是否存在  
  42.             File f = new File(DB_PATH); // 如  
  43.             // database 目录不存在，新建该目录  
  44.             if (!f.exists()) {  
  45.                 System.out.println("******************");  
  46.                 f.mkdir();  
  47.             }  
  48.   
  49.             try {  
  50.                 // 得到 assets 目录下我们实现准备好的 SQLite 数据库作为输入流  
  51.                 InputStream is = getBaseContext().getAssets().open(DB_NAME);  
  52.                 // 输出流  
  53.                 OutputStream os = new FileOutputStream(DB_PATH + DB_NAME);  
  54.   
  55.                 // 文件写入  
  56.                 byte[] buffer = new byte[1024];  
  57.                 int length;  
  58.                 while ((length = is.read(buffer)) > 0) {  
  59.                     os.write(buffer, 0, length);  
  60.                 }  
  61.   
  62.                 // 关闭文件流  
  63.                 os.flush();  
  64.                 os.close();  
  65.                 is.close();  
  66.             } catch (Exception e) {  
  67.                 e.printStackTrace();  
  68.             }  
  69.   
  70.         }  
  71.   
  72.         List<Map<String, Object>> list = new ArrayList<Map<String, Object>>();  
  73.   
  74.         try {  
  75.             list = getData();  
  76.             getDistinctData();  
  77.         } catch (SQLException e) {  
  78.             // TODO Auto-generated catch block  
  79.             e.printStackTrace();  
  80.         } catch (IOException e) {  
  81.             // TODO Auto-generated catch block  
  82.             e.printStackTrace();  
  83.         } catch (ClassNotFoundException e) {  
  84.             // TODO Auto-generated catch block  
  85.             e.printStackTrace();  
  86.         }  
  87.   
  88.         this.textView = (TextView) super.findViewById(R.id.textView1);  
  89.         // this.textView.setText(list.get(0).get("VALUE").toString());  
  90.         this.textView.setText("节点个数:" + col);  
  91.         int[][] array;  
  92.         array = new int[col][col];  
  93.         for (int x = 0; x < col; x++) {  
  94.             for (int y = 0; y < col; y++) {  
  95.                 for (int k = 0; k < list.size(); k++) {  
  96.                     if ((x + 1 == (Integer.parseInt(list.get(k)  
  97.                             .get("PRENODE_ID").toString())))  
  98.                             && (y + 1 == (Integer.parseInt(list.get(k)  
  99.                                     .get("NEXTNODE_ID").toString())))) {  
  100.                         array[x][y] = Integer.parseInt(list.get(k).get("VALUE")  
  101.                                 .toString());  
  102.                         break;  
  103.                     }  
  104.                 }  
  105.             }  
  106.         }  
  107.   
  108.         for (int i = 0; i < col; i++) {  
  109.             for (int j = 0; j < col; j++) {  
  110.                 if (array[i][j] == 0) {  
  111.                     array[i][j] = -1;  
  112.                 }  
  113.             }  
  114.         }  
  115.   
  116.         for (int i = 0; i < col; i++) {  
  117.             for (int j = 0; j < col; j++) {  
  118.                 System.out.println(array[i][j]);  
  119.             }  
  120.         }  
  121.   
  122.         int[] nodes = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,  
  123.                 17, 18, 19, 20, 21, 22, 23 };  
  124.         map = new ArrayList<Side>();  
  125.         for (int i = 0; i < list.size(); i++) {  
  126.             map.add(new Side((Integer.parseInt(list.get(i).get("PRENODE_ID")  
  127.                     .toString())), (Integer.parseInt(list.get(i)  
  128.                     .get("NEXTNODE_ID").toString())), (Integer.parseInt(list  
  129.                     .get(i).get("VALUE").toString()))));  
  130.         }  
  131.   
  132.         // 初始化已知最短路径的顶点集，即红点集，只加入顶点0  
  133.         redAgg = new ArrayList<Integer>();  
  134.         redAgg.add(nodes[0]);  
  135.   
  136.         // 初始化未知最短路径的顶点集，即蓝点集  
  137.         blueAgg = new ArrayList<Integer>();  
  138.         for (int i = 1; i < nodes.length; i++) {  
  139.             blueAgg.add(nodes[i]);  
  140.         }  
  141.   
  142.         // 初始化每个顶点在最短路径中的父节点，及它们之间的权重，权重-1表示不连通  
  143.         parents = new Side[nodes.length];  
  144.         parents[0] = new Side(-1, nodes[0], 0);  
  145.         for (int i = 0; i < blueAgg.size(); i++) {  
  146.             int n = blueAgg.get(i);  
  147.             parents[i + 1] = new Side(nodes[0], n, getWeight(nodes[0], n));  
  148.         }  
  149.           
  150.         // 从蓝点集中找出权重最小的那个顶点，并把它加入到红点集中  
  151.         while (blueAgg.size() > 0) {  
  152.             MinShortPath msp = getMinSideNode();  
  153.             if (msp.getWeight() == -1) {  
  154.                 msp.outputPath(nodes[0]);  
  155.             } else {  
  156.                 msp.outputPath();  
  157.             }  
  158.             int node = msp.getLastNode();  
  159.             redAgg.add(node);  
  160.             // 如果因为加入了新的顶点，而导致蓝点集中的顶点的最短路径减小，则要重新设置  
  161.             setWeight(node);  
  162.         }  
  163.     }  
  164.   
  165.     /* 
  166.      * 得到两点之间的权重 
  167.      */  
  168.     public int getWeight(int preNode, int nextNode) {  
  169.         if (map != null) {  
  170.             for (Side s : map) {  
  171.                 if (s.getPreNode() == preNode && s.getNextNode() == nextNode)  
  172.                     return s.getWeight();  
  173.             }  
  174.         }  
  175.         return -1;  
  176.     }  
  177.   
  178.     /* 
  179.      * 从蓝点集合中找出路径最小的节点 
  180.      */  
  181.     public MinShortPath getMinSideNode() {  
  182.         MinShortPath minMsp = null;  
  183.         if (blueAgg.size() > 0) {  
  184.             int index = 0;  
  185.             for (int j = 0; j < blueAgg.size(); j++) {  
  186.                 MinShortPath msp = getMinPath(blueAgg.get(j));  
  187.                 if (minMsp == null || msp.getWeight() != -1  
  188.                         && msp.getWeight() < minMsp.getWeight()) {  
  189.                     minMsp = msp;  
  190.                     index = j;  
  191.                 }  
  192.             }  
  193.             blueAgg.remove(index);  
  194.         }  
  195.         return minMsp;  
  196.     }  
  197.   
  198.     /* 
  199.      * 得到某一节点的最短路径（实际有多条，现在只考虑一条） 
  200.      */  
  201.     public MinShortPath getMinPath(int node) {  
  202.         MinShortPath msp = new MinShortPath(node);  
  203.         if (parents != null && redAgg != null) {  
  204.             for (int i = 0; i < redAgg.size(); i++) {  
  205.                 MinShortPath tempMsp = new MinShortPath(node);  
  206.                 int parent = redAgg.get(i);  
  207.                 int curNode = node;  
  208.                 while (parent > -1) {  
  209.                     int weight = getWeight(parent, curNode);  
  210.                     if (weight > -1) {  
  211.                         tempMsp.addNode(parent);  
  212.                         tempMsp.addWeight(weight);  
  213.                         curNode = parent;  
  214.                         parent = getParent(parents, parent);  
  215.                     } else {  
  216.                         break;  
  217.                     }  
  218.                 }  
  219.                 if (msp.getWeight() == -1 || tempMsp.getWeight() != -1  
  220.                         && msp.getWeight() > tempMsp.getWeight()) {  
  221.                     msp = tempMsp;  
  222.                 }  
  223.             }  
  224.         }  
  225.         return msp;  
  226.     }  
  227.   
  228.     /* 
  229.      * 得到一个节点的父节点 
  230.      */  
  231.     public int getParent(Side[] parents, int node) {  
  232.         if (parents != null) {  
  233.             for (Side nd : parents) {  
  234.                 if (nd.getNextNode() == node) {  
  235.                     return nd.getPreNode();  
  236.                 }  
  237.             }  
  238.         }  
  239.         return -1;  
  240.     }  
  241.   
  242.     /* 
  243.      * 重新设置蓝点集中剩余节点的最短路径长度 
  244.      */  
  245.     public void setWeight(int preNode) {  
  246.         if (map != null && parents != null && blueAgg != null) {  
  247.             for (int node : blueAgg) {  
  248.                 MinShortPath msp = getMinPath(node);  
  249.                 int w1 = msp.getWeight();  
  250.                 if (w1 == -1) {  
  251.                     continue;  
  252.                 }  
  253.                 for (Side n : parents) {  
  254.                     if (n.getNextNode() == node) {  
  255.                         if (n.getWeight() == -1 || n.getWeight() > w1) {  
  256.                             n.setWeight(w1);  
  257.                             n.setPreNode(preNode);  
  258.                             break;  
  259.                         }  
  260.                     }  
  261.                 }  
  262.             }  
  263.         }  
  264.     }  
  265.   
  266.       
  267.     public List<Map<String, Object>> getData() throws IOException,  
  268.             SQLException, ClassNotFoundException {  
  269.         SQLiteDatabase databaseSpiPlace = SQLiteDatabase.openOrCreateDatabase(  
  270.                 DB_PATH + DB_NAME, null);  
  271.         Cursor cursor = databaseSpiPlace.rawQuery("select * from ROUTE_PLAN",  
  272.                 null);  
  273.   
  274.         List<Map<String, Object>> list = new ArrayList<Map<String, Object>>();  
  275.         // ResultSetMetaData md = cursor.get.getMetaData();  
  276.         int columnCount = cursor.getColumnCount();  
  277.         while (cursor.moveToNext()) {  
  278.             Map<String, Object> rowData = new HashMap<String, Object>();  
  279.             for (int i = 0; i < columnCount; i++) {  
  280.                 rowData.put(cursor.getColumnName(i), cursor.getInt(i));  
  281.             }  
  282.             list.add(rowData);  
  283.         }  
  284.         cursor.close();  
  285.         return list;  
  286.     }  
  287.   
  288.     public void getDistinctData() {  
  289.         SQLiteDatabase databaseSpiPlace = SQLiteDatabase.openOrCreateDatabase(  
  290.                 DB_PATH + DB_NAME, null);  
  291.         Cursor cursor = databaseSpiPlace.rawQuery(  
  292.                 "select distinct PRENODE_ID from ROUTE_PLAN", null);  
  293.   
  294.         List<Map<String, Object>> list = new ArrayList<Map<String, Object>>();  
  295.         int i = 0;  
  296.         while (cursor.moveToNext()) {  
  297.             i++;  
  298.         }  
  299.         cursor.close();  
  300.         col = i;  
  301.     }  
  302.   
  303. }  


 结果预览：

图一为通过百度地图搜索而显示的最短路径结果：

android百度地图开发--自定义最短路径搜索图层

图一

 

图二为自定义最短路径搜索结果：

android百度地图开发--自定义最短路径搜索图层

图二

 

 在这里将代码分享出来，供大家参考学习~~~初次发帖，有不足之处望大家指正，相互学习~~


相关推荐