Быстрые точки в круговом тесте с numpy

Question

У меня есть большое количество точек сетки (x,y) с целыми координатами, которые я хочу проверить, если они находятся в небольшом количестве окружностей, заданных радиусом и центром. Точками являются некоторые заметные части изображения, а это означает, что имеется небольшое количество блоков неправильной формы, которые содержат точки. Там я хочу проверить наличие столкновений и подсчитать количество точек внутри круга. Мои текущие подходы довольно медленные (с python и numpy).

Теперь у меня есть две задачи:

1. испытание, если любая точка множества А в любом круге
2. Подсчитайте число точек множества В, которые находятся в кругу

Моя текущая реализация выглядит следующим образом (setA и setB являются Nx2 Numpy массивов и center является 1x2 массивом.):

1) Для каждого круга создать массив point - center, квадрат его поэлементно и взять сумму, а затем проверить, если он меньше, чем radius**2

for circle in circles: 
    if (((setA - circle.center)**2).sum(axis=1) < circle.radius**2).any(): 
     return "collision" 
return "no collision" 

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

2) Для каждого круга создайте массив расстояний и выполните проверку по методу, меньшему, чем радиус. Добавьте все массивы и подсчитайте ненулевые элементы результата.

pixels = sp.zeros(len(setB)) 
for circle in circles: 
    pixels += (((setB - circle.center)**2).sum(axis=1) < circle.radius**2) 
return np.count_nonzero(pixels) 

Есть ли простой способ ускорить это?

Я не хочу более оптимизировать (и сделать программу намного сложнее), но просто использовать numpy наиболее эффективным способом, используя как можно больше векторизации numpy.

Таким образом, создание самого совершенного пространственного дерева или аналогичного не является моей целью, но я считаю, что алгоритм O (n^2) для нескольких тысяч точек и 10-20 кругов должен быть таким же быстрым способом в среднем настольный компьютер сегодня.

Answer 1

Воспользовавшись координат являются целыми числами:

создать подстановок изображение

radius = max([circle.radius for circle in circles]) 
mask = np.zeros((image.shape[0] + 2*radius, image.shape[1] + 2*radius), dtype=int) 
for circle in circles: 
    center = circle.center + radius 
    mask[center[0]-circle.radius:center[0]+circle.radius + 1, 
     center[1]-circle.radius:center[1]+circle.radius + 1] += circle.mask 

circle.mask небольшая площадь пластырь, содержащий маску диска внутренних точек

подсчета столкновений в настоящее время, как легко, как

mask[radius:-radius, radius:-radius][setB[:,0], setB[:,1]].sum() 

быстрого создания дисков (без умножений, не квадратных корней):

r = circle.radius 
h2 = np.r_[0, np.add.accumulate(np.arange(1, 2*r+1, 2))] 
w = np.searchsorted(h2[-1] - h2[::-1], h2) 
q = np.zeros(((r+1), (r+1)), dtype=int) 
q[np.arange(r+1), w[::-1]] = 1 
q[1:, 0] -= 1 
q = np.add.accumulate(q.ravel()).reshape(r+1, r+1) 
h = np.c_[q, q[:, -2::-1]] 
circle.mask = np.r_[h, h[-2::-1]]