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。