开发语言java
org.geotools gt-graph 18.0
Geotools提供了一个Graph的扩展包,这个扩展包不只是对A*算法进行了实现,也对算法Dijkstra进行了实现,两种算法在Geotools中的用法基本一致。
2 基本概念介绍 2.1 Graph(图)可以理解为是一个将要建模的对象的容器,图里面存放的是很多的点(node)和边(edge)。
2.2 Node(点)Node(点)是将要建模的对象,它可以指的是实际地图中的一个坐标点,也可以指的是任意坐标系中的一个点,也可以指的是拓扑图里面的一个节点。构建好的Node全部都存放在Graph中。
2.3 Edge(边)边是指两个Node(点)的关联,一个边下面会有两个点,在图中的边是认为两个点之间可到达,边下面两个点分别表示NodeA和NodeB,节点方向为NodeA->NodeB,
3 在地图上标注POI点,并采集每个点的坐标如图,合肥紫云山公园(随便选的公园),随意标注13个POI点(随便标注的点),采集这13个点的坐标。
坐标采集可以通过百度、或者高德的坐标采集器实现。
如高德坐标采集器地址:高德地图获取地图坐标(GCJ-02坐标) - openGPS.cn
定位到该公园:117.329088,31.739236
获取到13个点的坐标。
4 标注出13个POI的拓扑关系,即到达关系如图,标注出每个POI的拓扑关系(随便标注的)
5 生成Node节点以及Edge边,并标注POI点与Node节点对应关系Node生成出来是无序的,如图所示(需根据生成的Node节点和POI点进行对应)。
//构造点 BasicGraphGenerator basicGraphGenerator = new BasicGraphGenerator(); BasicGraphBuilder basicGraphBuilder = new BasicGraphBuilder(); Coordinate[] coordinates = new Coordinate[12]; coordinates[0] = new Coordinate(104.069649, 30.542246); coordinates[1] = new Coordinate(104.071001, 30.542283); coordinates[2] = new Coordinate(104.073458, 30.542329); ..................... ListnodeList = new ArrayList<>(); for (int i = 0; i < 12; i++) { Node node = basicGraphGenerator.getGraphBuilder().buildNode(); basicGraphGenerator.getGraphBuilder().addNode(node); node.setObject(coordinates[i]); node.setID(i); node.setCount(i); node.setVisited(true); basicGraphBuilder.addNode(node); nodeList.add(node); }
Node生成示例数据如下:V=[6, 9, 1, 7, 4, 2, 8, 10, 5, 11, 3, 0]
Edge生成:
public static Graph buildEdge(BasicGraphBuilder basicGraphBuilder, ListnodeList) { BasicGraphGenerator basicGraphGenerator = new BasicGraphGenerator(); Map map = new HashMap<>(); //维护Edge关系 map.put(1, "2"); map.put(2, "3,12"); map.put(3, "4,10"); map.put(4, "5"); map.put(5, "6"); map.put(6, "7,11"); map.put(7, "8"); map.put(8, "1"); map.put(9, "4"); map.put(10, "9,11"); map.put(11, "12,7"); map.put(12, "7"); for (Map.Entry entry : map.entrySet()) { if (entry.getValue().split(",").length > 1) { String[] strings = entry.getValue().split(","); for (String string : strings) { //判断nodeList数组越界情况 if (Integer.parseInt(string) == 12) { string = "11"; } Edge edge = new BasicEdge(nodeList.get(entry.getKey()), nodeList.get(Integer.parseInt(string))); Long distance = getDistance(nodeList.get(entry.getKey()), nodeList.get(Integer.parseInt(string))); edge.setObject(distance); edge.setVisited(true); basicGraphBuilder.addEdge(edge); } } else { Integer key = entry.getKey(); //判断nodeList数组越界情况 if (Integer.parseInt(entry.getValue()) == 12) { entry.setValue("11"); } //判断nodeList数组越界情况 if (key == 12) { key = 11; } //构造边 Edge edge = new BasicEdge(nodeList.get(key), nodeList.get(Integer.parseInt(entry.getValue()))); Long distance = getDistance(nodeList.get(key), nodeList.get(Integer.parseInt(entry.getValue()))); edge.setObject(distance); edge.setVisited(true); basicGraphBuilder.addEdge(edge); } } System.out.println(basicGraphBuilder.getNodes()); System.out.println(basicGraphBuilder.getGraph()); return basicGraphBuilder.getGraph(); }
Edge生成示例数据如下:
E=[13 (2,3), 25 (10,11), 14 (2,11), 16 (3,10), 18 (5,6), 17 (4,5), 15 (3,4), 24 (10,9), 22 (8,1), 19 (6,7), 23 (9,4), 21 (7,8), 28 (11,7), 20 (6,11), 26 (11,11), 12 (1,2), 27 (11,7)]
注意,Edge括号中,描述的为POI点的序号。
标注Edge的关系,示例如图。
6 使用AStar导航进行计算路径public static void AStarShortestPath(Graph graph, Node startNode, Node endNode) { AStarIterator.AStarFunctions aStarFunction = new AStarIterator.AStarFunctions(endNode) { @Override public double cost(AStarIterator.AStarNode aStarNode, AStarIterator.AStarNode aStarNode1) { Edge edge = aStarNode.getNode().getEdge(aStarNode1.getNode()); System.out.println("edge=" + edge.getID() + ",Distance" + edge.getObject()); // return Integer.parseInt(String.valueOf(edge.getObject())); return 10; } @Override public double h(Node node) { return -10; } }; Date start = new Date(); AStarShortestPathFinder aStarPf = new AStarShortestPathFinder(graph, startNode, endNode, aStarFunction); try { aStarPf.calculate(); Date end = new Date(); System.out.println("AStar算法耗时:" + (end.getTime() - start.getTime())); aStarPf.getPath(); System.out.println("AStar算法距离:" + getPathLength(aStarPf.getPath())); } catch (Exception e) { e.printStackTrace(); } }7 完整代码
import org.geotools.data.DataStore; import org.geotools.data.shapefile.ShapefileDataStore; import org.geotools.data.simple.SimpleFeatureCollection; import org.geotools.feature.FeatureIterator; import org.geotools.graph.build.basic.BasicGraphBuilder; import org.geotools.graph.build.basic.BasicGraphGenerator; import org.geotools.graph.build.feature.FeatureGraphGenerator; import org.geotools.graph.build.line.LineStringGraphGenerator; import org.geotools.graph.path.AStarShortestPathFinder; import org.geotools.graph.path.Path; import org.geotools.graph.structure.Edge; import org.geotools.graph.structure.Graph; import org.geotools.graph.structure.Node; import org.geotools.graph.structure.basic.BasicEdge; import org.geotools.graph.traverse.standard.AStarIterator; import org.geotools.referencing.GeodeticCalculator; import org.geotools.referencing.crs.DefaultGeographicCRS; import org.locationtech.jts.geom.Coordinate; import org.opengis.feature.Feature; import java.io.File; import java.io.IOException; import java.net.MalformedURLException; import java.util.*; public class NavigationUtil { public static void main(String[] args) throws IOException { buildNodeAndEdgeGraph(); } public static void AStarShortestPath(Graph graph, Node startNode, Node endNode) { AStarIterator.AStarFunctions aStarFunction = new AStarIterator.AStarFunctions(endNode) { @Override public double cost(AStarIterator.AStarNode aStarNode, AStarIterator.AStarNode aStarNode1) { Edge edge = aStarNode.getNode().getEdge(aStarNode1.getNode()); System.out.println("edge=" + edge.getID() + ",Distance" + edge.getObject()); // return Integer.parseInt(String.valueOf(edge.getObject())); return 10; } @Override public double h(Node node) { return -10; } }; Date start = new Date(); AStarShortestPathFinder aStarPf = new AStarShortestPathFinder(graph, startNode, endNode, aStarFunction); try { aStarPf.calculate(); Date end = new Date(); System.out.println("AStar算法耗时:" + (end.getTime() - start.getTime())); aStarPf.getPath(); System.out.println("AStar算法距离:" + getPathLength(aStarPf.getPath())); } catch (Exception e) { e.printStackTrace(); } } public static DataStore readShapeFile(File shpFile) throws MalformedURLException { ShapefileDataStore shapefileDataStore = new ShapefileDataStore(shpFile.toURI().toURL()); return shapefileDataStore; } public static Graph buildNodeAndEdgeGraph() { //构造点 BasicGraphGenerator basicGraphGenerator = new BasicGraphGenerator(); BasicGraphBuilder basicGraphBuilder = new BasicGraphBuilder(); Coordinate[] coordinates = new Coordinate[12]; coordinates[0] = new Coordinate(104.069649, 30.542246); coordinates[1] = new Coordinate(104.071001, 30.542283); //此处省略好多点,麻烦自己手动采集 List8 参考文章nodeList = new ArrayList<>(); for (int i = 0; i < 12; i++) { Node node = basicGraphGenerator.getGraphBuilder().buildNode(); basicGraphGenerator.getGraphBuilder().addNode(node); node.setObject(coordinates[i]); node.setID(i); node.setCount(i); node.setVisited(true); basicGraphBuilder.addNode(node); nodeList.add(node); } buildEdge(basicGraphBuilder, nodeList); System.out.println("nodeList:" + nodeList); AStarShortestPath(basicGraphBuilder.getGraph(), nodeList.get(1), nodeList.get(5)); return basicGraphBuilder.getGraph(); } public static Graph buildGraph(SimpleFeatureCollection simFeatureCollect) { //构造线 LineStringGraphGenerator lineStringGen = new LineStringGraphGenerator(); FeatureGraphGenerator featureGen = new FeatureGraphGenerator(lineStringGen); FeatureIterator iter = simFeatureCollect.features(); while (iter.hasNext()) { Feature next = iter.next(); featureGen.add(next); } iter.close(); return featureGen.getGraph(); } public static Graph buildEdge(BasicGraphBuilder basicGraphBuilder, List nodeList) { BasicGraphGenerator basicGraphGenerator = new BasicGraphGenerator(); Map map = new HashMap<>(); map.put(1, "2"); map.put(2, "3,12"); map.put(3, "4,10"); map.put(4, "5"); map.put(5, "6"); map.put(6, "7,11"); map.put(7, "8"); map.put(8, "1"); map.put(9, "4"); map.put(10, "9,11"); map.put(11, "12,7"); map.put(12, "7"); for (Map.Entry entry : map.entrySet()) { if (entry.getValue().split(",").length > 1) { String[] strings = entry.getValue().split(","); for (String string : strings) { if (Integer.parseInt(string) == 12) { string = "11"; } Edge edge = new BasicEdge(nodeList.get(entry.getKey()), nodeList.get(Integer.parseInt(string))); Long distance = getDistance(nodeList.get(entry.getKey()), nodeList.get(Integer.parseInt(string))); edge.setObject(distance); edge.setVisited(true); basicGraphBuilder.addEdge(edge); } } else { Integer key = entry.getKey(); if (Integer.parseInt(entry.getValue()) == 12) { entry.setValue("11"); } if (key == 12) { key = 11; } //构造边 Edge edge = new BasicEdge(nodeList.get(key), nodeList.get(Integer.parseInt(entry.getValue()))); Long distance = getDistance(nodeList.get(key), nodeList.get(Integer.parseInt(entry.getValue()))); edge.setObject(distance); edge.setVisited(true); basicGraphBuilder.addEdge(edge); } } System.out.println(basicGraphBuilder.getNodes()); System.out.println(basicGraphBuilder.getGraph()); return basicGraphBuilder.getGraph(); } public static String getPathLength(Path path) { return path.toString(); } //计算两个节点的经纬度距离 public static Long getDistance(Node nodeA, Node nodeB) { // 84坐标系构造GeodeticCalculator GeodeticCalculator geodeticCalculator = new GeodeticCalculator(DefaultGeographicCRS.WGS84); Coordinate coordinate1 = (Coordinate) nodeA.getObject(); Coordinate coordinate2 = (Coordinate) nodeB.getObject(); // 起点经纬度 geodeticCalculator.setStartingGeographicPoint(coordinate1.getX(), coordinate1.getY()); // 末点经纬度 geodeticCalculator.setDestinationGeographicPoint(coordinate2.getX(), coordinate2.getY()); // 计算距离,单位:米 double orthodromicDistance = geodeticCalculator.getOrthodromicDistance(); return new Double(orthodromicDistance).longValue(); } }
- geoTools的A*(A star)算法计算最优路径 - 掘金 (juejin.cn)