iphone - 配列内の 2 点間の最大距離

Question

CGPoints ( NSValues でラップされた)を持つ配列があるとしましょう。互いに最も離れている 2 つの点を取得するにはどうすればよいですか。この 2 点間の距離が最大ということですか? 2 点ごとにチェックすることはできますが、効率的ではないようです。これを行うより良い方法はありますか？

手伝ってくれてありがとう！

Answer 1

ポイントが多すぎない場合 (最大 1000、集中的な場合は約 100)、単純なブルート フォース法 O(n ² ) を使用します。

詳細は読んでいませんが、おそらく最大距離は O(nlog n) で凸包アルゴリズム+回転キャリパーで計算できます。