Как мне создать непересекающиеся круги в фиксированной области?

Question

Как лучше всего создать известное количество непересекающихся кругов с фиксированным радиусом в ограниченном пространстве?

Answer 1

См. Теорема об упаковке кругов в Википедии

Answer 2

Способ сделать это с наименьшим оставшимся пространством - это поместить центры кругов в шестиугольную сетку, как шаблон, который вы получили бы, если бы делали пирамиду из монет.

Answer 3

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

Answer 4

Вы можете разделить экран как сетку и нарисовать круг в каждом "квадрате":)

Answer 5

Я не думаю, что ваша проблема хорошо определена. Какие-либо ограничения на поколение?

Вот алгоритм отклонения для случайного набора непересекающихся кругов фиксированного радиуса:

1. Вести список всех кругов
2. сгенерировать кандидата
   1. генерирует случайный центр в разрешенной области
   2. Проверьте каждый существующий круг в вашем списке на столкновение с кандидатом и отклоните, если какое-либо столкновение будет найдено. Если все прошло, добавьте этого кандидата в свой список.
3. Переходите к # 1, пока не будете удовлетворены сгенерированным числом

Редактировать: прочитать вопрос поближе, радиус указан ...

Answer 6

Это будет зависеть от формы пространства и других ограничений на характер окружностей, которые вы не указали. Например, чтобы сгенерировать N непересекающихся окружностей в прямоугольнике с высотой Y и длиной X, пусть диаметр каждого круга будет равен X / 10 * N или Y / 10 * N, в зависимости от того, что меньше, и пусть каждый центр будет разнесен равномерно на горизонтальной линии, разделяющей прямоугольник, охватывающий половину его длины.