矩形の検索矩形の配列からのポイントを含む

Question

私は長方形の配列を持っています。与えられた点を含む矩形を見つけようとしています。私はこの配列を繰り返し、CGRectContainsPointを使ってこの点を含むrectを見つけることができます。

CGRect rectContainingPoint; 
for (CGRect rect in arrayOfRects) { 
    if(CGRectContainsPoint(rect, point)) { 
     rectContainingPoint = rect; 
     break; 
    } 
} 

私は大規模な配列を反復処理する必要がどこに私の配列は非常に大きい場合、これはパフォーマンスの面でエレガントな解決策ではないかもしれないと感じが以下のように疑似コードです。楽観的なやり方でこれを見つけるための最善の解決策やアルゴリズムがあれば誰かが助けてくれる？

Answer 1

大きな配列を繰り返す必要がある場合、配列が非常に大きい場合、これはパフォーマンス面では洗練されていない可能性があります。楽観的なやり方でこれを見つけるための最善の解決策やアルゴリズムがあれば誰かが助けてくれる？

まず、実際にパフォーマンスの問題がありますか？アルゴリズムを改善する方法を検討する前にそれを決定してください。いったん何かが完了する必要があると確信したら...

現在のソリューションは長方形のコレクションを使った線形検索で、O（N）ソリューションです。これを改善するには、必要なテストの数を減らす検索方法が必要です。順序付けされたコレクション内のバイナリ検索には、より良いO（log N）動作があります。

順序付きコレクションを使用するには、検索ごとに順序付けられていないコレクションを並べ替える必要はありません。完全な並べ替えはO（NlogN）です。代わりに、ソートを維持するためにコレクションを並べ替えることを考えておく必要があります。バイナリ検索と同じように、挿入ごとにO（ログN）のパフォーマンスが可能です。

これはちょうど大きな問題を残していますが、並べ替えることができるように、長方形の適切な順序を工夫できますか？原点のx座標での順序付けが可能です。点のx座標が原点のx座標より小さい場合、包含のためにテストすると、その点は順序の後の任意の矩形内にあることはできません。あなたは、両方の原点座標に基づいて発注になど

TL見たいかもしれません; DR：長方形の

1. ソートあなたのリストをして
2. （挿入ごとにO（Nを記録））それはソート保ちますおそらく、すべてが高速になります起源は、バイナリサーチのようなものを使用してポイントの包含のためのこの
3. 検索用（S）座標使用することを検討して、何とか自分の四角形をオーダー（O（対数N））

エル。

ソートと検索を研究してコードを書いた後に問題に遭遇した場合は、新しい質問をし、コードを表示し、アルゴリズム（特にあなたが選んだ順序）を詳しく説明し、誰かが間違いなくあなたを助けてくれるでしょう。

HTH

Answer 2

大規模な配列の場合、メインスレッドを妨げることなくバックグラウンドスレッドで実行される列挙型ループを使用できます。