生成两个地理点之间的可能路径
Generating possible paths between 2 Geographical points
我目前正在做一项大学作业,要求我能够以某种方式在地图上的两点之间生成可能的路线。
我在生成路线时遇到问题。我基本上从 2 个点 A 和 B 开始,我在这些点之间创建一条边,我的算法采用中点,在中点的左右两侧生成 2 个新点并创建新边。所以1条边有3种不同的可能性。
这是问题的可爱绘画插图:
这在第一种情况下很好,但我在第二次迭代时遇到了问题,因为每条路线都有 2 条边。我不确定如何迭代生成新路由的过程。我想遍历此过程以创建具有 14 条边的路线,我认为这会导致 2744 种不同的可能路线。
这是我添加第一个 "base edge" 的代码,它是接下来的迭代部分,我不确定如何开始:
List<RouteGraph> routes = new ArrayList<>();
// Add Base Edge between A and B
MarkerNode nodeA = new MarkerNode(markers.get(0).getLat(), markers.get(0).getLng(), markers.get(0).getElevation());
MarkerNode nodeB = new MarkerNode(markers.get(1).getLat(), markers.get(1).getLng(), markers.get(1).getElevation());
RouteGraph baseRoute = new RouteGraph();
baseRoute.addEdge(nodeA, nodeB);
routes.add(baseRoute);
一种解决方案是递归地收缩边,如下代码所示:
import java.util.ArrayList;
import java.util.List;
import javafx.geometry.Point2D;
import javafx.scene.shape.Line;
public class DrawGraph {
private static Point2D start = new Point2D(150,450);
private static Point2D end = new Point2D(450,150);
public static void main(String[] args) {
List<Line> edges = makeEdges(4, start, end);
}
/**
* @param start, end represent base line
* @param numberOfLevels number of levels to build
* @return a list of all edges.
*/
private static List<Line> makeEdges(int numberOfLevels, Point2D start, Point2D end){
List<Line> edges = new ArrayList<>();
makeEdge(numberOfLevels, start, end, edges);
return edges;
}
//recursive construct edges
private static void makeEdge( int levels, Point2D start, Point2D end, List<Line> edges) {
if(levels < 0) return ;
//add edge to list
edges.add(new Line(start.getX(), start.getY(), end.getX(), end.getY()));
//make 2 new points
Point2D[] newPoints = makeNewPoints(start, end);
//recursive make 4 new lines
makeEdge(levels - 1, start, newPoints[0],edges);
makeEdge(levels - 1, newPoints[0], end, edges);
makeEdge(levels - 1, start, newPoints[1], edges);
makeEdge(levels - 1, newPoints[1], end, edges);
}
//returns 2 new points on the center line of the line represented by start, end
//the algorithm calculating the new points can be changed as need
private static Point2D[] makeNewPoints(Point2D start, Point2D end){
//edge's mid point
Point2D midPoint = lineMidPoint(start, end);
//the inclination angle of the edge
double angle = lineAngle(start, end);
//the distance of the 2 new points from the edge. change as needed
double distance = lineLength(start, midPoint) /4 ; //set to edge length / 4
//represents the change in x and in y from midpoint to new point
Point2D deltaXY = newPoint(midPoint, distance, angle);
//make and return 2 new points
return new Point2D[]{
new Point2D(midPoint.getX() + deltaXY.getX(), midPoint.getY() + deltaXY.getY()),
new Point2D(midPoint.getX() - deltaXY.getX(), midPoint.getY() - deltaXY.getY())
};
}
//mid point between two points
private static Point2D lineMidPoint(Point2D p1, Point2D p2) {
return new Point2D((p1.getX() + p2.getX()) /
2, (p1.getY() + p2.getY()) / 2);
}
//angle in radians of a line represented by two points
private static double lineAngle(Point2D start, Point2D end) {
double deltaY = start.getY() - end.getY() ;
double deltaX = end.getX()- start.getX() ;
return Math.atan2(deltaY, deltaX);
}
//length of a line represented by two points
private static double lineLength(Point2D start, Point2D end) {
double deltaY = end.getY() - start.getY();
double deltaX = end.getX() - start.getX();
return Math.sqrt(deltaY*deltaY + deltaX*deltaX);
}
//construct a new point at a distance from point p. angle represents the
//angle of the line p is on.
private static Point2D newPoint(Point2D p, double distance, double angle) {
double deltaY = distance * Math.cos(angle);
double deltaX = distance * Math.sin(angle);
return new Point2D(deltaX, deltaY) ;
}
}
使用 javafx Line
和 Point2D
可以更轻松地可视化 javafx 应用程序的边缘:
然而,Line
和Point2D
只是简单的数据结构,很容易被替换。
我目前正在做一项大学作业,要求我能够以某种方式在地图上的两点之间生成可能的路线。
我在生成路线时遇到问题。我基本上从 2 个点 A 和 B 开始,我在这些点之间创建一条边,我的算法采用中点,在中点的左右两侧生成 2 个新点并创建新边。所以1条边有3种不同的可能性。
这是问题的可爱绘画插图:
这在第一种情况下很好,但我在第二次迭代时遇到了问题,因为每条路线都有 2 条边。我不确定如何迭代生成新路由的过程。我想遍历此过程以创建具有 14 条边的路线,我认为这会导致 2744 种不同的可能路线。
这是我添加第一个 "base edge" 的代码,它是接下来的迭代部分,我不确定如何开始:
List<RouteGraph> routes = new ArrayList<>();
// Add Base Edge between A and B
MarkerNode nodeA = new MarkerNode(markers.get(0).getLat(), markers.get(0).getLng(), markers.get(0).getElevation());
MarkerNode nodeB = new MarkerNode(markers.get(1).getLat(), markers.get(1).getLng(), markers.get(1).getElevation());
RouteGraph baseRoute = new RouteGraph();
baseRoute.addEdge(nodeA, nodeB);
routes.add(baseRoute);
一种解决方案是递归地收缩边,如下代码所示:
import java.util.ArrayList;
import java.util.List;
import javafx.geometry.Point2D;
import javafx.scene.shape.Line;
public class DrawGraph {
private static Point2D start = new Point2D(150,450);
private static Point2D end = new Point2D(450,150);
public static void main(String[] args) {
List<Line> edges = makeEdges(4, start, end);
}
/**
* @param start, end represent base line
* @param numberOfLevels number of levels to build
* @return a list of all edges.
*/
private static List<Line> makeEdges(int numberOfLevels, Point2D start, Point2D end){
List<Line> edges = new ArrayList<>();
makeEdge(numberOfLevels, start, end, edges);
return edges;
}
//recursive construct edges
private static void makeEdge( int levels, Point2D start, Point2D end, List<Line> edges) {
if(levels < 0) return ;
//add edge to list
edges.add(new Line(start.getX(), start.getY(), end.getX(), end.getY()));
//make 2 new points
Point2D[] newPoints = makeNewPoints(start, end);
//recursive make 4 new lines
makeEdge(levels - 1, start, newPoints[0],edges);
makeEdge(levels - 1, newPoints[0], end, edges);
makeEdge(levels - 1, start, newPoints[1], edges);
makeEdge(levels - 1, newPoints[1], end, edges);
}
//returns 2 new points on the center line of the line represented by start, end
//the algorithm calculating the new points can be changed as need
private static Point2D[] makeNewPoints(Point2D start, Point2D end){
//edge's mid point
Point2D midPoint = lineMidPoint(start, end);
//the inclination angle of the edge
double angle = lineAngle(start, end);
//the distance of the 2 new points from the edge. change as needed
double distance = lineLength(start, midPoint) /4 ; //set to edge length / 4
//represents the change in x and in y from midpoint to new point
Point2D deltaXY = newPoint(midPoint, distance, angle);
//make and return 2 new points
return new Point2D[]{
new Point2D(midPoint.getX() + deltaXY.getX(), midPoint.getY() + deltaXY.getY()),
new Point2D(midPoint.getX() - deltaXY.getX(), midPoint.getY() - deltaXY.getY())
};
}
//mid point between two points
private static Point2D lineMidPoint(Point2D p1, Point2D p2) {
return new Point2D((p1.getX() + p2.getX()) /
2, (p1.getY() + p2.getY()) / 2);
}
//angle in radians of a line represented by two points
private static double lineAngle(Point2D start, Point2D end) {
double deltaY = start.getY() - end.getY() ;
double deltaX = end.getX()- start.getX() ;
return Math.atan2(deltaY, deltaX);
}
//length of a line represented by two points
private static double lineLength(Point2D start, Point2D end) {
double deltaY = end.getY() - start.getY();
double deltaX = end.getX() - start.getX();
return Math.sqrt(deltaY*deltaY + deltaX*deltaX);
}
//construct a new point at a distance from point p. angle represents the
//angle of the line p is on.
private static Point2D newPoint(Point2D p, double distance, double angle) {
double deltaY = distance * Math.cos(angle);
double deltaX = distance * Math.sin(angle);
return new Point2D(deltaX, deltaY) ;
}
}
使用 javafx Line
和 Point2D
可以更轻松地可视化 javafx 应用程序的边缘:
然而,Line
和Point2D
只是简单的数据结构,很容易被替换。