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

你的代码可以在不做太多修改的情况下，简化成下面这样：

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 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 3

这些框是轴对齐的吗？也就是说，它们的边缘是否与坐标轴平行？如果是这样的话，可以通过在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许可证的）。有关使用的算法和其他多边形内部测试算法的讨论，可以查看这个页面。