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

Метод покрытия прямоугольника конгруэнтными кругами с учётом дополнительных ограничений Текст научной статьи по специальности « Математика»

Видео:Как быстро распределить объекты по окружности в Corel DrawСкачать

Как быстро распределить объекты по окружности в Corel Draw

Аннотация научной статьи по математике, автор научной работы — Панкратов Александр Владимирович, Пацук Владимир Николаевич, Романова Татьяна Евгеньевна, Шеховцов Сергей Борисович

Рассматривается задача покрытия прямоугольника конгруэнтными кругами с ограничениями на размещение покрывающих кругов. Предлагаются методы построения оптимальных покрытий в классе предложенных вариантов модифицированных решёток.

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

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

Похожие темы научных работ по математике , автор научной работы — Панкратов Александр Владимирович, Пацук Владимир Николаевич, Романова Татьяна Евгеньевна, Шеховцов Сергей Борисович

Видео:Создать круг размером по длине прямоугольника для гибкого реза. Corel Draw от ДеревяшкинаСкачать

Создать круг размером по длине прямоугольника для гибкого реза. Corel Draw от Деревяшкина

The method of regular covering of rectangle by congruent circles taking account additional restrictions

The article considers a problem of a covering of rectangle by minimal number of congruent circles. Taking into account restrictions on minimal distances between the centers of circles and the centers of circles and the frontier of region. For solving the problem a lattice covering methods except for frontier of the rectangle are developed.

Видео:Построение эвольвенты окружностиСкачать

Построение эвольвенты окружности

Текст научной работы на тему «Метод покрытия прямоугольника конгруэнтными кругами с учётом дополнительных ограничений»

СИСТЕМЫ И ПРОЦЕССЫ УПРАВЛЕНИЯ

МЕТОД ПОКРЫТИЯ ПРЯМОУГОЛЬНИКА КОНГРУЭНТНЫМИ КРУГАМИ С УЧЁТОМ ДОПОЛНИТЕЛЬНЫХ ОГРАНИЧЕНИЙ

ПАНКРАТОВ А.В., ПАЦУКВ.Н.,

РОМАНОВА ТЕ, ШЕХОВЦОВ С.Б.__________

Рассматривается задача покрытия прямоугольника конгруэнтными кругами с ограничениями на размещение покрывающих кругов. Предлагаются методы построения оптимальных покрытий в классе предложенных вариантов модифицированных решёток.

Задачи покрытия относятся к классу задач геометрического проектирования [1]. Модели и методы решения задач покрытия выпуклой области кругами в различных постановках рассмотрены, например, в 1. В статье предлагается подход, учитывающий дополнительные условия размещения покрывающих кругов.

Многие научные и прикладные задачи имеют следующую постановку.

Существуют реальные объекты, которые имеют форму круга. Они обладают некоторым действием (или чувствительностью детектирования), которое распространяется на окружающую их область, имеющую во многих случаях круговую форму. Требуется, чтобы области действия реальных объектов покрывали некоторую территорию, т.е. каждая точка области находилась в сфере действия хотя бы одного объекта.

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

Пусть имеются: круг C радиуса r , прямоугольник P длины L и ширины H. Полагаем, что центр круга C совпадает с центром собственной системы координат, а начало O собственной системы координат прямоугольника р находится в левой нижней его вершине.

Задача. Построить покрытие прямоугольника P(0) минимальным числом m* кругов C(u;) таких, что

