public class TLcdCrossCountryShortestRouteAlgorithm
extends java.lang.Object
Cross country movement is the problem of finding the shortest route between two points in a specific area where no network (nodes and edges) is available. The area has an associated cost function defining for each two points in the area what the cost is to move from the first to the second point in a straight line.
The algorithm is based on the well-known Dijkstra algorithm, but is optimized for cross country movement.
This implementation discretizes the domain in model coordinates. All points and distance that are passed directly or indirectly (e.g. the bounds of a parameter) to an instance of this class or returned directly or indirectly (e.g. the points in the returned route) by an instance of this class are also expressed in this reference, unless explicitely stated otherwise.
Constructor and Description |
---|
TLcdCrossCountryShortestRouteAlgorithm(double aXDiscretizationStep,
double aYDiscretizationStep)
Constructs a new
TLcdCrossCountryShortestRouteAlgorithm with the specified
discretization. |
Modifier and Type | Method and Description |
---|---|
ILcdRoute<ILcdPoint,ILcdPolyline> |
getShortestRoute(ILcdPoint aStartPoint,
ILcdPoint aEndPoint,
ILcdCrossCountryDistanceFunction aDistanceFunction,
ILcdCrossCountryDistanceFunction aHeuristicDistanceFunction,
double aMaxSearchDistance)
Returns an
ILcdRoute describing the shortest route between the start and end
point. |
double |
getXDiscretizationStep()
Returns the distance in the
x direction between the nodes of the discretized
graph. |
double |
getYDiscretizationStep()
Returns the distance in the
y direction between the nodes of the discretized
graph. |
void |
setXDiscretizationStep(double aXDiscretizationStep)
Sets the distance in the
x direction between the nodes of the discretized graph. |
void |
setYDiscretizationStep(double aYDiscretizationStep)
Sets the distance in the
y direction between the nodes of the discretized graph. |
public TLcdCrossCountryShortestRouteAlgorithm(double aXDiscretizationStep, double aYDiscretizationStep)
TLcdCrossCountryShortestRouteAlgorithm
with the specified
discretization.aXDiscretizationStep
- the distance in the x
direction between the nodes of
the discretized graphaYDiscretizationStep
- the distance in the y
direction between the nodes of
the discretized graphjava.lang.IllegalArgumentException
- if the specified x or y discretization step is ≤ 0public double getXDiscretizationStep()
x
direction between the nodes of the discretized
graph.x
direction between the nodes of the discretized
graphpublic void setXDiscretizationStep(double aXDiscretizationStep)
x
direction between the nodes of the discretized graph.aXDiscretizationStep
- the distance in the x
direction between the nodes of
the discretized graphjava.lang.IllegalArgumentException
- if the specified discretization step is ≤ 0public double getYDiscretizationStep()
y
direction between the nodes of the discretized
graph.y
direction between the nodes of the discretized
graphpublic void setYDiscretizationStep(double aYDiscretizationStep)
y
direction between the nodes of the discretized graph.aYDiscretizationStep
- the distance in the y
direction between the nodes of
the discretized graphjava.lang.IllegalArgumentException
- if the specified discretization step is ≤ 0public ILcdRoute<ILcdPoint,ILcdPolyline> getShortestRoute(ILcdPoint aStartPoint, ILcdPoint aEndPoint, ILcdCrossCountryDistanceFunction aDistanceFunction, ILcdCrossCountryDistanceFunction aHeuristicDistanceFunction, double aMaxSearchDistance)
ILcdRoute
describing the shortest route between the start and end
point.aStartPoint
- the start point.aEndPoint
- the end point.aDistanceFunction
- a function that computes the cost to travel from one point to
another.aHeuristicDistanceFunction
- a distance function, indicating the estimated cost to travel
from one point to another. This function can be used to
accelerate the search process. Note that this estimate
should always be an underestimate of the real remaining
distance, in order to result in an optimal solution. A
heuristic function, although it can greatly increase the
performance is not required for the algorithm to work - it
may be null
.aMaxSearchDistance
- the maximum distance of the returned route.null
if no such
route is found.java.lang.IllegalArgumentException
- if the start or end point is not inside the bounds of the
distance function.