Устройство для моделирования размещения плоских геометрических объектов

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 09) (И) ЗОБРЕТЕТЕЛЬСТВУ ИОАН ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ К АВТОРСКОМУ СВИД(71) Институт проблем машиностроения АН УССР(56) . Патент США В 3596068,кл. 235-15 О, опублик. 1971.2. Авторское свидетельство СССРВ 613642, кл. С Об Р 7/38, 1971.(54)(57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ РАЗМЕЩЕНИЯ ПЛОСКИХ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ, содержащее блок распределения информации, который содержит две матрицы элементов И почислу информационных входов устройства в каждой матрице, блок формирования годографа, выполненный ввиде матрицы ячеек формирователя,каждая из которых состоит из первого триггера, первый блок коммутации, блок хранения годографа, выполненный в виде матрицы триггеров,блок запоминания области размещенияобъекта, блок формирования стробирующего сигнала, который состоитиэ матрицы элементов И, группы элементов ИЛИ, элемента ИЛИ и формирователя импульса, и блок управлениякоторый состоит из четырех элементов И, трех формирователей импульсов,первого триггера, первого элементазадержки, счетчика перебора элемен.тов п.п-мерного поля размещенияобъекта и генератора тактовых импуль"сов, первые входы одноименных элементов И каждой матрицы блока распределения информации объединеныи подключены к соответствующемуинформационному входу устройства,выходы элементов И первой матрицы блока распределения информации соединены с одноименными .информационными входами блока запоминания области размещения объекта, выходы элемен" тов И второй матрицы блока распреде" ления информации соединены с единичными входами первых триггеров одноименных ячеек формирователя блока формирования годографа, а выходы первых триггеров матрицы ячеек формирователя блока формирования годографа соединены с одноименными ин" формационными входами первого блока коммутации, выходы которого соединены с единичными входами одноименных триггеров матрицы блока хранения годографа, первые входы элементов И матрицы блока формирования строби" рующего сигнала подключены к од-. ноименным выходам блока запоминания области размещения объекта, а выходы. элементов И каждого столбца матрицы . блока формирования стробирующего сигнала через соответствующий эле" мент ИЛИ группы соединены с соответствующим входом элемента ИЛИ, выход которого соединен с входом формирователя импульса блока формирования стробирующего сигнала, выход которого соединен с управляющим входом первого блока коммутации, выход генератора тактовых импульсов блока , управления соединен с первыми входа" ми элементов И блока управления, второй вход первого из которых является входом запуска устройства, а выход первого. элемента И через первый формирователь импульса соеди ,нен с нулевыми входами первых триггеров ячеек формирователя блока фор 14131200295Б 1, так, чтобы вектор параметров раэмещения Р к удовлетворял условию( Р 1= (р,125 Считая теперь объект Бнеподвижным, т.е. зафиксировав значение Рг аналогично находим параметры размещения очередного объекта Б к и т.д .Пусть объекты Б, Бк Б К -1 О уже размещены. Будет считать все ранее размещенные объекты неподвижными. Согласно послвдавательности А далее необходимо размещать объект Бг,Функция цели для размещения т объектов принимает видХ =(Р 1 Рк ), Р е С(1=1,2 т) Считая значения векторов Р Р 1 фиксированными, разместим в абраг ласти Б/(Б ООБ .,) объект Бтак, чтобы вектор ега параметров размещения удовлетворял условию"лЛ-А Р) гу ,1 г 1 г 25На фиг. 1 приведена блок-схема устройства для моделирования размещения плоских геометрических объектов; на фиг. 2 - блок-схема блока распределения информации; на фиг, 3 - блоксхема блока формирования годографа; на фиг. 4 - схема ячейки формирователя; на фиг. 5 - блок-схема блока хранения гадаграфа; на фиг, 6 - схема блока формирования страбирующего сигнала; на фиг. 7 а, 6 и 8- схема35 блока управления; на фиг. 8 а, 6 и 8 - временные диаграммы работы устройства; на фиг, 9 - схема блока вычисления экстремальных точек годаграфа;40 на фиг. 10 - пример размещения плоских геометрических объектов.Устройство для моделирования размещения плоских геометрических объек тов содержит блок 1 распределения45 информации, блок 2 формирования гадографа, блок 3 коммутации, блок 4 хранения годографа, блок 5 запоминания области размещения объекта, блок 6 формирования стробирующего сигнала, блок 7 управления, дешифра 50 тор 8 состояний, блок 9 запомина - ния параметров размещения объектов, блок 10 коммутации, блок 1 запоминания конфигурации объекта, блок 12 вычисления экстремальных точек года- графа и информационные входы 13.Блок 1 распределения информации содержит матрицы 4-16 элементов И,содержащие соответственно элементы И 17-9 и выходы 20-22.Блок 2 формирования годографа содержит ячейки 23 формирователя, содержащие (фиг, 4 ) триггеры 24 и 25, элементы ИЛИ 26 и 27, элементы И 28-33 и информационный выход 34.Блок 4 хранения годографа содержит триггеры 35, информационные входы 36 и информационные выходы 37 и 38.Блок 6 формирования стробирующего сигнала содержит матрицу 39 элементов И, группу 40 элементов ИЛИ, элемент ИЛИ 41 и формирователь 42 импульса, Матрица 39 содержит элементы И 43, группа 40 - элементы ИЛИ 44.1Блок 7 управления содержит генератор 45 тактовых импульсов, элементы И 46-65, формирователи 66-85импульсов, элементы 86-89 задержки,триггеры 90-103, счетчик 104 перелбора элементов п.п-мерного поляразмещения объекта, счетчик 105перемещений объекта,по абсциссе,счетчик 106 перемещений объекта поардинате, схемы 107 и 108 сравнения,регистр 109 абсциссы, регистр 110ардинаты, вход 111 запуска, вход112 записи области размещения объекта и вход 113 записи объекта.Блок 12 вычисления экстремальныхточек гадографа содержит матрицы114 и 115 элементов И, элементыИЛИ 116 и 117, выходы 118 и 119и входы 120-123,На временных диаграммах работыустройства введены следующие обозначения:- импульс начальной установки;с - импульс записи области размещения;Со - импульс начальной установки(т=12 с) - импульс стробирогдвания элемента И 43 блока 6, конечного в строке т;т " (=с д) - импульс стробираваниягэлемента И 43 блока б, конечногов матрице;- импульс переписи (со стирагЫ1нием) содержимого триггера 25 ячей15 1200295ки 23; формирователя в триггер 24ячейки 23 п и с вПри поступлении запускающего имоб ь-м объекте вниз;ячейки 3;, при сдвиге информации пульса на вход 111 ззапуска синхронте вниз; но с тактовым сигналом генератора- импульс переписи .(со стиранием) 45 на выходе формирователя 66 формисодержимого триггера 24 ячейки 235 Ру" "мпульс Оъ который устанавформирователя в триггер 25 ячейки23ает в исходное состояние блоки фо ма ии обформирователя при сдвиге ин, 4, 5, 9 и 11 ешиормации об -м объекте вправо построке; 106, регистры 109 и 110 и триггеры й 5 - импульс переписи (со стиранием) О 90-103 блока 7 управления.По сигнасодержимого триггера 25 ячейки 2311лу на входе на выходе формиравалу 112 формирователя в триггер 24 ячейки . 67 ф23 о ми ователя формируется сигнал Сформирователя при сдвигеПо сигналу сигналу с на входе блока информации вправо по строкеУраспределения информации информаС - импульс переписи ( со сти анир - 15 ция о множестве точек, принадлежаем ) содержимого триггера 24 ячейки23щих о ъекту(область размещеб/3; формирователя в триггер 25 той ния), с входов 13 устройства запиже ячейки при сдвиге инфо ма ифр циоб сывается. в блок 5 запоминания облас 1-м объекте влево по строкей - имп льсУти Размещения объекта. По сигналу й - импульс переписи 1,со стиранием) гО на входе 13 на выходе формирователя содержимого триггера 25 ячейки 23 69 формируется сигнал с формирователя в триггер 24 ячейки23; ),1 формирователя при сдвиге По сигналу с на. входе блока ,1 информации влево по ст о еС 1 - импульс кон ароке, распределения информации информация- импульс конца построения годо" 25 о множестве точек, принадлежащих графа д-го объекта с областью раз- объекту Я, (первому из заданной мещения последовательности А ), с входов с - импульс поиска абсциссы экст устройства записьвается в блок ре алькой точки годографа; 2 формирования годографа. По этому с 5- импульс дешифрации значения ЗО же сигналу с, на входе блока 1 раса 0 сциссы; пределения информации информация с- импульс записи абсциссы в об объекте Я; записьвается в блок блок 9 запоминания параметров разме запоминания конфигурации объекщения объектовюта. В блоке 9 запоминания параметров с 1 у - импульс поиска ординаты экст Размещения объекта сигналом с отремальной точки го ог афа мечается номер размещаемого объекта.35 та сигналом с 1 от су " импульс дешифрации значенияордииаты;Задним фронтом импульс суста" с- импульс записи ординаты внавливает триггеры 90 и 91 блока 7 блок 9 запоминания параметров разме- управления в единичное состояние40У щения объектов; разрешающее прохождение тактовых с - импульс записи значений абсцис- сигналов через элементы И 50 и 51. сы и ординаты экстремальной точки го- Далее выполняется построение гододографа в регистры 109 и 110 соответ- рафа векторной функции плотногоУ 45размещения объекта Я. в области.1с - импульс сдвига информации об Р щ "и" од"м объекте в блоке 11 .по абсциссе; По тактовому импульсу С счетчик с 1 1 - импульс сдвига информации об 104 устанавливается в д,3-е состоя-м объекте в блоке 11 по ординате; ние (1=112с; . 1,2, д) На)фс - импульс записи в блок 5 инфор- соответствующем выходе счетчика мации об -м объекте (из блока 11), 104 формируется разрешающий сигимпульс конца размещения 1 го налПо сигналу11 на входе объекта (начальная установка отдель- блока б формирования стробирующего ных блоков, подготовка устройства сигнала (Фиг. 3 ) проверяется налидля размещения очередного объекта чие информации об объекте Яо в соиз заданной последовательности ). 55 ответствующем триггере (не показан )блока 5 запоминания, Если в п овеУстройство работает следующим обров,ераэом.ряемом триггере информация об боласти Я записана, то на выходе17 1200295 18 формирователя 42 блока 6 формиру- чек годографа находит в области ется импульс переписи, т.е. Форми- Г=8 О 8., М(х,у)68 ь точку с минималь рования импульса переписи не проис" ным значением абсциссы. ходит. По импульсу переписи содер- Далее вырабатывается сигнал. с 5 жимое блока 2 через блок 3 коммутации 5 по которому найденное значение абс" переписывается в блок 4 хранения го" циссы дешифрируется в дешифраторе 8 дографа без стирания ранее записан- состояний. По сигналу сзначение иой в нем информации. абсциссы экстремальной точки годоПо сигналу С на вьпсоде формиро- . графа записывается в блок 9 запомивателя 71 содержимое триггеров 24 10 нания параметров размещения объекячеек 23 формирователя переписы- та. По сигналусблок 12 вычис вается асс етнранием) в триггеры ления экстремальных. точек годографа 25 тех же ячеек, а-по сигналу йф определяет. ординату найденной экстна выходе формирователя 72 - из , ремальной тачки. триггеров 25 ячеек 23; формировате.ля в триггеры 24 ячеек 23+ фор- Далее вырабатывается сигналс мирователя, т.е. осуществляется сдвиг 1 по которому найденное значение орсодержимого блока 2 формированиядинаты дешифрнруется в дешифраторе годографа вправо на один шаг. 8 состояний. По сигналу сзначени 1Далее цикл повторяется до уста ординаты экстремальной точкигодоновки счетчика 104 в состояние, крат- графа записывается в блок 9 эапоное числу шагов сдвига по строке,минания параметров размещения объпо которому на выходе счетчика 104 екта. Затем вырабатываетея сигнал формируется сигнал 1" (у=1,2с). с,.,по которому производится запись По сигналу й " на выходе формирова значений абсциссы и ординаты эксттеля 70 формйруется сигнал ф Поремальной точки годографа в регистсигналам йг и г. содержимое блока ры 109 и 110 блока 7 управления.2 22 Формирования годографа сдвигается Задним фронтом сигнала с синх"на один шаг вниз, а триггер 91 блока ронно с тактовым сигналом триггер 7 управления устанавливается в сос 100 устанавливается в единичное тояние, разрешающее формирование сиг- состояние, разрешающее прохождение налов Е и Е+ тактовых сигналов через элементФ" ФИ 61. Очередными тактовыми сигналаПо сигналам й, и г. на выходах ми вырабатываются сигналы споФформирователей 73 и 74 соответственноЗ каждому из которых информация обсодержимое блока 2 Формирования года- ,объекте 8; сдвигается по абсциссеграфа сдвигается на один шаг влево, в блоке 11 запоминания конфигураЦикл повторяется до установки счетчи- ции объекта на один шаг. При дос"ка 104 в состояние БР=с й), по ко- тижении положейия объекта, соотторому .на соответствующем выходе Фор О ветствующего абсциссе экстремаль мируется сигнал с", ной точки, на выходе схемы 107сравнения формируется сигнал наПо сигналу 1 триггер 90 Устанав прекращение сдвига объекта поливается в состояние, запрещающее фор11 абсциссемированне сигналов , ),45и С+. Теперь блок 4 хранения Далее по сигналу с элемента И 621. 41годографа содержит информацию об об- триггер 101 устанавливается в едиласти Г ,0 Я,М(х,у)68 , граница ко- ничное состояние, разрешающее11торой представляет собой годограф прохождение тактовых сигналов чевекторной функции плотного размещения рез элемент И 63. Очередными тактообъекта 8 в области размещения 850выми сигналами вырабатываются сигнаПо управляющему сигналу Сс выхода лы с., по каждому из которыхэлемента 86 задержки триггер 92 ус" информация об объекте 8, сдвигаетсятанавливается в состояние, разрешаю- по ординате в блоке 11 запоминаниящее формирование сигнала с. Синх- конфигурации объекта на один шаг.ронно с тактовым сигналом генератор При достижении положения объекта,3 ю 545 на выходе формирователя 75 форми- соответствующего ординате экстремальруется сигнал с 2. По сигналу с , ной точки, на выходе схемы 1081блок 12 вычисления экстремальных то- сравнения формируется сигнал на1200295 19прекращение сдвига объекта по орди" нате.По сигналу с информация о координатах размещаемого объекта 31 из блока 11 через блок 10 коммутации записывается в блок 5 запоминания, причем запоминание положе-, ния очередного геометрического объекта в блоке 5 запоминания производится беэ стирания ранее накопленной информации. По окончании записи блок 5 запоминания содержит информацию об . области размещения Б,"БЯ, 1 1,2п. По сигналу с блока 7 управления устройство подготавливается для последовательно-одиночного размещения очередного плоского объекта из заданной последовательности А. Далее процесс последовательно-одиночного размещения объектов повторяется. 20Когда будетразмещен последиийгеометрический. объект иэ заданнойпоследовательности, процесс заканчивается, По окончании работы устройства блок 9 запоминания параметровразмещения объекта содержит параметры рационального размещения в об"ласти Я, объектов 81(1=1,2п)из заданной последовательности А.1 О Устройство определяет, рациональноепоследовательно-одиночное размещениеплоских геометрических объектов произвольной геометрической формы.Эффективность предлагаемого уст ройства для моделирования последовательно-одиночного размещения плоских геометрических объектов заключается в повышении производительноститруда и снижении трудоемкости реше ния задачи оптимизации размещенияобъектов, а также в экономии материально-технических ресурсов, которая составит в среднем ЗЖ.120 мирования годографа, нулевыми входами триггеров матрицы блока хранения годографа, входом сброса блоказапоминания области размещения объекта и входамисброса счетчика перебора элементов и и-мерного поля размещения объекта блока управления,.выходы которого соединены с вторыми,входами одноименных элементов Иматрицы блока формирования стробирующего сигнала, второй вход второгоэлемента И блока управления являет"ся входом записи области размещенияобъекта устройства, а выход этогоэлемента через второй формировательимпульса соединен с вторыми входамиэлементов И первой матрицы блокараспределения информации, второйвход третьего элемента И блока управления является входом записи объекта устройства, а выход третьего элемента И через третий формировательимпульса соединен с вторыми входамиэлементов И второй матрицы блокараспределения информации и единичным входом первого триггера блокауправления, единичный выход которогосоединен с вторым входом четвертогоэлемента И, выход которого соединенсо счетным входом счетчика перебораэлементов и и-мерного поля размещения объекта, выходы которого соединены с вторыми входами одноименных.элементов И матрицы блока формирования стробирующего сигнала, последнийвыход счетчика перебора элементови.и-мерного поля размещения объектачерез первый элемент задержки блокауправления соединен с нулевым входомпервого триггера этого блоха, о т -л и ч а ю щ е е с я . тем, что, с целью расширения функциональных возможностей за счет реализации процессапоследовательно-одиночного размещенияобъектов, оно содержит дешифраторсостояний, блок запоминания параметров размещения объектов, второй блоккоммутации, блок запоминания конфигурации объекта и блок вычисленияэкстремальных точек годографа, который содержит две матрицы элементов Ии элементы ИЛИ, причем блок распределения информации содержит третью матрицу элементов И по числу информационных входов устройства, ячейкиформирователя блока формированиягодографа содержат дополнительновторой триггер, элементы ИЛИ и элементы И, а блок управления содержит 0295 дополнительно шестнадцать элементов И, три элемента задержки, семнадцать формирователейимпульса, тринадцать триггеров, две схемы сравнения,счетчик перемещений объекта по абсциссе, счетчик перемещений объектапо ординате, регистр абсциссы ирегистр ординаты, первые входы элементов И третьей матрицы блока распределения информации подключены кодноименным информационным входамустройства, вторые входы этих элементов И объединены и подключенык выходу третьего формирователя импульса блока управления, а выходыэлементов И третьей матрицы блокараспределения информации соединеныс одноименными информационными входами блока запоминания конфигурации объекта, в 1,1-й ячейке формирователя матрицы блока формированиягодографа выходы первого, второгои третьего элементов И через первыйэлемент ИЛИ соединены со счетнымвходом второго триггера, единичныйвыход которого соединен с первымивходами четвертого, пятого и шестогоэлементов И, нулевой вход второготриггера подключен к выходу первогоформирователя импульса, счетный входпервого триггера подключен к выходувторого элемента ИЛИ, а единичныйвыход соединен с первыми входамипервого и второго элементов И, выходчетвертого элемента И ,1-ячейки фор-.мирователя соединен с первыми входамитретьего элемента И и второго элемента ИЛИ 1., 1+1-й ячейки формирователя,а выходы пятого и шестого элементовИ 1, 1-й ячейки формирователя соединены соответственно с вторым входомвторого элемента ИЛИ 1, 1-1-й ячейкиформирователя и. третьим входом второго элемента ИЛИ +1, 1-й ячейкиформирователя, в блоке вычисленияэкстремальных точек годографа первые.и вторые входы , 1-го элемента Ипервой матрицы подключены соответственно к единичному выходу , 1"готриггера и нулевому выходу д, 1+1-готриггера блока .хранения годографа,первые и вторые входы 1., 1-го элемента И второй матрицы подключенысоответственно к единичному выходу+1,1"го триггера блока хранениягодографа, выходы элементов И каждого столбца первой и второй матрицсоединены с входами соответствующих3200295г,3 д абике сб СрФк TрУВ1200295 Ф 2 Составитель Г. СорокинРедактор В. Петращ ТехредД,Мартяшова Корректор А. ЗимокосоЗака /55 П ое одписн Гос ударлам изо рМоскваП "Патент4 Дектная,35 Раушская наб.Тираж 709ственного комитета СССб етений и открытий200295 1элементов ИЛИ, выходы которых соединены с одноименными входами дешифратора состояний, выход которого соединен с информационным входом блока запоминания параметров размещения объекта, в блоке управления выход третьего формирователя импульса соединен с единичным входом второго триггера, а выход пятого элемента И через четвертый формирователь импульса соединен с нулевым входом третьего триггера, единичный выход которого соединен с вторым входом пятого элемента И, единичным входом четвертого триггера и с третьими входами элементов И первой матрицы блока вычисления экстремальных точек годографа, выход шестого элемента И через пятый формирователь импульса соединен с нулевым входом четвертого триггера, единичный выход которого соединен с вторым входом шестого элемента И, единичным входом пятого триггера и управляющим входом дешифратора состояний, выход седьмого элемента И через шестой формирователь импульса соеди", нен с нулевым входом пятого триггера, единичный выход которого соединен с вторым входом седьмого элемента И, единичным входом шестого триггера и входом записи блока запоминания параметров размещения объектов, выход восьмого элемента И через седьмой формирователь импульса сое" динен .с нулевым входом шестого триггера, единичный выход которого соединен с вторым входом восьмого элемента И, единичным входом седьмого триггера и третьими входами элементов И второй матрИцы блока вычисления экстремальных точек годографа, выход девятого элемента И через восьмой формирователь импульса сое. динен с нулевым входом седьмого .триггера, единичный выход которого соединен с вторым .входом девятого элемента И, единичным входом восьмого триггера и управляющим входом дешифратора состояний, выход десятого элемента И через девятый формирователь импульса соединен с нулевым входом восьмого триггера, единичный выход которого соединен с вторым входом десятого элемента И, единичным входом девятого триггера и входом записи блока запоминания параметров размещения объектов, выход одиннадцатого элемента И через десятый формирователь импульса соединен,с нулевым входом девятого триггера,единичный выход которого соединенс вторым входом одиннадцатого элемента И, и единичным входом десятого триггера, единичный выход которого соединен с вторым входомдвенадцатого элемента И, выход которого соединен с единичным входомодиннадцатого триггера, единичныйвыход которого соединен с вторымвходом тринадцатого элемента И,выход которого через одиннадцатыйформирователь импульса соединен снулевым входом десятого триггера,счетным входом счетчика перемеще-.ний объекта по абсциссе и управляющим входом блока запоминания конфи"гурации объекта, выход четырнадцатого элемента И соединен с нулевымвходом одиннадцатого триггера иединичным входом двенадцатого триггера, единичный выход которого соединен с вторым входом пятнадцатогоэлемента И, выход которого черездвенадцатый формирователь импульсасоединен со счетным входом счетчикаперемещений объекта по ординате иуправляющим входом блока запоминания конфигурации объекта, выходысчетчиков перемещений объекта поабсциссе и ординате соединены соответственно с первыми входами схемсравнения, вторые входы которых подключены соответственно к выходам регистров абсциссы и ординаты, входыкоторых соединены с соответствующими вторыми информационными выходами блока запоминания параметровразмещения объектов, выход первойсхемы сравнения соединен с вторымвходом четырнадцатого элемента И, авыход второй схемы сравнения соеди"нен с нулевым входом двенадцатоготриггера и единичным входом тринадцатого триггера, единичный выходкоторого соединен с вторым входомшестнадцатого элемента И, выход которого через тринадцатый формирователь импульса соединен с управляющимвходом второго блока коммутации, нулевым входом тринадцатоготриггера и единичным входом четырнадцатого триггера, единичный выход которого соединен с вторым входом семнадцатого элемента И, выходкоторого через четырнадцатый формирователь импульса соединен с нулевым входом четырнадцатого тригге1200295ра и вторым входом восемнадцатогоэлемента И, выход которого черезпятнадцатый формирователь импульса соединен с входом сброса счетчикаперебора элементов а,п-мерного поляразмещения объекта, и-кратный выходкоторого соединен с вторыми входами вторых элементов И ячеек формиро"вателя матрицы блока формированиягодографа и с входом второго элемента задержки блока управления,выход которого через шестнадцатыйформирователь импульсов соединенс вторым входом шестых элементов Иячеек формирователя матрицы блокаформирования годографа и со счетнымвходом второго триггера блока управления, единичный и нулевой выходыкоторого .соединены соответственно спервыми входами девятнадцатого идвадцатого элементов И, вторые входыкоторых подключены к выходу четвертого элемента И блока управления,1.Изобретение относится к вычислительной технике, в частности к устройствам специализированной вычислительной системы оптимального проектирования генеральных планов промыш" 5 ленных предприятий и технологических карт раскроя.Известна сйстема оптимального использования материала, содержащая блок цифрового преобразования геомет рических форм, арифметическое устройство, используемое для физического моделирования смещения отдельного куска по поверхности материала на основе заложенных правил и решения век- Ц торных уравнений в декартовой системе координат, и выходной блок вычерчивания 1 ,Однако использование арифметического устройства общего назначения 20 для последовательно-одиночного размещения объектов в известных устройствах приводит к снижению объема решаемых задач, увеличению времени решения задачи по сравнению с пепрог .раммными способами.Каиболее близким к.изобретению является устройство для моделирования выход девятнадцатого элемента И которого соединен с вторым входомпервых элементов И ячеек фьрмиро. вателя блока формирования годографа через семнадцатый формировательимпульса, а с вторым входом четвертых элементов И ячеек формирователяблока формирования годографа - черезтретий элемент задержки и восемнадцатый формирователь импульса, выходдвадцатого элемента И блока управления соединен с вторым входом третьихэлементов И ячеек формирователя бло"ка формирования годографа черездевятнадцатый формирователь импульса,а с вторым входом пятых элементов Иячеек формирователя блока формирования годографа - через четвертый элемент .задержки и двадцатый формирователь импульса, выход первого элемента задержки блока управления соединен с единичным входом третьеготриггера того же блока. размещения плоских геометрическихобъектов, содержащее блок .распределения информации, который содержит.две.матрицы элементов И по числу информационных входов устройства в каждой матрице, блок формирования годографа, выполненный в виде матрицаячеек формирователя, каждая из кото-,рых состоит из первого триггера, первый блок коммутации, блок хранЕннягодографа, выполненный в виде матрицы триггеров, блок запоминания области размещения объекта, блок формирогвания стробирующего сигнала, которыйсостоит из матрицы элементов И, группы элементов ИЛИ, элемента ИЛИ иформирователя импульса, и блок уп" .равления, который состоитиэ четырехэлементов И, трех формирователей импульсов, первого триггера, первого элемента. задержки,счетчика перебора элементов и п-мерного поля размещения объекта и генератора тактовых импульсов, первыевходы одноименных элементов И каждой матрицы блока распределения ин"формации объединены и подключены ксоответствующему информационному1200295 второй ход третьего элемента И блока управления является входом записи объекта устройства, а выходтретьего элемента И через третийформирователь импульса соединен свторыми входами элементов И второйматрицы блока распределения информации и единичным входом первоготриггера блока управления, единич ный вьгход которого соединен с вторымвходом четвертого элемента И, выходкоторого соединен со счетным входомсчетчика перебора элементов п.п-мер- .ного поля размещения объекта, выходы которого соединены с вторымивходами одноименных элементов И матрицы блока формирования стробирующего сигнала, последний выход счетчика перебора элементов п.п-мерногополя размещения объекта через первый элемент задержки блока управления соединен с нулевым входом первого триггера этого блока Г 2 3Известное устройство не позволя ет моделировать последовательноодиночное размещение плоских геометрических объектов.Цель изобретения - расширениефункциональных возможностей путемреализации процесса последовательноодиночного размещения объектов,35 входу устройства, выходы элементовИ первой матрицы блока распределения информации соединены с одноименными инфомационными вСодами блоказапоминания области размещения объекта, выходы элементов И второйматрицы блока распределения информации соединены с единичными входамипервых триггеров одноименных ячеекформирователя блока формированиягодографа, а выходы первых триггеровматрицы ячеек формирователя блока форформирования годографа соединены содноименными информационными входамипервого блока коммутации, выходы которого соединены с единичными входами одноименных триггеров матрицыблока хранения годографа, первыевходы элементов И матрицы блока формирования стробирующего сигнала подключены к одноименным выходам блоказапоминания области размещения объек.та, а выходы элементов И каждогостолбца матрицы блока формированиястробирующего сигнала через соответствующий элемент ИЛИ группы соединены с соответствующим входом эле:мента ИЛИ, выход которого соединенс входом формирователя импульса блока формирования стробируюшего сигнала, выход которого соединен с управляющим входом первого блока коммутации, выход генератора тактовыхимпульсов блока управления соединенс первыми входами элементов И блокауправления, второй вход первого изкоторых является входом запуска устройства, а выход первого элемента Ичерез первый формирователь импульсасоединен с нулевыми входами первыхтриггеров ячеек формирователя блокаформирования годографа, нулевымивходами триггеров матрицы блока хранения годографа, входом сброса блоказапоминания области размещения объекта и входами сброса счетчика перебора элементов п.п-мерного поля размещения объекта блока управления,выходы которого соединены с вторыми входами одноименных элементов Иматрицы блока формирования стробирующего сигнала, второй вход второго элемента И блока управления является входом записи области размещения объекта устройства, а выходэтого элемента через второй формирователь импульса соединен с вторыми входами элементов И первой матрицы блока распределения информации,Указанная цель достигается тем, что устройство для моделирования размещения плоских геометрических объектов, содержащее блок распределения информации, который содержит две матрицы элементов И по числу информационных входов устройства в каждой матрице, блок формирования годографа, выполненный в виде матрицы ячеек формирователя, каждая из которых состоит из первого триггера, первый блок коммутации, блок хранения годографа, выполненный в виде матрицы триггеров, блок запоминания области размещения объекта, блок формирования стробирующего сигнала, который состоит из матрицы элементов И, группы элементов ИЛИ, элемента ИЛИ и формирова,теля импульса, и блок управления, который состоит из четырех элементов И, трех формирователей импуль- сов, первого триггера, первого элемента задержки, счетчика перебора элементов и и-мерного поля размещения объекта и генератора тактовых импульсов, первые входы одноименных элементов И каждой матрицы блока5 1 распределения информации объединены и подключены к соответствующему информационному входу устройства, выходы элементов И первой матрицы блока распределения информации соединены с одноименными информационными входами блока запоминания области размещения объекта, а выходы элементов И второй матрицы блока распределения информации соединены с единичными входами первых триггеров одноименных ячеек формирователя бло" ка формирования гоДографа, а выходы. первых триггеров матрицы ячеек формирователя блока,.формирования годографа соединены с одноименными информационными входами первого блока коммутации, выходы которого соединены с единичными входами одноименных триггеров матрицы блока хра. нения годографа, первые входы элементов И матрицы блока формирования стробирующего сигнала подключены к одноименным выходам блока запоминания области размещения объекта, а выходы элементов И каждого столбца матрицы блока формирования стробнрующего сигнала через соответствующий элемент ИЛИ группы соединены с соответствующим входом эле" мента ИЛИ, выход которого соединен с входом формирователя импульса блока формирования стробирующего сигнала, выход которого соединен с управляющим входом первого блока коммутации, выход генератора тактовых импульсов блока управления соединен с первыми входами элементов И блока управления, второй вход первого из которых является входом запуска устройства, а выход первого элемента И через первый формирователь импульса соединен с нулевыми входами первых триггеров ячеек формирователя блока формирования годографа, нулевыми входами триггеров матрицы блока хранения годографа, входом сброса блока запоминания области размещения объекта и входами сброса счетчика перебора элементов и и-мерного поля размещения объекта блока управления, выходы которого соединены с вторыми входами одноименных элементов И матрицы блока формирования стробирующего сигнала, второй вход второго элемен та И блока управления является входом записи области размещения200295 Ь 5 О 15 20 25 30 35 40 45 50 55 объекта устройства, а выход этогоэлемента через второй формировательимпульса соединен с вторыми входамиэлементов И первой матрицы блокараспределения информации, второйвход третьего элемента И блока управления является входом записиобъекта устройства, а выход третьего элемента И через третий формирователь импульса соединен с вто"рыми входами элементов И второй матрицы блока распределения информациии единичным входом первого триггераблока управления, единичный выходкоторого соединен с вторым входомчетвертого элемента И, выход которого соединен со счетным входомсчетчика перебора элементов и и-мерного поля размещения объекта, выходы которого соединены с вторымивходами одноименных элементов Иматрицы блока формирования строби"рующего сигнала, последний выходсчетчика перебора элементов и и-мер-фного поля размещения объекта черезпервый элемент. задержки блока управ-,ления соединен с нулевым входомпервого триггера этого блока, содержит.дешифратор состояний, блок запоминания параметров размещенияобъектов, второй блок коммутации,блок запоминания конфигурации объекта и блок вычисления экстремальныхточек годографа, который содержитдве матрицы элементов И и элементыИЛИ, причем блок распределения информации содержит третью матрицу элементов И по числу информационныхвходов устройства, ячейки формирователя блока формирования годографасодержат дополнительно второй т 1 иг. -гер, элементы ИЛИ и элементы И, аблок управления содержит дополнительно шестнадцать элементов И, триэлемента задержки, семнадцать формирователей импульса, тринадцатьтриггеров, две схемы сравнения,счетчик перемещений объекта по абс.циссе, счетчик перемещений объектапо ординате, регистр абсциссы ирегистр ординаты, первые входы элементов И третьей матрицы блока распределения информации подключены кодноименным информационным входамустройства, вторые входы этих элементов И объединены и подключены квых цу третьего формирователя импульса блока управления, а выходы эле7200295 . 8ментов И третьей матрицы блока рас- входом четвертого триггера и трепределения информации соединены стьими,входа иодами элементов первойИодноименными информационными входа- матрицы блокалока вычисления экстремаль.ми блоказапоминания,конфигурации ных точек годо фк годографа, выход шестогообъекта н-й ячейке фформирона элемента И через пятый формировательтеля матрицы блока формирования го- импульса соединен с нулевым входомдографа выходы первого, второго и четвертого тригге ат ггера,. единичныи выходтретьего элементов И через первый которого соединен с вторым входомэлемент ИЛИ соединены со счетным шестого элемент Ил мента , единичным входомвходом второго триггера, единичный 10 пятого триггера и управляющим входомвыход которого соединен с первыми дешифратора состояний, выход седьвходами четвертого, пятого. и шесто- мого элемента И через шестои формиФго элементов И, нулевой вход второ- рователь импульса соединен с нулего триггера подключен к выходу пер- вым входом пятого т риггера, единкчныиного формирователя импульса, счет-, 15 выход которогосоединен с вторым .ный вход первого триггера подключен входом седьмого элемента И единичЭк выходу второго элемента ИЛИ, а ным входом шестого триггера и входомединичный выход соединен с первыми записи блока запоминапоминания параметроввходами первого и второго элементов размещения объея о ъектон, выход восьмогочерез седьмои формироваИ, выход четвертого элемента И 20 элемента И чере ф1,-й ячейки формирователя соединен тель импульса соединен с нулевым нхотриггера, единичный ныс первыми входами третьего элемента дом шестого триИ и второго элемента ИЛИ д,1+1-й ход которого соединен свторым нходомиячеики формирователя, а выходы пя- восьмого элемент Им нта , единичным входомтого и шестого элементов И 1, 1-й 25 седьмого триггера и третьими входамиячейки формирователя соединены соот- элементов И втовторои матрицы блока ны-ветственно с, вторым входом второго , числения экстремальных точек годограэлемента ИЛИ ,-1-й ячейки форми- фа, выход девятого элемента И черователя и третьим входом второго рез восьмой формирователь импульсаэлемента ИЛИ 1+1,1-й ячейки форми соединен с нулевым входом седьмогорователя, в блоке вычисления экстре- тРиггера, единичный выход которогомальных точек годографа первые и соединен с вторым входом девятоговторые входы ,1-го элемента И пер- элемента И, единичным входом носьвой матрицы подключены соответствен" мого тРиггера и управляющим входомно к единичному выходу 1,1-го тригге-, дешифратора состояний, выход десяра и нулевому выходу 1,1+1-го тригге- того элемента И через девятый формира блока хранения годографа, первые рователь импульса соединен с нулеи вторые входы ,1-го элемента И вто- ным входом восьмого триггера, единичРой матрицы подключены соотнетствен- ный выход которого соединен с вторымно к единичному выходу 1,1-го триггеО входом десятого элемента И, единичра и нулевому выходу +1, 1-го тригге- ным входом девятого триггера и входомра блока хранения годографа, выходы записи блока запоминания параметровэлементов И каждого столбца первой размещения объектов, выход одиннади нторой матриц соединены с входами цатого элемента И через десятый фор-соответствующих эдементов ИЛИ, выхо миронатель импульса соединен с нуле,ды которых соединены с одноименными ным входом девятого триггера, единич:входами дешифратора состояний, выход ный выход которого соединен с вторым которого соединен с информационным входом одийнадцатого элемента И, ивходом блока запоминания параметронединичным нходом десятого триггера,чРазмещения объекта, в блоке управле- единичныи выход которого соединен с ния выход третьего формирователя вторым входом двенадцатого элеменимпульса соединен с единичны в д . та И выход которого соединен с едивтоРОГо триггера, а выход пятничным Входом одиннадцатого триггеэлемента И ч речерез четвертый формирора, единичный выход которого соедиватель импульса соединен с нулевым 55мента И, выход которого через одинвходом третьего триггера, единичный надцатый формирователь импульсасоединен с нулевым входом десятоговходом пятого элемента И, единичным триггера, счетным входом счетчика9 .12 перемещений объекта по абсциссе и уп" равляющим входом блока запоминания конфигурации объекта, выход четырнад- цатого элемента И соединен с нулевым входом одиннадцатого триггера и единичным входом двенадцатого триггера, единичный вьмод которого соединен с вторым входом пятнадцатого элемента И, выход которого через двенадцатый формирователь импульса соединен со счетным входом счетчика перемещений объекта по ординате и управляющим входом блока запоминания конфигурации объекта, выходы счетчиков перемещений объекта по абсциссе и ординате соединены соответственно с первыми входами схем сравнения, вторые входы которых подключены соответствен- но к выходам регистров абсциссы и ординаты, входы которых соединеньг с соответствующими вторыми информационными выходами блока запоминания параметров размещения объектов, выход первой. схемы сравнеяна соединен с вторым входом четырйадцвтого элемента И, а выход второй схеиш сравнения соединен с нулевым входом двенадцатого триггера и единичным входом тринадцатого триггера, единичный выход которого соединен с вторым входом шестнадцатого элемента И, выход которого через тринадцатый формирователь импульса соедис. нен с управляющим входом второго блока коммутации, нулевым входом тринадцатого триггера и единичным 1входом четырнадцатого триггера, единичный выход которого соединен с вторым входом семнадцатого элемента И, выход которого через четырнадцатый формирователь импульса соединен с нулевым входом четырнадцатого триггера и вторым входом восемнадцатого элемента И, выход которого.через пятнадцатый формирователь импульса соединен с входом сброса счетчика перебора элементов а.п-мерного поля размещения объекта, и-кратный выход которого соединен .с вторыми входами вторых элементов И ячеек формирователя матрицы блока формирования годографа и с входом второго элемента задержки блока управления, выход которого через шестнадцатый формирователь импульса соединен с вторым входом шестых элементов И ячеек формирователя марицы блока формирования годографа и со счетным входом вто 00295 10рого триггера блока управления,единичный и нулевой выходы которогосоединены соответственно с,первымивходами девятнадцатого и двадцатогоэлементов И, вторые входы которькподключены к выходу четвертогоэлемента И блока управления,.вькоддевятнадцатого элемента И которогосоединен с вторым входом первых 10 элементов И ячеек формирователя блока формирования годографа через семнадцатый формирователь импульса,а с вторым входомчетвертых элементов И ячеек формирователя блока 15 формирования годографа - через третий элемент задержки и восемнадцатый формирователь импульса, выходдвадцатого элемента И блока управ"ления соединен с вторым входом тре тьих элементов И ячеек формирователяблока формирования годографа черездевятнадцатый формирователь импульса, а со вторым входом пятых элементов И ячеек формирователя блока р 5 Формирования годографа - через четвертый элемент задержки и двадцатыйформирователь импульса, выход первого элемента задержки блока управления соединен с единичным входом ЗГ/триггера того же блока.Р Суть способа последовательноодиночного размещений плоских геометрических объектов состоит в слеПод выражением "геометрическийобъект" или просто "объект" понимается некоторая замкнутая область,ограниченная кусочно-гладким конту О ром. Некоторую фиксированную точкуО внутри объекта 8 или на его границе назовем полюсом объекта, Свяжемобъект Яо с неподвижной системойкоординат ХОУ с началом в полюсе О, 4 Каждый объект 8,(1.=1,2п) иззаданной последовательностиАЯ,Я,,8свяжем с подвижнойсистемой координат ХО У с началомв полюсе О. Объекты 8;(1=1,2п) 50 и 80 будем называть взаимно ориентированными, если зафиксированы значе"ния их углов. поворота относительнонеподвижной системы координат ХОУ.Объекты называются плотно расположенными, если они касаются, но непересекаются.Годограф векторной функции плотного размещения представляет собойтраекторию движения полюса подвижно12 1200295 114го объекта при его плотном движенииотносительно неподвижного. ОбъектБ считаем заданным, если задана информация об области, определяющейобъект Я в системе координат с началом в полюсе О.Принцип действия устройства припостроении годографа векторной функции плотного размещения основан наследующем. Пусть Б и Я; - два взаимно ориентированных объекта с полюсами О и О соответственно. ОбъектБ , повернутый на угол я относительно первоначального положения, обозначим через Я, . Область, представляющув собой множество положений объекта Б. при движении его полюса по заданной линии, будем называть следомобъекта Б; и обозначим через БЛегко проверить, что если Б;след объекта Б, при движении егополюса по контуру объекта Б , то гра%1 эница области Б,.ОЯО, М (х,у)ЕБ является годографом векторной функцииплотного размещения объектов Б и Б0В функционирование предлагаемогоустройства заложен следующий очевидный принцип. Оптимальное размещениеобладает тем свойством, что каковабы ни была граница области размещения и какова бы ни была заданнаяпоследовательность размещаемых объектов, размещение каждого последующегообъекта должно быть оптимально относительно границы области размещенияи относительно размещения объектовв области возникшего в результатеразмещения предыдущих объектов иззаданной последовательности.Исходя из принятого принципа оптимальности метод решения поставленной задачи включает: построение годографа векторной функции плотного размещения размещаемого объекта Б. и области размещения; моделирование спо.соба последовательно-одиночного размещения. Таким образом, все объекты из заданной последовательности размещаются последонательно по одному. Ранее размещенные объекты считаются неподвижными, т.е. их параметры размещения имеют вполне определенные фиксированные значения. Каждый объект размещается так, что из всех его возможных положений выбирается такое, при котором значение функции цели у; достигает наименьшего значения только по тем переменным, которые являются парметрами размещаемого объекта.Рассмотрим иллюстрацию такогоспособа размещения объектов. Для этго каждому из размещаемых в области Б объектов поставим в соответствие числа иэ натурального рядаот 1 до и, где и - числа размещаемьобъектов. Пусть прн этом объектуБ, соответствует число 1, объектуБ - число 2 и т,д. Тогда произвольная последовательность из этихчисел однозначно определяет последовательность А размещения объектов Б, (=1,2п) .Рассмотрим некоторую последовательнос ть чис ел Ак , к .ко ) фгде к, Ф к 1,(=1,2, ,и), к,. е 1 1,п 1Тогда первому члену этой последовательности соответствует объектБК Если предположить, что задачаразмещения рассматривается применительно к одному объекту Б тоК 1 ф 15 функция цели будет зависеть от одного двумерного вектора РК 1(хК,у К),т,е. жд =х(Рк) Рк е С где С -замкнутое ограниченное множествов , -мерном пространстве, характеризующее область допустимых значений вектора Р ;, Расположим в области Б объект Б К. таким образом,чтобы вектор. его параметров размещения удовлетнорял условию(Р" ):м к (Р ).РК, ебНайденное значение вектора РК.К 1однозначно определяет положениеобъекта БК. в области Б . ЗафиксиК 1 о 40руем это положение, т.е. будем считать объект Б . неподвижным темК 1Ъсамым фиксируем значение вектораР, или, иными словами, группу переменных х;, у ,. функции цели рассматрнваемой задачи.45Второму члену к последовательности А соответствует объект ЯК 2Предположим, что задача размещениярассматривается применительно к двумобъектам Яи Б . Тогда функция50 цели имеет вид(Р РК,),Р,Е СЫ=1,2) .Если учесть, что объект Буже размещен и считается неподнижным, т.е.значение вектора РК уже зафиксиров55 ано, то функция цели зависит отодного вектора Р к