Эффективное нахождение ближайшей точки вдоль определенной оси в трехмерном пространстве - PullRequest
Новая
       7

Эффективное нахождение ближайшей точки вдоль определенной оси в трехмерном пространстве

1 голос
/ 20 марта 2012

Я играю с этим уже несколько дней и продолжаю сталкиваться со стенами производительности.

Данные:

  • от 10 до сотен тысяч точек 3D
  • Точки представляют собой положительные / отрицательные значения и падают на трехмерную сетку без наложения
  • редко будет добавлять новые очки
  • Обычно будет без зазоров, но пробелы возможны

Структура:

  • Должен быть в состоянии эффективно найти ближайших соседей по каждой оси («ближайшая точка слева») и только по этой оси.
  • Редко обрабатывает вставки или удаления после построения (но должен обрабатывать их)
  • Не нужно обрабатывать точки перекрытия

Я нашел возможное решение в http://docs.scipy.org/doc/scipy/reference/spatial.html,, однако дерево K-d представляется чрезвычайно расточительным для данных этого типа (более подходящим для кластеров произвольных точек) и настроенных для поиска точек в радиусе. Основным вариантом использования этих данных часто является нахождение (и отслеживание) ближайшей соседней точки вдоль каждой.

Пример данных (x, y, z): 

[(4, 3, 0), (4, 4, 0), (5, 3, 0), (3, 3, 0), (4, 3, 1), ...]

Возможно, мой гугл-фу подводит меня, и оптимальная структура уже существует (предпочтительно в Python), но я не смог ее найти.

Ответы [ 3 ]

3 голосов
/ 20 марта 2012

Как насчет построения 3 KD-деревьев для осей x, y, z соответственно?В любом случае, вам нужна какая-то древовидная структура.

0 голосов
/ 20 марта 2012

Если только точки считаются ближайшими, если они следуют за осью со значениями другой оси, например, статическими. что (1,1,0) не будет квалифицироваться как ближайшее к (0,0,0), но (4,0,0) вы могли бы: 

import numpy as np
#The .T is ofcourse not neccesary here but then you have to fix it below as well.
points = np.asarray( [(4, 3, 0), (4, 4, 0), (5, 3, 0), (3, 3, 0), (4, 3, 1)]).T
#You have still to check thiss for all points just showing for pt 0
on_same_xy = (points[:-1,:].T == points[:-1,0]).all(axis=1)

z_distance =  (points[2,on_same_xy] - points[2,0])
z_distance_up = z_distance[np.where(z_distance > 0)]
if z_distance_up.size == 0:
    up = None
else:
    up = z_distance_up.min()

z_distance_down = z_distance[np.where(z_distance < 0)]
if z_distance_down.size == 0:
    down = None
else:
    down = z_distance_down.max()

print "Z-up-neighbour %s, Z-down-neighbour %s" % (str(up), str(down))

Поскольку у вас есть два первых значения координат только для точек [-1,0], то положение точки вверх и вниз, а также расстояние можно получить сверху и снизу.

Я понимаю, что код немного запутался, но как только большой набор данных оказывается внутри nunpy, он действительно должен работать быстрее. Кроме того, опять же, вопрос в том, о чем просит ваш вопрос.

0 голосов
/ 20 марта 2012

Хм, поиск «ближе к левому» и все такое может оказаться сложным, так как вы говорите несколько точек на х = 4, тогда ему нужно будет найти замыкания на других осях.

Не сработает ли более простая "ближайшая точка", такая как следующая? 

for n in xrange(len(points)):
   diff = (((x0-points.x[n])**2) + ((y0-points.y[n])**2) + ((z0-points.z[n])**2))**0.5

Затем просто отсеиваем 'n' с наименьшей разницей (исключая текущую точку, если включена) ..: /

...