Равномерное распределение точек в круге

[Arigato]

Пусть задана окружность (x0,y0,r0). Необходимо внутри разместить случайные точки так, чтобы они были распределены равномерно.

Решение в лоб:

  with canvas do begin
    Ellipse(x0-r0,y0-r0,x0+r0,y0+r0);
    for i := 1 to 10000 do begin
      a:=2*Pi*random;
      r:=r0*random;
      x:=x0+round(r*cos(a));
      y:=y0+round(r*sin(a));
      Pixels[x,y]:=clred;
    end;
  end;

Но понятно, что распределение не равномерное, плотность точек выше к центру круга:

1.PNG

Есть идеи, как распределить точки равномерно?

[Arigato]

Есть такое решение, тоже в лоб:

  with canvas do begin
    Ellipse(x0-r0,y0-r0,x0+r0,y0+r0);
    for i := 1 to 10000 do begin
      repeat
        x:=x0+random(2*r0)-r0;
        y:=y0+random(2*r0)-r0;
      until (sqr(x-x0)+sqr(y-y0)<sqr(r0));
      Pixels[x,y]:=clred;
    end;
  end;

С поставленной задачей справляется, распределение равномерное:

2.PNG

Только присутствуют лишние холостые шаги, от которых хотелось бы избавиться.

[raxp]

...типа этого?

http://www.programmersforum.ru/showthread.php?t=252071

[Arigato]

Только там ничего нового, решение схоже с моим.

Сообщение от raxp

...типа этого?

Кстати, не аэрограф, а минное поле. Точки - мины.

[Аватар]

procedure TForm1.Button1Click(Sender: TObject);
var i,cx,cy,r: Integer;
    x,y: Real;
begin
  cx:=220; cy:=220; r:=200;
  Randomize;
  Canvas.Ellipse(cx-r,cy-r,cx+r,cy+r);
  for i:=1 to 10000 do begin
    x:=r*Sqrt(Random);
    y:=2*Pi*Random;
    Canvas.Pixels[cx+Round(x*cos(y)),cy+Round(x*sin(y))]:=clRed;
  end;
end;

[Arigato]

Получается в первое решение только добавить корень. Оригинально.
Вот только идею что-то понять не могу, видимо, время позднее. Интуитивно ясно, можно даже узреть по первой картинке, но как это обосновать?

[type_Oleg]

Сообщение от Arigato

.. но как это обосновать?

Тоже не соображу. Может быть есть простое и изящное обоснование, но в голову не идет.

А так, тупо в лоб ...
r - равномерно распределенная СВ ( r:=r0*random; )
Рассмотрим две маленькие области ( кольцевые сегменты, серые ). Толщина сегментов одинаковая , то есть r2-r1 = r4-r3 , потому вероятности
P(r1<r<r2) = P(r3<r<r4) и поэтому вероятности попадания в сегменты тоже будет одинаковая. А площадь у них разная, она пропорциональна среднему радиус-вектору сегментов.
Точнее, почти пропорциональна, чем тоньше, тем точнее. При бесконечно малой толщине - точно пропорциональна.

Вот отсюда как то и выведется наверное.
Если надо точное теоретическое обоснование - то всякие функции плотности, функции распределения, интегралы.

PS Не уверен, что корень из равн.распр. СВ и есть точный ответ. Может быть просто очень близкий.

[Arigato]

Если построить график плотности распределения точек в круге, то получаем вот что:

  x0:=300; y0:=300; r0:=200;
  randomize;
  canvas.Rectangle(x0-r0,y0,x0+r0,y0-r0);
  for i := 1 to 15000 do begin
    a:=2*Pi*random;
    r:=r0*random;
    x:=x0+round(r*cos(a));
    y:=y0;
    while canvas.Pixels[x,y]=clred do
      dec(y);
    canvas.Pixels[x,y]:=clred;
  end;

1.PNG

С корнем:

    r:=r0*sqrt(random);

2.PNG

То есть оно тоже не равномерно, просто нет такого пика в центре.

Пока наиболее верный результат дает решение #2, но оно не рациональное. Еще решения будут?

[Arigato]

Хотя, я не прав. Это плотность распределения только по x. То есть с квадратным корнем распределение в круге действительно равномерное. Это видно, если количество точек увеличить с 10000 до 100000:

1.PNG

[Аватар]

Теоретическое обоснование мне слабо провести, нужно копать в сторону векторных случайных величин, интегралов Лебега или Римана, не помню. А так прикинул, что площадь квадратичная функция от радиуса, методом тыка извлек корень квадратный, визуально получилось похоже