Поиск ближайших точек в многомерном пространстве.

Отсортировать по одной из координат

Другой вариант это kd-tree

вычислить расстояние до каждой точки

отсортировать

выбрать нужные

Сортировать даже не обязательно, зависит от задачи. Можно просто отфильтровать.

А если точки меняются, и результат нужно получать часто, то их можно хранить в sorted set

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

Есть такой метод, не знаю как называется правильно: допустим есть X и Y координаты. X в бинарном представлении: xn*2^n...x3*2^3, x2*2^2, x1*2^1, x0*2^0. Тогда можно координаты побитно объединить: xn, yn... x3, y3, x2, y2, x1, y1, x0, y0. И отсортировать по этому числу. Тогда регион для перебора сужается. Но это на плоскости или в кубе куда ещё ни шло. А если размерностей много — не вариант.

а) считать расстояние - не долго, просто формула; б) какой-бы хитрожопый алгоритм ты не придумал - все равно рассмотришь все точки, иначе ты откуда узнаешь где они вообще находятся.

Почему нельзя отфильтровать?

Вычислить расстояние до каждой точки - N.

Сортировать ~ N log(N).

Быстрее чем N не бывает.

Ну вообще-то поиск ближайших для заданной точки — это только часть алгоритма. И её повторять для заданного набора точек нужно многократно, для каждой точки вообще. Для каждой точки нужно найти ближайшие к ней и выполнить вычисления. И так для всего набора.

Если совсем далеко заходить, то нужно что-то попроще чем БПФ или АКФ в задаче определения периода для некого периодического сигнала. Считать переходы через 0 не вариант, сигнал сильно зашумлён.

на ЛОРе уже много раз обсасывалось. Воспользуйся поиском.

Сколько будет точек? Как часто проверять ближайших?

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

Отсортировать по одной координате (Х например) это O(N*log(N)). А дальше ты бинарным поиском за время log(N) находишь точку и за время O(хз какое) просматриваешь дельта-окрестность по Х-координате. Отбрасываешь расположенные далеко и получаешь список.

kd-tree посмотрел?

BSP?

И на чем экономим? На формуле расстояния?

kd-tree

плюсую.

kd-tree http://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search

если количество пространственных измерений велико (больше 3-4), то имеет смысл посмотреть R-tree вместо k-d.

Есть куча деревей: R с модификациями, M, kd, octree. Возьми то, которое подходит и фигачь

Google spatial data structures

Так вычислять расстояние нужно для каждой с каждой n! получается. Сортировка лучше

1) Сначала было непонятно, что повторяется многократно - кривая формулировка; 2) ответ про N; 3) постом ниже уточняют что многократно; 4) твой вброс.

Объяснить почему последний неконструктивен?

// другой анонимус

В школу!

К тому же \rho(a,b) = \rho(b,a)

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

ещё гугль

http://en.wikipedia.org/wiki/Nearest_neighbor_search

http://en.m.wikipedia.org/wiki/List_of_data_structures#section_3

так при n! мы и не рассматриваем ab и ba.

А как точки распределены? Если бол-мен равномерно, то вводите равномерную d-мерную сетку с шагом половина от расстояния отсечки, распределяете по ней точки, и дальше смотрите ячейки ближайшие к данной (это боян, см. слой Верле в молек. динамике).

Если точки распределены не равномерно, то некоторые ячейки этой сетки откажутся пустыми. Если таких ячеек много, получаем разреженный массив. Проще всего для хранения использовать std::map - в качестве ключа D целых чисел (индекс ячейки в D-мерном пр-ве), в качестве значения содержимое ячейки. Ключи сортируются сначала по одной координате, потом по другой и пр - в общем пишете структуру для ключа и определяете оператор < (я про С++, на других ЯП тоже как то так можно). При распределении частиц по ячейкам индекс ячейки находится сразу, если знать координаты нулевого узла и шаг сетки. По скорости поиска это то же самое что всякие деревья, только даже лучше - реализуется проще, а работать будет быстрее чем d-дерево;-)

ман квадро окто и далее деревья

задача для n точек в mмерии

n*n

ю мин

Ха, ну да, складываем же, а не умножаем. Ошибся я, но так или иначе не n, при переборе и не нужно им решать

