Этот калькулятор оценивает число малых окружностей заданного радиуса r можно разместить внутри большой окружности заданного радиуса R.
Этот калькулятор выводит максимальное число малых окружностей заданного радиуса r можно разместить внутри большой окружности заданного радиуса R. Например это могут быть малые трубы внутри большой, провода в кабель канале, круги, вырезаемые из круговой же заготовки и так далее.
Вы можете подумать, что для решения такой задачи должна быть выведена формула, но на самом деле это не так — формулы нет. Эта задача относится к классу оптимизационных задач, а точнее, задач упаковки. Эта задача известна как Упаковка кругов в круге. Упаковка кругов в круге — это двумерная задача упаковки, целью которой является упаковка единичных кругов в как можно меньший круг. См. Упаковка кругов в круге.
Для этой задачи найденное решение еще и должно быть проанализировано на оптимальность. Статья в википедии по ссылке выше приводит первые 20 решений (иными словами, приводит минимальные радиусы больших окружностей вмещающих заданное число единичных окружностей. Между прочим, по умолчанию входные параметры калькулятора дают ответ 11 кругов, что соответствует следующей диаграмме:
Хорошей новостью является то, что есть проект в интернете, целиком посвященный задачам упаковки — сайт Packomania. На сегодняшний день он содержит все найденные решения, автор сайта, Экард Спехт (Eckard Specht), сам участвует в поиске решений, и большинство решений, на самом деле найдены им. Оттуда можно взять соотношения r к R для решений, позволяющих упаковать от 1 до 2600 окружностей внутри большой, с графическими диаграммами решения.
Соотношения r/R, приведенные на сайте и использует калькулятор ниже для поиска оптимального решения. Если соотношение не попадает в диапазон известных решений, калькулятор выдает ошибку.
Видео:j-DESIGN.PRO - Упаковка окружностей в Grasshopper 2Скачать
Про двумерную упаковку: offline алгоритмы
Сегодня, дорогой Хабр, я расскажу тебе историю о комбинаторной оптимизации.
Издревле (как минимум, с начала прошлого века) математики задавались вопросом, как оптимально разместить некоторое количество пива нужных и полезных предметов в рюкзаке. Была сформулирована задача о ранце и ее подзадачи — тысячи их! — которые заинтересовали информатиков, криптографов и даже лингвистов.
От задачи о ранце отпочковалась задача об упаковке в контейнеры (Bin Packing Problem), одной из разновидностей которых является задача двумерной упаковки (2-Dimensional Bin Packing). Снова отбросив несколько вариаций, мы наконец придем к двумерной упаковке в полуограниченную полосу (2-Dimensional Strip Packing, 2DSP). Чувствуете, сколько интересного уже осталось за кадром? Но мы еще не закончили продираться сквозь классификацию. У 2DSP есть два варианта входных данных: когда набор упаковываемых объектов известен заранее (offline-проблема) и когда данные поступают порциями (online-проблема).
В этой статье рассматриваются алгоритмы решения offline-варианта 2DSP. Под катом немного матчасти и много картинок с цветными квадратиками.
Видео:Деление окружности на 3; 6; 12 равных частейСкачать
В чем, собственно, проблема?
Как частный случай задачи двумерной упаковки, 2DSP заключается в упаковке объектов конкретной формы в конечное число контейнеров конкретной формы таким способом, чтобы число использованных контейнеров было наименьшим или количество или объем объектов (которые упаковывают) были наибольшими. Разница с двумерной упаковкой состоит в том, что есть только один контейнер, и вместо минимизации количества контейнеров, мы минимизируем высоту заполненности одного. Обеспечиваем максимальную плотность упаковки, если хотите.
Так как проблема NP-трудная, исследования сфокусированы главным образом на разработке приближенных алгоритмов решения. (На Хабре упоминался генетический алгоритм). Приближенные алгоритмы находят оптимальное решение с определенной точностью, но не гарантируют оптимальной упаковки для любого набора данных. При этом критерий оптимальности зависит от того, что вы пытались оптимизировать.
Я расскажу о простейших стратегиях и о том, к чему это все применимо в жизни (кроме рюкзака с пивом).
Итак, имеем набор из n прямоугольников и полуограниченный контейнер-стакан с фиксированной шириной W и бесконечной высотой. Каждый прямоугольник по ширине не превышает W. Задача — уложить прямоугольники в стакан без наложений и пересечений так, чтобы стакан стал как можно менее полон. Условимся, что все прямоугольники должны быть упакованы ортогонально, их нельзя поворачивать.
 | | | |
| Исходные данные (начало XX века, кубизм) | Полуограниченная полоса | Вариант упаковки (похуже) | Вариант упаковки (получше) |
Видно, что задача имеет идеальное решение, при котором высота упакованных прямоугольников равна их суммарной площади деленной на ширину полосы.
Видео:Вписанная и описанная окружность - от bezbotvyСкачать
Зоопарк алгоритмов
Для offline варианта 2DSP сразу известен размер всех упаковываемых прямоугольников, поэтому их можно отсортировать, выбрать по определенному критерию, сгруппировать или просто натыкать в подходящие места. На этом и основываются большинство алгоритмов:
- уровневые (level)
- шельфовые (shelf)
- плоские (plane)
Плоские алгоритмы размещают прямоугольники строго вплотную друг к другу, но это не самая удачная стратегия, как может показаться на первый взгляд. Уровневые делят полосу на уровни, равные по высоте одному из выбранных прямоугольников, и помещают все остальные на конкретный уровень по определенному критерию. Шельфовые предопределяют сразу несколько шельфов (полок), и распихивают по ним прямоугольники, такое поведение характерно для online-алгоритмов, а это уже совсем другая история.
Чем распространяться на общие слова, лучше обо всем по порядку.
Видео:Построение эвольвенты окружностиСкачать
Next Fit Decreasing High
Алгоритм, что называется, «в лоб». Прямоугольники сортируются по не-возрастанию высоты (Decreasing High намекает), самый высокий располагается в левом нижнем углу полосы, тем самым инициализируя первый уровень, по высоте равный ему. Остальные прямоугольники располагаются слева направо, пока есть место на текущем уровне. Прямоугольник, который не поместился на уровне, помещается сверху, образуя следующий уровень, и так далее.
Иллюстрации для каждого алгоритма будут производиться для следующих двух примеров: для наглядности, в левом форма прямоугольников тяготеет к вытянутой, в правом — более квадратные.
Видео:Вписанные и описанные окружности. Вебинар | МатематикаСкачать
First Fit Decreasing High
Похожий на предыдущий алгоритм, с той разницей, что для каждого следующего прямоугольника ищется место не только на последнем уровне, а начиная с самого нижнего. Отсюда и «first fit» — прямоугольник помещается на первый подходящий уровень снизу. Интуитивно понятно, что упаковка будет качественнее. Еще одно значительное отличие — в производительности, так как в худшем случае придется рассматривать на каждом шагу все уровни снизу вверх.
Видео:1 2 4 сопряжение окружностейСкачать
Best Fit Decreasing High
Модификация предыдущего алгоритма. Суть ее в том, что из уровней, подходящих для упаковки очередного прямоугольника, выбирается не первый, а лучший. Лучший уровень — это такой, на котором останется минимум места после упаковки текущего прямоугольника. Проще говоря, выбирается минимальное подходящее пространство, что способствует лучшему заполнению уровней.
Видео:Расчет сегмента окружности по хорде и длине цилиндрической поверхности (трансцендентное уравнение)Скачать
Knapsack 0-1
Здесь стоит остановиться подробнее. Knapsack 0-1 — это частный случай задачи о ранце; примечателен тем, что кроме ответа на основной вопрос (нет, не 42, а полученный объем упаковки) дает еще и решение — список предметов, которые нужно упаковать. Порядок действий таков: прямоугольники сортируются по не-возрастанию высоты; упаковывается первый прямоугольник на новый уровень; для этого уровня находится решение задачи Knapsack 0-1, которое дает нам список прямоугольников, максимизированный по площади. Выбранные прямоугольники пакуются и извлекаются из списка неупакованных, уровень закрывается и открывается новый — инициализированный, как водится, первым (самым высоким) из оставшихся. Повторить, пока есть прямоугольники.
Видео:Всё про углы в окружности. Геометрия | МатематикаСкачать
Split Fit
Алгоритм, призванный улучшить FFDN по принципу «разделяй и властвуй». Для начала отбираются прямоугольники, которые шире чем половина полосы. Они будут упакованы в первую очередь. Из них выбираются еще более широкие — шире, чем 2/3 полосы; они упаковываются алгоритмом FFDH. Над ними, начиная со следующего уровня (назовем его уровень R), упаковываются оставшиеся, те, что все еще шире 1/2, но уже 2/3. Они тоже упаковываются с помощью FFDH. Это разделение создает свободный регион шириной 1/3 справа от только что упакованных, начинающийся на уровне R и заканчивающийся текущей верхней границей упаковки (то есть он не простирается выше прямоугольников 1/2
Источники вдохновения:
Nthabiseng Ntene An Algorithmic Approach to the 2D Oriented Strip Packing Problem
David Pisinger Knapsack problem
Survey on two-dimensional packing
Level Algorithms and Shelf Algorithms (осторожно, дизайн-вырви-глаз)
Видео:Окружность и круг, 6 классСкачать
Круги в круге
Видео:Как Найти Радиус Сегмента на Потолке. Радиус Окружности По Хорде И Высоте СегментаСкачать
Задача
Чему равен наименьший радиус круга, в котором можно разместить без наложений 7 единичных кругов? Обоснуйте ваш ответ.
Примечание. Единичный круг — круг радиуса 1. «Без наложений» означает, что круги могут касаться, но не должны иметь общих внутренних точек.
Видео:Вписанные и описанные четырехугольники. Практическая часть. 9 класс.Скачать
Подсказка 1
Радиус равен 3, а «оптимальная картинка» выглядит именно так, как вы ее себе, скорее всего, и представили (рис. 1).
Видео:Длина окружности. Математика 6 класс.Скачать
Подсказка 2
Удобно избавиться от понятия «наложение», перейдя от этой задачи к такой:
Рассмотрим вместо кругов только их центры. В круг какого наименьшего радиуса можно их все уместить?
В «оптимальной картинке» все центры являются вершинами и центром правильного шестиугольника со стороной 2 (рис. 2). При этом расстояние между любыми двумя вершинами и центром такого шестиугольника тоже равно 2, поэтому все точки лежат в круге радиуса 2. Нужно обосновать, что все эти точки нельзя уместить в круг меньшего радиуса. Для этого попробуйте рассмотреть случаи, сколько именно (из шести отличных от центра) точек образуют выпуклый многоугольник.
Видео:Окружность вписанная в треугольник и описанная около треугольника.Скачать
Решение
Будем действовать методом «от противного». Предположим, что шесть точек с попарным расстоянием 2 (или большим двух), удалось поместить в круг радиуса R BA и CH > CA. То есть при сдвиге A в H расстояния до точек B и C увеличились.
Наконец, если все точки лежат на единичной окружности, то они делят ее на 6 дуг, поэтому длина наименьшей из дуг не больше, чем 1/6 длины окружности, то есть не больше 2π/6. Это значит, что величина центрального угла этой дуги также не превышает 2π/6, а значит, расстояние между двумя точками, являющимися концами этой дуги, не больше 2sin(π/6) = 1.
Видео:Радиус описанной окружностиСкачать
Послесловие
Эта задача является примером огромного класса так называемых «минимаксных» задач вычислительной геометрии. В минимаксных задачах ищется наибольшее возможное значение какой-то величины, которая сама определена как наименьшее значение другой величины. В нашем случае минимаксная задача (к которой мы свели исходную) была такой: сначала среди всех 15 попарных расстояний между шестью точками в единичном круге выбирается наименьшее, а затем ищется такая конфигурация шести точек, для которой это расстояние будет максимальным из возможных.
Приведенное нами утверждение и его доказательство принадлежат замечательному американскому математику Рональду Грэхему (Ronald Graham), они опубликованы в 1968 году. Грэхем доказал даже более общую оценку для наименьшего расстояния d между какими-то из k точек, лежащих в единичном круге. Эта оценка имеет вид
(то есть d не превышает наибольшего из двух чисел — единицы и удвоенного синуса). Оценка Грэхема является оптимальной для 2 ≤ k ≤ 7, то есть существуют картинки, для которых достигаются значения из правой части этого неравенства. Для больших значений k указанная оценка неточна, поскольку она дает d ≤ 1, а на самом деле наибольшее из возможных значений минимального расстояния между точками строго меньше 1.
Естественное обобщение нашей задачи — поиск кругов наименьшего радиуса, в которые можно поместить N единичных кругов (или, что то же самое, поиск решения минимаксной задачи об N точках в единичном круге). В этом поиске усилия математиков сконцентрировались на двух направлениях — компьютерном моделировании и доказательствах оптимальности. Ниже на рис. 5 показаны несколько очевидных оптимальных картинок.
Оптимальность первых трех из них следует из приведенного выше результата Р. Грэхема. Оптимальность последней (для 8 кругов) была доказана в 1963 году голландцем Boele L. J. Braaksma в его диссертации под труднопроизносимым названием «Асимптотические расширения и аналитические продолжения для одного класса интегралов Барнса». Следующее продвижение, а также оптимальность вот такой вот картинки (рис. 6) с двумя внутренними кругами (для 10 кругов)
было получено немцем U. Pirl в 1969 году. Оптимальность аналогичной картинки для 11 кругов доказана еще на 25 лет позже, а для 12, 13 и 19 кругов — еще позже (последний из результатов — в 2003 году).
И. всё. Остальные результаты об упаковке кругов в круг на сегодняшний день находятся в состоянии «оптимальность предполагается, но не доказана». Так что просто полюбуйтесь на картинки (рис. 7) с доказанной оптимальностью (N = 12 и N = 19) и оцените: всего каких-то 15 лет назад это была терра инкогнита, обе задачи еще ждали своего решателя.
А следующие две картинки (для N = 14 и N = 15 соответственно) являются этой самой «инкогнитой» и сейчас (рис. 8). Дерзайте.
См. также:
1) Circle packing in a circle («Упаковка кругов в круг»). Достаточно детальная статья английской Википедии.
2) Circles in Circles. Страничка Эрика Фридмана, откуда мы позаимствовали большую часть иллюстраций. Там же на соседних страницах packing center рассказано о других задачах упаковки.
3) K. A. Dowsland, M. Gilbert, G. Kendall. A local search approach to a circle cutting problem arising in the motor cycle industry (PDF, 346 Кб). Статья в научном журнале Operational Research Society — международного сообщества, занимающегося исследованием операций, то есть научной дисциплиной, чья основная задача — обоснование оптимальности применения каких-либо научных достижений на практике.
В статье объясняется, как можно оптимизировать изготовление «звездочек» и других профилированных колёс (для зубчатых передач и др.) при производстве велосипедов и мотоциклов. С точки зрения математики — абсолютно ничего нового, но связь с практикой очень забавна. Интересно, появится ли когда-нибудь подобная статья для домохозяек — об оптимизации раскладывания котлет на сковородке?
🎥 Видео
Углы, вписанные в окружность. 9 класс.Скачать
Построение 8 угольника циркулемСкачать
Выборка с помощью окружностиСкачать
Построить описанную окружность (Задача 1)Скачать
Как решать задания на окружность ОГЭ 2021? / Разбор всех видов окружностей на ОГЭ по математикеСкачать
Математика | 5 ЗАДАЧ НА ТЕМУ ОКРУЖНОСТИ. Касательная к окружности задачиСкачать
