我有大量的2D点数据流(每秒数千个)。在这张地图上，我有几个固定的多边形(几十到几百个)。
我想实时确定(在功能相当强大的笔记本电脑上，几毫秒的顺序)多边形所在的每个点(多边形可以相交)。我想我应该使用光线投射算法。
然而，我需要一种方法来预处理数据，以避免扫描每个多边形。因此，我考虑使用树方法(PM四叉树或Rtree ?)。还有其他相关的方法吗?是否有一个好的PM四叉树实现你会推荐(在任何语言，最好是C(++)， Java或Python) ?
我用Java开发了一个多维索引库，可以在这里找到。它包含R*Tree, STR-Tree, 4棵四叉树(2棵用于点，2棵用于矩形)和一个临界树(可以通过交错坐标用于空间数据)。我还开发了ph树。
都是基于矩形/点的树，所以你必须将多边形转换成矩形，例如通过计算边界框。对于所有返回的边界框，你必须手动计算多边形是否真的与你的点相交。如果你的矩形不是太长，这应该仍然是有效的。
我通常发现PH-Tree是最有效的树，它具有快速的构建时间和非常快的查询时间，如果一个点与100个或更少的矩形相交(甚至更好)。STR/R*-树在较大的重叠大小(1000+)时效果更好。四叉树有点不可靠，当插入数百万个元素时，它们在数字精度上存在问题。
假设一个有100万个矩形的3D树，平均每次查询一个结果，PH-Tree在我的桌面(i7 4xxx)上每次查询大约需要3微秒，即每毫秒300个查询。