Реклама i
Стань нашим партнером - зарабатывай с нами!
| Правила | Регистрация | Пользователи | Поиск | Сообщения за день | Все разделы прочитаны |  Справка по форуму | Файлообменник |

Вернуться   Форум DWG.RU > Программное обеспечение > Программирование > Оптимальное размещение окружностей в прямоугольнике

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

Ответ
Поиск в этой теме
Непрочитано 05.10.2017, 19:01 #1
Оптимальное размещение окружностей в прямоугольнике
kefirrr
 
Регистрация: 29.12.2014
Сообщений: 28

Здравствуйте, уважаемые форумчане!

Снова обращаюсь к Вам за помощью.
Суть проблемы такова: есть прямоугольник с известными сторонами, и есть N окружностей с разными диаметрами .Нужно эти окружности разместить внутри прямоугольника как можно оптимальнее. (см. приложенный файл)

Может быть подскажете или наведете на мысль как это программно осуществить. Может есть какой-нибудь алгоритм, чтобы его можно было реализовать.

Если кто готов поделиться своими наработками- буду премного благодарна. Но я "программирую" только на VBA. Если есть готовые примеры на LISP- то можете объяснить что там и к чему


Заранее всем, кто проявил интерес- СПАСИБО

Вложения
Тип файла: dwg
DWG 2004
Прямоугольник и окружности.dwg (57.7 Кб, 187 просмотров)

Просмотров: 10166
 
Непрочитано 05.10.2017, 19:16
#2
Liukk

нестандартное оборудование, Пневмо-Гидро Системы
 
Регистрация: 28.12.2011
СПб
Сообщений: 1,707


Как решать подобные задачи проходили на курсе высшей математики (нахождение экстремумов функции в диф. и интегр. исчислении). Осталось только формализовать уравнение расположения окружностей в прямоугольнике (тут см. аналитическую геометрию)
Liukk вне форума  
 
Непрочитано 20.10.2017, 15:23
#3
KiisteN


 
Регистрация: 09.08.2014
Сообщений: 5


