Я хочу быстро (скажем, ‹1 мс) выполнить поиск ближайшего соседа по квадранту.
Ввод каждого поиска:
- фиксированный набор точек в 2D-пространстве (черные точки на изображении). Это остается постоянным при поиске, поэтому его можно сохранить в эффективной структуре данных. Количество баллов от 1 до 1000.
- точка, расположение которой различается для каждого поиска (красная точка на изображении). Абстрактно это делит 2D-пространство на 4 квадранта (разделенных красными линиями на изображении), очень похоже на начало координат в декартовых координатах.
Результат каждого поиска:
- черная точка из каждого красного квадранта, ближайшая (обведена синим на изображении) к красной точке.
На выходе обычно должно быть 4 точки, по одной из каждого квадранта. Но есть несколько возможных крайних случаев:
- квадрант, чтобы не было черных точек; не набрать очков за этот квадрант
- квадрант имеет несколько связей; собрать все такие точки для этого квадранта
- одна и та же точка лежит на границах (красные линии) квадрантов: не собирайте эту точку более одного раза
Вещи, которые я знаю, не будут работать:
- ближайшая точка только по одной оси, скажем, x, может быть очень далеко (обведена зеленым на изображении)
- вторая ближайшая точка в квадранте (обведена фиолетовым на изображении) может быть ближе, чем точки в других квадрантах. Простой поиск 4 ближайших соседей красной точки найдет эту точку, которую я не хочу.
РЕДАКТИРОВАТЬ: версия принятого кода ответа и тайминги
def trial1(quadneighbori,
printout = False, seedN = None, Npts = 1000, Niter = 1000):
if seedN != None: np.random.seed(seedN) # random seed
# Generate Npts (x,y) coordinates where x and y are standard normal
dataset = np.random.randn(Npts,2)
for n in range(Niter):
# Generate random pixel (x,y) coordinates where x and y are standard normal
red = np.random.randn(1,2)
dst, i = quadneighbori(dataset, red)
if printout: print(dst, i)
def quadneighbor1(dataset, red):
dst = np.zeros(4)
closest = np.zeros((4,2))
# Work out a Boolean mask for the 4 quadrants
right_exclu = dataset[:,0] > red[0,0]
top_exclu = dataset[:,1] > red[0,1]
Q1 = np.logical_and( top_exclu, right_exclu)
Q2 = np.logical_and(~top_exclu, right_exclu)
Q3 = np.logical_and(~top_exclu,~right_exclu)
Q4 = np.logical_and( top_exclu,~right_exclu)
Qs = [Q1, Q2, Q3, Q4]
for Qi in range(4):
# Boolean mask to select points in this quadrant
thisQuad = dataset[Qs[Qi]]
if len(thisQuad)==0: continue # if no points, move on to next quadrant
# Calculate distance of each point in dataset to red point
distances = cdist(thisQuad, red, 'sqeuclidean')
# Choose nearest
idx = np.argmin(distances)
dst[Qi] = distances[idx]
closest[Qi] = thisQuad[idx]
return dst, closest
# numba turns 1.53s trial1 to 4.12ms trial1
@nb.jit(nopython=True, fastmath=True)
def quadneighbor2(dataset, red):
redX, redY = red[0,0], red[0,1]
# Distance to and index of nearest point in each quadrant
dst = np.zeros(4) + 1.0e308 # Start large! Update with something smaller later
idx = np.zeros(4, dtype=np.uint32)
for i in nb.prange(dataset.shape[0]):
# Get this point's x,y
x, y = dataset[i,0], dataset[i,1]
# Get quadrant of this point (minus 1)
if x>redX:
if y>redY:
Qi = 0
else:
Qi = 1
else:
if y>redY:
Qi = 3
else:
Qi = 2
# Get distance (squared) of this point - square root is slow and unnecessary
d = (x-redX)*(x-redX) + (y-redY)*(y-redY)
# Update if nearest
if d<dst[Qi]:
dst[Qi] = d
idx[Qi] = i
return dst, idx
%timeit trial1(quadneighbor1)
111 ms ± 3.21 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit trial1(quadneighbor2)
4.12 ms ± 79.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
PS: cdist несовместимо с numba, но изменение строки для удаления cdist и добавления @nb.jit к quadneighbor1 ускоряет trial1(quadneighbor1) со 111 мс до 30,1 мс.
