球面上の最も近い点のペアを見つける

Question

2Dケース（xとy）に対して、n log n個の最も近いポイント対アルゴリズム（ShamosとHoey）を実装する方法を知っています。しかし、緯度と経度が与えられている問題では、このアプローチは使用できません。 2点間の距離は、haversineの式を使用して計算されます。

これらの緯度と経度をそれぞれのx座標とy座標に変換して、最も近い点のペアを見つける方法があるか、それを行うために使用できる別のテクニックがあるかどうかを知りたいと思います。

Answer 1

私はそれらを3次元座標に変換してから、divide and conquer approachを線ではなく平面を使用して使用します。これは間違いなく正しく動作します。球上の点だけを調べるとき、円弧距離（表面上を歩いている距離）による2つの最も近い点も、3次元デカルト距離によって最も近い2つになるので、これを保証することができます。実行時間はO（nlogn）になります。

3次元座標に変換するには、最も簡単な方法は（0,0,0）を地球の中心にしてから座標を（cos（lat）* cos（lon）、cos * sin（lan）、sin（lat））。これらの目的のために、計算を簡単にするために、地球の半径が1のスケールを使用しています。他の単位で距離を求めたい場合は、その単位で測ったときに地球の半径ですべての量を掛けてください。

これはすべて地球が球であることを前提としています。正確には1つではありませんが、ポイントに実際に高度がある場合もあります。したがって、これらの回答は完全に正確なものではありませんが、ほぼすべての場合に非常に近いでしょう。