algorithm - 快速点索引-(> 100.000.000)-in-polygon-(> 10.000)-test

Question

问题

我正在使用 openstreetmap-data 并想测试它们所在的多边形的点特征。总共有 10.000 个多边形和 100.000.000 个点。我可以将所有这些数据保存在内存中。多边形通常有 1000 个点，因此进行多边形中的点测试非常昂贵。

想法

我可以用 R 树索引所有多边形，这样我就可以只检查边界框被命中的多边形。

可能的新问题

由于多边形相互接触(想想​​行政边界)，不止一个多边形的边界框内有很多点，因此需要进行很多点多边形测试。

问题

你有什么比使用 R-Tree 更好的建议吗？

Answer 1

四叉树的效果可能比光栅化差 - 它们本质上是对 2x2 图像的重复光栅化...但肯定会利用光栅化处理所有简单的情况，因为测试光栅应该一样快因为它得到。如果您可以轻松解决 90% 的问题，您就有更多时间处理剩余的问题。

还要确保首先删除重复项。索引经常出现重复，而且它们显然对测试来说是多余的。

R*-trees 可能是一个值得尝试的好东西，但你需要非常小心地实现它们。

您要查找的操作是包含空间连接。我不认为你可以使用任何实现 - 但对于你的性能问题，无论如何我都会自己仔细实现它。还要确保调整参数并分析您的代码!

连接的基本思想是构建两棵树——一棵用于点，一棵用于多边形。 然后从每棵树的根节点开始，递归地重复以下操作直到叶级:

• 如果一个是非目录节点:
  • 如果两个节点不重叠:返回
  • 通过启发式方法(您需要弄清楚这部分，“更大的扩展”可能会作为开始)决定扩展哪个目录节点。
  • 递归到每个新节点，加上另一个未打开的节点作为新对。
• 叶节点:
  • 快速测试点与多边形边界框
  • 多边形中的慢速测试点

如果您对多边形进行快速内部测试，尤其是多边形中的矩形，则可以进一步加速此过程。如果它是近似的，它可能就足够了，只要它很快。

有关更多详细信息，请搜索 r-tree spatial join。