Нахождение ближайшей точки к данной точке

Question

Я искал все это, но, похоже, не могу найти лучший подход к этому. У меня есть около 22000 лат / долг точек, и я хочу найти ближайший к текущему местоположению iPhone. Я видел, как люди спрашивают о Quad Trees, алгоритме Дейкстры и пространственных базах данных. Какой лучше для iPhone? Пространственные базы данных кажутся самыми простыми, но я не уверен.

РЕДАКТИРОВАТЬ: на самом деле более 20000 очков. Вы думаете, что перебор всех их - это способ сделать это? Но спасибо за ваш вклад.

Спасибо.

Answer 1

Если вам нужно больше, чем O (N), вы можете получить его, только если сначала заплатите N lg N за построение некоторого пространственного хеша (квадри, октре, хеш-сетку или тому подобное). Тогда каждый тест будет приблизительно равен O (LG N), и, как правило, он может быть намного лучше, если кешировать последнее проверенное местоположение, если есть большая согласованность (как правило, есть).

Я бы, вероятно, построил октре в пространстве Эйлера (геоцентрическое, XYZ), потому что это позволяет мне получить «истинное» расстояние, а не «искаженное» расстояние широта / долгота. Однако на практике квад-дерево в широтном пространстве, вероятно, будет работать достаточно хорошо. Как только у вас есть попадание, вы держитесь за этот узел дерева (при условии, что дерево не перестраивается во время выполнения), и следующий запрос начинает идти с этого узла дерева, и ему нужно беспокоиться только об узлах, которые могут быть ближе, если предыдущий пункт отошел от предыдущего ответа.

Answer 2

На самом деле, лучше всего использовать расчет Haversine (большой круг) для точек широты и долготы, в противном случае все большие расстояния будут неправильными, особенно если вы используете простой триг, как в ответ Джерико .

Быстрый поиск предоставляет этот пример JavaScript:

var R = 6371; // km Radius of earth
var dLat = (lat2-lat1).toRad();
var dLon = (lon2-lon1).toRad(); 
var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
        Math.cos(lat1.toRad()) * Math.cos(lat2.toRad()) * 
        Math.sin(dLon/2) * Math.sin(dLon/2); 
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
var d = R * c;

С точки зрения структуры данных, Geohash стоит посмотреть.

Answer 3

Находясь на iPhone, вы можете использовать CoreLoaction для определения географического расстояния - с помощью CLLocation's – getDistanceFrom:

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

Answer 4

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

Затем, при поиске точек вблизи точки A в гексе X, вам нужно проверять только точки в гексе X и не более 3 соседних гексов.

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

Answer 5

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

так просто, как уже говорил Хаос, вы должны вычислить все расстояния между вашей позицией и всеми 20.000 точками, а затем отсортировать их

Answer 6

Я думаю, что этот алгоритм работает:

Создать массив, отсортированный по широте Создать массив, отсортированный по долготе

Чтобы найти ближайший, сначала найдите ближайший по широте делать бинарный поиск в массиве широты. Сделать то же самое для массива долготы. Теперь у вас есть 2 балла, один ближайший по широте, другой ближайший по долготе. Вычислите расстояния до каждой точки с помощью теоремы Пифагора. Побеждает ближайшая точка.

Роджер