7

緯度/経度のポイントの配列を入力として受け取るプログラムがあります。その配列をチェックして、すべてのポイントが特定の半径内にあることを確認する必要があります。たとえば、許可する最大半径は 100 マイルです。緯度/経度の配列 (MySQL データベースからのもので、10 ポイントが 10000 になる可能性があります) が与えられた場合、それらがすべて半径 100 マイルの円に収まるかどうかを判断する必要があります。

これにアプローチする方法にちょっと困惑しました。どんな助けでも大歓迎です。

4

4 に答える 4

5

すべての点を含む最小の円を見つけ、その半径を 100 と比較します。

于 2010-04-26T20:44:11.410 に答える
1

以下の答えは、地球が完全な球体であると仮定することを含みます。これは、地球を平面として扱うよりも正確な答えを与えるはずです.

緯度/経度ポイントのセットの半径を計算するには、まずポイントのセットが「半球状」であることを確認する必要があります。すべての点は、完全な球体の任意の半分に収まります。

Gupta と Saluja による論文「アプリケーションを使用したガウス球面の近接問題に対する最適なアルゴリズム」のセクション 3 を確認してください。具体的なリンクはありませんが、オンラインでコピーを無料で見つけることができると思います。このホワイト ペーパーは、ソリューションを実装するには不十分です。また、Ha と Yoo による「球面ポリゴンの最大交差のためのセントロイドの近似」の付録 1 も必要です。

私は、半球性テストの線形計画法部分を実行するためにメギドのアルゴリズムを使用しません。代わりに、Raimund Seidel による「Small-Dimensional Linear Programming and Convex Hulls Made Easy」で説明されている、線形計画問題を解くための Seidel のアルゴリズムを使用してください。また、Kurt Mehlhorn による「Seidel の Randomized Linear Programming Algorithm」と、Christer Ericson による「Real-Time Collision Detection」のセクション 9.4 も参照してください。

ポイントが半球状であると判断したら、Gupta と Saluja による論文のセクション 4 に進みます。この部分では、ポイントの「最小の囲み円」を実際に取得する方法を示します。

必要な二次計画法を実行するには、ND Botkin による論文「A Randomized Algorithm for Solving Quadratic Programs」を参照してください。このチュートリアルは役に立ちますが、論文では (1/2)x^TG x - g^T x を使用し、Web チュートリアルでは (1/2)x^TH x + c^T x を使用しています。1 つは項を加算し、もう 1 つは減算するため、符号関連の問題が発生します。この例の 2D QP 問題 も参照してください。ヒント: C++ を使用している場合、Eigen ライブラリは非常に優れています。

この方法は、上記の 2D 方法のいくつかよりも少し複雑ですが、地球の曲率を完全に無視するよりも正確な結果が得られるはずです。この方法には O(n) 時間の複雑さもあり、漸近的に最適である可能性があります。

注:上記の方法では重複データを適切に処理できない場合があるため、最小の囲み円を見つける前に、重複する緯度/経度ポイントを確認することをお勧めします。

于 2011-06-02T13:16:46.817 に答える
1

これを解決する最も簡単な方法は、座標を (X、Y、Z) に変換してから、球に沿って距離を見つけることです。

地球が半径 R の球であると仮定すると (完全に正しくありません)...

X = R * cos(long) * cos(lat)

Y = R * sin(long) * cos(lat)

Z = R * sin(緯度)

この時点で、3 空間に対するピタゴラスの定理の拡張を使用して、点間の距離を概算できます。

距離 = sqrt((x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2)

しかし、地表に沿った実際の距離を見つけるには、原点 (地球の中心) から 2 点までの角度を知る必要があります。

位置をベクトル V1 = (X1, Y1, Z1) および V2 = (X2, Y2, Z2) として表すと、角度は次のようになります。

angle = arcsin((V1 x V2) / (|V1||V2|))、x は外積です。

距離は次のとおりです。

距離 = (地球の円周) * 角度 / (2 * pi)

もちろん、これは標高の変化や地球が赤道で広いという事実を考慮していません.

私の数学を LaTeX で書かなかったことをお詫びします。

于 2010-04-26T20:46:13.527 に答える
0

この質問に対する回答を確認してください。任意の 2 点 (緯度、経度) 間の距離を測定する方法を提供します。次に、最小囲み円アルゴリズムを使用します。

平面上で最小の囲み円を見つけるのは非常に難しいと思われるため、緯度と経度、および球形ジオメトリを操作する際の微妙な点を排除するには、ポイントを XY 平面にマッピングすることを検討する必要があります。これにより、ある程度の歪みが生じますが、意図した縮尺が 100 マイルであれば、おそらくそれで問題ありません。円とその中心を XY 平面上に配置したら、いつでも地上の球体にマップして距離を再確認できます。

于 2010-04-26T20:45:48.630 に答える