Эффективный поиск точек в каждом пикселе с помощью Python

Question

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

У меня также есть очень длинный список случайно распределенных 2D точек. Я ищу эффективный способ найти индексы точек, присутствующих в каждом пикселе.

На данный момент у меня есть следующее:

import numpy as np
xgrid = np.linspace(0,10,11)
ygrid = np.linspace(0,10,11)

X_random_points = np.random.rand(int(1e7))*10
Y_random_points = np.random.rand(int(1e7))*10

for iterationX in range(0,len(xgrid)-1):
    for iterationY in range(0,len(ygrid)-1):
        valuesInCube = (X_random_points<xgrid[iterationX]) & (X_random_points>xgrid[iterationX-1]) & (Y_random_points<ygrid[iterationY]) &(Y_random_points>ygrid[iterationY-1])  

Мне было интересно, есть ли у кого-нибудь идея, как сделать это быстрее?

Answer 1

Я могу дать вам соответствующий подход, который все еще может быть полезным. Вместо этого вы можете найти, к какому пикселю относится каждая точка. Функции numpy.digitize и scipy.stats.binned_statistic_2d полезны здесь. scipy.stats.binned_statistic_2d кажется немного неуклюжим, поскольку он делает больше, чем просто складывание ваших очков и требует от вас дать некоторые значения для каждого из ваших пунктов x, y.

Следует отметить, что нумерация бункеров начинается с 1 (не 0).

x_p, y_p = np.digitize(X_random_points, xgrid), np.digitize(Y_random_points, xgrid)

# OR #

_, _, _, (x_p, y_p) = scipy.stats.binned_statistic_2d(X_random_points, Y_random_points, np.zeros(len(X_random_points)), bins=(xgrid, ygrid), expand_binnumbers=True)

Для определенного пикселя вы можете даже найти все точки, которые принадлежат этому пикселю из x_p и y_p.

Answer 2

Вы можете использовать np.floor, чтобы векторизовать всю операцию и избежать зацикливания полностью, если расстояние между пикселями равномерно в каждом направлении. Для вашего простого случая, где xgrid и ygrid являются целыми числами, вы можете просто сделать

X_random_points = ...
Y_random_points = ...
x_pixels = np.floor(X_random_points)
y_pixels = np.floor(Y_random_points)

Если ваши пиксели не находятся на целочисленной сетке, вы должны знать расстояние между ними. В этом случае я бы порекомендовал использовать np.arange вместо np.linspace для создания местоположения пикселей:

delta_x, delta_y = 0.5, 0.5
xgrid = np.arange(0, 5.1, delta_x)
ygrid = np.arange(0, 5.1, delta_y)

X_random_points = np.random.rand(int(1e7)) * 5
Y_random_points = np.random.rand(int(1e7)) * 5

x_pixels = np.floor(X_random_points / delta_x)
y_pixels = np.floor(Y_random_points / delta_y)

Вы действительно делаете то же самое для целочисленного случая, так как оба delta_x и delta_y оба равны 1.