1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022016 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


8  * it under the terms of the GNU General Public License as published by


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 


22  using System;


23 


24  namespace 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 


107  latitude1 = ConvertToRadian(x1);


108  longitude1 = ConvertToRadian(y1);


109  latitude2 = ConvertToRadian(x2);


110  longitude2 = ConvertToRadian(y2);


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  }

