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

Я ищу алгоритм, который может выполнять эффективный поиск в сетке.

У меня есть большой массив, который включает в себя все центральные точки (x, y, z)

Теперь для данного местоположения (xp, yp, zp) я хочу найти ближайший центроид к этому местоположению p.

В настоящее время я выполняю поиск грубой силы, который в основном для каждой точки p я просматриваю все точки, вычисляю расстояние до местоположения p и таким образом узнаю, какой это центроид.

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


search kdtree binary-search-tree octree
person A2LBK    schedule 13.12.2018    source источник
comment
Не могли бы вы объяснить, что вы подразумеваете под неструктурированной сеткой и для чего она вам нужна? Может быть, вам не нужны никакие сетки, похоже, вы можете поместить все центроиды в kd-дерево или октодерево, а затем выполнить поиск ближайшего соседа (xp, yp, zp), чтобы найти ближайший центроид?   -  person TilmannZ    schedule 13.12.2018
comment
@TilmannZ это неструктурированная сетка, в которой евклидово пространство дискретизировано нерегулярным образом. Следовательно, для понимания сетки требуется какая-то информация о топологии. Но да, ты прав. Мы можем предположить, что у меня есть множество точек-центроидов (x, y, z), и у меня есть множество точек-кандидатов (xp, yp, zp), где мне нужно найти ближайший центроид.   -  person A2LBK    schedule 13.12.2018
comment
Я изменил текст, чтобы никого не спутать термином неструктурированной сетки.   -  person A2LBK    schedule 13.12.2018

Ответы (1)


arrow_upward
0
arrow_downward

Я бы хотел вам пространственный индекс, такой как kd-tree или quadtree/octree (который вы предложили) или, возможно, решение на основе R-Tree.

Поместите все свои центроиды в индекс. Обычно вы можете связать любую точку в индексе с некоторыми дополнительными данными, поэтому, если вам это нужно, вы можете указать обратную ссылку на сетки, например координаты сетки).

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

В некотором смысле дерево квадрантов/октодерево само по себе не что иное, как дискретизирующая сетка, которая становится тоньше, если плотность точек увеличивается. Отличие от сетки в том, что она иерархична и пустые области вообще не сохраняются.

person TilmannZ    schedule 16.12.2018