S>Подскажите, как случайным образом заполнить прямоугольник S>непересекающимися окружностями одного радиуса, если число окружностей известно?
Что значит "случайным образом"?
Если надо прямоугольную коробку заполнить шарами и стороны прямоугольника — целые числа a и b, то очевидно подойдут шары диаметром HОД(a,b).
Здравствуйте, Ranger_XL, Вы писали:
R_X>Что значит "случайным образом"? R_X>Если надо прямоугольную коробку заполнить шарами и стороны прямоугольника — целые числа a и b, то очевидно подойдут шары диаметром HОД(a,b).
Случайным образом, т.е. чтобы каждый раз окружности располагались в разных местах прямоугольника.
Здравствуйте, sinful, Вы писали:
S>Подскажите, как случайным образом заполнить прямоугольник S>непересекающимися окружностями одного радиуса, если число окружностей известно?
Есть мысль, но не знаю насколько она правильна.
1. Вычислить размеры прямоугольника в заданных диаметрах окружности. Дробные части
отбрасываем.
2. Создаём массив нулевых элементов вычисленных в 1 размеров. N любых ячеек заполняем 1.
3. Перетасовываем единицы и нули в массиве.
Получили начальное приближение к случайному заполнению.
4. Цикл по всем окружностям. Повторять раз 20 — 30.
5. Вычислить случайные величины dx и dy, которые будут меньше R в несколько раз
6. Переместить окружность в точку (x + dx, y + dy), если другие окружности этому не препятствуют.
После этого должны получить некоторое подобие случайного распределения.
Разбиваешь твой ящик, куда нужно класть окружности на ячейки размером чуть больше чем нужно для одной окружности.
Случайным образом кладёшь в ячейки свои окружности.
Сдвигаешь каждую окружность в случайном направлении на случайное расстояние, если ей мешают, попробовать изменить расстояние/направление (пытатся это делать N раз), потом переходишь к следующей окружности.
Здравствуйте, sinful, Вы писали:
S>Подскажите, как случайным образом заполнить прямоугольник S>непересекающимися окружностями одного радиуса, если число окружностей известно?
Генерация n пар случайных чисел при условии что расстояние между парами не менее 2*r а расстояние до ближайшей стенки не менее r? Имеется проблема- часть окружностей может не поместится
Здравствуйте, Teolog, Вы писали:
T>Здравствуйте, sinful, Вы писали:
S>>Подскажите, как случайным образом заполнить прямоугольник S>>непересекающимися окружностями одного радиуса, если число окружностей известно?
T>Генерация n пар случайных чисел при условии что расстояние между парами не менее 2*r а расстояние до ближайшей стенки не менее r? Имеется проблема- часть окружностей может не поместится
Я так понимаю, задача поставленна так, что бы быть корректной в любом случае.
Проверить помещаются ли окружности в прямоугольник достаточно легко. Так что тут проблем нет.
Здравствуйте, Teolog, Вы писали:
T>Здравствуйте, sinful, Вы писали:
S>>Подскажите, как случайным образом заполнить прямоугольник S>>непересекающимися окружностями одного радиуса, если число окружностей известно?
T>Генерация n пар случайных чисел при условии что расстояние между парами не менее 2*r а расстояние до ближайшей стенки не менее r? Имеется проблема- часть окружностей может не поместится
Привожу реализацию (писал в спешке, Delphi)
unit Unit1;
{
Виноградов С.В. 29 июня 2005. Задача для форума RSDN (решение)
Заполнение прямоугольника окружностями радиуса R и количества N
}interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, ExtCtrls, StdCtrls, Spin;
type
TForm1 = class(TForm)
Image1: TImage;
Button1: TButton;
Label1: TLabel;
seR: TSpinEdit;
Label2: TLabel;
SeN: TSpinEdit;
seWidth: TSpinEdit;
seHeight: TSpinEdit;
procedure seWidthChange(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure seRChange(Sender: TObject);
procedure FormShow(Sender: TObject);
procedure SeNChange(Sender: TObject);
private{ Private declarations }public{ Public declarations }end;
S = record
X, Y : integer;
end;
TAS = array of S;
var
Form1: TForm1;
R, N, W, H : integer;
implementation{$R *.dfm}procedure TForm1.seWidthChange(Sender: TObject);
begin
Image1.Canvas.Rectangle(0, 0, ClientWidth, ClientHeight);
W := SeWidth.Value;
H := SeHeight.Value;
Image1.Canvas.Rectangle(0, 0, W, H);
Button1Click(Sender);
end;
procedure GetCoord(var T : TAS);
function IsCorrect(T : TAS; K: integer): boolean;
var
I, X, Y : integer;
E : extended;
begin
X := T[K].X;
Y := T[K].Y;
Result := false;
if (T[K].X >= W - R) or (T[K].X <= R) or
(T[K].Y >= H - R) or (T[K].Y <= R)
then exit;
For I := 0 to N - 1 do
begin
if I = K then continue;
E := sqrt( sqr(T[I].X - X) + sqr(T[I].Y - Y) );
if E < 2 * R then exit;
end;
Result := true;
end;
var
A : array of array of integer;
I, J : integer;
Wi, Hi : integer;
X, Y : integer;
begin
Wi := W div ( 2 * R );
Hi := H div ( 2 * R );
Setlength(A, Wi, Hi);
for I := 0 to N - 1 do
begin
repeat
X := random(Wi);
Y := random(Hi);
until A[X, Y] = 0;
A[X, Y] := 1;
T[I].X := X * 2 * R + R;
T[I].Y := Y * 2 * R + R;
end;
Finalize(A);
For J := 0 to N * N do
For I := 0 to N - 1 do
begin
X := random(R) div (R shr 2) - random(R) div (R shr 2);
Y := random(R) div (R shr 2) - random(R) div (R shr 2);
inc(T[I].X, X);
inc(T[I].Y, Y);
if NOT IsCorrect(T, I) then
begin
dec(T[I].X, X);
dec(T[I].Y, Y);
end;
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
T : TAS;
I : integer;
begin
Image1.Canvas.Rectangle(0, 0, ClientWidth, ClientHeight);
Image1.Canvas.Rectangle(0, 0, W, H);
if (W div R) * (H div R) / 4 <= N then exit;
SetLength(T, N);
GetCoord(T);
For I := 0 to N - 1 do
Image1.Canvas.Ellipse(T[I].X - R, T[I].Y - R, T[I].X + R, T[I].Y + R);
Finalize(T);
end;
procedure TForm1.seRChange(Sender: TObject);
begin
R := SeR.Value;
end;
procedure TForm1.FormShow(Sender: TObject);
begin
R := SeR.Value;
N := SeN.Value;
W := SeWidth.Value;
H := SeHeight.Value;
end;
procedure TForm1.SeNChange(Sender: TObject);
begin
N := SeN.Value;
end;
initialization
randomize;
end.
