Как рассчитать расстояние между двумя точками в Android FAST для МНОГИХ точек

Question

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

Меня не волнует прецессия, и точки находятся на расстоянии не более 25 км.

Есть ли другая формула, которую я могу использовать?

Answer 1

Во-первых, для предметов, которые находятся близко друг к другу, кривизна Земли не будет иметь большого значения. Следовательно, вы можете рассматривать его как плоскость, и в этот момент вы смотрите на теорему Пифагора для расстояния (квадратный корень из суммы квадратов расстояний x / y).

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

В-третьих, вы не указываете систему координат, которую используете для точек, но если вы можете выполнять свои вычисления с использованием математики с фиксированной точкой, это также повысит производительность, особенно на устройствах без сопроцессора. Вот почему надстройка Google Maps для Android использует GeoPoint и микродеграды, а не * double градусы Java в Location, которые вы получаете от LocationManager.

Answer 2

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

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

• Формула расстояния : с учетом двух точек (x1, y1) и (x2, y2) расстояниямежду этими точками задается формулой: http://www.purplemath.com/modules/distform.htm

Расстояние = sqrt ((x2 - x1) ^ 2 + (y2 - y1) ^ 2)

Обновление с правильными обозначениями:

double distance = Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));

Answer 3

До тех пор, пока вам не нужно справляться с опросами, и приближение приемлемо, для группировки это должно быть.Затем вы можете рассчитать относительное масштабирование между градусами широты и долготы всего один раз и использовать его для каждого прямого вычисления X в квадрате + y в квадрате, для относительных расстояний вы можете пропустить квадратный корень.

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

(lattitude diference for two points) * 1/cos(latitude)

Вы работаете с 1/cos(latitude) только один раздля всех точек, предполагая, что широта не сильно меняется в вашем наборе выборок.

Answer 4

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

Действительно стоит учиться, очень хорошо оптимизирует работу.