Лучший алгоритм для сравнения базовой координаты со списком из n координат и определения ближайших m координат?

Question

У меня есть код, который делает это прямо сейчас.Он отлично работает со списками малого и среднего размера, но когда у меня есть список размером n> 5000, мой алгоритм может занять почти 1 минуту на мобильном устройстве для запуска.Я в основном сравниваю объект Coordinate в Java со списком (Vector) объектов Coordinate.

Вот мой основной алгоритм:

• Обход каждого элемента в списке nx
• если в списке "10 ближайших" меньше 10 элементов, добавьте nx к списку и перейдите к следующему элементу
• , если в списке "10 ближайших" уже есть 10 элементов, рассчитайте расстояниемежду nx и базовыми координатами
• , если расстояние меньше, чем самое дальнее расстояние в «10 ближайших списках», затем удалите самый дальний элемент из этого списка и замените его на nx

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

Вот мой метод расчета расстояния:

public static double distance(double lat1, double lon1, double lat2, double lon2, char unit) {

  double theta = lon1 - lon2;

  double dist = Math.sin(deg2rad(lat1)) * Math.sin(deg2rad(lat2)) + Math.cos(deg2rad(lat1)) * Math.cos(deg2rad(lat2)) * Math.cos(deg2rad(theta));

  dist = acos(dist);

  dist = rad2deg(dist);

  dist = dist * 60 * 1.1515;

  if (unit == 'K') {

    dist = dist * 1.609344;

  } else if (unit == 'N') {

    dist = dist * 0.8684;

    }

  return (dist);

}

Answer 1

Вы можете хранить свои координаты в некотором дереве разделов пространства .

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

Редактировать: Чтобы сравнить расстояния, которые вы могли бы предварительно вычислить трехмерные координаты на сфере и использовать квадрат евклидова расстояния в сравнениях:

dx * dx + dy * dy + dz * dz

Answer 2

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

На веб-сайте показано, как вычислить координаты широты и долготы для точки и заданного расстояния. Это не совсем та же проблема, что у вас есть, но она может служить фильтром. В вашем случае вы, очевидно, пытаетесь найти 10 (или n) ближайших точек к данной точке. Вы можете применить следующий алгоритм, чтобы найти 10 (или n) ближайших точек:

Для первых n очков вы могли бы пройти полномасштабное расстояние расчет, который вы имеете, сохраняя расстояние вдоль каждой точки.

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

Продолжайте до конца ваших пунктов.

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

Откажитесь от самого дальнего из предыдущего набора из 10 «ближайших» точек.

Пересчитать ограничивающий прямоугольник lat, lon, основываясь на новой самой дальней точке.

Повторяйте, пока не обработаны все точки.

Преимущество этого подхода заключается в том, что вы можете избежать тяжелых вычислений для большого количества ваших очков. В зависимости от распределения ваших очков, вы все равно можете страдать от низкой производительности, например, если точки оказываются упорядоченными таким образом, что они находятся на уменьшающемся расстоянии от ваших целевых точек (точка [0] - самая дальняя, а точка [N]). ближайший)).

Answer 3

Ну, может быть, было бы быстрее сделать это с массивами.И вы можете сравнить квадрат расстояния вместо расстояния, что означает, что вам не нужно работать с квадратными корнями.

Было бы хорошо иметь действительный код.