私はポイントデータ（2Dで）（数千秒毎秒）の膨大なフローを持っています。このマップには、数十から数百のポリゴンが固定されています。ポイントがどのポリゴンであるかを調べる
ポリゴンが存在する各ポイント（ポリゴンが交差する可能性があります）に対して、リアルタイムで（かなり強力なラップトップでは数ミリ秒のオーダ）決定したいと考えています。 ray casting algorithmを使用すると思いました。
しかし、すべてのポリゴンをスキャンしないように、データを前処理する方法が必要です。 したがって、ツリーアプローチ（PM quadtreeまたはRtree？）の使用を検討します。他に関連する方法はありますか？ 推奨する良いPM Quadtreeの実装はありますか（どの言語でも、C（++）、Java、Pythonが好ましい）？
私はJavaでいくつかの多次元インデックスのライブラリを開発しました。それはhereです。これには、R * Tree、STR-Tree、4クオッドツリー（ポイント2つ、長方形2つ）、およびcritbitツリー（座標をインターリーブして空間データに使用することができます）が含まれています。私もPH-Treeを開発しました。
すべてのレクタングル/ポイントベースのツリーがあります。したがって、境界ボックスを計算するなどして、ポリゴンを矩形に変換する必要があります。すべての返されたバウンディングボックスに対して、ポリゴンが実際にあなたのポイントと交差する場合、手動で計算する必要があります。 長方形の長さがあまり伸びていない場合でも、効率的なはずです。
私は通常、PH-Treeが最も効率的なツリーであることを知りました。ポイントが100個の長方形またはそれ以下（さらに10個以下の場合）と交差する場合、高速の構築時間と非常に高速なクエリ時間を持ちます。 STR/R * -treesは、より大きいオーバーラップサイズ（1000+）でより優れています。クオッドツリーは信頼性が低く、数百万の要素を挿入するときの数値精度に問題があります。
PH-Treeは、100万個の四角形を持つ3Dツリーを仮定し、クエリあたり平均1つの結果があると仮定すると、デスクトップ（i7 4xxx）のクエリーあたり約3マイクロ秒、つまり1ミリ秒あたり300クエリが必要です。