множество (C0(u;),iє Jm> , Jm = , m> m* , образует укладку [1], где C0(ui) c C(ui) —

круги радиуса Го, Го 0 , i Є Jm , (1)

где Ф0i(u0,ui) — нормализованная ф -функция объекта P*(u0) = cl(R2 P(u0)) и круга C0(ui),

Xi(x,y) = -x + A , x 2(x,y) = -y + B ,

Хз(х,у) = x + A , x4(x,y) = y + B ,

A = L/2-r0 , B = H/2-r0 .

В нашем случае u0 = (0,0) .

Условие взаимного непересечения кругов C0(ui) и C0(u j), i ф j, i є Jm , j є Jm , описывается неравенством

где Фij(ui,uj) — нормализованнаяф -функция кругов C0(ui) и C0(uj),

фij(ui,uj) = -(xj -xi)2 + (yj -Уі)2 -2r0 . (4)

Будем искать решение задачи построения покрытия прямоугольника P среди (двойных) решётчатых покрытий [3] и покрытий, близких к решётчатым в определённом далее смысле.

Двойная решётка будет определяться векторами ai, a2 , b , где ai, a2 линейно-независимы (рис. 1).

Рис. 1. Решётчатое покрытие

Общая схема построения таких покрытий состоит в следующем.

Формируем множество трансляций

a1 = (a1x,0) = ^|a^|,0)>’ a0,a1 є r2. ^ ^

Здесь Ц-Ц — евклидова норма; k — число трансляций.

Пусть |a^| = 2ц, ц L , L1 L , то kmin > kmin

т.е. yj > r0 (см.(3)) имеем kmin > kr

Из условия (3) получаем оценку для k: kr

Следует заметить, что при r0 3r0 можно

получить оценку kmax Выбираем

k є [kmin,kmax] П 3,3 = .

Множество T1 (5) образует 1-й ряд покрытия (см. рис. 2).

Аналогично построим второй ряд покрытия

таким образом, что T2 покрывает прямоугольник U2 , причём k’ = k или k’ = k +1, intU1 Пint U2 =0 и T1 U T2 покрывает [0, L] х [0,2w + 8], 0 Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Таким образом, круги Cл , C;kj могут нарушать регулярность решётчатого покрытия.

Пусть рх. — прямая, проходящая через центры кругов ряда Т., рXi описывается уравнением y = 2w .

Обозначим g — расстояние между прямыми рX1 и Pxi (для всех типов покрытий, рассматриваемых ниже, g = r2 -ц2 ), h—расстояние между прямыми рх1 и Px2 (рис 2).

Число n рядов покрытия находится из условия

2g + (n-1)(g + h) = H), тогда n

функция [•] определяет минимальное целое, не меньшее её аргумента.

Если vn1 + r0 > H , (7)

то уменьшаем h в целях выполнения условия (1), что всегда возможно при r0 Г0 приведут к увеличению функции цели). Заметим, что точка х = 0 недопустима при Г0 > 0 .

Найдём минимальное допустимое значение х є [0,r0] .

Система уравнений для определения х имеет вид:

