私は2D計算幾何学/GISの問題を抱えていますが、これは一般的であるはずであり、使用する既存のコード/ライブラリを見つけたいと思っています。
問題は、小さなポリゴンの大きなセット（数千）のどのサブセットが単一の大きなポリゴンと交差するかを確認することです。（「小さい」と「大きい」とは、ポリゴンを定義するポイントの数ではなく、ポリゴンがカバーするスペースの量を指しますが、一般に、ポリゴンを定義するポイントの数は、その幾何学的サイズにほぼ比例すると仮定します。 。そして、比例感を与えるために、「大きい」を米国の州の多角形、「小さい」を町の多角形と考えてください。）
1つの大きなポリゴンPに対して各小さなポリゴンpに対して呼び出される、標準のCheckIfPolygonsIntersect（P、p）関数を使用した単純なソリューションが遅すぎると仮定します。大きなポリゴンを前処理して、小さなポリゴンの大部分の交差チェックを簡単にする方法があるようです。特に、大きなポリゴンを部分的/ほぼ塗りつぶす小さな長方形のセットを作成できるようです。同様に、実際には大きなポリゴン内にない大きなポリゴンの境界ボックスの領域を部分的/ほぼ埋める長方形の小さなセットを作成できます。次に、小さなポリゴンの大部分を簡単に含めるか除外することができます。大きなポリゴンの境界の範囲から完全に外れている場合は、除外されます。それらが、内側の境界の長方形であるが外側のポリゴンの長方形の1つの境界の内側に完全にある場合、それらは除外されます。それらのポイントのいずれかが内部長方形のいずれかにある場合、それらは含まれます。また、上記のいずれにも当てはまらない場合にのみ、CheckIfPolygonsIntersect（P、p）関数を呼び出す必要があります。
それはよく知られているアルゴリズムですか？任意の（凸面または凹面）ポリゴンの内部/外部長方形の妥当なセットを計算するための既存のコードを知っていますか？長方形はすべての場合に完全である必要はありません。それらは、ポリゴンの大部分と、ポリゴンの内側の境界が正しいが外側のポリゴンの領域の多くを埋める必要があります。
これらの長方形を計算する方法の簡単な計画は次のとおりです。
- 大きなポリゴンのバウンディングボックスを取り、その上にポイントのたとえば10x10グリッドを作成します
- 各ポイントについて、ポリゴンの内側か外側かを判断します
- 長方形のエッジの1つがポリゴンのエッジの1つと交差するまで、4つの方向のそれぞれで繰り返し拡張することにより、各ポイントを長方形に「成長」させます。この場合、行き過ぎになります（これは、実際には「バイナリ」で行われます。 「検索」のような反復なので、数回の反復で、各方向に拡張する正しい量を見つけることができます。もちろん、エッジを一度に1つずつ最大化するか、互いに協調して最大化するかという問題があります）
- 別のポイントの拡張によってカバーされる、まだ拡張されていないグリッドポイントはすべて消えます
- すべてのポイントが展開される（または消える）と、内側と外側の長方形のセットができあがります。
もちろん、大きなポリゴンの特定のクレイジーな凹型の形状は、いくつかの貧弱な/小さな長方形につながる可能性があります。しかし、ポリゴンがほとんど合理的であると仮定すると（たとえば、米国の州の形状であるとすると）、優れた長方形のセットが得られ、後で行う数千の交差チェックを大幅に最適化できるようです。 。
そのアルゴリズムの名前（およびコード）はありますか？
編集：私はすでに四分木を使用して、大きなポリゴンの境界長方形と交差する可能性のある小さなポリゴンを決定しています。したがって、問題は、これらのポリゴンのどれが実際に大きなポリゴンと交差するかを確認することです。
助けてくれてありがとう。