寻找位于二维区域内的点

Question

我有一个非常大的数据集，由（x，y）坐标组成。我需要知道这些点中哪些位于2D空间的某些区域内。这些区域由2D域中的4条线界定（其中一些边缘略微弯曲）。

对于较小的数据集，我使用了冗长的for循环来测试每个点是否属于每个区域。由于数据集的大小，这似乎不再是一个好的选择。

有更好的方法吗？

例如：

如果我有一组点： (0,1) (1,2) (3,7) (1,4) (7,5)

以及由以下线条界定的区域：

y=2
y=5
y=5*sqrt(x) +1
x=2

我希望找到一种方法来识别该区域中的点（或点）。

谢谢。

精确的代码在另一台计算机上，但是从记忆中它大致是这样的：

point_list = []
for i in range(num_po):
    a=5*sqrt(points[i,0]) +1
    b=2
    c=2
    d=5

    if (points[i,1]<a) && (points[i,0]<b) && (points[i,1]>c) && (points[i,1]<d):
         point_list.append(points[i])

这不是精确的代码，但应该可以给您一个我尝试过的想法。

- Bensciens

---

有多少个点和多少个区域（也称为多边形）？ - RickyA

现在，我们能否得到您用来测试它们的代码？ - RickyA

点的数量约为100万，多边形的数量是可变的，但我目前正在处理15个。我不确定这是否相关，但多边形不重叠，但可能在边界处相接触。 - Bensciens

嗯，1M并不算太大。你的代码现在需要多长时间才能运行？ - RickyA

我的错误，尽管点数可能会根据情况增加。我还没有单独测试过代码，它是一个更大过程的一部分。我正在尝试从我们以前使用的旧方法转换到一种新方法，该方法需要我们识别所有点的位置，而旧方法则不需要。使用旧方法需要15分钟，目前使用新方法需要两倍的时间。由于代码的这一部分将运行多次，额外的时间变得非常致命。 - Bensciens

Answer 1

如果你只有一个地区（或仅有少量地区），那么除了检查每个点之外，很难找到更好的方法。每个点的检查可以很快，尤其是如果您首先选择最快或最具有区分性的检查（例如，在您的示例中，也许是 x > 2）。

如果您有很多地区，则可以通过使用空间索引（例如 R-Tree）来提高速度，这将快速识别正确区域内的一小组候选对象。然后，逐个检查每个候选对象，就像您已经在进行的检查一样。您可以选择对点或地区进行索引。

我使用Python Rtree包进行空间索引，并发现它非常有效。

- strubbly

Answer 2

这被称为范围搜索问题，是计算几何学中一个经过深入研究的问题。这个主题相当复杂（因为你的平方根使事情非线性化，从而更加困难）。在这里有一篇关于如何使用SciPy在Python中进行计算几何的不错博客文章。

- John Coleman

Answer 3

长评论：

你没有告诉我们完整的故事。

如果你有一个大的点集（假设有N个点）和一个曲线四边形集合（假设有M个），并且你需要解决这个问题一次，那么你无法避免对所有点进行穷举测试以确定是否在接受区域内。

不过，你可能可以预处理这M个区域，使得对接受区域进行点测试所需的操作少于M次（接近Log(M)次）。但由于M的值很小，大幅节省的可能性不大。

现在，如果你不仅仅有一个接受区域，而是有多个接受区域要依次应用于同一点集上，那么更复杂的解决方案是可行的（即范围搜索），它可以将N次比较减少到大约Log(N)次，这是一个相当显著的改进。

也许点集并不完全随机，并且存在一些可以利用的点集属性。

你应该告诉我们更多信息并展示一个示例案例。

- user1196549