Index: applications/editors/josm/plugins/navigator/build.xml =================================================================== --- applications/editors/josm/plugins/navigator/build.xml (revision 3686) +++ applications/editors/josm/plugins/navigator/build.xml (revision 3686) @@ -0,0 +1,136 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + java version: ${java.version} + + + + + + + + + + + + <!-- plugins available on this site --> + <plugins> + <plugin id="${ant.project.name}" version="${plugin.version}"> + <name>${ant.project.name}</name> + <description>${plugin.description}</description> + <resource>${plugin.site.url}${plugin.jar}</resource> + </plugin> + </plugins> + + + + + + + <?xml version="1.0"?> +<site version="1.0"> + <!-- meta data of site --> + <site-info> + <site-name>${plugin.site.description}</site-name> + <site-url>${plugin.site.url}</site-url> + </site-info> + + <!-- plugins available on this site --> + <plugins> + <plugin id="${ant.project.name}" version="${plugin.version}"> + <name>${ant.project.name}</name> + <description>${plugin.description}</description> + <resources> + <resource src="${plugin.site.url}${plugin.jar}" + target="${josm.home.dir}/plugins/${plugin.jar}"/> + </resources> + </plugin> + </plugins> +</site> + + + + + + + + + + + + + + + Index: applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/JosmEdgeFactory.java =================================================================== --- applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/JosmEdgeFactory.java (revision 3686) +++ applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/JosmEdgeFactory.java (revision 3686) @@ -0,0 +1,25 @@ +/** + * + */ +package at.dallermassl.josm.plugin.navigator; + +import org.jgrapht.EdgeFactory; +import org.openstreetmap.josm.data.osm.Node; + +/** + * @author cdaller + * + */ +public class JosmEdgeFactory implements EdgeFactory { + + + + /* (non-Javadoc) + * @see org.jgrapht.EdgeFactory#createEdge(java.lang.Object, java.lang.Object) + */ + public WayEdge createEdge(Node sourceVertex, Node targetVertex) { + throw new RuntimeException("not implemented"); + } + + +} Index: applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/NavigatorAction.java =================================================================== --- applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/NavigatorAction.java (revision 3686) +++ applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/NavigatorAction.java (revision 3686) @@ -0,0 +1,75 @@ +/** + * + */ +package at.dallermassl.josm.plugin.navigator; + +import static org.openstreetmap.josm.tools.I18n.tr; + +import java.awt.event.ActionEvent; +import java.util.ArrayList; +import java.util.Collection; +import java.util.List; + +import javax.swing.AbstractAction; + +import org.openstreetmap.josm.data.SelectionChangedListener; +import org.openstreetmap.josm.data.osm.DataSet; +import org.openstreetmap.josm.data.osm.Node; +import org.openstreetmap.josm.data.osm.OsmPrimitive; + +/** + * @author cdaller + * + */ +public class NavigatorAction extends AbstractAction implements SelectionChangedListener { + private NavigatorPlugin navigatorPlugin; + private List selectedNodes; + private int selectionChangedCalls; + + public NavigatorAction(NavigatorPlugin navigatorPlugin) { + super(tr("Navigate")); + this.navigatorPlugin = navigatorPlugin; + selectedNodes = new ArrayList(); + DataSet.listeners.add(this); + + } + + /* (non-Javadoc) + * @see java.awt.event.ActionListener#actionPerformed(java.awt.event.ActionEvent) + */ + public void actionPerformed(ActionEvent e) { + navigatorPlugin.navigate(selectedNodes); + + } + + /* (non-Javadoc) + * @see org.openstreetmap.josm.data.SelectionChangedListener#selectionChanged(java.util.Collection) + */ + public void selectionChanged(Collection newSelection) { + ++selectionChangedCalls; +// System.out.println("new selection: " + newSelection); +// System.out.println("selection till now: " + selectedNodes); + if(selectionChangedCalls > 1 && (newSelection == null || newSelection.size() == 0)) { + System.out.println("clearing selection for navigation"); + selectedNodes.clear(); + selectionChangedCalls = 0; + return; + } + if(selectionChangedCalls > 1) { + selectionChangedCalls = 0; + } + Node node; + // find a newly selected node and add it to the selection + for(OsmPrimitive selectedElement : newSelection) { + if(selectedElement instanceof Node) { + node = (Node)selectedElement; + if(!selectedNodes.contains(node)) { + selectedNodes.add(node); +// System.out.println("adding node " + node.id); + System.out.println("navigation nodes: " + selectedNodes); + } + } + } + } + +} Index: applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/NavigatorPlugin.java =================================================================== --- applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/NavigatorPlugin.java (revision 3686) +++ applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/NavigatorPlugin.java (revision 3686) @@ -0,0 +1,93 @@ +/** + * + */ +package at.dallermassl.josm.plugin.navigator; + +import static org.openstreetmap.josm.tools.I18n.tr; + +import java.awt.event.ActionEvent; +import java.awt.event.ActionListener; +import java.util.ArrayList; +import java.util.List; + +import javax.swing.JMenu; +import javax.swing.JMenuBar; +import javax.swing.JMenuItem; + +import org.jgrapht.Graph; +import org.jgrapht.alg.DijkstraShortestPath; +import org.openstreetmap.josm.Main; +import org.openstreetmap.josm.data.osm.Node; +import org.openstreetmap.josm.data.osm.Segment; + +/** + * Plugin that allows navigation in josm + * + * @author cdaller + * + */ +public class NavigatorPlugin { + private Graph graph; + + + /** + * + */ + public NavigatorPlugin() { + super(); + JMenuBar menu = Main.main.menu; + JMenu navigatorMenu = new JMenu(tr("Navigation")); + JMenuItem navigatorMenuItem = new JMenuItem(new NavigatorAction(this)); + navigatorMenu.add(navigatorMenuItem); + JMenuItem resetMenuItem = new JMenuItem(tr("Reset Graph")); + resetMenuItem.addActionListener(new ActionListener() { + public void actionPerformed(ActionEvent e) { + graph = null; + } + }); + navigatorMenu.add(resetMenuItem); + menu.add(navigatorMenu); + + } + + public Graph getGraph() { + if(graph == null) { + OsmGraphCreator graphCreator = new OsmGraphCreator(); + //graph = graphCreator.createGraph(); + graph = graphCreator.createSegmentGraph(); + } + return graph; + } + + /** + * @param startNode + * @param endNode + */ + public void navigate(List nodes) { + System.out.print("navigate nodes "); + for(Node node : nodes) { + System.out.print(node.id + ","); + } + System.out.println(); + + DijkstraShortestPath routing; + List fullPath = new ArrayList(); + List path; + for(int index = 1; index < nodes.size(); ++index) { + routing = new DijkstraShortestPath(getGraph(), nodes.get(index - 1), nodes.get(index)); + path = routing.getPathEdgeList(); + if(path == null) { + System.out.println("no path found!"); + return; + } + fullPath.addAll(path); + } + List segmentPath = new ArrayList(); + for(SegmentEdge edge : fullPath) { + segmentPath.add(edge.getSegment()); + } + Main.ds.setSelected(segmentPath); + Main.map.mapView.repaint(); + System.out.println("shortest path found: " + fullPath); + } +} Index: applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/OsmGraphCreator.java =================================================================== --- applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/OsmGraphCreator.java (revision 3686) +++ applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/OsmGraphCreator.java (revision 3686) @@ -0,0 +1,216 @@ +/** + * + */ +package at.dallermassl.josm.plugin.navigator; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.Set; + +import org.jgrapht.Graph; +import org.jgrapht.graph.DirectedWeightedMultigraph; +import org.jgrapht.graph.SimpleDirectedWeightedGraph; +import org.jgrapht.graph.SimpleGraph; +import org.openstreetmap.josm.Main; +import org.openstreetmap.josm.data.osm.Node; +import org.openstreetmap.josm.data.osm.Segment; +import org.openstreetmap.josm.data.osm.Way; + +/** + * @author cdaller + * + */ +public class OsmGraphCreator { + private Map> nodeSegmentMap = new HashMap>(); + private Set segments = new HashSet(); + private Set ways = new HashSet(); + private Set crossingNodes = new HashSet(); + private List edges = new ArrayList(); + + private Map highwayWeight; + private static final double DEFAULT_WEIGHT = Double.MAX_VALUE; + + public OsmGraphCreator() { + highwayWeight = new HashMap(); + highwayWeight.put("motorway", 130.0); + highwayWeight.put("primary", 100.0); + highwayWeight.put("secondary", 70.0); + highwayWeight.put("unclassified", 50.0); + highwayWeight.put("residential", 40.0); + } + + public Graph createSegmentGraph() { + SimpleDirectedWeightedGraph graph = new SimpleDirectedWeightedGraph(SegmentEdge.class); + //SimpleGraph graph = new SimpleGraph(SegmentEdge.class); + SegmentEdge edge; + double weight; + // iterate all ways and segments for all nodes: + for(Way way : Main.ds.ways) { + for(Segment segment : way.segments) { + if(segment.from.id == 21100429 | segment.to.id == 21100429) { + System.out.println("loggin tegetthoff/radetzky for way " + way.get("name") + ", seg = " + segment); + } + graph.addVertex(segment.from); + graph.addVertex(segment.to); + edge = new SegmentEdge(segment); + graph.addEdge(segment.from, segment.to, edge); + weight = getWeight(way, segment); + System.out.println("edge for segment " + segment.id + "(from node "+ segment.from.id + " to node " + + segment.to.id + ") has weight: " + weight); + graph.setEdgeWeight(edge, weight); + if(!isOneWay(way)) { + edge = new SegmentEdge(segment); // create a second edge for other direction + graph.addEdge(segment.to, segment.from, edge); + graph.setEdgeWeight(edge, weight); + System.out.println("inverse segment " + segment.id + "(from node "+ segment.to.id + " to node " + + segment.from.id + ") has weight: " + weight); + } + } + } + return graph; + } + + /** + * Returns the weight for the given segment depending on the highway type and the length of the + * segment. + * @param way + * @param segment + * @return + */ + public double getWeight(Way way, Segment segment) { + String type = way.get("highway"); + if(type == null) { + return 0.0d; + } + Double weightValue = highwayWeight.get(type); + double weight; + if(weightValue == null) { + weight = DEFAULT_WEIGHT; + } else { + weight = weightValue.doubleValue(); + } + double distance = segment.from.coor.distance(segment.to.coor) * 111000; // deg to m (at equator :-) + return distance / weight; + } + + public boolean isOneWay(Way way) { + // FIXXME: oneway=-1 is ignored for the moment! + return way.get("oneway") != null || "motorway".equals(way.get("highway")); + } + + public Graph createGraph() { + createEdges(); + DirectedWeightedMultigraph graph = new DirectedWeightedMultigraph(new JosmEdgeFactory()); + + for(WayEdge edge : edges) { + graph.addVertex(edge.getStartNode()); + graph.addVertex(edge.getEndNode()); + graph.addEdge(edge.getStartNode(), edge.getEndNode(), edge); + } + return graph; + } + + private void createEdges() { + System.out.println("Start free Memory: " + (Runtime.getRuntime().freeMemory())); + // iterate all ways and segments for all nodes: + for(Way way : Main.ds.ways) { + for(Segment segment : way.segments) { + addSegmentForNode(segment.from, segment); + addSegmentForNode(segment.to, segment); + segments.add(segment); + } + //ways.add(way); + } + System.out.println("after all segments free Memory: " + (Runtime.getRuntime().freeMemory())); + // find nodes with one or more than two segments: + Set nodeSegments; + for(Node node : nodeSegmentMap.keySet()) { + nodeSegments = nodeSegmentMap.get(node); + if(nodeSegments.size() == 1 || nodeSegments.size() > 2) { + crossingNodes.add(node); + } + } + System.out.println("after all crossings free Memory: " + (Runtime.getRuntime().freeMemory())); + System.out.println("Number of Nodes: " + Main.ds.nodes.size()); + System.out.println("Number of Segments: " + Main.ds.segments.size()); + System.out.println("Number of Graph Vertices: " + crossingNodes.size()); + System.out.println("Number of Nodes in Segment Map: " + nodeSegmentMap.keySet().size()); + // find for every crossing node all connected crossing nodes: + Node targetNode; + WayEdge edge; + List edgeSegments; + for(Node sourceNode : crossingNodes) { + targetNode = sourceNode; + for(Segment segment : nodeSegmentMap.get(sourceNode)) { + edge = new WayEdge(); + edgeSegments = new ArrayList(); + boolean crossingReached = false; + do { + targetNode = getOtherEnd(targetNode, segment); + edgeSegments.add(segment); + // FIXXME calculate length of segment for edge + if(crossingNodes.contains(targetNode)) { + crossingReached = true; + } else { + segment = getOtherSegment(targetNode, segment); + } + } while(!crossingReached); + edge.setSegments(edgeSegments); + edge.setStartNode(sourceNode); + edge.setEndNode(targetNode); + System.out.println("Adding edge with " + edgeSegments.size() +" segments: " + edgeSegments); + System.out.println("after adding edge free Memory: " + (Runtime.getRuntime().freeMemory())); + edges.add(edge); + } + } + } + + /** + * Returns the other segment for the given node (works only for non crossing + * nodes). + * @param node + * @param segment + * @return + */ + private Segment getOtherSegment(Node node, Segment segment) { + Set segments = nodeSegmentMap.get(node); + if(segments.size() != 2) { + throw new RuntimeException("the given node has more than two nodes!"); + } + if(!segments.contains(segment)) { + throw new RuntimeException("the given segment is not connected to the given node"); + } + Iterator segIter = segments.iterator(); + Segment next = segIter.next(); + if(segment.equals(next)) { + return segIter.next(); + } else { + return segment; + } + } + + private void addSegmentForNode(Node node, Segment segment) { + Set segments = nodeSegmentMap.get(node); + if(segments == null) { + segments = new HashSet(); + nodeSegmentMap.put(node, segments); + } + if(!segments.contains(segment)) { + segments.add(segment); + } + } + + private Node getOtherEnd(Node node, Segment segment) { + if(segment.from.equals(node)) { + return segment.to; + } else { + return segment.from; + } + } + + +} Index: applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/SegmentEdge.java =================================================================== --- applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/SegmentEdge.java (revision 3686) +++ applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/SegmentEdge.java (revision 3686) @@ -0,0 +1,36 @@ +/** + * + */ +package at.dallermassl.josm.plugin.navigator; + +import org.jgrapht.graph.DefaultWeightedEdge; +import org.openstreetmap.josm.data.osm.Segment; + +/** + * @author cdaller + * + */ +public class SegmentEdge extends DefaultWeightedEdge { + private Segment segment; + + public SegmentEdge() { + super(); + System.out.println("warning: edge without segment!"); + } + + /** + * @param segment + */ + public SegmentEdge(Segment segment) { + super(); + this.segment = segment; + } + + /** + * @return the segment + */ + public Segment getSegment() { + return this.segment; + } + +} Index: applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/WayEdge.java =================================================================== --- applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/WayEdge.java (revision 3686) +++ applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/WayEdge.java (revision 3686) @@ -0,0 +1,87 @@ +/** + * + */ +package at.dallermassl.josm.plugin.navigator; + +import java.util.List; + +import org.openstreetmap.josm.data.osm.Node; +import org.openstreetmap.josm.data.osm.Segment; + +/** + * @author cdaller + * + */ +public class WayEdge { + private long length; + private Node startNode; + private Node endNode; + private List segments; + + public WayEdge() { + + } + + public WayEdge(int length) { + this.length = length; + } + + /** + * @return the length + */ + public long getLength() { + return this.length; + } + + /** + * @param length the length to set + */ + public void setLength(long length) { + this.length = length; + } + + /** + * @return the segments + */ + public List getSegments() { + return this.segments; + } + + /** + * @param segments the segments to set + */ + public void setSegments(List segments) { + this.segments = segments; + } + + /** + * @return the startNode + */ + public Node getStartNode() { + return this.startNode; + } + + /** + * @param startNode the startNode to set + */ + public void setStartNode(Node startNode) { + this.startNode = startNode; + } + + /** + * @return the endNode + */ + public Node getEndNode() { + return this.endNode; + } + + /** + * @param endNode the endNode to set + */ + public void setEndNode(Node endNode) { + this.endNode = endNode; + } + + + +}