Какой эффективный способ расчета ближайшей точки?

Question

У меня есть объекты с данными о местоположении, хранящимися в Базовых данных, я хотел бы иметь возможность выбирать и отображать только ближайшую точку к текущему местоположению. Я знаю, что есть формулы, которые вычисляют расстояние от текущего широты / долготы до сохраненного широты / долготы, но мне интересно, как лучше всего это сделать для набора из 1000+ точек, хранящихся в Базовых данных. Я знаю, что мог бы просто вернуть точки из Базовых данных в массив, а затем пройтись по циклу, ища минимальное значение для расстояния между точками, но я думаю, что есть более эффективный метод, возможно, использующий Базовые данные в некотором роде. *

Любое понимание будет оценено.

EDIT: Я не знаю, как я пропустил это при моем первоначальном поиске, но этот вопрос SO предлагает просто выполнить итерацию массива объектов Core Data, но ограничить размер массива ограничительной рамкой на основе текущего местоположения. Это лучшее, что я могу сделать?

Answer 1

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

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

Answer 2

Я не так много знаю о базовых данных, но есть хорошо известные алгоритмы, такие как Quadtree для решения этой проблемы

Answer 3

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

Самое простое решение для NNS проблема в том, чтобы вычислить расстояние от точки запроса к каждому другому указать в базе данных, отслеживая из "лучших пока". Этот алгоритм, иногда называют наивным подход, имеет время работы O (Nd)

Локальное чувствительное хеширование (LSH) является методика группировки точек в пространстве в «ведра» на основе некоторого расстояния метрика, работающая по точкам. Точки которые находятся рядом друг с другом под выбранные метрики сопоставляются с тем же ведро с высокой вероятностью