C/C++

Распределение случайных точек внутри окружности радиуса R и с центром (x, y)

Задача, собственно, в следующем:
Есть окружность радиуса R, количество точек N, и минимально допустимое значение разброса расстояний между точками. Необходимо сгенерировать N случайных точек, чтобы они были помещены внутрь окружности, и расстояние между ними не было меньше допустимого минимального разброса.
Игорь Толмачёв
Игорь Толмачёв
8 924
Это возможно далеко не при всех отношениях чисел R, N и дистанции разброса d. Вот так можно попробовать:
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <ctime>
using namespace std;
double r()
{
return 1. * rand() / RAND_MAX;
}
int main()
{
const double τ = 6.2831853071795864769;
int i, j, k, l, m, N, timeold;
double X, Y, R, a, b, c, d;
cout.precision(17);
while (1)
{
k = 0;
cout << "X Y R N d » ";
cin >> X >> Y >> R >> N >> d;
double *x = new double [N];
double *y = new double [N];
timeold = time(NULL);
back: srand(timeold);
for (i = 0; i < N; i++)
{
l = 1;
while (l)
{
m = 1;
b = R * r();
c = τ * r();
x[k] = X + b * cos(c);
y[k] = Y + b * sin(c);
for (j = 0; j < k; j++)
if (pow(x[k] - x[j], 2) + pow(y[k] - y[j], 2) < d)
{
m = 0;
break;
}
if (m) l = 0;
if (time(NULL) == timeold + 1) goto back;
}
printf("%4d)%20.10f%19.10f\n", k + 1, x[k], y[k]);
k++;
}
cout << k << endl;
}
}
Sarkar Nazarov
Sarkar Nazarov
29 440
Лучший ответ
Игорь Толмачёв Если будет не сложно, можете дать ссылку на pastebin? Я благодарен, что вы потратили счое время на решение этой задачи, но смотреть на такой формат кода из-за механики ответов очень сложно.
Игорь Толмачёв Ваше решение мне более менее понятно, однако оно неэффективно. Конечно, решение данной мной задачи кажется мне неэффективным из-за вложенного цикла, в котором вы сравниваете расстояния между предыдущими расставленными точками и новой, потому что ввиду рандомного выбора мы можем получить аналог богосорта, который в итоге зависнет при большом количестве точек и малым размером окружности. Но за решение еще раз благодарю.
Sarkar Nazarov Условие надо поставить нормальное, проверяющее - возможно ли вообще такое в принципе, тогда ничего и виснуть не будет. Вот только это довольно таки сложное условие, сложнее вроде чем вся эта программа!.
Да, и ещё, даже если N точек удастся задать, надо же каким-то образом позаботиться об равномерной вероятности их распределения, а не просто о случайном формировании массива точек! ｡◕‿◕｡
максимум точек запихнуть?
ДМ
Дмитрий Межевой
21 700
Дмитрий Межевой Реализация как-нибудь потомю Может кто и раньше сделает
Дмитрий Межевой а как расставить решаешь сам? Ну вот и сначала в вектор МАКСИМУМ пар координат ХУ, а потом уже случайную координату ХУ ищешь в векторе или близкую у ним
Дмитрий Межевой Или другой вариант - xy на этой сетке выбираешь как x0y0 это центр окружности Скажем номер точки= ху / шаг, а точка получается НОМЕР ТОЧКИ * шаг + ху. Непонятно сразу? Мне просто возиться лень
Дмитрий Межевой а чтобы не повторяться сделаешь квадратную матрицу размером Диаметр / ШАГ и там номер точки это индексы матрицы и присвоишь им 1 если точка выставлена иначе ищешь свободную ближайшую. Это задача явно не универская. Так что алгоритма и так достаточно

Похожие вопросы