查找距离指定地点最近的城市

Question

我想找到离给定地点最近的城市。我已经存储了一些我想要使用的城市的位置。我有我的位置，但我不知道如何找到离我所在地最近的城市？

Cities
New York - Lat 40.714353; Long -74.005973
Washington - Lat 38.895112; Long -77.036366
....more cities

My location
Philadephia - Lat 39.952335; Long -75.163789

那么我应该如何比较坐标以找到最近的城市？我正在用C＃编程，但只知道算法的解决方案对我来说已经足够了:)感谢您的帮助

Answer 1

你应该用你的高中知识来解决这个问题，你的算法是：

最近= sqrt（（lat2 - lat1）^ 2 +（Long2-Long1）^ 2）现在这给你空中距离。

因此，当您对值数组执行此操作时，可以使用asort函数来比较哪一个最接近您。

Answer 2

严格来说，你想要使用Haversine formula。

然而，虽然你可能只是在远北或远南点略微出局，你可能会假装墨卡托投影对距离是准确的，而忽略了地球的曲率。如果您要拥有大量城市，尤其如此，因为误差更大，更远的点来自目标点。因此你只需要使用毕达哥拉斯：

relDist = √((xLat - yLat) × (xLat - yLat) + (xLng - yLng) × (xLng - yLng))

但是既然你只关心（并且只得到）一个相对排序，你可以跳过平方根位，这是最重的一步：

relDist = (xLat - yLat) × (xLat - yLat) + (xLng - yLng) × (xLng - yLng)

如果您将坐标存储为实际坐标的倍数（例如存储纽约（40.664167，-73.938611）作为对（406642，-739386），那么它本身也更快，它也可以在整数上合理地执行。如果你想按照接近给定点的顺序快速排序大量的地方，这可能是一个很大的提升。

然而，如果你真的关心地​​球是圆形的那么精确，那么以下实施的是Haversine：

private const double radiusE = 6378135; // Equatorial radius
private const double radiusP = 6356750; // Polar radius
private const double radianConv = 180 / Math.PI;
public static double GetDistanceBetweenPoints(double lat1, double long1, double lat2, double long2)
{
  double dLat = (lat2 - lat1) / radianConv;
  double dLong = (long2 - long1) / radianConv;
  double a = Math.Sin(dLat / 2) * Math.Sin(dLat / 2) + Math.Cos(lat2) * Math.Sin(dLong/2) * Math.Sin(dLong/2);
  return Math.Sqrt((Math.Pow(radiusE * radiusP * Math.Cos(lat1 / radianConv), 2)) / (Math.Pow(radiusE * Math.Cos(lat1 / radianConv), 2) + Math.Pow(radiusP * Math.Sin(lat1 / radianConv), 2))) * (2 * Math.Atan2(Math.Sqrt(a), Math.Sqrt(1 - a)));
}

Answer 3

两点（x1，y1）和（x2，y2）之间的距离是

d = sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2)

所以在c＃中你我们将：

public City FindNearestCity(double currentLatitude, double currentLogitude, List<City> cities)
{
    Dictionary<City, double> distances = new Dictionary<City, double>();
    foreach (City city in cities)
    {
        double distance = Math.Sqrt(Math.Pow(city.latitude - currentLatitude, 2)  + Math.Pow(city.Longitude - currentLogitude, 2));
        distances.Add(city, distance);
    }
    double minimumDistance = distances.Min(distance => distance.Value);
    return distances.First(distance => distance.Value == minimumDistance).Key;
}

Answer 4

访问here你可以找到两个c＃函数，使用Brute force和divide-con-conquer算法在两个维度中找到一组给定点中最近的两个点。

Answer 5

乔恩的回答非常鼓舞人心，尽管缺少一些东西。

• lat1应该在一个 double a = Math.Sin(dLat / 2) * Math.Sin(dLat / 2) + Math.Cos(lat1/ RadianConv) * Math.Cos(lat2/ RadianConv) * Math.Sin(dLong / 2) * Math.Sin(dLong / 2);
• 有时候，最后一个语句中的模拟半径给出了2000ish，它应该接近RadiusE或RadiusP，所以我用的是平均半径。 return 6371* (2 * Math.Atan2(Math.Sqrt(a), Math.Sqrt(1 - a)));