10

重複の可能性:
最大直線寸法 2 次元のポイント セット

各ポイント間の距離を計算して最大のものを取得することはできますが、ポイントの数が多い (> 1000) 場合は、あまり効率的な方法とは言えません。

注: これは iPhone 用なので、処理能力はあまり高くありません。

4

4 に答える 4

9

Why not just compute the convex hull of the points? Depending on the algorithm you use, it takes either O(n) or O(n log n) time and eliminates all the inner points from consideration. Then, only check these outermost points to find the two that are the farthest away.

于 2009-10-24T16:31:44.380 に答える
8

セットの直径を計算するよう求めています。標準的な手法は、最初に凸包を計算することです。これにより、問題は凸多角形の直径を見つけることになります。ポイントを削除しない場合でも、この追加情報は問題を効率的に解決するために必要なものです。ただし、凸多角形の直径を見つけるのは簡単ではありません。このタスクのアルゴリズムに関するいくつかの公開された論文は、正しくないことが判明しています。

これは、タスクの正しい O(n) アルゴリズムのかなり読みやすい議論です (ここで、n は凸包の点の数です)。

また、iPhone はそれほど制限されていないことに注意してください。完全に単純なアルゴリズムでさえ、慎重に記述された実装では、1000 点を 10 分の 1 秒未満で処理できます。もちろん、正しいアルゴリズムを使用すると、はるかに高速になります =)

于 2009-10-24T17:10:58.930 に答える
0

x座標が最も低い点から始めます。（ポイントXと呼びます）ポイントxで始まり、ポイントを通る垂直線のセットを作成します。ポイントXの左側に他のポイントはありません）ラインを時計回りにゆっくりと回転させて、境界内の次のポイントを見つけます（または反時計回り）線が他の点に接触するまで（以下を参照）。そのポイントをセットに追加し、その次のポイントで繰り返して次のポイントを取得し、最終的に元のポイントxに戻るまで続けます。npwには、完全なセットの境界を形成するポイントのセットがあります。この縮小されたセットの各ペア間の距離を比較して、最も離れているペアを見つけます。

To "rotate the line" (to find each sequential boundary point), take the point which is "furthest" in the direction perpindicular to the line used for the last boundary point, and construct a new line between the last boundary point and that "next" point. Then verify that there are no other points furthur in the new perpindicular direction formed by that new line. If there are no other points "furthur out" in the dirtection perpindicular to this line or to the last line, then this is the right cjhoice for the next boundary point, if there is such a point, switch to that one and retest.

于 2009-10-24T16:31:36.377 に答える
0

一連の点の凸包の直径の計算については、これらのページ（リンクされているページと「次の」リンクをクリックして到達可能なページ）を参照してください。

私の簡単な要約：

  1. 凸包内の点のセットを計算します（= O（n log n）、O（n）を取得するのは、とにかくO（n log n）を取るリストを最初にソートする場合のみです）
  2. 境界に沿って注文する（ ＃1にグラハムスキャンを使用すると、これを無料で入手できます）
  3. O（n）直径アルゴリズムの1つを使用して、最大直径の対蹠点をスキャンします。Shamosアルゴリズムは、回転キャリパーアルゴリズムの1つであるため、私にはよく見えます。
于 2009-10-25T02:31:02.767 に答える