Патент ссср 416689
4I6689
ОПИСАНИЕ
ИЗОБРЕТЕН ИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Союз Советских
Социалистических
Республик
Зависимое от аит. свидстсльст!5Я М 371598 I. Кл. G 06f 7j38 !
Заявлено 27.XI l.1971 (№ 1729327 18-24) с присоединением заявки М
Приор!Ггст
Опуб ltlti013 IIIO 25.11.! Ë4. Б!Ось т и1,,Х, 7
Государственный комитет
Совета Министров СССР оо делам изобретений
0TKPbITHH
УД Е, 681.323:371.0!1 (088.8) Дата опубликования описи:!пii 18.%111.1971
Авторы и 3 О о р с т с н I I 5i
В. Н. Удовиченко, 1О. 1. Стоян, В. Л. Рвачев, В. А. Фролов, Е. А. Королева и H. В. Алипов
Харьковский институт радиоэлектроники
Заявитель
ФУНКЦИОНАЛЬНЫЙ ПРЕОБРАЗОВАТЕЛЬ
Изоб!ретение относится к вычислительной технике.
Известно устройство для оп!ределсии5! расстояния между полюсами двумерных геометрических фи!гур, содержащее <первую и вторую матрицы элементов памяти и логические элементы, в котором элементы, памяти первой матрицы соединены между собой в схемы регистров сдвига полярной системы координат, а элементы памяти второй и1атрицы включены в схемы регистра сдвига Ilo строкам и столбцам прямоугольной системы координатт, Вь1ходы и входы элементов нам яти о!беих матриц, отображающих близлежащие точки соответственно полярной и прямоугольной системы координат, соединены между собой через схемы «И», два входа которых
IIoJtKëIo Предлагаемое устройство, с целью расширения класса решаемых задач, содержит два счетчика, блок управления, последовательно включенные блок памяти и решающий блок, дополнительную координатную матрицу из элсмеIãoâ памяти и второй логичеакий блок, входы и выходы которого соединены соопвстсгьшшо с выходами и входами второй и дополш!тельной м;!триц из элементов памяти и первыми выхо 1о.! и входом блока управлсни51, второй, грстш! II чствертый выходы блока управления присоединены соответсгвенно ко входам блока памяти, решающего блока и первого логического блока, два выхода которого подключены через счетчики ко второ10 му и третьему входам блока управления. 1-Ià фиг. 1 вреде авлеиа блок-схема предлаг,iLмого устройства; на фиг. 2 -- пример размещеiiiiii геометрических фигур It!1 плоско;т:!. 15 Матрица 1;!з элементов памяти, образуюIII,их сетку в ш!Ляриой системе координат и сос Гавс!51!Ощих рсГис рьl сдвиГЯ по 5 Гловой координате, соединена через логически!! блок 2 с координа! ио!1 ма грицей 3 из элементов 2С и
С 11С 1 Ее! Е !COOP;11!II! сдвига по сгрокам и столбцам матрицы. Матрица 3 с помощь!о логического блока —; íà.-.огичио соединена с дополнительной матрицей 25 5 из элс;ic тов п11«!5!ти, образующих сетку в .прт.моугольиой системе координат и составляющих та же реги=тры сдв!ига по строкам и столбцам. Каждый элемент памяти в узлах ка?кдой а!Ятрицы 1, 2, 3 предназначен для 30 храп! ния би!1;1рн5!ь информации О соотвстст 416689 вующей координате одной точки двумерной геометрической фигуры. Два выхода логического блока 2 соединены: один — через счетчик 6 по координате Х, а второй — через счетчик 7 по коорди ате Y с блоком 8 управления и через ного с блоком 9 памяти. Соотвстс1вукицис вы»о II>l б,10К2 8 уп(7 ав 7 Сi!1151 COC;I IIIIC!111 7311?I! е С p 11 I;l io1цим блоком 10. Устройство работает слс чующим об?разом. По,кот!андам олока 8 управления пп!(?орм?1ция о координатах геометрической фигуры записывается в соответствующие элементы г1амяти матрицы 1 из внешних устройств ввода. По соответствующему сигналу 1шформация о координата: с помощью логического блока 2 переписывается в координатную,матрицу 3, 1послс чего информация в матрице 3 сдвигается по оси Х на один такт. Логис!еский блок 2 определяет, имеется или нет пересечение фигур, записанных в матрицах 1 и 3. При наличии пересечения производится сдвиг информации в координатной матрице 3 еще на один шаг и проверяется пересечение. Процесс сдвига по оси Х,проводився до тех пор, пока проверка па,пересечение пс дает информации об отсутствии пересечения, Счетчик 6 по координате Х при этом фиксирует количество сдвигов»о координате Х, ". с. и соответствующем масштабе расстояние между полюсами двух пересекающихся фигур. После очередного определения pacciu5IH»5. между полюсами геомепрических фигур, записанных в координатные матрицы 1 и 3, проводят стирание информации в матрице 3, сдвиг информации в матрице 1 iia один такт по угловой координате (поворот геометрической фигуры на определенный угu;I) и cIIOB2 повторяют указа?нный;процесс. Информация о расстояниях между пол!осами геометрических фигур на каждом углс поворота фигуры в матрице 1 фиксируется cчетчпком 6 по координате Х и зяпо1!Ппяет«51 l> блоке 9 памяти. При суммарном сдвиге по угловой координате па 180,lip05!ecc !!П(7с !С7ciiiili функции плотного одномерного размещения геометрических фигур па плоскости заканчивается. Дальнейшее опрсдслсппс оп7!1:5!27»liuro двухрядного;размещения фигур произвольной формы на плоскость заключается в минимизации площади параллелограмма при условиях, что,полюса фигур размещены в всрпшпах э I ОГО H3 (72 7ëñëoÃpll>l з!3 (с;1. фи! . 2) и фигуры ме?кду со бо!! Не пересекаются. Вначале определяется за !31111ос положение фигуры 01посптельпо ocè Х, пр;1 Icorunnii 173сстояп>ие между по,>1юсам1! двух фигур ирп отсутствии пересечения ми!пима Iblloe. Выбранное положение заданной фигуры зяписывяс.— "я в матрицу 1, перепосигся B мятр щу 3 и затем в .::атрицу 5. В последней информация о расположении фигуры сдвигается по ос:i Х Пс! ВСЛИЧИПУ (ПОЛУЧeН1<УЮ ВЫШЕ) РаССТОЯНИЯ между полюсами. Затем проводится вторично перенос i!Hôuðмации из матрицы 3 В матрицу 5 (пя освобожденное после сдвига мс«70) . >тll Р32:l el!!cllHH Н2 фпг. 2 !J003113>lellli 51, 5;. 33 1,3B1lIIIcI> оп(?сдслснпои 150.!Ичт!Иои "5?> 117 торя от î.lllcilHIli>ill процесс, причем сдвигают ипформяцшо, пмс10щу!ОС!1 В матрице 3, одновременно 10 оси Х il llo ucll (на один такт, па Величины, создающие В результате гео»eiричсского сложения угол 7 и производят исс 7e;iuB3HHC ii2 пересечение. (1рп каки -либо Вслпчппах C:Hcùe171è 110 осп Х и У, пере«счс:!Нс прекрятHT«51 и определится pacctuHH.. Ie между полюса IH фигур 51, $ . которое покажет счетчик 6 по осн Х и счетчик 7 по оси . 3 To . i 0.a u»< e !i I i,i ф и г у p I>I B I 3 7 p H Ii e 3: i ep e H осится В матрицу 5, где опа cpBHl.aeic5 по оси Х па расстояние, равное расстоянию по оси Х между полюсами фигур Sl, S2. Затем ipoBOдится проверка па наличие пересечения между ф ГураМИ 51, S., ПрИ Н2ЛИс!ИП ПЕрССЕЧЕПИя ;1роводят дальнейший сдвиг iio координатам Х и ? в матрице 3 до получен:!я сигнала оо 0;сутствии пересечения. Изме11ениям угла !5 находят оптимальную вели гипу угла 75, при котором расстояние между фигурами 5„S.; будет минимальным при отсутствии пересечения. Решающий блок 10 вычисляет оптимальное количество фигур, КОI 01>ые 710?Кно Рс!3 5!ещат1> В заданной Оолс!Зл Предлагаемое ус1ройстио позволяет решать задачи о:г1И?!ал1Н!Ого многорядного размещеHii5I Н,.70ñêHõ ф:1г>>(7 ня плоскости и в заданных областях, например, при многорядной штамповке и рязлпчпых видах решетчатых размещений. 1 l р с д м е 1 i! 3 и 0 р с т e i l l! ?I i1? > ПКЦНО:1;!.11>HI>il! ПРСООРЯЗОВс1TC.>71 .10 3!3т. «В. ¹ 374598, îl ;личяющийся тем, что, с целью расширения класса ?ешасмых задач, o H «О дс 1э ж и 7: I B li c H e ò ÷ è 1>. 2, 0 л О к у и (7 2 В л с и и я, H0C7eÄOÂ2! C7i>H0 ВКЛЮЧ СПИ ЫЕ ОЛОК П с! МЯ7 11 и решающий 0 iuк, допо7пп!е7ьпу!О коордппатр() 11ólo матрицу из элементов памяти и Второй 7огический олок, входы и Выходы которого соединены соответственно с выходами и B?;o;l3ìè второй и дополнительной >13Tp:Ill, из элеМСП 1 OB ПЯ:5151 1 И ll П! :PBI>DIH В>Ь1ХОДО И ВХОД051 блока управления, второй, третий и четвертый выхо III блока управления,при осдипены соот;!Стсi Beuèu ко входам блока памяти, решающего блока и:1срвого логического блока, два Выхода ко«upolo подключены через счстчпкп ко второму и третьему входам блока управле1!ИЯ. 416689 Корректор Е. Зимина 1 сдактор Л. Батыгин Заказ 1637, o Изд. М 527 Тираж 624 Подписное Ц11ИИПИ Государственного комитета Совета Министров СССР по делам изобретений и откр:,:тин Москва, gi-35, Раушская наб., д. 4, 5 Типография, пр. Сапунова. 2 Составитель Л. Маслов Текред Л. Богданова ) 