2kp = L + 2х g = у[т

; + r = sjr2 -r02 +yjr2 + (p-х)2

2 I L + 2х lr -I——— I + r =

=*ir2 — r02 +a h2-1^ -х

Уравнение (10) можно решить аналитически или численно (в программной реализации применялось численное решение).

Для метода 1 (рис. 3) используются:

h = r, G = (0,0,1,1), Q = (—х, х, -х, х),

D = (0,0, х + r0, -х — fy) .

Рис. 3. Вариант построения покрытия методом 1 Метод 2.

Используется вариант (k, k). Положение кругов C11, C21 рядов Т1, Т2 аналогично их положению в методе 1, а положение кругов C2k, C^ аналогично положению кругов C3k , C2,k+1.

Построение решетки и определение смещения X аналогично методу 1. Первое равенство в системе

(9) заменяется на (2k — 1)ц = L + 2х .

Для метода 2 (рис. 4) используются:

h = r, G = (0,1, ОД), Q = (-х,х, -х,х),

D = (0, -х — Го, х + Г0,0) .

Рис. 6. Вариант построения покрытия методом 4 Метод 5.

Используется вариант (k, k). Первый ряд строим таким образом, чтобы последнее пересечение кругов совпадало с l , а первое сдвигалось на некоторую величину х (которую мы ниже оптимизируем) относительно 0 влево.

Рис. 4. Вариант построения покрытия методом 2

Применяется вариант (k, k).

1. C11 П C(d1 — a1) є p0, абсцисса центра C21 равна r0.

2. C2k П C(d2 + (k + 1)a1) є pL .

Зависимость для ц и k имеет вид: (2k — 1)ц + Г0 = L . Для метода 3 (рис. 5) используются:

h =7r1 2 -r02 , G = (0,1,0,! , Q = (0,-r0,D,0,

Рис. 5. Вариант построения покрытия методом 3 Метод 4.

Применяется вариант (k, k +1).

1. Положение Cn , C 21 такое же, как и в методе 3.

2. C2,k+1 П C(d2 + (k + 2)a1) є Pl . Абсцисса центра последнего круга ряда T2 равна L — r0 (отражаем последний круг относительно прямой х = l ).

Значение ц находим из формулы: 2k ц = L .

Для метода 4 (рис. 6) используются:

h =УІr2 -r02 , G = (0,0,1,! , Q = (0,0,Г0,Г0) ,

Чтобы удовлетворить условию (1), поворачиваем круг ряда T2 , абсцисса центра которого совпадает с абсциссой точки пересечения кругов Cn и C12 на угол у , таким образом, чтобы точка пересечения круга C11 и прямой Р0 (с большим значением ординаты) принадлежала frC21 (см. рис. 5).

Пусть х0 = ц — х — абсцисса центра круга Cn .

Высота x(n, х0) определяется следующим образом:

Определим х0 = argminmax %(n, х0) при условии

Получим х = Ц-х0 при условии Ц-х0 >r0 (следует из построения ряда T1).

Оценим пределы, в которых может находиться n . Максимальное n находим из покрытия, заданного следующими значениями (см. рис. 6): х = 0 , L = 2kц, 2g + (n — 1)(g + h) = H , где h = r0 ; т.е. считать для

+1 = [(H-2r’)(r’+ r0)] , здесь

h -r0, r’ = -Jr2 -(2k)2 + r0.

Минимальное n из покрытия, заданного следующими значениями (рис. 7):

L -r0 = (2k — 1)ц, 2g + (n — 1)(g + h) = H , где h = g , 2g + 2g(n -1) = H , 2gn = H ,

Г H ] HJr2 (L r° 1

Для метода 5 (рис. 7) используются:

L + x — 2кц , h = r cos у = yj r2 — (p-x)2 >

G = (0,0,1,1), Q = (-x, 0,2p-rsiny, 0, D = (0,0,0,0 .

Рис. 7. Вариант построения покрытия методом 5

Например, для значений L = 2.5 , H = 3 , r = 1, Г0 = 0.3 метод 5 оптимален.

Из всех m , полученных методами 1—5, выбираем минимальное m *.

Научная новизна. Предложены методы построения покрытий прямоугольника кругами, решётчатых, за исключением, возможно, границы области покрытия. Каждый из предложенных методов может давать оптимум при определённом наборе соотношений L , H , r , r0 . Оценка покрытия близка к теоретически оптимальной при L >> r, H >> r.

Практическая ценность. Предложен точный метод построения покрытий в классе предложенных вариантов модифицированных решёток, при этом учтены одновременно условия покрытия и размещения, что важно для практических приложений, например, при построении систем автоматической противопожарной защиты.

Сравнительный анализ. В работе [3] предложен альтернативный подход к решению аналогичной задачи, однако при этом не учитываются дополнительные условия на размещение покрывающих кругов.

РЕШЕНИЕ ЗАДАЧИ УПАКОВКИ КРУГОВ В ВЫПУКЛЫЙ МНОГОУГОЛЬНИК С ПОМОЩЬЮ МОДИФИЦИРОВАННОГО МЕТОДА СУЖАЮЩИХСЯ ОКРЕСТНОСТЕЙ

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

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

Литература: 1. Стоян Ю. Г., Яковлев С. В. Математические модели и оптимизационные методы геометрического проектирования. К.: Наук. думка, 1986. 267 с. 2. Антошкин А.А., Панкратов А.В., Пацук В.Н., Романова Т.Е, Шеховцов С.Б. Задача покрытия прямоугольной области кругами заданного радиуса // Радиоэлектроника и информатика. 2001. № 3. С. 38 — 41. 3. Панкратов А.В., Пацук В.Н., Романова Т.Е, Антошкин А.А. Метод регулярного покрытия прямоугольной области кругами заданного радиуса // Радиоэлектроника и информатика. 2002. № 1. С. 50 — 52. 4. Стоян Ю.Г., Яковлев С.В. Оптимизация покрытий трансляциями ограниченных множеств// Докл. АН УССР. Сер.А, 1988. № 7.- С.20-23. 5. RogersC.X. Packings and Coverings. Cambridge: University Press, 1964. 6. СтоянЮ.Г. Об одном обобщении функции плотного размещения//Докл. АНУССР. Сер. A. 1980. №8. С. 70-74. 7. KuperbergG. Double-lattice packing of convex bodies in the plane/G.Kuperberg and W.Kuperberg/ /Discrete and Comp. Geometry. 1990. № 5. P. 389-397.

Поступила в редколлегию 27.08.2004

Рецензент: д-р физ.-мат. наук, проф. С.В. Яковлев

Панкратов Александр Владимирович, канд. техн. наук, научный сотрудник отдела математического моделирования и оптимального проектирования Института проблем машиностроения НАН Украины им. А.Н. Подгорного. Адрес: Украина, 61046, Харьков, ул. Пожарского, 2/10, тел. (0572) 95-95-36.

Пацук Владимир Николаевич, канд. техн. наук, старший научный сотрудник отдела математического моделирования и оптимального проектирования Института проблем машиностроения НАН Украины им. А.Н. Подгорного. Адрес: Украина, 61046, Харьков, ул. Пожарского, 2/10, тел. (0572) 95-95-36.

Романова Татьяна Евгеньевна, д-р техн. наук, старший научный сотрудник отдела математического моделирования и оптимального проектирования Института проблем машиностроения НАН Украины им. А.Н. Подгорного. Адрес: Украина, 61046, Харьков, ул. Пожарского, 2/10, тел. (0572) 95-95-36.

Шеховцов Сергей Борисович, канд. техн. наук, доцент кафедры прикладной математики Национального университета внутренних дел. Адрес: Украина, 61180, Харьков, пр. 50-летия СССР, 27, тел. (0572) 50-30-67.

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

Задача упаковки кругов относится к классу задач оптимизационного геометрического проектирования. Математические модели и методы размещения кругов в прямоугольной полосе рассматривались в работах [1,2]. В [3] рассмотрен подход к поиску глобального экстремума задачи упаковки кругов равного радиуса в квадрате. Малоисследованными остаются задачи упаковки кругов одинакового радиуса в произвольные односвязные и многосвязные области. Данные задачи являются многоэкстремальными, что вызывает трудности при их математическом и компьютерном моделировании. Эти трудности, в частности, связаны с отсутствием приемлемых способов перебора многочисленных локальных экстремумов. В статье предлагается новый альтернативный подход к решению задачи упаковки кругов, основанный на направленном переборе локальных экстремумов, что позволяет находить лучшие приближения к глобальным экстремумам.

Видео:Как растянуть узор по кругу или вдоль пути. Corel Draw от ДеревяшкинаСкачать

Как растянуть узор по кругу или вдоль пути. Corel Draw от Деревяшкина

Про двумерную упаковку: offline алгоритмы

Сегодня, дорогой Хабр, я расскажу тебе историю о комбинаторной оптимизации.
Издревле (как минимум, с начала прошлого века) математики задавались вопросом, как оптимально разместить некоторое количество пива нужных и полезных предметов в рюкзаке. Была сформулирована задача о ранце и ее подзадачи — тысячи их! — которые заинтересовали информатиков, криптографов и даже лингвистов.

От задачи о ранце отпочковалась задача об упаковке в контейнеры (Bin Packing Problem), одной из разновидностей которых является задача двумерной упаковки (2-Dimensional Bin Packing). Снова отбросив несколько вариаций, мы наконец придем к двумерной упаковке в полуограниченную полосу (2-Dimensional Strip Packing, 2DSP). Чувствуете, сколько интересного уже осталось за кадром? Но мы еще не закончили продираться сквозь классификацию. У 2DSP есть два варианта входных данных: когда набор упаковываемых объектов известен заранее (offline-проблема) и когда данные поступают порциями (online-проблема).

В этой статье рассматриваются алгоритмы решения offline-варианта 2DSP. Под катом немного матчасти и много картинок с цветными квадратиками.

Видео:Как скруглить углы прямоугольника в CoreldrawСкачать

Как скруглить углы прямоугольника в Coreldraw

В чем, собственно, проблема?

Как частный случай задачи двумерной упаковки, 2DSP заключается в упаковке объектов конкретной формы в конечное число контейнеров конкретной формы таким способом, чтобы число использованных контейнеров было наименьшим или количество или объем объектов (которые упаковывают) были наибольшими. Разница с двумерной упаковкой состоит в том, что есть только один контейнер, и вместо минимизации количества контейнеров, мы минимизируем высоту заполненности одного. Обеспечиваем максимальную плотность упаковки, если хотите.

Так как проблема NP-трудная, исследования сфокусированы главным образом на разработке приближенных алгоритмов решения. (На Хабре упоминался генетический алгоритм). Приближенные алгоритмы находят оптимальное решение с определенной точностью, но не гарантируют оптимальной упаковки для любого набора данных. При этом критерий оптимальности зависит от того, что вы пытались оптимизировать.
Я расскажу о простейших стратегиях и о том, к чему это все применимо в жизни (кроме рюкзака с пивом).

Итак, имеем набор из n прямоугольников и полуограниченный контейнер-стакан с фиксированной шириной W и бесконечной высотой. Каждый прямоугольник по ширине не превышает W. Задача — уложить прямоугольники в стакан без наложений и пересечений так, чтобы стакан стал как можно менее полон. Условимся, что все прямоугольники должны быть упакованы ортогонально, их нельзя поворачивать.

Оптимальное размещение окружностей в прямоугольникеОптимальное размещение окружностей в прямоугольникеОптимальное размещение окружностей в прямоугольникеОптимальное размещение окружностей в прямоугольнике
Исходные данные
(начало XX века, кубизм)
Полуограниченная полосаВариант упаковки (похуже)Вариант упаковки (получше)

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

Видео:8 класс, 31 урок, Взаимное расположение прямой и окружностиСкачать

8 класс, 31 урок, Взаимное расположение прямой и окружности

Зоопарк алгоритмов

Для offline варианта 2DSP сразу известен размер всех упаковываемых прямоугольников, поэтому их можно отсортировать, выбрать по определенному критерию, сгруппировать или просто натыкать в подходящие места. На этом и основываются большинство алгоритмов:

  1. уровневые (level)
  2. шельфовые (shelf)
  3. плоские (plane)

Плоские алгоритмы размещают прямоугольники строго вплотную друг к другу, но это не самая удачная стратегия, как может показаться на первый взгляд. Уровневые делят полосу на уровни, равные по высоте одному из выбранных прямоугольников, и помещают все остальные на конкретный уровень по определенному критерию. Шельфовые предопределяют сразу несколько шельфов (полок), и распихивают по ним прямоугольники, такое поведение характерно для online-алгоритмов, а это уже совсем другая история.

Чем распространяться на общие слова, лучше обо всем по порядку.

Видео:Оптимальное распределение или экономная раскладка. Лазерная резка и Corel Draw от ДеревяшкинаСкачать

Оптимальное распределение или экономная раскладка. Лазерная резка и Corel Draw от Деревяшкина

Next Fit Decreasing High

Оптимальное размещение окружностей в прямоугольникеОптимальное размещение окружностей в прямоугольнике
Алгоритм, что называется, «в лоб». Прямоугольники сортируются по не-возрастанию высоты (Decreasing High намекает), самый высокий располагается в левом нижнем углу полосы, тем самым инициализируя первый уровень, по высоте равный ему. Остальные прямоугольники располагаются слева направо, пока есть место на текущем уровне. Прямоугольник, который не поместился на уровне, помещается сверху, образуя следующий уровень, и так далее.
Иллюстрации для каждого алгоритма будут производиться для следующих двух примеров: для наглядности, в левом форма прямоугольников тяготеет к вытянутой, в правом — более квадратные.

Видео:Взаимное расположение окружности и прямой. 7 класс.Скачать

Взаимное расположение окружности и прямой. 7 класс.

First Fit Decreasing High

Оптимальное размещение окружностей в прямоугольникеОптимальное размещение окружностей в прямоугольнике
Похожий на предыдущий алгоритм, с той разницей, что для каждого следующего прямоугольника ищется место не только на последнем уровне, а начиная с самого нижнего. Отсюда и «first fit» — прямоугольник помещается на первый подходящий уровень снизу. Интуитивно понятно, что упаковка будет качественнее. Еще одно значительное отличие — в производительности, так как в худшем случае придется рассматривать на каждом шагу все уровни снизу вверх.

Видео:Взаимное расположение окружностей. 7 класс.Скачать

Взаимное расположение окружностей. 7 класс.

Best Fit Decreasing High

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

Видео:Окружность и прямоугольник Corel DrawСкачать

Окружность и прямоугольник Corel Draw

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 (осторожно, дизайн-вырви-глаз)

Видео:Сетка под быстрый раскрой прямоугольников с помощью панели макросов для Corel Draw от ДеревяшкинаСкачать

Сетка под быстрый раскрой прямоугольников с помощью панели макросов для Corel Draw от Деревяшкина

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

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

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

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

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

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

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

💡 Видео

ПОСТРОИТЬ ПРАВИЛЬНЫЙ ПЯТИУГОЛЬНИК [construction a regular pentagon]Скачать

ПОСТРОИТЬ ПРАВИЛЬНЫЙ ПЯТИУГОЛЬНИК [construction a regular pentagon]

Донышко 2 или как распределить объект не только по окружности, но и по кривой.Скачать

Донышко 2 или как распределить объект не только по окружности, но и по кривой.

ПОСТРОИТЬ ПРАВИЛЬНЫЙ 11-УГОЛЬНИК [construction of regular hendecagon]Скачать

ПОСТРОИТЬ ПРАВИЛЬНЫЙ 11-УГОЛЬНИК  [construction of regular hendecagon]

Сможешь найти радиус окружности? Окружность, вписанная в прямоугольный треугольникСкачать

Сможешь найти радиус окружности? Окружность, вписанная в прямоугольный треугольник

Команды "RECTANGLE" - прямоугольник, "POLYGON" - многоугольникСкачать

Команды "RECTANGLE" - прямоугольник, "POLYGON" - многоугольник

Разбираем урок из Азбуки КОМПАС-График "Распределитель"Скачать

Разбираем урок из Азбуки КОМПАС-График "Распределитель"

Как распределить объекты вдоль кривой или произвольного пути. Corel Draw от ДеревяшкинаСкачать

Как распределить объекты вдоль кривой или произвольного пути. Corel Draw от Деревяшкина
Поделиться или сохранить к себе: