поиск и сортировка по огромному массиву широты и долготы

Question

, поэтому у меня есть массив широты / долготы (это ложная широта / долгота, как вы можете видеть, но только для иллюстрации точки, и исходный размер массива НАМНОГО больше этого):

<?php
$my_nodes = array(
1=> array(273078.139,353257.444),
2=> array(273122.77,352868.571),
3=> array(272963.687,353782.863),
4=> array(273949.566,353370.127),
5=> array(274006.13,352910.551),
6=> array(273877.095,353829.704),
7=> array(271961.898,353388.245),
8=> array(272839.07,354303.863),
9=> array(273869.141,354417.432),
10=> array(273207.173,351797.405),
11=> array(274817.901,353466.462),
12=> array(274862.533,352958.718),
13=> array(272034.812,351852.642),
14=> array(274128.978,354676.828),
15=> array(271950.85,354370.149),
16=> array(275087.902,353883.617),
17=> array(275545.711,352969.325)));

?>

Я хочу иметь возможность найти ближайший узел (в данном случае это узел 1,2,3, 4,5, ...) для заданной широты X и широты Y. Я знаю, что самый простой способ сделать этосделать цикл for, а затем сделать разницу погрешности (abs (latitude_X - latitude_X_array) + abs (latitude_Y - latitude_Y_array)), но это будет очень неэффективно по мере увеличения размера массива.

Я думал о выполнении бинарного поиска, однако массив должен быть отсортирован первым в бинарном поиске, однако трудно отсортировать широту / долготу, и в конце мы находим CLOSEST широту / долготу вмассив для заданного широты X, длинны Y. Какой подход я должен использовать здесь?

ОБНОВЛЕНИЕ:

Марк имеет правильную точку, эти данные могут быть сохранены в базе данных.Однако, как я могу получить такую ​​информацию из БД, если я хочу ближайшую?

Answer 1

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

Answer 2

Чтобы отсортировать многомерный массив в PHP, вам придется перебирать все элементы и сравнивать по два за раз.Для массива размера n, который делает O (n) сравнений.Для нахождения ближайшего узла в отсортированном массиве необходимо вычислить расстояние O (log n).
Если вы выполните итерацию по всем элементам, вычислите расстояние до целевого узла и запомните ближайший элемент, вам будет достаточно O (n)расчеты расстояния.
Предполагая, что сравнение двух узлов означает сравнение значений широты и долготы и, следовательно, O (2), и далее, предполагая, что вычисление расстояния между двумя узлами равно O (3), вы заканчиваете
O(2n + 3 log n) для бинарного поиска и O (3n) для наивного поиска.
Таким образом, двоичный поиск занимает n - 3 log n меньше операций и выполняется примерно на 33% быстрее.

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

Answer 3

Я предполагаю, что вы храните свои данные в таблице БД, как эта?

id | lat   | long   | data
------------------------------------------------
1 | 123.45 | 234.56 | A description of the item
2 | 111.11 | 222.22 | A description of another item

В этом случае вы можете использовать SQL, чтобы сузить набор результатов.

Если вы хотите найти элементы, близкие к сетке с номером 20,40, вы можете выполнить следующий запрос:

SELECT * 
FROM locations
WHERE lat BETWEEN 19 AND 21
AND long BETWEEN 39 AND 41

Это вернет все таймы в сетке 2x2 рядом с указанной сеткой.ссылка

Некоторые базы данных также предоставляют пространственные типы данных (как MySQL, так и Postgres), и их, возможно, стоит изучить для этой работы.У меня, однако, нет опыта с такими вещами, поэтому я боюсь, что не смогу помочь с этим.

Answer 4

У меня была похожая проблема, когда я хотел повторно сэмплировать большое количество точек широты / долготы для создания сетки полей высоты. Самый простой способ, который я нашел, был таким:

1. разделите лат / длинное пространство на регулярную сетку
2. создать корзину для каждого квадрата сетки
3. пройти по списку, добавив каждую точку в корзину для квадрата сетки, она попадает в
4. затем найдите квадрат сетки вашей точки X, точка Y падает и оттуда ищите наружу