algorithm - 2 都市間の距離の計算

Question

2 つの都市間の距離はどのように計算しますか?

score 33 · Accepted Answer

地球の曲率を考慮する必要がある場合は、大圏距離があなたが探しているものです。ウィキペディアの記事は、おそらく私よりも数式がどのように機能するかを説明するのに優れています。また、詳細を説明するこの航空数式ページもあります。

数式はパズルの最初の部分にすぎませんが、任意の都市でこれを機能させる必要がある場合は、緯度/経度を取得するための位置データベースが必要になります。幸いなことに、これはGeonames.orgから無料で入手できますが、市販のデータベースが利用可能です（googleに問い合わせてください）。したがって、一般に、必要な2つの都市を検索し、緯度/経度の座標を取得して、ウィキペディアの作業例のように数式にプラグインします。

その他の提案：

完全な商用ソリューションとして、多くのトラック会社が送料を計算するために使用するPCMilerがあります。
Googleマップ（または他の）APIを呼び出します。1日に多くのリクエストを実行する必要がある場合は、結果をサーバーにキャッシュすることを検討してください。
また、データをグループ化する必要があると思われる場合は、都市、郊外、町などの同等性データベースの構築を検討することも非常に重要です。ただし、これは非常に複雑になり、問題に対する万能の解決策が見つからない場合があります。

最後になりましたが、ジョエルはしばらく前にこの問題についての記事を書いたので、ここに行きます：新機能：就職活動

score 9 · Accepted Answer

9

Haversine 式を使用します。

于 2008-08-22T21:42:08.260 に答える

score 2 · Accepted Answer

これは、SQL Server 2008 の geography タイプで非常に簡単に実行できます。

SELECT geography::Point(lat1, lon1, 4326).STDistance(geography::Point(lat2, lon2, 4326))
-- computes distance in meters using eliptical model, accurate to the mm

4326 は WGS84 楕円体地球モデルの SRID です。

score 1 · Accepted Answer

地球のような実際の球形の惑星上の2つの実際の都市間の最短距離について話している場合は、大円距離が必要です。

score 1 · Accepted Answer

A*アルゴリズムを使用して、これら 2 つの都市間の最短経路を見つけることができます。これにより、距離が得られます。

score 1 · Accepted Answer

平面で作業していて、「カラスが飛ぶように」ユークリッド距離が必要な場合:

// Cities are points x0,y0 and x1,y1 in kilometers or miles or Smoots[1]
dx = x1 - x0;
dy = y1 - y0;
dist = sqrt(dx*dx + dy*y);

三角法は必要ありません！ピタゴラスの定理と、平方は常に正であるという事実だけで、sqrt() に渡す正の数を取得するために dx = abs(x1 - x0) などは必要ありません。

おそらくこれを1行で行うことができ、コンパイラはおそらく上記の同等のコードを削減することに注意してください。

dist = sqrt((x1-x0)*(x1-x0) + (y1-y0)*(y1-y0));

[1] http://en.wikipedia.org/wiki/Smoot

score 0 · Accepted Answer

私は最近これでたくさんの仕事をしています。SQL2008の新機能がこれを本当に簡単にしていることに気づきました。1秒未満の時間で100kレコードテーブルのXkmを超えているすべてのポイントを見つけることができます...それほど粗末ではありません。

私のテストでの大円（球形の仮定）法は、ヴィンセント式（地球が何であるかである楕円体の仮定）と比較した場合、約2.5マイル離れていました。

本当の秘訣は、私がグーグルを使用しているために、緯度と長さを取得することです。

score 0 · Accepted Answer

@Jared-コード例のマイナーな修正。最初のコード例の最後の行は次のようになります。

dist = sqrt(dx*dx + dy*dy);

score 0 · Accepted Answer

0

私は距離をとてもシンプルできれいに使います

于 2012-06-04T22:48:46.820 に答える

score 0 · Accepted Answer

都市の緯度/経度を見つけて、緯度/経度座標の距離推定アルゴリズムを使用します。

score 0 · Accepted Answer

コード例が必要な場合は、自宅で掘り下げることができると思いますが、以前の多くの回答と同様に、計算を行うには long / lat db が必要です

score 0 · Accepted Answer

2 つの都市間の距離を取得するには、ルックアップテーブルを使用することをお勧めします。

* 距離 a を計算する式は、非常に計算量が多い.. * 都市間の距離が変化する可能性は低いため、これは理にかなっています。

したがって、必要が非常に具体的でない限り (衛星や地形アルゴリズムなどからの地形マッピングなど)、実際には都市のリストと都市間の距離をテーブルに保存し、必要に応じて検索する必要があります。

score 0 · Accepted Answer

情報を取得したら、それが変更されない場合は、何らかの形で保存することに同意します. @Marko Tinto T-SQLサンプルをありがとう。SQL Server にアクセスできない場合、または別の方法を好む場合: 高精度が必要な場合は、Vincenty アルゴリズムに関するウィキペディアのエントリで詳細を確認してください。他の言語に簡単に移植できる js 実装があると思います。また、そのページの下部には、Vincenty アルゴリズムよりも 1000 倍正確であると主張するgeographicLibへのリンクがあります (データが適切であれば、問題になる可能性があります)。

Vincenty メソッドのようなものを使用するのはなぜですか? 地球は完全な球体ではなく、そのような方法により、地球をモデル化するためにより正確な長軸と短軸を入力できるためです。

algorithm - 2 都市間の距離の計算

14 に答える 14

Related

Reference