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