0

问题

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

主意

我可以用 R-Tree 索引所有多边形，允许我只检查边界框被命中的多边形。

可能的新问题

由于多边形相互接触（想想​​行政边界），在不止一个多边形的边界框中有很多点，因此迫使许多点在多边形测试。

问题

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

4

2 回答 2

1

四叉树的工作可能比光栅化更糟糕——它们本质上是对 2x2 图像的重复光栅化......但绝对可以在所有简单的情况下利用光栅化，因为测试光栅应该尽可能快。如果你能轻松解决 90% 的问题，你就有更多的时间来解决剩下的问题。

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

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

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

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

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

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

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

于 2014-09-04T17:03:31.843 回答
0

尝试使用四叉树。

基本上你可以递归地将空间分成 4 个部分，然后对于每个部分你应该知道：a）作为给定部分的超集的多边形 b）与给定部分相交的多边形

这给出了一些您可能不满意的 O(log n) 开销因子。

另一种选择是仅使用网格划分空间。您应该保留与上述情况相同的信息或网格的每个部分。这确实只有一些恒定的开销。

这两个选项都假设多边形的分布在某种程度上是均匀的。

如果您可以离线处理点，还有另一个选项（换句话说，您可以选择点的处理顺序）。然后，您可以使用一些扫线技术，在其中按一个坐标对点进行排序，按此排序顺序迭代点，并在迭代期间仅维护一组有趣的多边形。

于 2014-09-02T16:45:31.903 回答