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

Question

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

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

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

Answer 1

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

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

Answer 2

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

Answer 3

Что вы делаете, называется Nearest neighbor search и имеет запись Википедии, описывающая методы используют для расчета Это. Я думаю, что это хорошее начало, как Сложности для каждого метода состояние, так что вы можете измерить сложность в отношении, как, каким образом реализация будет :)

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

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