2

我正在尝试找到离给定位置最近的城市。我已经存储了一些我想合作的城市的位置。我有我的位置，但我不知道如何找到离我最近的城市？

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# 编写程序，但只知道算法的解决方案对我来说是足够的 :) 感谢您的帮助

4

5 回答 5

5

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

最近 = sqrt ( (lat2 - lat1) ^2 + (Long2-Long1) ^2 ) 现在这给了你你的空中距离。

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

于 2012-11-07T12:17:27.783 回答
4

Strictly, you'd want to use the Haversine formula.

However, while you could perhaps be just slightly out in far northern or far southern points, you could probably get by by pretending that Mercator projections are accurate for distance, and ignoring the curvature of the earth. This is especially true if you are going to have lots of cities, as the error is greater, the further points are from the target point. Hence you would just use Pythagoras':

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

But since you only care about (and only get) a relative ordering, you can skip the square-root bit, which is the heaviest step:

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

As well as being faster in and of itself, it can also be reasonably preformed on integers, should you store your coordinates as multiples of the actual coordinate (e.g. storing New York's (40.664167, -73.938611) as the pair (406642, -739386). This can be a big boost if you want to quickly sort a large number of places in order of proximity to a given point.

If however you really care about precision in the face of the fact that the earth is round, then the following implements 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)));
}
于 2012-11-07T12:33:07.640 回答
0

两点 (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;
}
于 2012-11-07T12:32:19.410 回答
0

访问此处， 您可以找到两个使用蛮力和分治算法的 c# 函数，以在二维给定点的集合中找到最接近的两个点。

于 2012-11-07T12:32:39.190 回答
0

乔恩的回答非常鼓舞人心，尽管缺少的部分很少。

  • 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)));
于 2018-09-14T00:54:21.743 回答