Поиск точки 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

Есть ли лучший способ, чем поиск по точкам? Может, какая-то неочевидная рутина?

Спасибо!

Answer 1

Если я правильно понимаю вашу проблему, то должно сработать следующее при условии, что ваши очки также являются 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 2

Выровнены ли оси этих блоков? т. е. ребра параллельны координатным осям? Если это так, то это можно сделать довольно эффективно с помощью векторизованных сравнений на массивах 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]

внесение изменений в> = и <=, если вы предпочитаете, чтобы они были включены. </p>

Если вам нужен произвольный четырехугольник, matplotlib на самом деле имеет подпрограмму matplotlib.nxutils.points_inside_poly, которую вы можете использовать (если она установлена) или скопировать ее (она лицензирована BSD). См. эту страницу для обсуждения используемых алгоритмов и других алгоритмов для тестов внутри полигона.

Answer 3

Если вам действительно нужно использовать getProduct ... упаковку, распаковку и хорошие имена переменных ftw!

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 4

Я использовал аналогичную процедуру для построения цветных графиков плотности:

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

Ваше решение - O(N), где N - количество баллов. Если N достаточно велико и вы выполняете запрос isInside много раз, вы можете рассмотреть сортировку точек и затем использовать бинарный поиск, чтобы найти соответствующие точки.

Как всегда, сначала укажите, нужна ли вам эта оптимизация.

Answer 7

Без особых изменений ваш код может быть сжат до:

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 8

Если ваши прямоугольники прямоугольные, не перекрываются и не имеют пробелов, то почему бы вам просто не позвонить numpy.histogram2d? См. Документы NumPy .