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

StackOverflow https://stackoverflow.com/questions/1283016

  •  16-09-2019
  •  | 
  •  

質問

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

これにどのようにアプローチすればよいのか、まったくわかりません。ラジアンを使用することも検討しましたが、要件を満たしているものはないようです。

参考までに、LAMP スタックはここにあります...

役に立ちましたか？

解決

次のクエリは、すべての点間の距離を計算し、最大の距離と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

今、私は手を前に、これらの計算を行うと、別のテーブルに結果を格納する推薦ます。

他のヒント

一見すると、これは最初に次のことを見つけることで解決できます。 凸包 ポイントの（使用 グラハムのスキャン, 、たとえば）そして、 回転キャリパー その直径については。

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

  1. 緯度と経度の値を平均して、10 個のリストの中心を見つけます。

  2. データベース内の各 (緯度、経度) ペアについて、大圏の公式を使用して、ステップ (1) の中心からの距離を計算します。

  3. 最大の 2 つの距離を選択します。

明らかな最適化:世界を N 個の「正方形」 (例: 経度 10 度、緯度 10 度) に分割し、各ペアの中心間の大圏距離を事前に計算します。これをデータベースに保存します。これで、最も遠い「正方形」をすばやく検索し、それらのタイル内の (緯度、経度) ペアのみを確認できるようになりました。

ここで 2点間の距離のためにPHPで実装するアルゴリズム緯度と経度に基づいています。

「総エントリのサブセットが」大きい場合には、迅速行うにはかなりの数の計算を持っていることに注意してください。その場合は、あなたが都市のペア間の距離を事前に計算し検討する必要があります。

EDIT：10度の最適化が動作しないのはなぜます：

以下に示すように、4つの正方形を取る

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

唯一の正方形の中心を測定し、それらの距離を比較することによって、あなたはAとDはさらに離れてAとCよりも取得しかし、都市1と3はさらに離れて1及び2よりも明らかにされています。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top