using System.Collections.Generic;
public static void Main()
var O = new List<double[]>()
{new[]{152.8, 20.1}, new[]{151.9, 20.8}, new[]{151.7, 21.1}, new[]{151.4, 21.7}, new[]{150, 22.8}, new[]{149, 23.7}, new[]{148.6, 24}, new[]{147.6, 25.2}, new[]{147.1, 25.6}, new[]{146.4, 26.1}, new[]{144.6, 26.9}, new[]{143.6, 27.4}, new[]{143.2, 27.6}, new[]{141.6, 28.6}, new[]{140.7, 28.9}, new[]{140.1, 29.5}, new[]{138.8, 29.9}, new[]{137.6, 30.3}, new[]{136.2, 30.4}, new[]{134.5, 30.8}, new[]{134, 31.1}, new[]{133.1, 31.2}, new[]{131.8, 31.8}, new[]{131.4, 32.3}, new[]{130.8, 33}, new[]{130.2, 33.7}, new[]{129.8, 34}, new[]{129.6, 34.9}, new[]{129.4, 35.2}};
var P = new List<double[]>()
{new[]{126, 15.3}, new[]{125.8, 15.9}, new[]{124.9, 16.8}, new[]{124.6, 17.5}, new[]{124.3, 18.2}, new[]{124.4, 18.8}, new[]{124, 18.9}, new[]{124, 19.3}, new[]{123.8, 19.6}, new[]{123.8, 20}, new[]{123.9, 20.5}, new[]{123.9, 20.6}, new[]{123.9, 20.7}, new[]{124, 21.1}, new[]{124, 21.3}, new[]{124, 21.3}, new[]{124.2, 21.3}, new[]{124.3, 21.4}, new[]{124.3, 21.5}, new[]{124.4, 21.6}, new[]{125.3, 25.4}, new[]{125.2, 31.2}, new[]{125.1, 31.4}, new[]{125.1, 31.8}, new[]{125.1, 32.1}, new[]{125.1, 32.5}, new[]{125.1, 32.8}, new[]{125.1, 33.1}, new[]{125, 33.6}, new[]{125.0, 34}, new[]{125, 34.3}, new[]{125, 34.7}, new[]{125, 34.9}, new[]{125, 35.3}, new[]{125, 35.6}, new[]{125, 35.9}, new[]{125, 36.4}, new[]{125, 36.7}, new[]{125.0, 37}, new[]{125.1, 37.3}, new[]{125.3, 38}, new[]{125.5, 39}, new[]{126.5, 41.1}, new[]{126.7, 41.8}, new[]{126.9, 42.4}, new[]{127, 42.8}, new[]{127.1, 43.4}, new[]{127.3, 43.7}, new[]{129.2, 44.3}, new[]{128.9, 44.8}, new[]{129.2, 45.5}, new[]{129.8, 46.1}, new[]{130.1, 46.7}, new[]{130.2, 47}, new[]{130.4, 47.2}, new[]{130.5, 47.8}, new[]{130.7, 48.1}};
var Q = new List<double[]>()
{new[]{148.6, 24.9}, new[]{146.4, 25.8}, new[]{145.7, 26.1}, new[]{145, 26.7}, new[]{143.4, 27.9}, new[]{142.6, 28.3}, new[]{141.7, 28.9}, new[]{140.9, 29.9}, new[]{140, 30.8}, new[]{139.5, 31.4}, new[]{139, 32.8}, new[]{138.9, 33.4}, new[]{139, 34.1}, new[]{139.7, 35.4}, new[]{140.2, 35.8}, new[]{140.9, 36.3}, new[]{142.4, 37.3}, new[]{143.3, 37.9}, new[]{144.2, 38.4}, new[]{146.4, 39.1}, new[]{147.3, 39.3}, new[]{148.3, 39.9}, new[]{151, 40.5}};
Console.WriteLine($"201908 vs 201913 => {FrechetDistance(O, P):0.000}");
Console.WriteLine($"201908 vs 201915 => {FrechetDistance(O, Q):0.000}");
Console.WriteLine($"201913 vs 201915 => {FrechetDistance(P, Q):0.000}");
Console.WriteLine($"201915 vs 201908 => {FrechetDistance(Q, O):0.000}");
public static double EuclideanDistance(double x1, double y1, double x2, double y2)
return Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
public static double ComputeDistance(double[, ] distances, int i, int j, List<double[]> P, List<double[]> Q)
if (distances[i, j] > -1)
distances[i, j] = EuclideanDistance(P[0][0], P[0][1], Q[0][0], Q[0][1]);
else if (i > 0 && j == 0)
distances[i, j] = Math.Max(ComputeDistance(distances, i - 1, 0, P, Q), EuclideanDistance(P[i][0], P[i][1], Q[0][0], Q[0][1]));
else if (i == 0 && j > 0)
distances[i, j] = Math.Max(ComputeDistance(distances, 0, j - 1, P, Q), EuclideanDistance(P[0][0], P[0][1], Q[j][0], Q[j][1]));
distances[i, j] = Math.Max(Math.Min(ComputeDistance(distances, i - 1, j, P, Q), Math.Min(ComputeDistance(distances, i - 1, j - 1, P, Q), ComputeDistance(distances, i, j - 1, P, Q))), EuclideanDistance(P[i][0], P[i][1], Q[j][0], Q[j][1]));
distances[i, j] = Double.PositiveInfinity;
public static double FrechetDistance(List<double[]> P, List<double[]> Q)
double[, ] distances = new double[P.Count, Q.Count];
for (int y = 0; y < P.Count; y++)
for (int x = 0; x < Q.Count; x++)
return ComputeDistance(distances, P.Count - 1, Q.Count - 1, P, Q);