Цитата:
Сообщение от Liukk Посмотреть сообщение
Как решать подобные задачи проходили на курсе высшей математики (нахождение экстремумов функции в диф. и интегр. исчислении). Осталось только формализовать уравнение расположения окружностей в прямоугольнике (тут см. аналитическую геометрию)
Простите, что вмешиваюсь...
Я когда-то тоже хотел решить эту задачу. И да, мне не хватило знаний математики...
Только вот это другой раздел математики, нежели Вы перечислили! Это Комбинаторика - подраздел теории вероятности.
Я даже хотел изучить "мат.часть" данного раздела математики, но НЕАСИЛИЛ ((
KiisteN вне форума  
 
Непрочитано 20.10.2017, 16:02
#4
Bendaho

Проектный Институт СпецКонсалтИнжиниринг
 
Регистрация: 24.03.2015
Питер
Сообщений: 85


Простите и меня за вмешательство...
Увидел достаточно известную задачу, над которой ранее тоже ломал голову.
Как уже было сказано выше это комбинаторика.
Для окружностей равного диаметра задача тривиальна - гуглим "упаковка шаров".
Для окружностей разного диаметра - известных мне математических моделей нет. По крайней мере лет 10-15 назад.
У нас была подобная задача. Программисты потребовали ввести дополнительные параметры.
Мною было предложено принять набор конкретных диаметров окружностей.
У нас были трубопроводы - возможные диаметры известны.
После этого уже был написан алгоритм. Суть алгоритма не знаю. Решали ребята с мех-мата НГУ.
Мне выдавалось уже готовое решение в графическом виде.

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

P.S. И да, само понятие оптимальности требует формулировки. То есть численных (формульных) критериев.

Про алгоритмы похожей задачи интересно на хабре https://habrahabr.ru/post/136225/
Про выбор модели http://www.ugatu.su/assets/files/doc...eevIS/diss.pdf


То есть я все это писал дабы показать что задача непроста даже с точки выбора модели расчета.

Последний раз редактировалось Bendaho, 20.10.2017 в 16:39. Причина: добавил..
Bendaho вне форума  
 
Непрочитано 20.10.2017, 20:05
#5
Liukk

нестандартное оборудование, Пневмо-Гидро Системы
 
Регистрация: 28.12.2011
СПб
Сообщений: 1,707


Цитата:
Сообщение от Bendaho Посмотреть сообщение
Для окружностей разного диаметра - известных мне математических моделей нет.
А ведь именно это и было указано в качестве ТЗ. И именно для этого и нужно диф. исчисление (нахождение локальных экстремумов функции), а не комбинаторика.
Liukk вне форума  
 
Непрочитано 21.10.2017, 22:29
#6
zamtmn

КИПиА
 
Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
<phrase 1=


много материала по теме и около http://mathworld.wolfram.com/CirclePacking.html
zamtmn вне форума  
 
Непрочитано 23.10.2017, 23:38
#7
veb86

Проектировщик электрических сетей
 
Регистрация: 17.01.2014
Пенза
Сообщений: 176


Я склонен считать что это решается генетическими алгоритмами. Вот интересная работа, которая указывает направление движения. http://vestnik.sibsutis.ru/uploads/1372915760_1066.pdf
veb86 вне форума  
 
Непрочитано 26.10.2017, 15:10
#8
kp+

идущий по граблям
 
Регистрация: 26.05.2005
Сообщений: 5,091


Цитата:
Сообщение от kefirrr Посмотреть сообщение
Может быть подскажете или наведете на мысль как это программно осуществить. Может есть какой-нибудь алгоритм, чтобы его можно было реализовать.
Есть. Отсюда: http://citeseerx.ist.psu.edu/viewdoc...=rep1&type=pdf
Если не понравится, в гугле еще много ссылок по запросу "circle packing in rectangle algorithm"
Вот на С# https://www.codeproject.com/articles...hm-ported-to-c
Вложения
Тип файла: pdf 10.1.1.99.5620.pdf (132.0 Кб, 94 просмотров)

Последний раз редактировалось kp+, 26.10.2017 в 15:19.
kp+ вне форума  
 
Непрочитано 27.10.2017, 15:57
#9
Tom2k7


 
Регистрация: 11.10.2011
Сообщений: 25


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

я раскладывал кабель в лотке
причем сделал в начале плотную упаковку, а потом добавил обвязку кабеля в пучки, там внутри 3 варианта, определяются константой CalcMode

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

условия пересечения новых с установленными проверяются функцией nocollizion
сами касания обзываются tryLeft, TryPair и т д.
CalcTrunk вызывает их все, с учетом метода расчета
как бы и все

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

проблемы были с точностью расчетов, не все коллизии отрабатывались

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

да, верхняя граница не проверяется, потому что все равно все отрисовывалось на экране как есть
Вложения
Тип файла: zip Trunk.zip (3.3 Кб, 102 просмотров)

Последний раз редактировалось Tom2k7, 27.10.2017 в 16:11.
Tom2k7 вне форума  
Ответ
Вернуться   Форум DWG.RU > Программное обеспечение > Программирование > Оптимальное размещение окружностей в прямоугольнике

Размещение рекламы
Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Какой язык перспективен для инженера-конструктора с условием The_Mercy_Seat Программирование 705 17.03.2021 14:19
Допустимо ли в подвальном этаже размещение санузла располагающегося под эвакуационной ЛК и непосредственно не граничащего с маршем этой ЛК ? myhome Архитектура 8 19.07.2017 20:48
как считать координаты окружностей ua3rad Программирование 12 19.11.2012 09:59
Возможно ли размещение небольшого гостиничного комплекса на территории промышленного предприятия ? OlgaSmith Технология и организация строительства 3 10.05.2011 17:08
Как при помощи лиспа нарисовать цепочку окружностей вдоль воображаемой линии Serge_BN LISP 8 18.03.2010 20:32