python - 查找哪些点在二维区域中

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])

这不是确切的代码，但应该让我了解我的尝试。

Answer 1

如果您只有一个(或少量)区域，那么很难比检查每个点做得更好。每个点的检查可能很快，特别是如果您首先选择最快或最具鉴别力的检查(例如，在您的示例中，可能是 x > 2)。

如果您有多个区域，则可以通过使用空间索引(可能是 R-Tree )来提高速度，该索引可以快速识别出位于正确区域中的一小组候选对象。然后每个候选人都被一一检查，就像你已经在检查一样。您可以选择索引点或区域。

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