Содержание к диссертации
Введение
Глава 1. Обзор существующих моделей и методов решения задачи нерегулярного размещения деталей сложных форм 12
1.1. Многообразие задач раскроя-упаковки 12
1.2. Классификация моделей раскроя-упаковки 17
1.3. Основные определения и постановка задачи размещения плоских геометрических объектов 19
1.3.1 Основные понятия и определения 19
1.3.2 Общая постановка задачи размещения плоских ГО 24
1.4. Методы решения задач упаковки ГО 26
1.4.1 Классификация методов решения задач нерегулярного размещения ГО 26
1.4.2 Точные методы решения задач нерегулярного размещения ГО 31
1.4.3 Методы комбинаторной оптимизации и способ выборочного размещения и удаления 45
1.4.4 Метод последовательного уточнения оценок 49
1.4.5 Решение задачи размещения плоских ГО на основе дискретно- логического представления информации 51
1.5. Выводы по первой главе 54
Глава 2. Математическая модель задачи нерегулярного размещения плоских многоугольников в произвольной односвязной области и итерационный метод нахождения ее локального экстремума 56
2.1. Описание математической модели задачи 56
2.2. Решение задачи поиска локального оптимума 60
2.3. Иллюстрация работы метода 63
2.4. Выводы по второй главе 66
Глава З. Алгоритмы реализации разработанного метода нахождения локального экстремума задачи размещения невыпуклых ориентированных многоугольников в невыпуклой многоугольной области размещения 67
3.1. Алгоритм реализации итерационного метода нахождения локального экстремума 67
3.2. Построение выпуклой оболочки для многоугольника 70
3.3. Алгоритм разбиения невыпуклых многоугольников на выпуклые 73
3.4. Построение годографов для моделирования УВН и УРО 78
3.5. Ликвидация взаимного пересечения годографов 86
3.6. Выводы по третьей главе 89
Глава 4. Комбинация алгоритма нахождения локального экстремума с ж приближенными методами последовательного одиночного размещения и его исследование 90
4.1. Общая схема комбинации точного метода поиска локального экстремума и приближенных методов ПОР 90
4.2. Модификация предложенной схемы для классического «жадного» алгоритма 92
4.3. Модификация предложенной схемы для метода ПОР по принципу «первый подходящий с упорядочиванием» (ГШУ) на основе ДЛПИ и ЦК... 95
4.4. Вычислительные эксперименты 102
4.5. Выводы по четвертой главе 104
Заключение 105
Список литературы
- Основные определения и постановка задачи размещения плоских геометрических объектов
- Классификация методов решения задач нерегулярного размещения ГО
- Решение задачи поиска локального оптимума
- Построение годографов для моделирования УВН и УРО
Введение к работе
Актуальность темы. На сегодняшний день и в обозримом будущем в различных сферах производства возникают и будут возникать проблемы ресурсо- и энергосбережения, связанные с задачами раскроя и упаковки (компоновки). К таким задачам относятся: задачи оптимального раскроя материала на заготовки произвольной формы, решаемые при производстве изделий в машиностроительной, авиастроительной, судостроительной, текстильной, кожевенной, деревообрабатывающей, мебельной и многих других отраслях промышленности; задачи компоновки: грузов в разнообразного вида контейнеры, схем генеральных планов промышленных предприятий, двигателей, радиоэлементов на платах и т.д.; задачи распределения — от памяти вычислительных машин до участков леса, предназначенных для вырубки или посадки.
Все вышеперечисленные задачи по своей сути относятся к проблеме оптимизационного геометрического моделирования, заключающейся в оптимизации размещения данного вида объектов в заданных областях.
Сложность решения этих задач заключается в том, что они относятся по своей сложности к классу NP-трудных проблем оптимизации, т.е. для которых пока не существует методов и алгоритмов, находящих точное решение за полиномиальное время [63].
Анализ отечественной и зарубежной литературы, информационных интернет-источников позволяет сделать вывод, что исследованием и разработкой методов решения данного класса задач занимаются: Харьковская школа Р-У академика Ю.Г. Стояна; Институт алгоритмов и научных вычислений Германии (Т. Ленгауэр); В. Миленковик, К. Даниэльс (США); К. Доусланд, В. Доусланд (Великобритания); ряд российских ученых, среди которых Э.А. Мухачева, М.А. Верхотуров, В.В. Мартынов, А.А. Петунии, В.Д. Фроловский [7].
В классе задач двумерного Р-У на верхних ступенях сложности, по отношению к другим задачам Р-У, находятся задачи нерегулярного размещения геометрических объектов сложных форм. Это связано с трудоемкостью формализации условий взаимного непересечения объектов и условий их размещения в заданных областях Р-У.
Разработанные на сегодняшний момент методы точного решения таких задач не находят своего применения на практике, так как оказываются эффективными только при сравнительно небольшом числе объектов. При увеличении числа объектов значительно усложняется поиск не только глобального, но и локальных экстремумов, точные методы перестают отвечать требованиям надежности, и скорости работы. Дискретность работы средств цифровой вычислительной техники, трудоемкость базирующихся на них аналитических алгоритмов в большинстве случаев обуславливает сложность математических моделей и, как следствие, неустойчивость работы создаваемого математического обеспечения. В связи с этим наибольшее применение получили приближенные методы решения, основанные на эвристических и метаэвристических подходах, дискретных способах представления геометрической информации. Основной недостаток этих методов - отсутствие математически обоснованного доказательства не только глобальной, но даже локальной оптимальности полученного решения. Применение точных алгоритмов поиска локального экстремума к результатам работы приближенных методов позволит получить математически обоснованный локальный оптимум задачи двумерного размещения объектов различного вида при раскрое и упаковке промышленных материалов, что приведет к большей экономии материальных ресурсов. Все выше сказанное определяет актуальность разработки эффективных и надежных методов поиска локального экстремума задачи двумерного размещения ГО различного вида при решении задач Р-У промышленных материалов.
Эта задача может быть решена посредством разработки эффективных математических моделей и их решения с помощью методов математического программирования.
Целью работы является разработка методов и алгоритмов поиска локального экстремума задачи двумерного нерегулярного размещения ГО на анизотропном материале (поворот ГО запрещен) на основе заданного начального приближения, а также подходов к использованию разработанных методов в комбинации с приближенными методами.
Основные задачи исследования в соответствии с поставленной целью сформулированы следующим образом:
Разра ботать математическую модель представления задачи двумерного размещения ГО с ограничениями в виде линейных неравенств.
Разработать методы и алгоритмы нахождения локального экстремума на основе построенной модели и подходов математического программирования при заданном начальном приближении.
Разработать программное обеспечение для решения задачи поиска локального экстремума с учетом технологических ограничений.
Провеет и вычислительный эксперимент для разработанных методов и алгоритмов.
Методы исследования. Результаты исследований, выполненных в работе, базируются на основных положениях системного анализа, исследования операций, аналитической и вычислительной геометрии, машинной графики, а также структурного, модульного и объектно-ориентированного программирования. В процессе исследований использовались методы и инструменты организации комплексов программных средств, машинные эксперименты для оценки эффективности алгоритмов.
Результаты, выносимые на защиту:
1. Математическая модель задачи размещения плоских ориентированных многоугольников в невыпуклой области с ограничениями в виде специальной структуры на основе пересечений и объединений линейных неравенств.
Метод нахождения локального экстремума для задачи размещения плоских многоугольников на анизотропном материале на основе идеологии активного набора с использованием построенной модели задачи.
Алгоритмическое и программное обеспечение для реализации разработанного метода поиска локального экстремума задачи размещения деталей в заданной области с учетом технологических ограничений.
Схема комбинации разработанного метода поиска локального экстремума с приближенными методами последовательного одиночного размещения. Результаты вычислительных экспериментов для созданного метода поиска локального экстремума.
Научная новизна работы заключается в следующем:
Область допустимых решений математической модели задачи размещения плоских ориентированных многоугольников в многоугольной области задается в аналитическом виде как специальная структура неравенств, имеющая вид пересечения систем и объединений линейных неравенств.
Разработанный итерационный метод поиска локального экстремума на основе идеологии активного набора применим не только к системам, но и к специальным структурам линейных неравенств, включающих как пересечение, так и объединение линейных неравенств.
Создана схема комбинации точного метода поиска локального экстремума с приближенными методами последовательного одиночного размещения. Такой подход позволяет не только улучшать результат, полученный приближенными методами, но и получать математически обоснованное решение практических задач Р-У.
Практическая ценность работы состоит в создании математического и программного обеспечения для решения задач построения двумерных планов раскроя-упаковки, с учетом технологических ограничений, возникающих при решении прикладных задач. Результаты вычислительного эксперимента показывают, что применение разработанного программного обеспечения позволяет улучшить решение, полученное приближенным методом на основе классического «жадного» алгоритма, на 0,5 - 8 %.
Основание для выполнения исследований
Работы в данном направлении проводились автором в Уфимском государственном авиационном техническом университете в 2002-2005 гг. в рамках проектов РФФИ 01-99-00937 и 01-01-00510.
Внедрение результатов: в учебном процессе Уфимского государственного авиационного технического университета; в Рекламном агентстве RMC (г. Уфа).
Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях:
Международная конференция «Информационные системы и технологии» (Новосибирск, 2003);
Российская конференция «Дискретный анализ и исследование операций» DAOR'04 (Новосибирск, 2004); XIII Байкальская международная школа семинар Иркутск-Северобайкальск «Методы оптимизации и их приложение» (Северобайкальск, 2005);
Научно-технические семинары кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета (2002-2005гг.).
Публикации. По теме диссертации опубликованы 7 работ, в том числе 5 статей и 2 материалов конференций.
Структура работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Объем основной части диссертации составляет 115 с, в том числе 48 рисунков, список литературы из 80 наименований на 9 с.
10 Основное содержание работы
В первой главе дается обзор существующих задач раскроя-упаковки, рассматриваются различные модели, дается их классификация. Развитие технологии инженерного проектирования привело к увеличению интереса к проблемам данной направленности. Это вызвано потребностью в экономии материальных и временных затрат, связанных изготовлением продукции в различных сферах промышленного производства. Не последнее место как по практической значимости, так и по сложности занимают задачи двумерного Р-У. В главе приводится постановка задачи размещения плоских геометрических объектов в общем виде, дается классификация методов ее решения. Кроме этого описываются основные подходы к решению, начиная от точных методов и заканчивая методами, основанными на дискретно-логическом представлении информации и цепном кодировании.
Во второй главе описывается предлагаемая математическая модель задачи нерегулярного размещения многоугольников на анизотропном материале и метод нахождения локального экстремума этой задачи. Математическая модель представляет условия размещения многоугольников в виде пересечения систем и объединений линейных неравенств, функцией цели служит длина занятой части области размещения — линейная функция. Предлагаемый итерационный метод решения основан на идеологии активного набора. Он позволяет на основе начального приближения получать математически обоснованный локальный оптимум задачи размещения ГО.
Третья глава посвящена алгоритмическому обеспечению, необходимому для построения разработанной математической модели и нахождению на ее основе локального экстремума для задачи размещения невыпуклых ориентированных многоугольников в заданной области с учетом технологических ограничений. В частности, описываются используемые алгоритмы для решения задачи в целом, построения выпуклой оболочки, разбиения невыпуклых многоугольников на выпуклые, построение годографов функций плотного размещения и внутренних годографов для многоугольников и области, алгоритм получения годографа невыпуклых многоугольников в виде набора непересекающихся выпуклых многоугольников и т.д.
В четвертой главе представлена схема комбинации метода поиска локального оптимума и приближенных методов на основе последовательного одиночного размещения. Данная схема позволяет получить математически обоснованное решение, найденное точным методом поиска локального экстремума и при этом использовать преимущества приближенных методов такие как, например, относительно высокую скорость получения решения, а также применять разработанный метод поиска локального экстремума независимо от вида используемого приближенного метода ПОР. В главе приведены примеры реализации данной схемы для классического «жадного» алгоритма и метода на основе подхода «первый подходящий с упорядочиванием» с использованием ДЛПИ и ЦК, а также результаты вычислительного эксперимента.
Заключение содержит основные выводы и результаты диссертационной работы.
Основные определения и постановка задачи размещения плоских геометрических объектов
Под плоским геометрическим объектом пространства R будем понимать двухпараметрические точечные множества, ограниченные соответственно замкнутыми, открытыми, связными или несвязными точечными подмножествами s, граница которых определяется каноническим уравнением [50]: /(х,У) = 0 (1-1)
Здесь знак = соответствует точкам, принадлежащим границе 5, знаки и соответствуют точкам, лежащим вне и внутри границы s, если s - замкнутая линия, или точкам, лежащим по разные стороны разомкнутой границы s.
Для задания границы области s может использоваться неканоническое Щ уравнение вида g(x,y) = 0, где g(x,y) = -f(x,y), где f(x,y) = 0 каноническое уравнение границы области s.
Из всего многообразия двумерных ГО будем рассматривать лишь замкнутые и разомкнутые многоугольные, т.е. границами которых являются отрезки прямых.
Положение ГО Р, являющегося двухпараметрическим множеством точек, в пространстве R2 будет однозначно определено, если будет известно положение связанной с ним двумерной системы координат. На рисунке 4 показано задание локальной системы координат для общего случая - -мерного пространства. Х /ОХ 2...Х к, связанной с ГО, относительно А-мерной системы XiOX2...Xk пространства Rk, требуется задать: начало координат - точку О (к параметров) и оси ОХ /с (по к-1 параметру на каждую в общем случае). Всего k + (k-l)xk = к2 параметров.
Таким образом, для однозначного определения положения двумерного ГО в / -пространстве требуется задать четыре параметра. Если же оси двумерной системы координат будут выбраны не произвольно, а связаны определенным соотношением, например, взаимно перпендикулярны, то число параметров для определения ГО в такой системе координат будет меньше на единицу, т.е. равно трем. Если обозначить -ТОГсистему координат плоскости, а Х О У - систему, связанную с ГО, $ - угол между осями ХО и О Х , то точечное множество, определяющее плоский ГО в двумерном пространстве и заданное каноническим уравнением (1-1) и согласно формулам преобразования движения, будет определяться неравенством: (1-2) Д(х - x )cos# + {у- у )sin6 , (у - /)cos 9 - (х - x )smO] = = F{x,y,x ,y\e) Q Движением (процессом размещения) будем считать такие преобразования ГО, которые сохраняют его форму, изменяя лишь параметры положения (в вышеприведенном примере это х\ у\ 9).
Очевидно, что эти преобразования составляют группу преобразований движения, включающую в себя параллельный перенос, поворот, центральную симметрию и их композиции.
Введем обозначения для внутренних точек ГО Р - IntP, для точек, лежащих на границе - clP, также обозначим операции пересечения, объединения и вычитания двух ГО Pj и Р2 соответственно [50].
Два ГО Pi и Р2 могут пересекаться IntPl f]IntP2 0, не пересекаться -р1 Г] Р2 = 0, касаться - clP, П с1Р2 Ф 0, IntP! П ШР2 = 0.
Под годографом функции плотного размещения (в дальнейшем -внешним годографом или просто годографом) Ну объекта Pj относительно Р, понимается такое множество положений центра объекта Pj, при котором выполняется условие IntPt П IntP: = 0 (рис. 5).
Внутренним годографом Ну объекта Pj относительно Р, понимается такое множество положений центра объекта Р,, при котором выполняется условие P.f]P. = Р. (рис. 5).
Размещением (укладкой, упаковкой) называется такое расположение ГО, когда они не имеют пересечений между собой, т.е. когда выполняется условие IntPt П IntPj = 0 Для всех пар ГО / и j её составляющих.
Существуют регулярные и нерегулярные (системные и несистемные, периодические и непериодические - синонимы) размещения.
Регулярные укладки в Rk -пространстве образованы параллельными переносами группы ГО той же размерности на векторы: amj=bj m О"3) где т = ±\,± 2,... +со;у 1,2,...,А. Остальные размещения составляют группу нерегулярных.
Качество заполнения пространства может быть оценено при помощи численной величины, называемой критерием размещения (заполнения),
В качестве критерия размещения могут выступать плотность заполнения или коэффициент использования при Р-У различных материалов, длина связывающей сети при размещении радиоэлементов на плате и т.д. Также может присутствовать не один, а комбинация критериев размещения, объединенных в общей целевой функции при использовании весовых коэффициентов или каким-либо другим способом. Однако все эти критерии, так или иначе, связаны с параметрами положения ГО, входящих в математическую модель того или иного процесса размещения. Уточнение критерия размещения производится при постановке конкретной задачи или класса задач.
Классификация методов решения задач нерегулярного размещения ГО
Эта техника основана на постепенном уточнении годографов. Этот подход был разработан Миленковиком [74].
Базовая идея метода разбиения - нахождение множества возможных позиций ГО в области и выполнение иерархического комбинаторного поиска на этом представлении.
Дано Су, обозначающее выпуклое подмножество множества R . Предположим, что точка размещения pt ГО Р{ находится внутри выпуклой области Су (Pj -Cj), для каждой пары ГО Pt и Pj, l i j n, и для каждой пары Pt и W, 1 i n, соответственно (рис. 10).
В связи с тем, что все Су являются выпуклыми, для определения координат размещения ГО с учетом условий взаимонепересечения и минимизации длины занятой части полосы могут быть использованы методы ЛП, например, симплекс-метод. Если С» с Н«,1 i j п, и CiW сHiW,1 i n, то координаты размещения, вычисленные методами ЛП, будут удовлетворять соответствующим ограничениям. Метод поиска для определения этих подмножеств Си с Ну, которые определяют оптимальное размещение, использует технику разбиения, базируется на постепенном уточнении годографов. Алгоритм поиска оперирует списками С = (C1W,...,CnW,Си,...,Сц,C(n_l)n,R,l),l i j n, и выполняет иерархический поиск, который можно представить деревом решений Т. Каждый узел дерева имеет свой собственный список С. Су фиксирует относительное положение двух ГО Pj и Pj как рассмотрено выше. R обозначает. конечное размещение, которое определяется решением соответствующей задачи ЛП и / обозначает длину занятой части полосы, соответствующей размещению R. Метод использует стек для хранения множества списков, который и обрабатывается в процессе решения.
Изначально, в стек помещается список С . Элементы С0 выбираются следующим образом: Су,=SR2,l i j n, и CIW =Ш2 J i n. Если С0 формируется таким образом, то всевозможные размещения (включая размещения, которые содержат взаимопересечения ГО между собой и с границей области) ГО в области Р-У могут быть получены.
На каждой итерации алгоритм берет очередной список С из стека. Во-первых, алгоритм делает проверку - есть ли в списке такой элемент Су, что Су- t Ну. Если не существует таких элементов, то С не нужно разбивать на части и при помощи методов ЛП может быть найдено такое размещение ГО, которое не содержит их взаимопересечений. Если полученная упаковка лучше, чем наилучшая из найденных ранее, то алгоритм сохраняет эту упаковку как новое лучшее размещение. Если же в списке есть такой элемент Су, что Ctj tH{j, то список С разбивается на два новых списка С1 и С2 так, что разбиваемый элемент С„ из С делится на Су и Су с условием Су zCy,z = 1,2. Су выбирается так, чтобы оно было выпуклым (для возможности применения методов ЛП с целью нахождения оптимального размещения) и такое, что Су П Ну Ф 0, если же последнее условие не выполняется, то размещения, которые соответствуют подмножеству Cz больше не могут быть свободны от взаимопересечений. Еще одним условие для выбора Су и Су является следующее: (Су U Су ) П Ну = Су П Ну. Это гарантирует, что нет таких возможных размещений Pi относительно Pj (определяемых Ну), которые были бы потеряны на шаге разбиения. Задачи, которые определяются списками Cz,z = l,2, проверяются на возможность применения методов ЛП.
Решение задачи поиска локального оптимума
Задачу нахождения локального экстремума с ОДР, заданную в виде ограничений (2-10) будем решать методом, основанным на идеологии активного набора. Для этого перепишем ее в следующем виде: требуется найти минимум линейной функции цели С=(с-х) с=(с;, сг, ...,с„}єКк и соответствующий ему вектор х=(хі, Х2, ...» Xji)&R на области допустимых решений:
При этом задана точка v=(v/, v2, ..., v/JtD - начальное приближение. Если задача состоит в минимизации занятой части области размещения, то вектор с=(0,0,0,...,0,1).
Идея метода: на каждом шаге выбирается вектор движения geR и его длина а. Новое приближение берется как v =v+ag. Основная задача - выбрать направление движения так, чтобы оно максимально уменьшало функцию цели.
Пусть в точке v активны к неравенств (активным будем называть то неравенство xn j +b , 0 (гиперплоскость в R ), которое в точке v превращается в равенство и точка v принадлежит непосредственно гиперграни хп . +Ь О области D, а не ее продолжению). В этом случае задачу нахождения оптимального вектора g можно записать в виде: найти g = min (gc) при условиях: 1- І?І=И- Если с=1, то ограничение можно записать как g=l или g2=l. 2. Для любого активного неравенства xn j + 6J 0, (/=0, 1,..., т J=\, 2,..., кт) (v + g)n j + b j 0. Так как в точке v эти неравенства активные, то vn j + bj - 0, следовательно, условие сведется к gn j 0.
Если решать задачу выбора направления движения в той формулировке, что описана выше, то это будет задача математического программирования с линейной функцией цели и квадратичными ограничениями. Для решения этой задачи можно использовать метод множителей Лагранжа и, например, метод ветвей и границ [ 19, 20], но применение такого подхода на практике затруднено из-за больших вычислительных затрат на решение данной задачи. Поэтому условие 1 было заменено более мягкими условиями gi \ и gi -\.
В этом случае, заменив вектор g на разность векторов у и Д, получим задачу линейного программирования: Начальное базисное решение д О, у=1, 2=1, у=0 и /ї=0 следует из формы записи задачи. Следовательно, базисными переменными будут (х, у, z). Здесь группа ограничений xJ= nJy + nJf3ij = l,2t...,u, где и - число активных неравенств, соответствует условию 2, а ограничения у. = у. + Д +1, г. = .-Д + 1, у. 0,Д 0, / = 1,2,. ..,п - первому условию. Решая данную задачу, найдем вектор направления движения g, имеющий минимальное расхождение с вектором уменьшения функции цели.
Для нахождения длины шага - а, каждая дизъюнкция или конъюнкция линейных неравенств проверяются на пересечения с лучом, исходящим из точки v в направлении вектора движения g. Для этого для каждой группы неравенств Dj (z-0,1,...,т) подсчитываются значения промежуточных величин р\-{уп1.) + У. и y ign .) (/=1, ..., к,). Для D0 определяются множества
Следовательно, получаем следующее приближение v =v+ag. Процесс заканчивается, когда в результате определения направления движения будет получен вектор g, такой, что (gc) 0. Последнее полученное решение v является локальным экстремумом.
Доказательство: предположим, что точка v не является точкой локального экстремума. Следовательно, 3g такой, что Vf є [ОД] v + tg eD, т.е. для всех неравенств, в том числе и для активных \ft е[0,\] (v + tg )n j +b\ 0 = tg n . 0, и ((v + g )c) (vc) = (g c) 0. Это противоречит тому, что минимальное скалярное произведение для векторов g, удовлетворяющих условию 2 больше или равно нуля.
Построение годографов для моделирования УВН и УРО
Артом [53] в его статье, посвященной проблеме карт раскроя. В западной литературе для годографа часто используют термин «no-fit polygon (NFP)» [56]. Годограф двух многоугольников А и В, обозначенный как Н4В, многоугольник, который получается из операции скольжения, в которой А и В имеют специфические роли. Первый многоугольник, А, в нижнем индексе определен как фиксированный многоугольник, чье начало отсчета принимается находящимся в точке (0,0). Второй многоугольник, В, назван трассирующим многоугольником, перемещается по контуру многоугольника А. Отслеживание движения В выполняется таким образом, что В не вращается и А и В всегда касаются, но никогда не перекрываются. Геометрическое место контрольной точки формирует замкнутый путь, который является НАВ. Рисунок 27 иллюстрирует это трассирующее перемещение. Если роли изменились, тогда результирующий годограф обозначается как НВА - НАЗ, повернутый на 180.
Таким образом, годограф определяет допустимую область размещения одного многоугольника относительно другого, причем его граница определяет точки касания многоугольников. Такой годограф будем называть внешним годографом. Если многоугольник В двигается не с внешней стороны, а с внутренней стороны границы многоугольника Л, то такой годограф И АВ будем называть внутренним. Внутренний годограф определяет условие размещения многоугольника В внутри многоугольника А.
Несколько исследователей [14, 75, 79] отметили связи между годографом и формой векторного дополнения, известного как сумма Минковского. Если А и В - два произвольных множества точек в л-мерном пространстве тогда сумма Минковского А а В считается как: АФ В = {а + Ь :а є А,Ь є В]. (3-1)
Для того, что бы убедиться, что А-В, известная как разность Минковского между А и В, эквивалентна НАВ достаточно векторной алгебры.
Свойства годографа могут использоваться в различных методах решения задач двух- и трехмерного Р-У для моделирования УВН и УРО. А
Алгоритм построения годографа для двух выпуклых многоугольников является простым, надежным и быстрым механизмом построения УВН. Рассмотрим выпуклые многоугольники А и В. Для построения годографа многоугольника В относительно многоугольника А - НАВ, многоугольник А ориентируется против часовой стрелки, многоугольник В - по часовой (рис. 28.а)). Затем все вектора ребер многоугольников помещаются в одну точку -получается диаграмма наклонов ребер многоугольников (рис. 28.6)). Если теперь приставить их друг к другу в порядке следования, соответствующем обходу диаграммы наклонов ребер против часовой стрелки, то получившийся многоугольник будет НАВ (рис. 28.в)) [56].
Будем считать, что все последовательности задаются в виде циклических списков, т.е. предыдущим элементом для первого будет последний, а следующим для последнего - первый.
Пусть контур многоугольника Л задается набором векторов (ей е2, .... e„J, а контур многоугольника В - (tt/, иг, -, U/J. Обозначим суммарное число ребер в многоугольниках А и В h=k+m. Список, состоящий из всех векторов многоугольника А и всех векторов многоугольника В, отсортированный по возрастанию углов наклона будет иметь вид: (g,, g?, ..., gij. Поместим g, в начало координат, тогда вершины многоугольника #, задаваемого таким списком будут: (0, g,, ..., gi+...+gh-і) или {ph р2, ..., pk), где
Так как вычисление углов наклона требует значительных вычислительных затрат, то в реализации алгоритма были использованы оценки, позволяющие однозначно ставить каждому углу наклона вектора ребра многоугольника оценку. В качестве оценок для векторов ребер v = (х,у) использовалась следующая величина:
Теперь необходимо установить соответствие между положением многоугольника Н и позицией многоугольника А так, чтобы при этом многоугольник Н соответствовал годографу НАВ. Вектор смещения многоугольника Н определяется как: (xf -хЧ -х?,у? -у! -y?) + vA =vH +vA, (3-3) где xf - значение абсциссы самой левой точки многоугольника А; x, - значение абсциссы самой правой точки многоугольника В; х" - значение абсциссы самой левой точки многоугольника Я; yf -значение ординаты самой верхней точки многоугольника Л; УІ - значение ординаты самой нижней точки многоугольника В; у" - значение ординаты самой верхней точки многоугольника Я; vA - координаты контрольной точки многоугольника А в глобальной системе координат.
На практике кроме условия на взаимное непересечения объектов часто требуется, чтобы объекты находились на определенном расстоянии друг от друга. В этом случае вышеописанный алгоритм не даст непосредственно условие на размещение многоугольников друг относительно друга.
Пусть d - заданное наименьшее расстояние между многоугольниками А и В. Такое расстояние называется эквидистантой и говорит о том, что как бы не располагались многоугольники А к В расстояние между их границами не должно превышать величины d. Тогда для описания условия на взаимное размещение этих многоугольников выполним дополнительную обработку многоугольника НАВ.
Будем считать, что никакие две точки среди точек р/, р2, ..., рь многоугольникаНлв не совпадают. Пусть и/, л2, ..., я/, - вектора внешних нормалей единичной длины соответствующих ребер многоугольника НАВ. Образуем список точек p[,p",p 2,p",...,p h,pl, где р\ = pt+dnt_ p-=Pi+dnt, і = 1,2,...,Л. Тогда годограф многоугольников А и В с учетов заданного минимального расстояния d между ними будет описываться замкнутым контуром, состоящим из дуг окружности радиусом d {р\,р") и отрезков (р",р м) (/ = 1,2,...,h) (рис. 29). Для представления полученного контура в виде многоугольника необходима аппроксимация составляющих его дуг.
