Вычисление расстояния между двумя координатами X, Y в PHP

Question

Я пишу инструмент для игры, который включает в себя вычисление расстояния между двумя координатами на тороидальной плоскости шириной 500 единиц. Таким образом, [0,0] - [499,499] являются действительными координатами, а [0,0] и [499,499] также находятся рядом друг с другом.

В настоящее время в моем приложении я сравниваю расстояние между городами с местоположением [X, Y], соответствующим местоположению [X, Y] пользователя, которое они предварительно настроили.

Для этого я нашел этот алгоритм, который работает:

Math.sqrt ( dx * dx + dy * dy );

Поскольку сортировка перемещаемого списка по расстоянию полезна для выполнения, я реализовал этот алгоритм в запросе MySQL и сделал его доступным для моего приложения, используя следующую часть моего оператора SELECT:

SQRT( POW( ( ".strval($sourceX)." - cityX ) , 2 ) + POW( ( ".strval($sourceY)." - cityY ) , 2 ) ) AS distance

Это прекрасно работает для многих вычислений, но не принимает во внимание тот факт, что [0,0] и [499,499] расположены друг на друге.

Можно ли каким-либо образом настроить этот алгоритм для получения точного расстояния, учитывая, что 0 и 499 находятся рядом?

Answer 1

Полагаю, вы имеете в виду координаты обтекания и ничего сферической формы. Как плоский лист бумаги, где концы магически связаны друг с другом.

Это означает, что для карты размером 500x500 расстояние в направлении x (или y) составляет не более 250. (Если бы это было больше 250 шагов, мы могли бы лучше пройти 500-x шагов назад.)

Простой способ исправить это, будет

dx = Math.abs(dx);
dy = Math.abs(dy);
if (dx > 250)
  dx = 500 - dx;
if (dy > 250)
  dy = 500 - dy;
distance = Math.sqrt ( dx * dx + dy * dy );

Answer 2

Обновление (тор):

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

Для этого ответ довольно прост - картезианская формула, которую вы даете, более или менее верна. Однако вам нужно обернуть расстояния так, чтобы все, что больше или равно 250 = 500/2, было переведено в число от 0 до 250.

Так что ответ примерно такой (я вообще не знаю PHP, поэтому, возможно, потребуется изменить синтаксис)

dx1 = min(dx, 500-dx)
dy1 = min(dy, 500-dy);
distance = Math.sqrt(dx1*dx1 + dy1*dy1);

(Предполагается, что вы определили dx и dy как абсолютную величину различий.)

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

Оригинальный ответ (сфера):

Вы не объяснили, как ваши (x, y) координаты отображаются на точки на сфере!

Существует (буквально) бесконечное количество вариантов, каждый из которых соответствует отдельной проекции карты , и формула для каждого из них различна. Обратите внимание, что независимо от того, какой выбор вы сделаете, значение этих двух координат очень разное.

Если ваши (x, y) действительно долгота и широта, например, существует множество консервативных формул (например, haversine), но вам придется сначала перевести 0-> 499 в 0-> 360 градусов для долготы и -90-> 90 градусов по широте. (Обратите внимание, что lon и lat ведут себя по-разному на сфере!)

Но я подчеркиваю, что любой выбор , который вы сделаете, будет искажать плоскую геометрию, которую вы получите, если вы нанесете на график (x, y), а не то, как она действительно выглядит на сфере.

(Наконец, если вы действительно имеете в виду, что верхний край такой же, как нижний, а правый такой же, как левый, то у вас, вероятно, есть тор, а не сфера!)

Answer 3

Звучит так, будто вы просто используете специальное конечное декартово пространство, которое «выложено плиткой».В этом случае каждый объект не имеет уникальной позиции.Вместо (x, y) это (x + i * w, y + j * h) для всех возможных целочисленных значений i и j, где w и h - ширина и высота вашего "окна" соответственно.

Очевидно, что расстояние не является уникальным, но минимальное расстояние составляет всего лишь min (d (p1, p2))) для всех i, j.

Если ваши координаты перенесены, вам просто нужно вычислить их для i = -1,0,1 и j = -1,0,1, а затем взять наименьшую.

Answer 4

Если вы знаете широту и долготу двух точек - вы можете использовать формула haversine для вычисления расстояния между двумя точками на сфере.

Но, как я понял, вы хотите формулу, которая точна для почти антиподальных точек. Формула Haversine не работает здесь. В таком случае вам нужна формула Винсенти , которая точна даже в антиподальных случаях.

http://en.wikipedia.org/wiki/Great-circle_distance#Formulae

Answer 5

Я пишу ответ, если две координаты находятся в 2-мерной плоскости, где концы не встречаются друг с другом, о которых OP не спрашивал.Но это может помочь кому-то в будущем.

Если ваши точки находятся в двухмерной плоскости, расстояние между точками (x1, y1) и (x2, y2) определяется теоремой Пифагора :

d = squareroot( square(x2 - x1) + square(y2 - y1) )

В PHP

$x1 = $y1 = 2;
$x2 = $y2 = 5;
$distance = sqrt( pow(($x2-$x1),2) + pow(($y2-$y1),2) );
echo $distance;              // 4.2426406871193

Answer 6

Хотя некоторые ответы здесь были очень близки, проблема была окончательно решена с помощью этого сегмента SELECT:

SQRT( POW( LEAST( ABS($sourceXstr-cityX), ( 500 +LEAST($sourceXstr,cityX)-GREATEST($sourceXstr,cityX))) , 2 ) + POW( LEAST( ABS($sourceYstr-cityY), ( 500 +LEAST($sourceYstr,cityY)-GREATEST($sourceYstr,cityY))) , 2 ) ) AS distance

Answer 7

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

Я думаю, что лучший подход будет основан на широте и долготе, например:

http://jan.ucc.nau.edu/~cvm/latlongdist.html

В MySQL встроено геокодирование. Почему бы не использовать это?

http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL