Free cookie consent management tool by TermsFeed Policy Generator

# source:branches/2864_PermutationProblems/HeuristicLab.Problems.Instances/3.3/Types/DistanceHelper.cs@15541

Last change on this file since 15541 was 15541, checked in by fholzing, 6 years ago

#2864: CleanUp of old code, added LOP benchmark instances

File size: 5.9 KB
Line
2/* HeuristicLab
3 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23
24namespace HeuristicLab.Problems.Instances {
25  public enum DistanceMeasure { Direct, Euclidean, RoundedEuclidean, UpperEuclidean, Geo, Manhattan, Maximum, Att };
26
27  public static class DistanceHelper {
28    /// <summary>
29    /// If only the coordinates are given, can calculate the distance matrix.
30    /// </summary>
31    /// <returns>A full distance matrix between all cities.</returns>
32    public static double[,] GetDistanceMatrix(DistanceMeasure distanceMeasure, double[,] coordinates, double[,] distances, int dimension) {
33      if (distances != null) return distances;
34
35      distances = new double[dimension, dimension];
36      for (int i = 0; i < dimension - 1; i++)
37        for (int j = i + 1; j < dimension; j++) {
38          distances[i, j] = GetDistance(i, j, distanceMeasure, coordinates, distances);
39          distances[j, i] = distances[i, j];
40        }
41
42      return distances;
43    }
44
45    public static double GetDistance(DistanceMeasure distanceMeasure, double x1, double y1, double x2, double y2) {
46      switch (distanceMeasure) {
47        case DistanceMeasure.Att:
48          return AttDistance(x1, y1, x2, y2);
49        case DistanceMeasure.Direct:
50          throw new ArgumentException("Direct distance measure requires distance matrix for distance calculation.");
51        case DistanceMeasure.Euclidean:
52          return EuclideanDistance(x1, y1, x2, y2);
53        case DistanceMeasure.Geo:
54          return GeoDistance(x1, y1, x2, y2);
55        case DistanceMeasure.Manhattan:
56          return ManhattanDistance(x1, y1, x2, y2);
57        case DistanceMeasure.Maximum:
58          return MaximumDistance(x1, y1, x2, y2);
59        case DistanceMeasure.RoundedEuclidean:
60          return Math.Round(EuclideanDistance(x1, y1, x2, y2));
61        case DistanceMeasure.UpperEuclidean:
62          return Math.Ceiling(EuclideanDistance(x1, y1, x2, y2));
63        default:
64          throw new InvalidOperationException("Distance measure is not known.");
65      }
66    }
67
68    #region Private Helpers
69    private static double GetDistance(int i, int j, DistanceMeasure distanceMeasure, double[,] coordinates, double[,] distances) {
70      switch (distanceMeasure) {
71        case DistanceMeasure.Att:
72          return AttDistance(coordinates[i, 0], coordinates[i, 1], coordinates[j, 0], coordinates[j, 1]);
73        case DistanceMeasure.Direct:
74          return distances[i, j];
75        case DistanceMeasure.Euclidean:
76          return EuclideanDistance(coordinates[i, 0], coordinates[i, 1], coordinates[j, 0], coordinates[j, 1]);
77        case DistanceMeasure.Geo:
78          return GeoDistance(coordinates[i, 0], coordinates[i, 1], coordinates[j, 0], coordinates[j, 1]);
79        case DistanceMeasure.Manhattan:
80          return ManhattanDistance(coordinates[i, 0], coordinates[i, 1], coordinates[j, 0], coordinates[j, 1]);
81        case DistanceMeasure.Maximum:
82          return MaximumDistance(coordinates[i, 0], coordinates[i, 1], coordinates[j, 0], coordinates[j, 1]);
83        case DistanceMeasure.RoundedEuclidean:
84          return Math.Round(EuclideanDistance(coordinates[i, 0], coordinates[i, 1], coordinates[j, 0], coordinates[j, 1]));
85        case DistanceMeasure.UpperEuclidean:
86          return Math.Ceiling(EuclideanDistance(coordinates[i, 0], coordinates[i, 1], coordinates[j, 0], coordinates[j, 1]));
87        default:
88          throw new InvalidOperationException("Distance measure is not known.");
89      }
90    }
91
92    private static double AttDistance(double x1, double y1, double x2, double y2) {
93      return Math.Ceiling(Math.Sqrt(((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) / 10.0));
94    }
95
96    private static double EuclideanDistance(double x1, double y1, double x2, double y2) {
97      return Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
98    }
99
100    private const double PI = 3.141592;
101    private const double RADIUS = 6378.388;
102    private static double GeoDistance(double x1, double y1, double x2, double y2) {
103      double latitude1, longitude1, latitude2, longitude2;
104      double q1, q2, q3;
105      double length;
106
111
112      q1 = Math.Cos(longitude1 - longitude2);
113      q2 = Math.Cos(latitude1 - latitude2);
114      q3 = Math.Cos(latitude1 + latitude2);
115
116      length = (int)(RADIUS * Math.Acos(0.5 * ((1.0 + q1) * q2 - (1.0 - q1) * q3)) + 1.0);
117      return (length);
118    }
119
120    private static double ConvertToRadian(double x) {
121      return PI * (Math.Truncate(x) + 5.0 * (x - Math.Truncate(x)) / 3.0) / 180.0;
122    }
123
124    private static double ManhattanDistance(double x1, double y1, double x2, double y2) {
125      return Math.Round(Math.Abs(x1 - x2) + Math.Abs(y1 - y2), MidpointRounding.AwayFromZero);
126    }
127
128    private static double MaximumDistance(double x1, double y1, double x2, double y2) {
129      return Math.Max(Math.Round(Math.Abs(x1 - x2), MidpointRounding.AwayFromZero), Math.Round(Math.Abs(y1 - y2), MidpointRounding.AwayFromZero));
130    }
131    #endregion
132  }
133}
Note: See TracBrowser for help on using the repository browser.