python - 多数のポイントのポイントインポリゴン

Question

多数のポイント (O(100 万) がポリゴンのコレクション (O(10)) の内側にあるか外側にあるかを判断する最も効率的な方法は何でしょうか?後者は必ずしも凸状ではありませんが、そうではありません穴があります. 現時点では、ポイントの位置をバウンディング ボックスと比較してポイントの数を削減し、残りのポイントでこの交差数法を使用します. しかし、おそらくより速い方法はありますか?

Answer 1

そのための効率的な matplotlib 関数があります: matplotlib.nxutils.points_inside_poly()。アルゴリズムは、このページに記載されています。

Answer 2

軸に沿ったバウンディング ボックスがあると仮定すると、ポイントのリストを x 座標で並べ替え、リスト上のポイントがバウンディング ボックスの内側または外側にある場所をバイナリ検索で見つけ、多数のポイントを一度に破棄する可能性があります。y 座標について繰り返します。次に、残りのポイントで前と同じように続行します。ポリゴンの三角形分割を実行して、バウンディング ボックス内のテストを高速化できます。

平面の面積が多角形の面積よりもはるかに大きく、多角形が適度にコンパクトである場合に最適なパフォーマンスを発揮します (つまり、長くて薄くないため、多くの誤検知が発生する可能性があります)。

Answer 3

四分木を生成するときに決定するあるレベルの精度で、「私はポリゴンの内側ですか、それとも外側ですか」という大まかなテストを高速で行うために 、おそらく四分木を使用します。

各ルックアップは O(log n) であり、これは可能な限り高速になります。「エッジを含む」とマークされた四分木のセル内にあるポイントについては、従来のポイントインポリゴン テストを実行する必要があります。