Создание случайных координат вокруг местоположения
Я хотел бы иметь функцию, которая принимает географическое местоположение (широта, долгота) и генерирует случайные множества координат вокруг него, но также принимает эти параметры как часть расчета:
- Число случайных координат для создания
- Радиус генерации в
- Минимальное расстояние между случайными координатами в метрах
- Корневые координаты для создания местоположений вокруг него.
Пример того, как будет генерация:
![Example]()
Какой хороший подход для достижения этого?
Ответы
Ответ 1
Метод грубой силы должен быть достаточно хорошим.
for each point to generate "n"
find a random angle
get the x and y from the angle * a random radius up to max radius
for each point already generated "p"
calculate the distance between "n" and "p"
if "n" satisfies the min distance
add new point "n"
В PHP генерировать новую точку легко
$angle = deg2rad(mt_rand(0, 359));
$pointRadius = mt_rand(0, $radius);
$point = array(
'x' => sin($angle) * $pointRadius,
'y' => cos($angle) * $pointRadius
);
Затем вычисляя расстояние между двумя точками
$distance = sqrt(pow($n['x'] - $p['x'], 2) + pow($n['y'] - $p['y'], 2));
** Изменить **
Чтобы прояснить то, что сказали другие, и после дальнейших исследований (я не математик, но комментарии действительно заставляют меня задуматься), здесь самое простое определение гауссовского распределения:
Если вы были в 1 измерении, то $pointRadius = $x * mt_rand (0, $Радиус); было бы хорошо, так как нет различия между $radius и $x, когда $x имеет гауссовское распределение.
В двух или более измерениях, однако, если координаты ($ x, $y,...) имеют гауссовских распределений, то радиус радиуса $не имеет гауссовское распространение.
Фактически распределение $radius ^ 2 в 2 размерах [или k размеры] - это так называемое "распределение хи-квадратов с 2 [или k] степеней свободы, при условии, что ($ x, $y,...) независимы и имеют нулевые средства и равные дисперсии.
Следовательно, чтобы иметь нормальное распределение, вам придется изменить линию сгенерированного радиуса на
$pointRadius = sqrt(mt_rand(0, $radius*$radius));
как предложили другие.
Ответ 2
как говорит другой ответ, самый простой способ - генерировать случайные точки, а затем отбрасывать те, которые слишком близки к другим (не забудьте также проверить минимальное расстояние до центральной точки, если это необходимо).
Однако генерация случайных точек сложнее, чем объясняется. во-первых, вам нужно выбрать радиус в случайном порядке. во-вторых, вам нужно иметь больше очков на больших радиусах (потому что там "больше места" там). поэтому вы не можете просто сделать радиус равномерным случайным числом.
выберите число от 0 до $radius * $radius
. затем возьмите sqrt()
от этого, чтобы найти радиус для построения (это работает, потому что площадь пропорциональна квадрату радиуса).
Я не знаю, что php (см. исправление Karolis в комментариях), но из другого ответа я думаю, что это означало бы:
$angle = deg2rad(mt_rand(0, 359));
$radius = sqrt(mt_rand(0, $max_radius * $max_radius));
тогда проверьте это на предыдущие пункты, как уже описано.
Наконец, не забывайте, что вы можете достичь состояния, в котором вы можете создавать больше очков, поэтому вы можете установить верхний предел цикла "try and discard", чтобы избежать попадания в бесконечный цикл, когда пространство (близко к).
ps, как говорится в другом ответе, это O (n ^ 2) и поэтому непригоден для большого числа точек. вы можете в некоторой степени решить это путем сортировки точек по радиусу и только с учетом различий $min_distance
, если $min_distance << $max_radius
(как показано на рисунке); лучше, чем это требует более сложного решения (например, при больших радиусах, также использующих угол, или используя отдельное квадратное дерево для хранения и сравнения позиций). но для десятков точек я представляю, что это было бы необязательно.
Ответ 3
Создание случайных координат вокруг местоположения
function generateRandomPoint( $centre, $radius ){
$radius_earth = 3959; //miles
//Pick random distance within $distance;
$distance = lcg_value()*$radius;
//Convert degrees to radians.
$centre_rads = array_map( 'deg2rad', $centre );
//First suppose our point is the north pole.
//Find a random point $distance miles away
$lat_rads = (pi()/2) - $distance/$radius_earth;
$lng_rads = lcg_value()*2*pi();
//($lat_rads,$lng_rads) is a point on the circle which is
//$distance miles from the north pole. Convert to Cartesian
$x1 = cos( $lat_rads ) * sin( $lng_rads );
$y1 = cos( $lat_rads ) * cos( $lng_rads );
$z1 = sin( $lat_rads );
//Rotate that sphere so that the north pole is now at $centre.
//Rotate in x axis by $rot = (pi()/2) - $centre_rads[0];
$rot = (pi()/2) - $centre_rads[0];
$x2 = $x1;
$y2 = $y1 * cos( $rot ) + $z1 * sin( $rot );
$z2 = -$y1 * sin( $rot ) + $z1 * cos( $rot );
//Rotate in z axis by $rot = $centre_rads[1]
$rot = $centre_rads[1];
$x3 = $x2 * cos( $rot ) + $y2 * sin( $rot );
$y3 = -$x2 * sin( $rot ) + $y2 * cos( $rot );
$z3 = $z2;
//Finally convert this point to polar co-ords
$lng_rads = atan2( $x3, $y3 );
$lat_rads = asin( $z3 );
return array_map( 'rad2deg', array( $lat_rads, $lng_rads ) );
}
generate_random_point(array(3.1528, 101.7038), 4);
Ответ 4
Другие уже объяснили вам математику. Но я думаю, что наиболее проблематичной является производительность. Метод грубой силы для проверки расстояний между точками может быть достаточно хорошим, если у вас есть только 50 очков. Но слишком медленно, когда у вас 1000 очков или даже больше. Для 1000 очков для этого требуется не менее полумиллиона операций.
Поэтому мое предложение состояло в том, чтобы сохранить все случайно сгенерированные точки в B-tree или двоичное дерево поиска (по значению x и по значению y). Используя упорядоченное дерево, вы сможете эффективно получить точки, находящиеся в области [x ± min_distance, y ± min_distance]. И это единственные моменты, которые необходимо проверить, резко сократив количество необходимых операций.