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

Question

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

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

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

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

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

Answer 1

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

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

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

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