私は等しい半径の円がある矩形の領域を持っています。私は、どのサークルが他のサークルと重なっているかを知りたい（アウトプットは2要素のオーバーラップサークルのリストである）。重複する円を見つける
円の2つが重なっている（中心間の距離が直径より小さいかどうかを確認する）方法を知っています。すべての円のペアについてこのチェックを実行できますが、より良いアルゴリズム（O(n^2)より速い）があるかどうか疑問に思っていました。
EDIT
円の数は、通常、約100あると重なり、非常に頻繁に発生しません。
ここにいくつかの文脈があります： 長方形はゲームの戦場です。ユニットの動きは小さなステップで行われ、ユニット間の衝突を検出しようとしています。
問題文の新しい説明が与えられたら、別の方法をお勧めします。
1つの円の直径に等しいグリッドステップで、戦場に正方形のグリッドを重ねます。すべてのサークルは、最大4つのセルでオーバーラップすることができます各セルで、重なり合う円のリストを保持します（そして移動ごとに更新します）。
潜在的な衝突を検出するには、サークルあたり約4回のセル/サークルテストが必要になります。線形時間に近い。
簡単な解決策として、2dツリーにセンタを挿入し、クエリ半径2Rのすべてのセンタを中心に循環範囲クエリーを実行します。良い状態では、これはO（N Log（N））とすることができる。
また、ちょうどXのセンターをソートし、順番にすべての円を試してください。そして、2Dの距離を確認し、二分探索で、横軸Xcのを見つけ、XC-2RへとXcの+ 2Rにスキャンします。
二分探索のコストはO（N Log（N））になります。円が一辺Sの正方形内に均一に広がっている場合、幅4Rのストライプは4RN/S円を含んでいるため、総コストは4RN2/Sになります。これは、Sが大きい場合には良好な性能である（正方形内のN個の密接に囲まれた円の場合、S〜2R√N、したがって2N√Nの比較と考える）。
Nの値が小さいと、網羅的な検索を行うことができないと確信していません。（ –
ダイレクトアンサー：一般にO（n^2）よりも良くなることはありません。なぜなら、サークルはすべて重複する可能性があるからです。したがって、n^2回答を生成する必要があります。
もっと具体的になると、より良い回答が得られる可能性があります。例えば、あなたが実際にやろうとしていることは、2Dシミュレーションで境界球を見つけることであるなら、エンティティはフレーム間でしか動かないということから利益を得ることができます。それで、それが何であるかについてもっと知りましょう。
EDIT：あなたはあなたの質問を編集しました。実際には、2Dシミュレーションで衝突検出を探しています。 https://en.wikipedia.org/wiki/Collision_detectionをチェックアウトすると、正確にあなたのケースのためにいくつかのアルゴリズムを指しています。
私は軸ごとの境界間隔のリスト（「2D」では2）を保持しているそのページの詳細が好きであり、それらの境界間隔（それらは定義上は一意である） （すなわち、「重なり状態」が存在する）。これにより、正常に動作する場合のO(n²)が削除されます。彼らはそれの複雑さの見積もりを提供しませんが、それは基本的にソートになるので、それは多かれ少なかれ私にはO(n logn)のように見え、フレーム間の変化はごくわずかです。
O（N²）、実際には最悪の場合やむを得ないことはおそらく悲観的なことです） –
OPは私の意図です私たちは他のソリューションについて考えることができます。実際には、私は答えを編集します:) – AnoE
良い質問。 :)私はあなたに掃引線アルゴリズムのいくつかの並べ替えを行うことができるようです。 – blazs
Hmmm。 。 。すべての円は他のすべての円と重複する可能性があります。私には、最悪のケースではO（n^2）よりもうまく行かないことが示唆されていますが、それを最適化するヒューリスティックがあるかもしれません。 –
@ GordonLinoff出力の影響を受けやすいアルゴリズムがあるはずです。オーバーラップ数（および円の数）に比例した時間で実行されるアルゴリズムです。これは多少関連したセグメント交差問題の場合である。 – blazs