Index: /applications/editors/josm/plugins/public_transport/build.xml
===================================================================
--- /applications/editors/josm/plugins/public_transport/build.xml (revision 28317)
+++ /applications/editors/josm/plugins/public_transport/build.xml (revision 28318)
@@ -27,5 +27,6 @@
-
+
+
Index: /applications/editors/josm/plugins/public_transport/src/public_transport/AStarAlgorithm.java
===================================================================
--- /applications/editors/josm/plugins/public_transport/src/public_transport/AStarAlgorithm.java (revision 28318)
+++ /applications/editors/josm/plugins/public_transport/src/public_transport/AStarAlgorithm.java (revision 28318)
@@ -0,0 +1,127 @@
+package public_transport;
+
+import java.util.Iterator;
+import java.util.Map;
+import java.util.TreeMap;
+import java.util.TreeSet;
+import java.util.Vector;
+
+public abstract class AStarAlgorithm
+{
+ // The following abstract functions and subclasses must be overridden by a class using
+ // AStarAlgorithm.
+
+ public static abstract class Vertex implements Comparable< Vertex >
+ {
+ public abstract int compareTo(Vertex v);
+ };
+
+ public static abstract class Edge
+ {
+ public abstract Vertex getBegin();
+ public abstract Vertex getEnd();
+
+ public abstract double getLength();
+ };
+
+ public abstract Vector< Edge > getNeighbors(Vertex vertex);
+
+ public abstract double estimateDistance(Vertex vertex);
+
+ // end of interface to override -------------------------------------------
+
+ public AStarAlgorithm(Vertex begin, Vertex end)
+ {
+ this.begin = begin;
+ this.end = end;
+ openList = new TreeMap< Vertex, Double >();
+ closedList = new TreeSet< Vertex >();
+ pathTail = new TreeMap< Vertex, Edge >();
+ }
+
+ public Vertex determineCurrentStart()
+ {
+ Vertex minVertex = null;
+ double minDist = 0;
+ Iterator< Map.Entry< Vertex, Double > > iter = openList.entrySet().iterator();
+ while (iter.hasNext())
+ {
+ Map.Entry< Vertex, Double > entry = iter.next();
+ double distance = entry.getValue().doubleValue() + estimateDistance(entry.getKey());
+ if (minVertex == null || distance < minDist)
+ {
+ minDist = distance;
+ minVertex = entry.getKey();
+ }
+ }
+ if (minVertex != null)
+ {
+ System.out.print(openList.get(minVertex).doubleValue());
+ System.out.print("\t");
+ System.out.println(minDist);
+ }
+
+ return minVertex;
+ }
+
+ Vector< Edge > shortestPath()
+ {
+ // Travel through the network
+ Vertex currentStart = begin;
+ openList.put(currentStart, 0.0);
+ while (currentStart != null && !currentStart.equals(end))
+ {
+ double startDistance = openList.get(currentStart).doubleValue();
+
+ // Mark currentStart as visited.
+ openList.remove(currentStart);
+ closedList.add(currentStart);
+
+ Iterator< Edge > neighbors = getNeighbors(currentStart).iterator();
+ while (neighbors.hasNext())
+ {
+ Edge edge = neighbors.next();
+
+ // Don't walk back.
+ if (closedList.contains(edge.getEnd()))
+ continue;
+
+ // Update entry in openList
+ Double knownDistance = openList.get(edge.getEnd());
+ double distance = startDistance + edge.getLength();
+
+ if (knownDistance == null || distance < knownDistance.doubleValue())
+ {
+ openList.put(edge.getEnd(), distance);
+ pathTail.put(edge.getEnd(), edge);
+ }
+ }
+
+ currentStart = determineCurrentStart();
+ }
+
+ if (currentStart == null)
+ return null;
+
+ // Reconstruct the found path
+ Vector< Edge > backwards = new Vector< Edge >();
+ Vertex currentEnd = end;
+ while (!currentEnd.equals(begin))
+ {
+ backwards.add(pathTail.get(currentEnd));
+ currentEnd = pathTail.get(currentEnd).getBegin();
+ }
+
+ Vector< Edge > result = new Vector< Edge >();
+ for (int i = backwards.size()-1; i >= 0; --i)
+ result.add(backwards.elementAt(i));
+ return result;
+ }
+
+ protected Vertex begin;
+ protected Vertex end;
+
+ private TreeSet< Vertex > closedList;
+ private TreeMap< Vertex, Double > openList;
+ private TreeMap< Vertex, Edge > pathTail;
+};
Index: /applications/editors/josm/plugins/public_transport/src/public_transport/PublicTransportAStar.java
===================================================================
--- /applications/editors/josm/plugins/public_transport/src/public_transport/PublicTransportAStar.java (revision 28318)
+++ /applications/editors/josm/plugins/public_transport/src/public_transport/PublicTransportAStar.java (revision 28318)
@@ -0,0 +1,147 @@
+package public_transport;
+
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.TreeMap;
+import java.util.TreeSet;
+import java.util.Vector;
+
+import org.openstreetmap.josm.data.osm.Node;
+import org.openstreetmap.josm.data.osm.Way;
+import org.openstreetmap.josm.Main;
+
+public class PublicTransportAStar extends AStarAlgorithm
+{
+ public PublicTransportAStar(Node start, Node end)
+ {
+ super(new NodeVertex(start), new NodeVertex(end));
+ };
+
+ public static class NodeVertex extends AStarAlgorithm.Vertex
+ {
+ public NodeVertex(Node node)
+ {
+ this.node = node;
+ }
+
+ public int compareTo(AStarAlgorithm.Vertex v)
+ {
+ return this.node.compareTo(((NodeVertex)v).node);
+ }
+
+ public boolean equals(Object o)
+ {
+ if ((NodeVertex)o == null)
+ return false;
+ return node.equals(((NodeVertex)o).node);
+ }
+
+ public Node node;
+ };
+
+ public static class PartialWayEdge extends AStarAlgorithm.Edge
+ {
+ public PartialWayEdge(Way way, int beginIndex, int endIndex)
+ {
+ this.way = way;
+ this.beginIndex = beginIndex;
+ this.endIndex = endIndex;
+ }
+
+ public AStarAlgorithm.Vertex getBegin()
+ {
+ return new NodeVertex(way.getNode(beginIndex));
+ }
+
+ public AStarAlgorithm.Vertex getEnd()
+ {
+ return new NodeVertex(way.getNode(endIndex));
+ }
+
+ public double getLength()
+ {
+ int min = beginIndex;
+ int max = endIndex;
+ if (endIndex < beginIndex)
+ {
+ min = endIndex;
+ max = beginIndex;
+ }
+
+ double totalDistance = 0;
+ for (int i = min; i < max; ++i)
+ totalDistance += way.getNode(i).getCoor().greatCircleDistance(way.getNode(i+1).getCoor());
+ return totalDistance;
+ }
+
+ public Way way;
+ public int beginIndex;
+ public int endIndex;
+ };
+
+ public Vector< AStarAlgorithm.Edge > getNeighbors(AStarAlgorithm.Vertex vertex)
+ {
+ if (waysPerNode == null)
+ {
+ waysPerNode = new TreeMap< Node, TreeSet< Way > >();
+
+ Iterator< Way > iter = Main.main.getCurrentDataSet().getWays().iterator();
+ while (iter.hasNext())
+ {
+ Way way = iter.next();
+
+ // Only consider ways that are usable
+ if (!way.isUsable())
+ continue;
+
+ // Further tests whether the way is eligible.
+
+ for (int i = 0; i < way.getNodesCount(); ++i)
+ {
+ if (waysPerNode.get(way.getNode(i)) == null)
+ waysPerNode.put(way.getNode(i), new TreeSet< Way >());
+ waysPerNode.get(way.getNode(i)).add(way);
+ }
+ }
+ }
+
+ NodeVertex nodeVertex = (NodeVertex)vertex;
+ System.out.println(nodeVertex.node.getUniqueId());
+
+ Vector< AStarAlgorithm.Edge > result = new Vector< AStarAlgorithm.Edge >();
+ // Determine all ways in which nodeVertex.node is contained.
+ Iterator< Way > iter = waysPerNode.get(nodeVertex.node).iterator();
+ while (iter.hasNext())
+ {
+ Way way = iter.next();
+
+ // Only consider ways that are usable
+ if (!way.isUsable())
+ continue;
+
+ // Further tests whether the way is eligible.
+
+ for (int i = 0; i < way.getNodesCount(); ++i)
+ {
+ if (way.getNode(i).equals(nodeVertex.node))
+ {
+ if (i > 0)
+ result.add(new PartialWayEdge(way, i, i-1));
+ if (i < way.getNodesCount()-1)
+ result.add(new PartialWayEdge(way, i, i+1));
+ }
+ }
+ }
+
+ return result;
+ }
+
+ TreeMap< Node, TreeSet< Way > > waysPerNode = null;
+
+ public double estimateDistance(AStarAlgorithm.Vertex vertex)
+ {
+ NodeVertex nodeVertex = (NodeVertex)vertex;
+ return ((NodeVertex)super.end).node.getCoor().greatCircleDistance(nodeVertex.node.getCoor());
+ }
+};
Index: /applications/editors/josm/plugins/public_transport/src/public_transport/RoutePatternAction.java
===================================================================
--- /applications/editors/josm/plugins/public_transport/src/public_transport/RoutePatternAction.java (revision 28317)
+++ /applications/editors/josm/plugins/public_transport/src/public_transport/RoutePatternAction.java (revision 28318)
@@ -1116,4 +1116,8 @@
int insPos = itineraryTable.getSelectedRow();
+ // Temp
+ Node firstNode = null;
+ Node lastNode = null;
+
for (int i = 0; i < currentRoute.getMembersCount(); ++i)
{
@@ -1131,4 +1135,11 @@
itemsToReflect.add(new RelationMember(role, item.getWay()));
+
+ // Temp
+ if (firstNode == null)
+ {
+ firstNode = item.getWay().getNode(0);
+ }
+ lastNode = item.getWay().getNode(item.getWay().getNodesCount() - 1);
}
else if (item.isNode())
@@ -1150,4 +1161,21 @@
if (currentRoute == ((RouteReference)relsListModel.elementAt(i)).route)
relsList.setSelectedIndex(i);
+ }
+
+ // Temp
+ if (firstNode != null)
+ {
+ Vector< AStarAlgorithm.Edge > path = new PublicTransportAStar(firstNode, lastNode).shortestPath();
+ Iterator< AStarAlgorithm.Edge > iter = path.iterator();
+ while (iter.hasNext())
+ {
+ PublicTransportAStar.PartialWayEdge edge = (PublicTransportAStar.PartialWayEdge)iter.next();
+ System.out.print(edge.way.getUniqueId());
+ System.out.print("\t");
+ System.out.print(edge.beginIndex);
+ System.out.print("\t");
+ System.out.print(edge.endIndex);
+ System.out.print("\n");
+ }
}
}
@@ -2108,4 +2136,5 @@
private void fillStoplistTable
(Iterator relIter, int insPos) {
+
while (relIter.hasNext())
{
@@ -2115,15 +2144,15 @@
StopReference sr = detectMinDistance
(curMember.getNode(), segmentMetrics, cbRight.isSelected(), cbLeft.isSelected());
- double offset = segmentMetrics.elementAt((sr.index+1) / 2).distance;
- System.out.print(sr.index);
- System.out.print(" ");
- System.out.print(offset);
- System.out.print(" ");
- System.out.println(sr.pos);
- if (sr.index % 2 == 0)
- offset += sr.pos;
- stoplistData.insertRow(insPos, curMember.getNode(), curMember.getRole(), offset);
- if (insPos >= 0)
- ++insPos;
+ if (sr == null)
+ stoplistData.insertRow(insPos, curMember.getNode(), curMember.getRole(), 360.0);
+ else
+ {
+ double offset = segmentMetrics.elementAt((sr.index+1) / 2).distance;
+ if (sr.index % 2 == 0)
+ offset += sr.pos;
+ stoplistData.insertRow(insPos, curMember.getNode(), curMember.getRole(), offset);
+ if (insPos >= 0)
+ ++insPos;
+ }
}
}
@@ -2174,5 +2203,5 @@
(Node node, Vector< SegmentMetric > segmentMetrics,
boolean rhsPossible, boolean lhsPossible) {
- if (node == null)
+ if (node == null || node.getCoor() == null)
return null;