это было бы так, если бы надо было искать просто ближайшие точки, а не точки лежащие ближе чем фикс. расстояние.

И на чем экономим? На формуле расстояния?

Экономим на том, что не пересчитываем массив расстояний и не сортируем его каждый раз, когда нам нужно найти окружение другой точки в том же массиве.

И массив еще может быть динамическим, но это уже маленько другая история.

А для однократного поиска, да, подходит любой способ, если количество размерностей невелико.

Это из той серии задача, что и сортировка выбором. Что и с использованием аксиомы симметрии, что и без, там квадрат)

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

Закинь все множество точек в таблицу COORD БД . Каждая точка при этом получит уникальный идентификатор P_ID (point ID). Построй индексы по P_ID и по каждой из координат (X,Y,Z,...).

Далее, есть точка A0(X0,Y0,Z0,...) и расстояние R0, найти все точки внутри сферы с центром в A0 и радиусом R0.

Очевидно, что быстрее и проще найти куб, которого касается сфера.

X0-R0 <= X <= X0+R0
Y0-R0 <= Y <= Y0+R0
Z0-R0 <= Z <= Z0+R0
...

select P_ID from 
 (select P_ID from 
   (select P_ID from 
     (select P_ID from  COORD  where Z between (Z0-R0) and (Z0+R0)) CZ
    where Y between (Y0-R0) and (Y0+R0)) CY
  where X between (X0-R0) and (X0+R0)) CX

Если результат недостаточно точен, то можно:
1. (точно) из всех полученных P_ID выбрать те, для которых R=SQRT(X^2+Y^2+Z^2+...) <= R0
2. (не точно) задать некий Rd0=0.9*R0 (0.9 - коэфф. ошибки подобия) и считать, что куб

     X0-Rd0 <= X <= X0+Rd0
     Y0-Rd0 <= Y <= Y0+Rd0
     Z0-Rd0 <= Z <= Z0+Rd0
     ...

гы

select P_ID,X,Y,Z from 
 (select P_ID,X,Y,Z from 
   (select P_ID,X,Y,Z from 
     (select P_ID,X,Y,Z from  COORD  where Z between (Z0-R0) and (Z0+R0)) CZ
    where Y between (Y0-R0) and (Y0+R0)) CY
  where X between (X0-R0) and (X0+R0)) CX

А можно сделать изврат по сокращению потребления памяти в подзапросах:

select P_ID from 
 (select P_ID,X from 
   (select P_ID,X,Y from 
     (select P_ID,X,Y,Z from  COORD  where Z between (Z0-R0) and (Z0+R0)) CZ
    where Y between (Y0-R0) and (Y0+R0)) CY
  where X between (X0-R0) and (X0+R0)) CX

select P_ID from 
  (select P_ID,X from 
     (select P_ID,X,Y from  COORD  where Z between (Z0-R0) and (Z0+R0)) CZ
   where Y between (Y0-R0) and (Y0+R0)) CY
where X between (X0-R0) and (X0+R0)

Ну вообще-то поиск ближайших для заданной точки — это только часть алгоритма. И её повторять для заданного набора точек нужно многократно, для каждой точки вообще. Для каждой точки нужно найти ближайшие к ней и выполнить вычисления. И так для всего набора.

А я бы ввёл понятие региона пространства Region(Realm_ID,Region_ID,Xmin,Xmax,Ymin,Ymax,Zmin,Zmax), с характерным размером Rr. И заставил бы каждую точку при insert или update определять Realm_ID своего реалма и Region_ID региона. Завёл бы таблицу смежности регионов RegionLinks. Тогда, в случае 3D пространства и без телепортов, имеем 27 соседних регионов, которыми можно значительно сократить выборку, как при определении соседних точек, так и при определении своего нового региона - местоположения при перемещении.

Регионы можно объединить в реалмы Realms(Realm_ID,Description), по которым можно уже партиционировать таблицы. Таблицу смежности реалмов - по вкусу. К примеру, выделить плотные скопления точек и пустующие пространства в отдельные реалмы.

При массированной вставке будет тормозить «не по децки», но при рассчёте для каждой точки - выгоды прогнозируемы.

...только смежность региона с самим собой при выборках не забудь, please.