ポイントのセットが与えられた場合、互いに最も遠い2つのポイントを見つけるにはどうすればよいですか？ [複製]
https://stackoverflow.com/questions/1618398
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
可能な重複：
最大直線寸法2d点セット
各ポイント間の距離を計算して最大値を取ることはできますが、ポイント数が多い（＆gt; 1000）場合は効率的な方法とは言えません。
注：これはiPhone向けであるため、処理能力はあまりありません。
解決
セットの直径の計算を求めています。標準的な手法では、最初に凸包を計算します。これにより、凸多角形の直径を見つける問題が軽減されます。ポイントを削除しない場合でも、この追加情報は、問題を効率的に解決するために必要なものです。ただし、凸多角形の直径を見つけることは完全に簡単ではありません。このタスクのアルゴリズムを含むいくつかの公開された論文は間違っていることが判明しました。
かなり読みやすいディスカッションタスクの正しいO（n）アルゴリズム（nは凸包の点の数）。
また、iPhoneは 制限されていないことに注意してください。完全に素朴なアルゴリズムでさえ注意深く書かれた実装は、1/10秒未満で1000ポイントを処理できます。もちろん、正しいアルゴリズムを使用すると、はるかに高速になります=）
他のヒント
X座標が最も低いポイントから開始します。 （ポイントXと呼ぶ） 「境界点」のセットを作成します ポイントxから始まり、ポイントを通る垂直線、PointXの左側に他のポイントはないはずです）ラインが他のポイントに触れるまで時計回り（または反時計回り）にゆっくりとラインを回転させ、境界内の次のポイントを見つけます（以下を参照） ）。そのポイントをセットに追加し、最終的に元のポイントxに戻るまで、次のポイントを取得して次のポイントを取得します。 npwには、完全なセットの境界を形成するポイントのセットがあります。この縮小セットの各ペア間の距離を比較して、最も離れているペアを見つけます。
「行を回転させる」には（連続する各境界点を見つけるため）、「最も遠い」点を取得します。最後の境界点に使用される線に垂直な方向で、最後の境界点とその「次」との間に新しい線を作成します。ポイント。次に、その新しい線によって形成される新しい垂直方向に他のポイントが存在しないことを確認します。他に「ファーザーアウト」ポイントがない場合この線または最後の線に垂直なダーティクションでは、これが次の境界点の右のチョイスであり、そのような点がある場合は、その点に切り替えて再テストします。
これらのページ（一連のポイントの凸包の直径を計算する際に「次へ」リンクをクリックすることでリンクされ、ページに到達できます。
クイックサマリー：
- 凸包（= O（n log n）のポイントのセットを計算し、O（n）を取得するのは、とにかくO（n log n）を取るリストを最初にソートする場合のみです）
- 境界に沿った注文（グラハムスキャンを＃ 1）
- O（n）直径アルゴリズムのいずれかを使用して、最大直径を持つ対pod点をスキャンします。 Shamosアルゴリズムは、キャリパーの回転アルゴリズム。
