real-time - 确定一个点在哪些多边形中

Question

我有大量的点数据流(二维)(每秒数千个)。在这张 map 上，我有几个固定的多边形(几十到几百个)。

我想实时确定(在相当强大的笔记本电脑上几毫秒的数量级)它所在的多边形(多边形可以相交)的每个点。我想我会使用 ray casting algorithm .

不过，我需要一种方法来预处理数据，以避免扫描每个多边形。因此，我考虑使用树方法(PM 四叉树或 Rtree？)。还有其他相关方法吗？是否有您会推荐的良好 PM 四叉树实现(使用任何语言，最好是 C(++)、Java 或 Python)？

Answer 1

我用Java开发了一个多维索引的库，可以找到here .它包含 R*Tree、STR-Tree、4 个四叉树(2 个用于点，2 个用于矩形)和一个 critbit 树(可通过交错坐标用于空间数据)。我还开发了 PH-Tree .

所有基于矩形/点的树，因此您必须将多边形转换为矩形，例如通过计算边界框。对于所有返回的边界框，您必须手动计算多边形是否真的与您的点相交。如果您的矩形不是太长，这应该仍然有效。

我通常发现 PH-Tree 是最高效的树，如果一个点与 100 个或更少的矩形相交(10 个或更少的矩形更好)，它的构建时间和查询时间都非常快。 STR/R* 树在重叠尺寸较大 (1000+) 时效果更好。四叉树有点不可靠，它们在插入数百万个元素时会出现数值精度问题。

假设一棵具有 100 万个矩形的 3D 树，平均每个查询一个结果，PH-Tree 在我的桌面(i7 4xxx)上每个查询需要大约 3 微秒，即每毫秒 300 个查询。