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

厳密には、Haversine式を使用する必要があります。

ただし、おそらく極北または極南の地点からわずかに外れている可能性がありますが、メルカトル図法が距離に対して正確であると偽って、地球の湾曲を無視することで、おそらくうまくいく可能性があります。これは、都市がたくさんある場合に特に当てはまります。エラーが大きいほど、ターゲットポイントから離れたポイントになります。したがって、ピタゴラスを使用するだけです。

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)));
}
于 2012-11-07T12:33:07.640 に答える
0

2点(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

ここにアクセスすると、ブルート フォースと分割統治アルゴリズムを使用して2つのc#関数を見つけ、2次元の特定のポイントのセットから最も近い2つのポイントを見つけることができます。

于 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 に答える