2D ケース (x と y) に対して n log n 最も近い点のペア アルゴリズム (Shamos と Hoey) を実装する方法を知っています。ただし、緯度と経度が与えられている問題では、このアプローチは使用できません。2 点間の距離は、harsine 式を使用して計算されます。
これらの緯度と経度をそれぞれの x 座標と y 座標に変換し、最も近いポイントのペアを見つける方法があるかどうか、またはそれを行うために使用できる別の手法があるかどうかを知りたいです。
2715 次
1 に答える
12
それらを 3 次元座標に変換してから、線ではなく平面を使用した分割統治法を使用します。これは間違いなく正しく動作します。球上の点のみを調べる場合、円弧距離 (サーフェス上を歩く距離) で最も近い 2 つの点は、3 次元デカルト距離でも最も近い 2 つの点であるため、これは確実です。この実行時間は O(nlogn) になります。
3 次元座標に変換するには、(0,0,0) を地球の中心にするのが最も簡単な方法で、座標は (cos(lat)*cos(lon),cos(lat)*sin(lan) です。 )、sin(緯度))。これらの目的のために、計算を簡単にするために、地球の半径が 1 であるスケールを使用しています。他の単位で距離が必要な場合は、その単位で測定された地球の半径をすべての量に掛けるだけです。
これはすべて、地球が球体であると仮定していることに注意してください。正確に 1 というわけではなく、ポイントには実際には高度も含まれている可能性があるため、これらの答えは完全に正確というわけではありませんが、ほぼすべてのケースでほぼ正確になります。
于 2011-08-20T04:23:30.397 に答える