确定一个点在哪些多边形中。

Question

我有大量的点数据（2D）（每秒数千个）。在这张地图上，我有几个固定的多边形（几十到几百个）。

我想实时确定每个点位于哪些多边形中（多边形可以相交），并且需要在一台相当强大的笔记本电脑上以几毫秒的顺序完成。我考虑使用射线投射算法。

然而，我需要一种预处理数据的方法，以避免扫描每个多边形。因此，我考虑使用树结构方法（PM四叉树或Rtree？）。是否有其他相关方法？您推荐的PM Quadtree实现是否好用（任何语言，最好是C(++), Java或Python）？

- Robin

Answer 1

我开发了一个Java的多维索引库，包括R*Tree、STR-Tree、4个四叉树（2个用于点，2个用于矩形）以及一个Critbit Tree（可以通过交错坐标用于空间数据）。您可以在这里找到它。我还开发了PH-Tree。

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

通常我认为PH-Tree是最有效的树，它具有快速的构建时间和非常快速的查询时间，如果一个点与100个或更少的矩形相交（甚至10个或更少），效果更好。STR/R*-trees更适合大的重叠尺寸（1000+）。四叉树有点不可靠，当插入数百万个元素时会出现数值精度问题。

假设有一个包含1百万个矩形的3D树，并且平均每次查询只有一个结果，PH-Tree在我的桌面电脑上（i7 4xxx）每次查询大约需要3微秒，即每毫秒可处理300个查询。

- TilmannZ