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

Question

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

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

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

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

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

Answer 1

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

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

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

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