Changeset 8462 for branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning

Timestamp:

08/09/12 16:20:19 (13 years ago)

Author:

spimming

Message:

#1894:

• calculate distance in kilometers for two locations
• generate IGraph from a datasource
• adapted test program

Location:

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3

Files:

• Graph/OsmGraph.cs (modified) (2 diffs)
• Osm.Data/XmlDataSource.cs (modified) (3 diffs)
• Osm/IDataSource.cs (modified) (2 diffs)
• Osm/Utils.cs (modified) (1 diff)

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/OsmGraph.cs

@@ -71 +71 @@
     public float GetWeight(Way edge, OsmVertex<Node> source, OsmVertex<Node> target) {
       double distance = Utils.Distance(source.Node.Point, target.Node.Point);
+      //double distance = Utils.LocationDistance(source.Node.Point, target.Node.Point);
       int speed = edge.GetMaxSpeed();
       double weight = (distance / speed) * 3.6;
+      //double weight = (distance / speed);
       return (float)weight;
     }
@@ -84 +86 @@
     public float EstimatedCosts(OsmVertex<Node> source, OsmVertex<Node> target) {
       double distance = Utils.Distance(source.Node.Point, target.Node.Point);
+      //double distance = Utils.LocationDistance(source.Node.Point, target.Node.Point);
       int speed = 130;
       double costs = (distance / speed) * 3.6;
+      //double costs = (distance / speed);
       return (float)costs;
     }

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Osm.Data/XmlDataSource.cs

@@ -1 +1 @@
 
+using System;
 using System.Collections.Generic;
 using System.IO;
 using System.Xml;
+using HeuristicLab.Problems.RoutePlanning.Graph;
 namespace HeuristicLab.Problems.RoutePlanning.Osm.Data {
   public class XmlDataSource : IDataSource {
@@ -82 +84 @@
     }
 
-    #endregion
+    public IGraph GetRoutingGraph() {
+      IGraph graph = new Graph.Graph();
+      foreach (Way way in ways.Values) {
+        List<Node> nodes = way.Nodes;
+        for (int i = 0; i < way.Nodes.Count - 1; i++) {
+          Vertex v1 = new Vertex(nodes[i].Id, nodes[i].Longitude, nodes[i].Latitude);
+          graph.AddVertex(v1);
+          Vertex v2 = new Vertex(nodes[i + 1].Id, nodes[i + 1].Longitude, nodes[i + 1].Latitude);
+          if (v1.Id == 370626403) {
+            Console.WriteLine();
+          }
+          graph.AddVertex(v2);
+          if (way.OneWay) {
+            Edge<Vertex> edge = new Edge<Vertex>(v1, v2);
+            edge.Category = (short)way.HighwayTag;
+            graph.AddEdge(edge);
+          } else {
+            Edge<Vertex> edgeForward = new Edge<Vertex>(v1, v2);
+            edgeForward.Category = (short)way.HighwayTag;
+            graph.AddEdge(edgeForward);
+
+            Edge<Vertex> edgeBackward = new Edge<Vertex>(v2, v1);
+            edgeForward.Category = (short)way.HighwayTag;
+            graph.AddEdge(edgeBackward);
+          }
+
+        }
+      }
+      return graph;
+    }
+
+    #endregion
+
+    #region Private Methods
 
     private void ReadData() {
@@ -214 +249 @@
       }
     }
+
+    #endregion
   }
 }

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Osm/IDataSource.cs

@@ -1 +1 @@
 
 using System.Collections.Generic;
+using HeuristicLab.Problems.RoutePlanning.Graph;
 namespace HeuristicLab.Problems.RoutePlanning.Osm {
   public interface IDataSource {
@@ -8 +9 @@
     List<Way> GetWays(Node node);
     Relation GetRelation(long relationId);
+    IGraph GetRoutingGraph();
   }
 }

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Osm/Utils.cs

@@ -8 +8 @@
       double dy = p2.Y - p1.Y;
       return Math.Sqrt(dx * dx + dy * dy);
+    }
+
+    public static double LocationDistance(PointD p1, PointD p2) {
+      // The Haversine formula
+      /* dlon = lon2 - lon1
+            dlat = lat2 - lat1
+            a = (sin(dlat/2))^2 + cos(lat1) * cos(lat2) * (sin(dlon/2))^2
+            c = 2 * atan2(sqrt(a), sqrt(1-a)) 
+            d = R * c
+       */
+
+      double lat1Rad = p1.Y * (Math.PI / 180.0);
+      double long1Rad = p1.X * (Math.PI / 180.0);
+      double lat2Rad = p2.Y * (Math.PI / 180.0);
+      double long2Rad = p2.X * (Math.PI / 180.0);
+
+      double longitude = long2Rad - long1Rad;
+      double latitude = lat2Rad - lat1Rad;
+
+      double a = Math.Pow(Math.Sin(latitude / 2.0), 2.0) +
+                   Math.Cos(lat1Rad) * Math.Cos(lat2Rad) *
+                   Math.Pow(Math.Sin(longitude / 2.0), 2.0);
+
+      double c = 2.0 * Math.Asin(Math.Sqrt(a));
+
+      const double earthRadiusKms = 6376.5;
+      double distance = earthRadiusKms * c;
+
+      return distance;
     }