Python的点查找（坐标分级？）

Question

问候，

我想斌点(x, y)阵列成箱[(x0, y0), (x1, y0), (x0, y1), (x1, y1)]阵列（元组是角点）

到目前为止，我有以下例程：

def isInside(self, point, x0, x1, y0, y1): 
    pr1 = getProduct(point, (x0, y0), (x1, y0)) 
    if pr1 >= 0: 
     pr2 = getProduct(point, (x1, y0), (x1, y1)) 
     if pr2 >= 0: 
      pr3 = getProduct(point, (x1, y1), (x0, y1)) 
      if pr3 >= 0: 
       pr4 = getProduct(point, (x0, y1), (x0, y0)) 
       if pr4 >= 0: 
        return True 
    return False 

def getProduct(origin, pointA, pointB): 
    product = (pointA[0] - origin[0])*(pointB[1] - origin[1]) - (pointB[0] - origin[0])*(pointA[1] - origin[1]) 
    return product 

有没有更好的方法，然后逐点查找？也许一些不明显的numpy例程？

谢谢！

Answer 1

这些盒子的轴是否对齐？即是平行于坐标轴的边缘？如果是这样的话，这可以通过NumPy数组上的矢量化比较来非常有效地完成。

def in_box(X, B): 
    """ 
    Takes an Nx2 NumPy array of points and a 4x2 NumPy array of corners that 
    form an axis aligned box. 
    """ 
    xmin = B[:,0].min(); xmax = B[:,0].max() 
    ymin = X[:,1].min(); ymax = X[:,1].max() 
    return X[X[:,0] > xmin & X[:,0] < xmax & X[:,1] > ymin & X[:,1] < ymax] 

修改为> =和< =如果你喜欢他们具有包容性。

如果你需要一个任意的四边形，matplotlib实际上有一个例程matplotlib.nxutils.points_inside_poly，你可以使用（如果你有它安装）或者复制它（它是BSD许可的）。对于所使用的算法和其他算法中，一个多边形测试的讨论见this page。

Answer 2

没有太多的改变，你的代码可以压缩到：

def isInside(self, point, x0, x1, y0, y1): 
    return getProduct(point, (x0, y0), (x1, y0)) >= 0 and 
      getProduct(point, (x1, y0), (x1, y1)) >= 0 and 
      getProduct(point, (x1, y1), (x0, y1)) >= 0 and 
      getProduct(point, (x0, y1), (x0, y0)) >= 0 

def getProduct(origin, pointA, pointB): 
    product = (pointA[0] - origin[0])*(pointB[1] - origin[1]) - (pointB[0] - origin[0])*(pointA[1] - origin[1]) 
    return product 

Answer 3

你的解决方案是O(N)其中N为点数。如果N足够大，你正在运行的查询isInside了很多次，你可能会考虑分拣点，然后使用二进制搜索以找到切合点。

与往常一样，第一个人资料是否真的需要这种优化。

Answer 4

如果我理解你的问题正确然后下面应该工作假设你点也是2元组。

def in_bin(point, lower_corner, upper_corner): 
    """ 
    lower_corner is a 2-tuple - the coords of the lower left hand corner of the 
    bin. 
    upper_corner is a 2-tuple - the coords of the upper right hand corner of the 
    bin. 
    """ 
    return lower_corner <= point <= upper_corner 

if __name__ == '__main__': 
    p_min = (1, 1) # lower left corner of bin 
    p_max = (5, 5) # upper right corner of bin 

    p1 = (3, 3) # inside 
    p2 = (1, 0) # outside 
    p3 = (5, 6) # outside 
    p4 = (1, 5) # inside 

    points = [p1, p2, p3, p4] 

    for p in points: 
     print '%s in bin: %s' % (p, in_bin(p, x_min, x_max)) 

此代码表明，你可以直接比较的元组 - 有关于这个文档中的一些信息：http://docs.python.org/tutorial/datastructures.html#comparing-sequences-and-other-types

Answer 5

您确实需要这样一个复杂的检查开始？

def isInside(self, point, x0, y0, x1, y1): 
    x,y = point 
    if x0 > x1: x0,x1 = x1,x0 #these cause no 
    if y0 > y1: y0,y1 = y1,y0 #side effect. 

    return x0 <= x <= x1 and y0 <= y <= y1 

Answer 6

我用了一个类似的程序做colourmapped密度图：

#calculate densities 
rho = zeros((nx,ny)); 
for i in range(N): 
    x_sample = int(round(ix[i])) 
    y_sample = int(round(iy[i])) 

    if (x_sample > 0) and (y_sample > 0) and (x_sample<nx) and (y_sample<ny): 
     rho[y_sample,x_sample] = rho[y_sample,x_sample] + 1 

相反，你可以存储x和y样本计数密度。

Answer 7

如果你真的需要FTW使用getProduct ...包装，拆包和良好的变量名！

def isInside(self, point, x0, x1, y0, y1): 
    A = x0,y0 
    B = x1,y0 
    C = x1,y1 
    D = x0,y1 

    return getProduct(point, A, B) and 
      getProduct(point, B, C) and 
      getProduct(point, C, D) and 
      getProduct(point, D, A) 

def getProduct(origin, pointA, pointB): 
    xA,yA = pointA 
    xB,yB = pointB 
    x,y = point 

    return (xA - x)*(yB - y) - (xB - x)*(yB - y) 

Answer 8

假设你的盒子是长方形的，不重叠，并没有差距，那么你为什么不只是调用numpy.histogram2d？见the numpy docs。