同じサイズの長方形のコレクションがたくさんあります。これらの長方形に含まれるべきではないランダムな点を生成しているので、生成された点が長方形の1つにあるかどうかをテストし、ある場合は新しい点を生成します。
Rツリーの使用は機能しているように見えますが、実際には点ではなく長方形を対象としています。ポイントでも機能するRツリーアルゴリズムの修正バージョンを使用することもできますが、より良い解決策がすでにある場合は、車輪の再発明はしたくありません。私はデータ構造にあまり詳しくないので、私の問題に役立つ構造がすでに存在するのではないでしょうか。
要約すると、基本的に私が求めているのは、Pythonで機能し、特定の長方形のセット内の任意の長方形に点があるかどうかを確認するために使用できる優れたアルゴリズムを誰かが知っているかどうかです。
編集：これは2Dであり、長方形は回転しません。
このRedditスレッドはあなたの問題に対処します：
長方形のセットがあり、それらのいずれかに点が含まれているかどうかを判断する必要があります。高速ルックアップが重要である、これを行うためのいくつかの良いデータ構造は何ですか？
ユニバースが整数である場合、または精度のレベルがよく知られていて高すぎない場合は、カラーリングを使用したO（1）ルックアップを使用して、スレッドからのabelssonの提案を使用できます。
いつものように、時間と空間のトレードオフを行うことができます。これは、定数が非常に低いO（1）ルックアップです。init：すべての長方形を十分な精度で包むのに十分な大きさのビットマップを作成し、それを黒に初期化します。長方形を含むすべてのピクセルを白に着色します。O（1）ルックアップ：点（x、y）は白ですか？もしそうなら、長方形がヒットしました。
その投稿にアクセスして、最も受け入れられているModernRoninの回答を完全に読むことをお勧めします。ここに貼り付けました：
まず、ミクロの問題。任意に回転した長方形と点があります。ポイントは長方形の内側にありますか？
これを行うには多くの方法があります。しかし、最良の方法は、2次元ベクトル外積を使用することだと思います。まず、長方形のポイントが時計回りに格納されていることを確認します。次に、1）側面の2つの点によって形成されるベクトル、および2）側面の最初の点からテスト点までのベクトルを使用して、ベクトルの外積を行います。結果の符号を確認します。正は側面の内側（右側）にあり、負は外側にあります。4辺すべての内側にある場合は、長方形の内側にあります。または、同等に、それがいずれかの辺の外側にある場合、それは長方形の外側にあります。詳細はこちら。
この方法では、ベクトルごとに3つの減算*×辺ごとに2つのベクトルに加えて、辺ごとに1つの外積（3つの乗算と2つの加算）が必要になります。辺あたり11フロップ、長方形あたり44フロップ。
外積が気に入らない場合は、次のようにすることができます。各長方形の内接円と外接円を計算し、内接円の内側の点を確認します。もしそうなら、それも長方形の中にあります。そうでない場合は、外接長方形の外側にあるかどうかを確認してください。もしそうなら、それも長方形の外側にあります。それが2つの円の間にある場合、あなたはf **** dであり、それを難しい方法でチェックする必要があります。
2Dで点が円の内側にあるかどうかを確認するには、2つの減算と2つの2乗（=乗算）が必要です。次に、平方根を実行する必要がないように、距離の2乗を比較します。これは4フロップで、2つの円を掛けると8フロップになりますが、それでもわからない場合があります。また、これは、外接円または内接円を計算するためにCPU時間を支払わないことを前提としています。これは、長方形セットで実行する事前計算の量に応じて、当てはまる場合と当てはまらない場合があります。
いずれにせよ、特に1億個の長方形がある場合は、すべての長方形に対してポイントをテストすることはおそらく良い考えではありません。
これはマクロの問題につながります。セット内のすべての長方形に対してポイントをテストすることを回避するにはどうすればよいですか？2Dでは、これはおそらく四分木 問題です。3Dでは、generic_handleが言ったこと-八分木。頭のてっぺんから、おそらくB+ツリーとして実装します。d = 5を使用すると、各ノードに最大4つの子を含めることができます。これは、クワッドツリーの抽象化に非常にうまくマッピングされるためです。ただし、長方形のセットが大きすぎてメインメモリに収まらない場合（最近はあまりありません）、ディスクブロックと同じサイズのノードを使用するのがおそらく良い方法です。
同じ正確な点に中心を持つ1万のほぼ同一の長方形を持つデータセットのように、厄介な縮退したケースに注意してください。：P
この問題が重要なのはなぜですか？光線がポリゴンと交差するかどうかをチェックすることは、コンピュータグラフィックスで役立ちます。つまり、あなたが撃った狙撃ライフルのショットは、あなたが撃っている人に当たったのですか？また、GPSユニットなどのリアルタイムマップソフトウェアでも使用されます。GPSは現在の座標を教えてくれますが、地図ソフトウェアはその地点が大量の地図データのどこにあるかを見つけ、1秒間に数回実行する必要があります。
繰り返しになりますが、 ModernRoninの功績は...
軸に沿って配置された四角形の場合、四角形を識別するために 2 つのポイント (4 つの数字) だけが必要です。従来は、左下隅と右上隅です。与えられた点 (X test , Y test ) が四角形 (X BL , Y BL , X TR , Y TR ) とオーバーラップしているかどうかを確認するには、両方をテストします。
明らかに、テストする点のセットが十分に大きい場合、これにはかなりの時間がかかる可能性があります。問題は、テストを最適化する方法です。
明らかに、最適化の 1 つは、すべての長方形を囲むボックス (バウンディング ボックス) の X 値と Y 値の最小値と最大値を確立することです。これをすばやくテストすると、さらに調べる必要があるかどうかが示されます。
総表面積のどれだけが長方形で覆われているかによって、長方形を含む重複しないサブエリアを見つけることができる場合があり、ポイントに重なる長方形を含むことができないサブエリアの検索を避けることができます。適切なデータ構造の事前計算を犠牲にして、検索中の比較を保存します。四角形のセットが十分にまばらである場合、オーバーラップがない可能性があり、その場合、これは力ずくの検索に陥ります。同様に、長方形のセットが非常に密集しているため、長方形を分割せずに分割できる境界ボックスにサブ範囲がない場合。
ただし、境界領域をたとえば 4 分の 1 (各方向に半分) に任意に分割することもできます。次に、元のセットよりも多くのボックスを含むボックスのリストを使用します (任意の境界の 1 つに重なるボックスごとに 2 つまたは 4 つのボックス)。これの利点は、検索から 4 つの 4 分の 3 を除外できることです。これにより、補助ストレージを犠牲にして、全体で実行する検索の量を減らすことができます。
したがって、これまでと同様に、時空間のトレードオフがあります。そして、事前計算と検索のトレードオフ。運が悪いと、事前計算で何も達成されません (たとえば、ボックスが 2 つしかなく、どちらの軸でも重なりません)。一方で、かなりの検索時間の利点を達成できます。
あなたのRツリーアプローチは、私が知っている最良のアプローチです（Rツリーはあなたの場合に構築するのに便利なように見えるため、四分木、B +ツリー、またはBSPツリーよりも選択するアプローチです）。警告: 私は専門家ではありませんが、大学の 4 年生のアルゴリズムの授業で覚えていることがいくつかあります。
これを試してみませんか。計算とメモリの両方でかなり軽いようです。
スペースのベースラインへのすべての長方形の投影を検討してください。その行間隔のセットを次のように表します
{[Rl1, Rr1], [Rl2, Rr2],..., [Rln, Rrn]}, ordered by increasing left coordinates.
ポイントが (x, y) であると仮定し、ポイント x を含む行間隔に到達するまで、このセットの左側から検索を開始します。
何もしない場合、ポイント (x,y) はすべての長方形の外側にあります。
[Rlk, Rrk], ..., [Rlh, Rrh], (k <= h) の場合、y がこれらの長方形のいずれかの垂直範囲内にあるかどうかを確認します。
終わり。
幸運を。
ジョン・ドナー
BSP ツリーを参照することをお勧めします(また、クアッドツリーまたはオクツリーの可能性もあり、そのページにもリンクがあります)。それらは、空間全体を再帰的に分割するために使用され、チェックする必要がある長方形をすばやくチェックすることができます。
少なくとも 1 つの巨大なパーティションがあり、すべての四角形をチェックする必要があります。最大で、パーティションが非常に小さくなり、単一の四角形のサイズになります。もちろん、パーティションの粒度が細かくなればなるほど、チェックしたい四角形を見つけるためにツリーをたどる時間が長くなります。
ただし、ポイントのチェックに適した長方形の数を自由に決定して、対応する構造を作成できます。
ただし、長方形の重なりに注意してください。とにかく BSP ツリーを事前に計算する必要があるため、その間にオーバーラップを削除して、明確なパーティションを取得できるようにすることもできます。