Размещение случайных кругов без перекрытия (и без использования грубой силы)?

Я только что представил назначение Java, в котором мне нужно было нарисовать некоторые круги случайно на экране как часть игры. Одна из задач, поставленных перед нами, заключалась в том, чтобы убедиться, что ни один из кругов не перекрывается. Я закончил с странным подходом (потому что я хотел: D), что в основном просто создал шаблон из центра экрана, используя триггер, что было весело. Хотя круги в этом методе никогда не перекрываются, это не идеально... распределение кругов довольно упаковано вокруг середины экрана с очень небольшим пространством, используемым в углах.

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

После обсуждения решений с другом (и после TON поиска в Google) нам действительно очень интересно посмотреть, как это можно было бы сделать без грубой силы. Требования:

20 кругов с радиусом десяти единиц для рисования в окне 640x480
Абсолютно без перекрытия кругов
в противном случае случайное распределение по экрану

Возможно, используя стандартную библиотеку?

Ответ 1

Составьте список 640x480 записей и поместите в них последовательные номера от 1 до 307.200 (640x480). Каждая запись представляет собой один пиксель на экране.
Случайно выберите число от 1 до 307.200, которое представляет собой пиксель на экране. Нарисуйте круг.
Рассчитайте все пиксели, которые находятся в радиусе 10 пикселей от этого круга. Удалите все записи, представляющие эти пиксели из списка.

Повторите десять раз.

Ответ 2

Сделайте сетку, покрывающую весь экран; поместите сетку в набор. Каждая секция сетки должна быть 10 единиц (размер ваших кругов).

для цикла 1-20.
Нарисуйте одну сетку из набора, произвольно.
Поместите круг в эту сетку; центр круга - это центр сетки.
Удалите эту сетку из набора.
Далее для цикла.

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

Теперь, какие другие системы пространственного разбиения будут полезны здесь и как?

Ответ 3

Определить набор, содержащий действительные координаты.
Найдите случайный элемент из этого набора.
Исключить из набора все недействительные координаты.
Перейдите к 2.

Ответ 4

Это то, что я искал. Я делаю в основном то же самое, но в HTML5. К счастью, мне просто нужно было разместить 100 кругов с радиусом 20 пикселей на холсте 800px на 400 пикселей. Использование подхода грубой силы работает до 120 кругов.

Вот мое решение.

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