NumPy - Можно ли это векторизовать?

Question

Работаю над новым сценарием и впервые погружаюсь в NumPy. Преимущества памяти по своей сути очевидны, но векторизация является проблематичной концепцией.

У меня есть 2 NumPy массивов, представляющих точки и блоки XY, и для каждой точки мне нужно определить, какие прямоугольники будут пересекаться.

Два массива имеют такие структуры:

>>> points
array([[40.00183, 20.005],
       [39.9975, 20.0125],
       [57.01822, 16.997]], dtype=float32)

>>> boxes
array([[40.00183, 20.005, 39.9975, 20.0125],
       [39.9975, 20.0125, 57.01822, 16.997],
       [57.01822, 16.997, 40.00183, 20.005]], dtype=float32)

Фактические значения здесь составлены, фактически ящики не являются даже ящиками, но это структура. points - это массив ND с формой (N, 2) и boxes с формой (M, 4).

Алгоритм тестирования пересечений:

def intersect(p: np.ndarray, b: np.ndarray) -> bool:
    '''Intersection testing using DeMorgan's Law'''
    return ( p[0] < b[2] and
             p[0] > b[0] and
             p[1] < b[3] and
             p[1] > b[1] )

Все векторизации, которые я видел, включают скаляры, я не видел ни одного, связанного с функцией, использующей 2 массива.

Answer 1

Вы действительно можете! Как оказалось, у меня возникла точно такая же проблема, и я кодировал решение следующим образом:

def point_is_inside_box(point, bb):
  '''
  point: (x,y) np array of shape Nx2
  bb: (xmin,ymin,xmax,ymax) np array of shape Mx4

  Return: boolean matrix MxN where each column stands for "point n is in box m"
  '''
  # Logic: xmin <= x < xmax and ymin <= y < ymax
  point = point[None,...]
  bb = bb[...,None,:]
  return (bb[...,0] < point[...,0]) & (point[...,0] < bb[...,2]) & (bb[...,1] < point[...,1]) & (point[...,1] < bb[...,3])

По сути, идея заключается в использовании правил вещания numpy. Поскольку входное значение состоит из двух векторов, я добавляю размеры st point, имеющие форму [1,N,2], и bb, имеющие форму [M,1,4]. Таким образом, вещание будет применять операторы < к каждой паре (pt, box) в массивах, получая результат в виде матрицы формы [M,N].

О разрезании:

• ... называется многоточие и эквивалентно столько :, сколько необходимо для заполнения недостающих размеров. Вы можете думать об этом как о сокращении «взять все из всех других измерений, которые я здесь явно не заявляю». Так, например, если point имеет форму [42,2], я могу выбрать все значения x с помощью point[:,0] или point[...,0]. Однако, если point имеет форму [42,1,2], второй оператор будет все еще выбирать все значения x, в то время как первый оператор не будет работать (его нужно изменить на point[:,:,0])

• None эквивалентно np.newaxis. Я в основном говорю numpy вставить новое измерение в эту указанную c позицию. Можно утверждать, что использование np.newaxis вместо None более читабельно. И они были бы правы.

Об использовании памяти:

Предполагается, что при добавлении дополнительных измерений в массив копий не происходит (не уверен, что случай, но я предполагаю, что это не так), вам понадобится дополнительная память для N*M логических значений, которые могут стать значительными, если у вас много точек и блоков. В этом случае, учитывая вероятную сильную разреженность выходной матрицы, может быть интересно попробовать использовать разреженные матрицы scipy , сохраняя структуру кода одинаковой. Понятия не имею, сработает ли это, или же это эффективно.

Answer 2

import numpy as np

points = np.array(
    [[10, 12],
    [22, 24],
    [5, 10]]
)

boxes = np.array(
    [[0, 0, 100, 100],
    [15, 20, 50, 30],
    [4, 9, 6, 11]]
)

result = (points[:,:1] > boxes[:,0]) * \
         (points[:,:1] < boxes[:,2]) * \
         (points[:,1:] > boxes[:,1]) * \
         (points[:,1:] < boxes[:,3])

результат:

array([[ True, False, False],
       [ True,  True, False],
       [ True, False,  True]])

результат [p] [b] равен True, если точка p находится внутри поля b

Answer 3

def intersect2D(p: np.ndarray, b: np.ndarray) -> np.ndarray:
    '''Intersection testing using DeMorgan's Law'''
    return np.logical_and(
         np.logical_and(p[:, 0] < b[:, 2], p[:, 0] > b[:, 0]),
         np.logical_and(p[:, 1] < b[:, 3], p[:, 1] > b[:, 1])
    )