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 that you have read and understand our privacy policy and code of conduct.

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