1

У меня есть класс Ball, его метод Draw, который рисует окружность. При клике на форму я создаю обьект класса и вызываю метод, который рисует окружность в рандомном месте рандомного размера. Вопрос такой, каким образом предотвратить генерацию окружностей так, чтобы они не пересекались при создании?

1

2 ответа 2

5

Две окружности не пересекаются, если расстояние между их центрами больше суммы их радиусов

Пусть наша окружность представлена структурой:

struct Circle
{
    public double X { get; set; }
    public double Y { get; set; }
    public double R { get; set; }
}

Все наши уже сгенерированные окружности хранятся в некоторой коллекции:

List<Circle> circles = new List<Circle>();

Тогда, генерацию новой окружности, которая не пересекается ни с какой другой, можно выполнить следующим образом:

Circle nextCircle;
do
{
    nextCircle = new Circle
    {
        // Здесь мы генерируем координаты центра и радиус
    };
}
while (circles.All(c => // Для всех уже существующих окружностей
    Sqr(c.R + nextCircle.R) > Sqr(c.X - nextCircle.X) + Sqr(c.Y - nextCircle.Y) ));
//  квадрат суммы радиусов            квадрат расстояния между центрами
circles.Add(nextCircle);

Здесь я использую вспомогательную функцию возведения в квадрат:

double Sqr(double x) => x * x;

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


Если необходимо учитывать также варианты, в которых одна окружность полностью лежит внутри другой, то надо модифицировать условие таким образом:

do
{
    ...
}
while (circles.All(c =>
       Sqr(c.R + nextCircle.R) > Sqr(c.X - nextCircle.X) + Sqr(c.Y - nextCircle.Y)
    || Sqr(c.R - nextCircle.R) > Sqr(c.X - nextCircle.X) + Sqr(c.Y - nextCircle.Y) ));

Второе условие это преобразованное выражение неравенства: расстояние между центрами плюс меньший радиус меньше большего радиуса

6
  • 2
    Есть ещё вариант, когда одна окружность полностью лежит внутри другой, тогда они тоже не пересекаются. Могу дополнить ответ, если такой вариант тоже нужно учесть. 7 июл 2017 в 4:43
  • 1
    Дополните, это важный случай. 7 июл 2017 в 7:28
  • @PavelMayorov, готово! 7 июл 2017 в 7:52
  • Вопрос пять месяцев висел без хорошего ответа. Стоило сделать внятный заголовок — ответ появился. :)
    – Nick Volynkin
    7 июл 2017 в 8:36
  • @NickVolynkin, дело не в заголовке, а в том, что этот вопрос вообще "всплыл", да еще и с указанием модератора на качество ответа. Я просто, например, вглубь на 5 месяцев вообще не хожу 7 июл 2017 в 8:51
1

Альтернативная реализация, которая гарантированно находит новую окружность за одну итерацию.

Простая идея состоит в том, что все наши окружности будут вложены одна в другую, и для добавления новой окружности нам достаточно, чтобы самая большая из существующих окружностей лежала полностью внутри.

Пусть радиус этой окружности R, тогда мы отступаем от её центра на R + 1, и добавляем окружность с центром в полученной точке радиуса 2R + 2.

Получается такой код:

var lastCircle = circles.Last();
var R = lastCircle.Radius + 1;
var newCircle = new Circle(center: lastCircle.Center + new Vector(R, 0), radius: 2 * R);
circles.Add(newCircle);
2
  • добавил одну окружность с центром в т. (0, 0) радиуса 1, затем сгенерировал по вашему алгоритму еще 9 окружностей, вот что получилось: imgur.com/ir6UH1b Думаю, это условиям задачи не удовлетворяет... 9 июл 2017 в 6:36
  • @Андрей: Согласен, баг, радиус надо было больше увеличивать. Поправил код.
    – VladD
    9 июл 2017 в 9:48

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.