1

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

これにアプローチする方法について頭を悩ませることはできません。ラジアンの使用も検討しましたが、要件を満たすものはないようです。

参考までに、LAMPスタックはここに行きます...

4

4 に答える 4

2

次のクエリは、すべてのポイント間の距離を計算し、距離が最大の 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

これらの計算を事前に行い、結果を別のテーブルに保存することをお勧めします。

于 2009-08-15T22:38:10.340 に答える
2

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

于 2009-08-15T22:39:38.747 に答える
1

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

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

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

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

明らかな最適化: 世界を N 個の「正方形」 (たとえば、経度 10 度、緯度 10 度) に分割し、各ペアリングの中心間の大圏距離を事前に計算します。これをデータベースに格納します。これで、最も遠い「正方形」をすばやく探して、それらのタイル内の (緯度、経度) ペアのみを確認できます。

于 2009-08-15T22:30:25.737 に答える
0

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

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

編集: 10 度の最適化が機能しない理由:

下図のように正方形を4つ取ります

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

正方形の中心のみを測定し、それらの距離を比較すると、A と D は A と C よりも離れていることがわかります。ただし、都市 1 と 3 は明らかに 1 と 2 よりも離れています。

于 2009-08-15T22:36:40.233 に答える