リスト内の緯度/経度の最長距離

Question

私はジオコードされたエントリのデータベースを持っています。私は、2つのエントリが合計エントリのサブセットから最も離れているかどうかを判断する必要があります。たとえば、リストから10個のエントリのリストを選択し、そのリスト内で最大の距離を表す2つの場所を決定します。

私はこのアプローチにどのように頭を回すことができません。私はラジアンを使用することも考えましたが、何もその要件を満たしていないようです。

FYI

、ここに行くLAMPスタック...

Answer 1

次のクエリは、すべてのポイント間の距離を計算し、最大の距離を持つ2つを返します。

SELECT coor1.longitude as lon1, 
     coor1.latitude as lat1, 
     coor2.longitude as lon2, 
     coor2.latitude as lat2, 
     (ACOS(
     COS(RADIANS(coor1.latitude)) * 
     COS(RADIANS(coor1.longitude)) * 
     COS(RADIANS(coor2.latitude)) * 
     COS(RADIANS(coor2.longitude)) + 
     COS(RADIANS(coor1.latitude)) * 
     SIN(RADIANS(coor1.longitude)) * 
     COS(RADIANS(coor2.latitude)) * 
     SIN(RADIANS(coor2.longitude)) + 
     SIN(RADIANS(coor1.latitude)) * 
     SIN(RADIANS(coor2.latitude)) 
     ) * 6378      --- Use 3963.1 for miles 
     ) 
AS DistanceKM 
FROM coordinates coor1, 
    coordinates coor2 
WHERE NOT (coor1.longitude = coor2.longitude AND coor1.latitude = coor2.latitude) 
ORDER BY DistanceKM DESC 
LIMIT 1;         --- Only the biggest 

私はこれらの計算を手前で行い、その結果を別のテーブルに保存することを推奨します。

Answer 2

ブルートフォースアプローチ：

1. 緯度と経度の値を平均して10のリストのセンターを探します。データベース内の各（緯度、経度）ペアについて

2. 、ステップから中心までの距離を算出する大円式を使用（1）

3. は最大二つの距離をピック。

明白な最適化は：N「正方形」の世界を破る（例えば、10度経度、10度の緯度）と、各ペアの中心間の大圏距離を予め計算します。これをデータベースに保存します。今すぐあなたはすぐに遠方の「四角形」を探し、それらのタイルの内側の唯一のチェック（緯度、経度）のペアを見つけることができます。

Answer 3

PHPで実装されているthe algorithmは、緯度と経度に基づいて2つの点の間の距離を表します。

「合計エントリのサブセット」が大きい場合は、すばやく計算を行う必要があります。その場合、都市ペア間の距離を事前に計算することを検討することをお勧めします。

EDIT：10度の最適化が動作しない理由：唯一の正方形の中心を測定し、それらの距離を比較することによって

------------------- 
|  |  | 
| A | B | 
|  |  | 
|_______1|________| 
|  |2  | 
| C | D | 
|  |  | 
|_______3|________| 

以下のように

は4つの正方形を取り、あなたがAを取得し、Dされていますしかし、都市1と都市3は、1と2よりはるかに離れています。

Answer 4

これを見て、これは最初に点のconvex hull（たとえばGraham's scanを使用して）を見つけてからそれに続いて直径のrotating calipersを実行することで解決できます。