|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectde.cm.osm2po.routing.DefaultRouter
public class DefaultRouter
Dijkstra-AStar-Implemetation eines Routings.
Intern wird komplett auf Objekte (verbundene Datentypen) verzichtet.
Stattdessen werden Listen von Objekten, z.B. die der Edge
s,
pro Attribut auf einzelnde Arrays aufgeteilt.
Das bringt einen enormen Geschwindigkeitsgewinn, gerade unter Java.
Unter C++ waere dies unnoetig, da hier Struct-Maskerading moeglich waere.
Der Graph
liefert aus Speichergruenden fuer die Kosten pro Segments
kleine floats. Dies ist hinreichend genau
fuer kurze Segmente (10mm genau auf ~1km), jedoch nicht fuer eine Summe von
Segmenten (1m genau auf ~1000km).
Aus diesem Grund rechnet die PriorityQueue intern mit doubles.
Koordinaten fuer die AStar-Heuristik sind noch ungenauer (~10cm).
Dies ist jedoch zu vernachlaessigen, da es sich lediglich um eine
Heuristik pro Punkt handelt und hier nicht aufsummiert wird.
Der Fehler bleibt hier konstant klein. Abschliessend muss jedoch erwaehnt
sein, dass float schneller als double zu berechnen ist,
Java allerdings kaum float-Funktionen bereitstellt.
Constructor Summary | |
---|---|
DefaultRouter()
|
Method Summary | |
---|---|
protected double |
calcEdgeCost(int edgeIdx)
Liefert die Kosten einer Kante. |
protected double |
calcVertexCost(int vertexId)
Liefert die heuristischen Kosten eines Vertex. |
int[] |
findPath(Graph graph,
int sourceId,
int targetId,
float maxCost,
java.util.Properties params)
Traversiert den Graphen, bricht ab, sobald der Ziel-Vertex besucht wurde und liefert den Path. |
int[] |
getVisited()
Liefert eine Menge aller besuchten VertexIDs. |
boolean |
isVisited(int vertexId)
Liefert true, wenn sich ein Vertex nach der Traversierung in der BlackList (ClosedList) befindet, also besucht bzw. erreicht wurde. |
int[] |
makePath(int toTargetId)
Erstellt den Pfad nach erfolgreichem MultiPathRouter.traverse(Graph, int, int, float, Properties)
Dabei werden vom Ziel die Kanten rueckwaerts durchfahren,
die Reihenfolge umgedreht und vorwaers sortiert zurueckgeliefert. |
void |
reset()
Gibt Speicherresourcen frei. |
void |
setLog(Log log)
Setzt einen optionalen Logger. |
void |
traverse(Graph graph,
int sourceId,
int targetId,
float maxCost,
java.util.Properties params)
Traversiert den Graphen bis zur Abbruchbedingung. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public DefaultRouter()
Method Detail |
---|
public void reset()
SingleTargetRouter
SingleTargetRouter.getVisited()
sind danach nicht mehr
moeglich und verursachen Fehler. Es muss dann erst wieder
SingleTargetRouter.findPath(Graph, int, int, float, Properties)
aufgerufen werden, um auf derartige Informationen
abzugreifen.
reset
in interface SingleTargetRouter
public void setLog(Log log)
SingleTargetRouter
setLog
in interface SingleTargetRouter
log
- Log
public void traverse(Graph graph, int sourceId, int targetId, float maxCost, java.util.Properties params)
traverse
in interface MultiPathRouter
graph
- Graph
sourceId
- Vertex Start Id (1-wertig)targetId
- Vertex Ziel Id (1-wertig)maxCost
- Abbruchbedingung bei Ueberschreitung dieser Kosten.params
- Properties
weitere Einstellungen (NULLABLE).
MultiPathRouter.makePath(int)
,
SingleTargetRouter.getVisited()
public int[] findPath(Graph graph, int sourceId, int targetId, float maxCost, java.util.Properties params)
SingleTargetRouter
findPath
in interface SingleTargetRouter
graph
- Graph
sourceId
- Vertex Start IdtargetId
- Vertex Ziel IdmaxCost
- Maximal zulaessige Wegkosten. Abbruchkriterium.params
- Properties
weitere Einstellungen (NULLABLE).
Edge
-Objekte
vom Start zum Ziel oder null, wenn nicht gefunden.public final int[] makePath(int toTargetId)
MultiPathRouter
MultiPathRouter.traverse(Graph, int, int, float, Properties)
Dabei werden vom Ziel die Kanten rueckwaerts durchfahren,
die Reihenfolge umgedreht und vorwaers sortiert zurueckgeliefert.
makePath
in interface MultiPathRouter
toTargetId
- Id des ZielVertex. Dies muss nicht zwangslaeufig
der Ziel-Knoten, sein. Es kann auch ein beliebiger Vertex aus
SingleTargetRouter.getVisited()
uebergeben werden, um so weitere Pfade zu finden.
Edge
-Objekte
vom Start zum Ziel oder null, wenn kein Pfad vorhanden.public final int[] getVisited()
SingleTargetRouter
getVisited
in interface SingleTargetRouter
public final boolean isVisited(int vertexId)
MultiPathRouter
isVisited
in interface MultiPathRouter
vertexId
- int Id des Vertex > 0.
protected double calcVertexCost(int vertexId)
vertexId
- Id des Vertex
protected double calcEdgeCost(int edgeIdx)
edgeIdx
- int Index in der Adjazenzliste.
|
osm2po-core-4.8.8 (c) 2012 Carsten Moeller - info@osm2po.de | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |