Changeset 3832 in osm


Ignore:
Timestamp:
2007-07-29T01:02:57+02:00 (17 years ago)
Author:
christofd
Message:

add way to edge for description

File:
1 edited

Legend:

Unmodified
Added
Removed

  • applications/editors/josm/plugins/navigator/src/at/dallermassl/josm/plugin/navigator/OsmGraphCreator.java

    r3749 r3832  
    2323/**
    2424 * @author cdaller
    25  *
     25 * 
    2626 */
    2727public class OsmGraphCreator {
    28   private Map<Node, Set<Segment>> nodeSegmentMap = new HashMap<Node, Set<Segment>>();
    29   private Set<Segment> segments = new HashSet<Segment>();
    30   private Set<Way> ways = new HashSet<Way>();
    31   private Set<Node> crossingNodes = new HashSet<Node>();
    32   private List<WayEdge> edges = new ArrayList<WayEdge>();
    33  
    34   private Map<String, Double> highwayWeight;
    35   private static final double DEFAULT_WEIGHT = Double.MAX_VALUE;
    36  
    37   public OsmGraphCreator() {
    38     highwayWeight = new HashMap<String, Double>();
    39     highwayWeight.put("motorway", 130.0);
    40     highwayWeight.put("primary", 100.0);
    41     highwayWeight.put("secondary", 70.0);
    42     highwayWeight.put("unclassified", 50.0);
    43     highwayWeight.put("residential", 40.0);
    44     highwayWeight.put("footway", 1.0);
    45   }
    46  
    47   public Graph<Node, SegmentEdge> createSegmentGraph() {
    48     SimpleDirectedWeightedGraph<Node, SegmentEdge> graph = new SimpleDirectedWeightedGraph<Node, SegmentEdge>(SegmentEdge.class);
    49     //SimpleGraph<Node, SegmentEdge> graph = new SimpleGraph<Node, SegmentEdge>(SegmentEdge.class);
    50     SegmentEdge edge;
    51     double weight;
    52     // iterate all ways and segments for all nodes:
    53     for(Way way : Main.ds.ways) {
    54       for(Segment segment : way.segments) {
    55         if(segment.from.id == 21100429 | segment.to.id == 21100429) {
    56           System.out.println("loggin tegetthoff/radetzky for way " + way.get("name") + ", seg = " + segment);
    57         }
    58         graph.addVertex(segment.from);
    59         graph.addVertex(segment.to);
    60         edge = new SegmentEdge(segment);
    61         graph.addEdge(segment.from, segment.to, edge);
    62         weight = getWeight(way, segment);
    63         System.out.println("edge for segment " + segment.id + "(from node "+ segment.from.id + " to node "
    64           + segment.to.id + ") has weight: " + weight);
    65         graph.setEdgeWeight(edge, weight);
    66         if(!isOneWay(way)) {
    67           edge = new SegmentEdge(segment); // create a second edge for other direction
    68           graph.addEdge(segment.to, segment.from, edge);
    69           graph.setEdgeWeight(edge, weight);         
    70           System.out.println("inverse segment " + segment.id + "(from node "+ segment.to.id + " to node "
    71             + segment.from.id + ") has weight: " + weight);
    72         }
    73       }
    74     }
    75     return graph;
    76   }
    77  
    78   /**
    79    * Returns the weight for the given segment depending on the highway type and the length of the
    80    * segment.
    81    * @param way
    82    * @param segment
    83    * @return
    84    */
    85   public double getWeight(Way way, Segment segment) {
    86     String type = way.get("highway");
    87     if(type == null) {
    88       return 0.0d;
    89     }
    90     Double weightValue = highwayWeight.get(type);
    91     double weight;
    92     if(weightValue == null) {
    93       weight = DEFAULT_WEIGHT;
    94     } else {
    95       weight = weightValue.doubleValue();
    96     }
    97     double distance = Math.sqrt(segment.from.coor.distance(segment.to.coor)) * 111000; // deg to m (at equator :-)
    98     return distance; // weight;
    99   }
    100  
    101   public boolean isOneWay(Way way) {
    102     // FIXXME: oneway=-1 is ignored for the moment!
    103     return way.get("oneway") != null || "motorway".equals(way.get("highway"));
    104   }
    105  
    106   public Graph<Node, WayEdge> createGraph() {
    107     createEdges();
    108     DirectedWeightedMultigraph<Node, WayEdge> graph = new DirectedWeightedMultigraph<Node, WayEdge>(new JosmEdgeFactory());
    109 
    110     for(WayEdge edge : edges) {
    111       graph.addVertex(edge.getStartNode());
    112       graph.addVertex(edge.getEndNode());
    113       graph.addEdge(edge.getStartNode(), edge.getEndNode(), edge);
    114     }
    115     return graph;
    116   }
    117  
    118   private void createEdges() {
    119     System.out.println("Start free Memory: " + (Runtime.getRuntime().freeMemory()));
    120     // iterate all ways and segments for all nodes:
    121     for(Way way : Main.ds.ways) {
    122       for(Segment segment : way.segments) {
    123         addSegmentForNode(segment.from, segment);
    124         addSegmentForNode(segment.to, segment);
    125         segments.add(segment);
    126       }
    127       //ways.add(way);
    128     }
    129     System.out.println("after all segments free Memory: " + (Runtime.getRuntime().freeMemory()));
    130     // find nodes with one or more than two segments:
    131     Set<Segment> nodeSegments;
    132     for(Node node : nodeSegmentMap.keySet()) {
    133       nodeSegments = nodeSegmentMap.get(node);
    134       if(nodeSegments.size() == 1 || nodeSegments.size() > 2) {
    135         crossingNodes.add(node);
    136       }
    137     }
    138     System.out.println("after all crossings free Memory: " + (Runtime.getRuntime().freeMemory()));
    139     System.out.println("Number of Nodes: " + Main.ds.nodes.size());
    140     System.out.println("Number of Segments: " + Main.ds.segments.size());
    141     System.out.println("Number of Graph Vertices: " + crossingNodes.size());
    142     System.out.println("Number of Nodes in Segment Map: " + nodeSegmentMap.keySet().size());
    143     // find for every crossing node all connected crossing nodes:
    144     Node targetNode;
    145     WayEdge edge;
    146     List<Segment> edgeSegments;
    147     for(Node sourceNode : crossingNodes) {
    148       targetNode = sourceNode;
    149       for(Segment segment : nodeSegmentMap.get(sourceNode)) {
    150         edge = new WayEdge();
    151         edgeSegments = new ArrayList<Segment>();
    152         boolean crossingReached = false;
    153         do {
    154           targetNode = getOtherEnd(targetNode, segment);
    155           edgeSegments.add(segment);
    156           // FIXXME calculate length of segment for edge
    157           if(crossingNodes.contains(targetNode)) {
    158             crossingReached = true;
    159           } else {
    160             segment = getOtherSegment(targetNode, segment);
    161           }
    162         } while(!crossingReached);
    163         edge.setSegments(edgeSegments);
    164         edge.setStartNode(sourceNode);
    165         edge.setEndNode(targetNode);
    166         System.out.println("Adding edge with " + edgeSegments.size() +" segments: " + edgeSegments);
    167         System.out.println("after adding edge free Memory: " + (Runtime.getRuntime().freeMemory()));
    168         edges.add(edge);
    169       }
    170     }
    171   }
    172  
    173   /**
    174    * Returns the other segment for the given node (works only for non crossing
    175    * nodes).
    176    * @param node
    177    * @param segment
    178    * @return
    179    */
    180   private Segment getOtherSegment(Node node, Segment segment) {
    181     Set<Segment> segments = nodeSegmentMap.get(node);
    182     if(segments.size() != 2) {
    183       throw new RuntimeException("the given node has more than two nodes!");
    184     }
    185     if(!segments.contains(segment)) {
    186       throw new RuntimeException("the given segment is not connected to the given node");
    187     }
    188     Iterator<Segment> segIter = segments.iterator();
    189     Segment next = segIter.next();
    190     if(segment.equals(next)) {
    191         return segIter.next();
    192     } else {
    193       return segment;
    194     }
    195   }
    196  
    197   private void addSegmentForNode(Node node, Segment segment) {
    198     Set<Segment> segments = nodeSegmentMap.get(node);
    199     if(segments == null) {
    200       segments = new HashSet<Segment>();
    201       nodeSegmentMap.put(node, segments);
    202     }
    203     if(!segments.contains(segment)) {
    204       segments.add(segment);
    205     }
    206   }
    207  
    208   private Node getOtherEnd(Node node, Segment segment) {
    209     if(segment.from.equals(node)) {
    210       return segment.to;
    211     } else {
    212       return segment.from;
    213     }
    214   }
    215  
     28    private Map<Node, Set<Segment>> nodeSegmentMap = new HashMap<Node, Set<Segment>>();
     29    private Set<Segment> segments = new HashSet<Segment>();
     30    private Set<Way> ways = new HashSet<Way>();
     31    private Set<Node> crossingNodes = new HashSet<Node>();
     32    private List<WayEdge> edges = new ArrayList<WayEdge>();
     33
     34    private Map<String, Double> highwayWeight;
     35    private static final double DEFAULT_WEIGHT = Double.MAX_VALUE;
     36
     37    public OsmGraphCreator() {
     38        highwayWeight = new HashMap<String, Double>();
     39        highwayWeight.put("motorway", 130.0);
     40        highwayWeight.put("primary", 100.0);
     41        highwayWeight.put("secondary", 70.0);
     42        highwayWeight.put("unclassified", 50.0);
     43        highwayWeight.put("residential", 40.0);
     44        highwayWeight.put("footway", 1.0);
     45    }
     46
     47    public Graph<Node, SegmentEdge> createSegmentGraph() {
     48        SimpleDirectedWeightedGraph<Node, SegmentEdge> graph = new SimpleDirectedWeightedGraph<Node, SegmentEdge>(SegmentEdge.class);
     49        // SimpleGraph<Node, SegmentEdge> graph = new SimpleGraph<Node, SegmentEdge>(SegmentEdge.class);
     50        SegmentEdge edge;
     51        double weight;
     52        // iterate all ways and segments for all nodes:
     53        for(Way way : Main.ds.ways) {
     54            if(!way.deleted) {               
     55                for(Segment segment : way.segments) {
     56                    if(!segment.deleted) {
     57                        graph.addVertex(segment.from);
     58                        graph.addVertex(segment.to);
     59                        edge = new SegmentEdge(segment);
     60                        edge.setWay(way);
     61                        graph.addEdge(segment.from, segment.to, edge);
     62                        weight = getWeight(way, segment);
     63                        System.out.println("edge for segment " + segment.id + "(from node "+ segment.from.id + " to node "
     64                            + segment.to.id + ") has weight: " + weight);
     65                        graph.setEdgeWeight(edge, weight);
     66                        if(!isOneWay(way)) {
     67                            edge = new SegmentEdge(segment, true); // create a second edge for other direction
     68                            edge.setWay(way);
     69                            graph.addEdge(segment.to, segment.from, edge);
     70                            graph.setEdgeWeight(edge, weight);         
     71                            System.out.println("inverse segment " + segment.id + "(from node "+ segment.to.id + " to node "
     72                                + segment.from.id + ") has weight: " + weight);
     73                        }
     74                    }
     75                }
     76            }
     77        }
     78        return graph;
     79    }
     80
     81    /**
     82     * Returns the weight for the given segment depending on the highway type and the length of the
     83     * segment.
     84     *
     85     * @param way
     86     * @param segment
     87     * @return
     88     */
     89    public double getWeight(Way way, Segment segment) {
     90        String type = way.get("highway");
     91        if (type == null) {
     92            return 0.0d;
     93        }
     94        Double weightValue = highwayWeight.get(type);
     95        double weight;
     96        if (weightValue == null) {
     97            weight = DEFAULT_WEIGHT;
     98        } else {
     99            weight = weightValue.doubleValue();
     100        }
     101        double distance = Math.sqrt(segment.from.coor.distance(segment.to.coor)) * 111000; // deg
     102                                                                                            // to m
     103                                                                                            // (at
     104                                                                                            // equator
     105                                                                                            // :-)
     106        return distance; // weight;
     107    }
     108
     109    public boolean isOneWay(Way way) {
     110        // FIXXME: oneway=-1 is ignored for the moment!
     111        return way.get("oneway") != null || "motorway".equals(way.get("highway"));
     112    }
     113
     114    public Graph<Node, WayEdge> createGraph() {
     115        createEdges();
     116        DirectedWeightedMultigraph<Node, WayEdge> graph = new DirectedWeightedMultigraph<Node, WayEdge>(
     117            new JosmEdgeFactory());
     118
     119        for (WayEdge edge : edges) {
     120            graph.addVertex(edge.getStartNode());
     121            graph.addVertex(edge.getEndNode());
     122            graph.addEdge(edge.getStartNode(), edge.getEndNode(), edge);
     123        }
     124        return graph;
     125    }
     126
     127    private void createEdges() {
     128        System.out.println("Start free Memory: " + (Runtime.getRuntime().freeMemory()));
     129        // iterate all ways and segments for all nodes:
     130        for (Way way : Main.ds.ways) {
     131            for (Segment segment : way.segments) {
     132                addSegmentForNode(segment.from, segment);
     133                addSegmentForNode(segment.to, segment);
     134                segments.add(segment);
     135            }
     136            // ways.add(way);
     137        }
     138        System.out
     139            .println("after all segments free Memory: " + (Runtime.getRuntime().freeMemory()));
     140        // find nodes with one or more than two segments:
     141        Set<Segment> nodeSegments;
     142        for (Node node : nodeSegmentMap.keySet()) {
     143            nodeSegments = nodeSegmentMap.get(node);
     144            if (nodeSegments.size() == 1 || nodeSegments.size() > 2) {
     145                crossingNodes.add(node);
     146            }
     147        }
     148        System.out.println("after all crossings free Memory: "
     149                        + (Runtime.getRuntime().freeMemory()));
     150        System.out.println("Number of Nodes: " + Main.ds.nodes.size());
     151        System.out.println("Number of Segments: " + Main.ds.segments.size());
     152        System.out.println("Number of Graph Vertices: " + crossingNodes.size());
     153        System.out.println("Number of Nodes in Segment Map: " + nodeSegmentMap.keySet().size());
     154        // find for every crossing node all connected crossing nodes:
     155        Node targetNode;
     156        WayEdge edge;
     157        List<Segment> edgeSegments;
     158        for (Node sourceNode : crossingNodes) {
     159            targetNode = sourceNode;
     160            for (Segment segment : nodeSegmentMap.get(sourceNode)) {
     161                edge = new WayEdge();
     162                edgeSegments = new ArrayList<Segment>();
     163                boolean crossingReached = false;
     164                do {
     165                    targetNode = getOtherEnd(targetNode, segment);
     166                    edgeSegments.add(segment);
     167                    // FIXXME calculate length of segment for edge
     168                    if (crossingNodes.contains(targetNode)) {
     169                        crossingReached = true;
     170                    } else {
     171                        segment = getOtherSegment(targetNode, segment);
     172                    }
     173                } while (!crossingReached);
     174                edge.setSegments(edgeSegments);
     175                edge.setStartNode(sourceNode);
     176                edge.setEndNode(targetNode);
     177                System.out.println("Adding edge with " + edgeSegments.size() + " segments: "
     178                                + edgeSegments);
     179                System.out.println("after adding edge free Memory: "
     180                                + (Runtime.getRuntime().freeMemory()));
     181                edges.add(edge);
     182            }
     183        }
     184    }
     185
     186    /**
     187     * Returns the other segment for the given node (works only for non crossing nodes).
     188     *
     189     * @param node
     190     * @param segment
     191     * @return
     192     */
     193    private Segment getOtherSegment(Node node, Segment segment) {
     194        Set<Segment> segments = nodeSegmentMap.get(node);
     195        if (segments.size() != 2) {
     196            throw new RuntimeException("the given node has more than two nodes!");
     197        }
     198        if (!segments.contains(segment)) {
     199            throw new RuntimeException("the given segment is not connected to the given node");
     200        }
     201        Iterator<Segment> segIter = segments.iterator();
     202        Segment next = segIter.next();
     203        if (segment.equals(next)) {
     204            return segIter.next();
     205        } else {
     206            return segment;
     207        }
     208    }
     209
     210    private void addSegmentForNode(Node node, Segment segment) {
     211        Set<Segment> segments = nodeSegmentMap.get(node);
     212        if (segments == null) {
     213            segments = new HashSet<Segment>();
     214            nodeSegmentMap.put(node, segments);
     215        }
     216        if (!segments.contains(segment)) {
     217            segments.add(segment);
     218        }
     219    }
     220
     221    private Node getOtherEnd(Node node, Segment segment) {
     222        if (segment.from.equals(node)) {
     223            return segment.to;
     224        } else {
     225            return segment.from;
     226        }
     227    }
    216228
    217229}
Note: See TracChangeset for help on using the changeset viewer.