Генерация случайных координат вокруг местоположения

Question

Я хотел бы иметь функцию, которая принимает географическое местоположение (широта, долгота) и генерирует случайные наборы координат вокруг него, но также принимает эти параметры как часть вычисления:

• Количество произвольных координат для создания
• Радиус для генерации в
• Минимальное расстояние между случайными координатами в метрах
• Корневые координаты для создания мест вокруг него.

Пример того, как будет выглядеть поколение:

Какой хороший подход для достижения этой цели?

Answer 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));было бы хорошо, так как нет разницы между $ radius и $ x, когда $ x имеет гауссово распределение.

В двух или более измерениях, однако, если координаты ($ x, $ y, ...) имеют гауссовские распределения, то радиус $ radius не имеет гауссовского распределения.

На самом деле распределение $ radius ^ 2 в 2 измерениях [или k измерениях] - это то, что называется «хи-квадрат с 2 [или k] степенями свободы», при условии ($ x,$ y, ...) независимы и имеют нулевое среднее значение и равные дисперсии.

Поэтому, чтобы иметь нормальное распределение, вам нужно изменить линию сгенерированного радиуса на

$pointRadius = sqrt(mt_rand(0, $radius*$radius));

, как предлагали другие.

Answer 2

Создание случайных координат вокруг местоположения

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 ) );
}

Использование

generateRandomPoint(array(3.1528, 101.7038), 4);

Answer 3

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

однако, генерирование случайных точек сложнее, чем объяснено. Во-первых, вам нужно выбрать радиус случайным образом. во-вторых, вам нужно иметь больше точек на больших радиусах (потому что там «больше места»). так что вы не можете просто сделать радиус равномерным случайным числом.

Вместо этого выберите число от 0 до $radius * $radius. затем возьмите sqrt() от этого, чтобы найти радиус для построения графика (это работает, потому что площадь пропорциональна квадрату радиуса).

я не знаю php ( см. Исправление Каролиса в комментариях ), но из другого ответа я думаю, что это будет означать:

$angle = deg2rad(mt_rand(0, 359));
$radius = sqrt(mt_rand(0, $max_radius * $max_radius));

Затем проверьте это по предыдущим пунктам, как уже описано.

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

ps как комментарий говорит о другом ответе, это O (n ^ 2) и поэтому не подходит для большого количества точек. Вы можете решить эту проблему в некоторой степени, отсортировав точки по радиусу и рассматривая только те из них, которые находятся в пределах $min_distance, пока $min_distance << $max_radius (как на вашем чертеже); для достижения лучшего результата требуется более сложное решение (например, при больших радиусах также с использованием угла или использования отдельного четырехугольного дерева для хранения и сравнения позиций). но для десятков пунктов я думаю, что в этом не было бы необходимости.

Answer 4

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

Поэтому я предлагаю сохранить все случайно сгенерированные точки в B-дерево или двоичное дерево поиска (по значению x и значению y). Используя упорядоченное дерево, вы сможете эффективно получать очки, которые находятся в области [x ± min_distance, y ± min_distance] . И это единственные моменты, которые необходимо проверить, что значительно сокращает количество необходимых операций.