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

Ответ 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]. И это единственные моменты, которые необходимо проверить, резко сократив количество необходимых операций.