Сколько окружностей можно вписать в прямоугольник
Перейти к содержимому

Сколько окружностей можно вписать в прямоугольник

  • автор:

Сколько малых одинаковых окружностей радиуса r можно вписать в большую окружность радиуса R

Этот калькулятор оценивает число малых окружностей заданного радиуса r можно разместить внутри большой окружности заданного радиуса R.

Этот калькулятор выводит максимальное число малых окружностей заданного радиуса r можно разместить внутри большой окружности заданного радиуса R. Например это могут быть малые трубы внутри большой, провода в кабель канале, круги, вырезаемые из круговой же заготовки и так далее.

Вы можете подумать, что для решения такой задачи должна быть выведена формула, но на самом деле это не так — формулы нет. Эта задача относится к классу оптимизационных задач, а точнее, задач упаковки. Эта задача известна как Упаковка кругов в круге. Упаковка кругов в круге — это двумерная задача упаковки, целью которой является упаковка единичных кругов в как можно меньший круг. См. Упаковка кругов в круге.

Для этой задачи найденное решение еще и должно быть проанализировано на оптимальность. Статья в википедии по ссылке выше приводит первые 20 решений (иными словами, приводит минимальные радиусы больших окружностей вмещающих заданное число единичных окружностей. Между прочим, по умолчанию входные параметры калькулятора дают ответ 11 кругов, что соответствует следующей диаграмме:

http://en.wikipedia.org/wiki/File:Disk_pack11.svg

Хорошей новостью является то, что есть проект в интернете, целиком посвященный задачам упаковки — сайт Packomania. На сегодняшний день он содержит все найденные решения, автор сайта, Экард Спехт (Eckard Specht), сам участвует в поиске решений, и большинство решений, на самом деле найдены им. Оттуда можно взять соотношения r к R для решений, позволяющих упаковать от 1 до 2600 окружностей внутри большой, с графическими диаграммами решения.

Соотношения r/R, приведенные на сайте и использует калькулятор ниже для поиска оптимального решения. Если соотношение не попадает в диапазон известных решений, калькулятор выдает ошибку.

Сколько окружностей можно уместить в квадрат

Author24 — интернет-сервис помощи студентам

Нужна функция, которая ответит на вопрос: Сколько окружностей радиуса R можно уместить в квадрат со стороной A?

94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Сколько полных окружностей можно построить.
Вася взял большой циркуль и вошел в комнату, пол которой представляет собой квадрат, со стороной.

Как найти, сколько окружностей можно вместить в треугольник?
Заданы радиус окружности и длина стороны правильного треугольника. Определить, сколько таких.

Уместить как можно больше блоков
Знаем ширину блока, в этот блок необходимо разместить как можно больше дочерних блоков. Ширина.

Во скольких отрезках А можно уместить отрезки В
Дано цельные числа А и В (А>В). Во скольких отрезках А можно уместить отрезки В?

294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,037

Если расставлять в шахматном порядке, то N = A*A/(2R*2R) c округлением до ближайшего меньшего числа являющегося квадратом.
Только вот не все так просто. Данный вид задач на английском называется Circle Packing
Вот англоязычная статья на википедии к упаковке кругов в квадрат http://en.wikipedia.org/wiki/C. n_a_square но там не непонятно откуда берется число из формулы.
Алгоритма в понятном виде я так и не нашел, возможно нужно изучать выкладки на английском языке.
http://mathworld.wolfram.com/CirclePacking.html

В русской вики имеется упоминание что самая плотная упаковка кругов в 2D случае имеет плотность , правда мне не понятно отношение чего к чему представляет данная цифра.

87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

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

Определить, сколько квадратов можно отсечь, если каждый раз отсекается самый большой квадрат
Дан прямоугольник со сторонами А и Б, где А и Б — натуральные числа. От него отсекаются квадраты.

Выяснить, можно ли прямоугольник a,b уместить внутри прямоугольника со сторонами c,d
Доброго времени суток. Даны действительные положительные числа a,b,c,d. Выяснить, можно ли.

Даны положительные a, b, c, d. Выяснить, можно ли прямоугольник со сторонами a и b уместить внутри
Даны положительные a, b, c, d. Выяснить, можно ли прямоугольник со сторонами a и b уместить внутри.

Или воспользуйтесь поиском по форуму:

Сколько окружностей можно вписать в прямоугольник

Регистрация: 03.05.2008

Сообщений: 25

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

Сообщение от Utkin

Ну как частный случай, если все окружности разных диаметров + все что описано выше, то поместятся все .

Да, вы правы. Я перепутал круги и окружности.
Извиняюсь за два поста подряд.

Последний раз редактировалось Stilet; 27.10.2010 в 15:50 .

Сколько окружностей можно вписать в прямоугольник

1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code. /code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии «срочно надо», заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке

Модераторы: Akina, shadeofgray
‘> Размещение окружностей в прямоугольнике

  • Подписаться на тему
  • Сообщить другу
  • Скачать/распечатать тему

Сообщ. #1 , 28.06.16, 11:39
Рейтинг (т): нет

Добрый день.
Дан прямоугольник шириной W и высотой H. Даны N1 окружностей диаметром D1, N2 окружностей диаметром D2. Nk окружностей диаметром Dk. N>=1, k>=1, D>0. Разместить окружности в прямоугольнике так, чтобы
Окружности не пересекались между собой
Окружности не пересекались с границами прямоугольника
Окружности были распределены по всей площади прямоугольника. Т.е. например так, чтобы не было ситуации, когда все окружности «забились» в угол.
Окружности располагались на как можно меньшем количестве горизонтальных/вертикальных осей. Т.е. чтобы была некая сетка осей.
Предложить варианты размещения

Буду рад любой помощи. Задача имеет прикладной смысл на практике — будут производиться электромонтажные коробки с отверстиями для ввода кабелей.

Сообщ. #2 , 28.06.16, 12:15
Рейтинг (т): 135

Самое простое решение: расположить центры окружностей на сетке, окружности отсортировать по диаметру, разместить их «змейкой», подвигать линии сетки, чтобы окружности разместились более-менее равномерно. Поскольку речь идет о кабелях, то разница в диаметрах окружностей будет небольшой (вряд ли кто-то будет заводить в одну коробку высоковольтный и телефонный кабель), так что все получится красиво. Нужно будет учесть ширину отступов между окружностями, но это можно сделать автоматически, если заранее уменьшить размеры прямоугольника и увеличить радиусы окружностей на половину ширины отступа.

Сообщ. #3 , 28.06.16, 13:39
Рейтинг (т): нет

Поскольку речь идет о кабелях, то разница в диаметрах окружностей будет небольшой (вряд ли кто-то будет заводить в одну коробку высоковольтный и телефонный кабель)

На самом деле кабель может быть многожильным и будет один большой ввод, но внутри коробки он разовьется на 20-30 небольших кабелей. И по соседству может быть двужильный кабель небольшого сечения. Поэтому диаметры могут сильно отличаться.

Нужно будет учесть ширину отступов между окружностями, но это можно сделать автоматически, если заранее уменьшить размеры прямоугольника и увеличить радиусы окружностей на половину ширины отступа

В данном случае задача уже сведена к минимуму и все отступы и критические расстояния заложены в размеры прямоугольника и диаметры окружностей, соответственно окружности могут касаться друг друга и стенок прямоугольника.

Самое простое решение: расположить центры окружностей на сетке, окружности отсортировать по диаметру, разместить их «змейкой», подвигать линии сетки, чтобы окружности разместились более-менее равномерно

А вот с этого момента поподробнее По какому алгоритму располагать на сетке? что значит «змейкой»? и как распределить равномерно?

Сообщение отредактировано: nicki1987 — 28.06.16, 13:40
Сообщ. #4 , 28.06.16, 16:17
Рейтинг (т): 135

«Змейкой» — это значит, что первый ряд заполняется слева направо, второй — справа налево, третий — опять слева направо и т. д. Алгоритм видится примерно такой:

1. Сортируем окружности по убыванию диаметров.
2. Размещаем первый ряд окружностей вдоль длинной стороны прямоугольника, столько, сколько сможем. Для определенности используем ландшафтную ориентацию прямоугольника. Все центры окружностей кладем на одну горизонтальную линию. После размещения равномерно расталкиваем окружности по горизонтали. Теперь центры окружностей задают вертикальные линии сетки.
3. Размещаем следующий ряд «змейкой», центры опять кладем на одну горизонтальную линию, каждый центр на соответствующей вертикальной линии сетки. По завершении ряда максимально прижимаем его к предыдущему ряду. Повторяем операцию, пока не закончатся окружности.
4. Если вдруг между двумя окружностями ряда оказывается достаточно места, то размещаем посередине между ними очередную окружность, ее центр задает новую вертикальную линию сетки для следующих рядов.
5. После того, как все окружности размещены, равномерно расталкиваем ряды.

P. S. «Равномерно расталкиваем» означает: у нас есть N объектов, с суммарной шириной L, которые нужно равномерно разместить на ширине M, M >= L. Тогда добавляем между объектами промежутки шириной (M — L)/(N — 1).

Сообщ. #5 , 28.06.16, 17:51
Рейтинг (т): 541
Цитата AVA12 @ 28.06.16, 16:17
1. Сортируем окружности по убыванию диаметров.

Уже плохо. То есть хорошо с точки зрения технологии, но плохо с точки зрения приближения к оптимальности.
По-хорошему, нужно «через один», причём чтобы максимум разности диаметров пар соседних кругов был минимален.

Сообщ. #6 , 28.06.16, 19:17
Рейтинг (т): нет

«Змейкой» — это значит, что первый ряд заполняется слева направо, второй — справа налево, третий — опять слева направо и т. д. Алгоритм видится примерно такой:

1. Сортируем окружности по убыванию диаметров.
2. Размещаем первый ряд окружностей вдоль длинной стороны прямоугольника, столько, сколько сможем. Для определенности используем ландшафтную ориентацию прямоугольника. Все центры окружностей кладем на одну горизонтальную линию. После размещения равномерно расталкиваем окружности по горизонтали. Теперь центры окружностей задают вертикальные линии сетки.
3. Размещаем следующий ряд «змейкой», центры опять кладем на одну горизонтальную линию, каждый центр на соответствующей вертикальной линии сетки. По завершении ряда максимально прижимаем его к предыдущему ряду. Повторяем операцию, пока не закончатся окружности.
4. Если вдруг между двумя окружностями ряда оказывается достаточно места, то размещаем посередине между ними очередную окружность, ее центр задает новую вертикальную линию сетки для следующих рядов.
5. После того, как все окружности размещены, равномерно расталкиваем ряды.

P. S. «Равномерно расталкиваем» означает: у нас есть N объектов, с суммарной шириной L, которые нужно равномерно разместить на ширине M, M >= L. Тогда добавляем между объектами промежутки шириной (M — L)/(N — 1).

Подход интересный. Мне он в голову не приходил. Пока, конечно, непонятно возникнут-ли трудности с его программированием. На первый взгляд смущает «равномерное расталкивание». Все же если сначала идут большие диаметры, то снизу под, например, первым из них может оказаться маленький диаметр, как и весь ряд. Тогда при равномерном расталкивании маленького ряда оси сместятся в другом порядке, отличном от осей больших диаметров.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *