Задача взаимного размещения многогранников. Построение характеристического многогранника. Система плагинов
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
логично показывается, что, если С не содержит точку 0, то многогранники не пересекаются. Таким образом, граница множества С - характеристический многогранник. Стоит отметить, что это определение применимо не только к многогранникам, его можно использовать и для других объектов (к примеру, при построении характеристического множества для сферы и многогранника). В научных публикациях задачу построения характеристического многогранника часто называют задачей построения суммы Минковского двух многогранников.
Алгоритмы для выпуклых многогранников
Алгоритм, основанный на построении выпуклой оболочки
Пусть даны два многогранника P1 и P2. V - множество вершин P1, U - множество вершин P2. Определим множество точек W = V + - U. Построим выпуклую оболочку множества W. Граница этого множества - искомый характеристический многогранник [3].
Алгоритм, основанный на скольжениях
В этом алгоритме рассматриваются различные виды скольжений одного многогранника по другому и для случаев, когда скольжение возможно, строятся грани характеристического многогранника. Более подробно этот алгоритм будет описан ниже. В данной работе рассматривается этот алгоритм в силу того, что его легче обобщить для случая невыпуклых многогранников, нежели первый.
Алгоритмы для невыпуклых многогранников
Алгоритм, использующий разбиение на выпуклые многогранники
Разобьем многогранники P1 и P2 на несколько многогранников так, чтобы новые многогранники были выпуклые. Для каждой пары многогранников, такой, что один многогранник принадлежит разбиению P1, а другой - разбиению P2, построим характеристический многогранник (любым из рассмотренных выше способов). Объединив все построенные выпуклые характеристические многогранники, получим искомый характеристический многогранник. То, что полученный объект действительно является характеристическим многогранником, следует из свойств суммы Минковского:
(A U B) + C = (A + C) U (B + C)
(A U B) + (C U D) = (A + C) U (B + C) U (A + D) U (B + D)
и т.д. для произвольного количества множеств.
У этого метода есть существенные проблемы. Во-первых, если исходные многогранники сложные, то количество многогранников в разбиении будет велико, а, следовательно, количество выпуклых характеристических многогранников, которые нужно построить, также будет велико. Во-вторых, разработать эффективный метод объединения большого количества многогранников достаточно проблематично. Все это может привести к низкой производительности программной реализации алгоритма. Этот алгоритм и способы его оптимизации описаны в [4].
Алгоритмы, основанные на скольжениях
Аналогично, случаю выпуклых многогранников, рассматриваются все возможные скольжения и строятся грани. Но в данном случае, у построенных граней нужно удалить некоторые их части. Эффективные алгоритмы решения данной задачи для двухмерного случая (т.е. построения характеристического многоугольника) рассматриваются в статьях [5] и [6]. Алгоритмы, предлагаемые в них, основаны на том факте, что отрезки, образующие контур характеристического многоугольника, можно разбить на циклы и упорядочить. Для трехмерного случая аналогичное упорядочивание граней не всегда возможно.
В работе [7] приводится алгоритм, в котором части граней характеристического многогранника удаляются с помощью булевых операций. Из-за того, что для каждой построенной грани нужно решать задачу булевого вычитания невыпуклых многоугольников, при реализации этого алгоритма могут возникнуть проблемы с производительностью.
В данной же работе рассматривается другой способ удаления частей грани. Его идея заключается в том, что построенные грани разрезаются друг другом, а затем производится удаление ненужных частей путем проверки пересечения исходных многогранников.
В работе также описаны оптимизации, которые можно применить, чтоб получить эффективный алгоритм.
Алгоритм построения характеристического многогранника для случая выпуклых исходных объектов
Опишем процедуру построения характеристического многогранника для случая, когда оба исходных объекта являются выпуклыми многогранниками. Пусть P1 - неподвижный многогранник, P2 - подвижный многогранник, v0 - выбранная точка в системе координат P2. В результате скольжения P2 по P1, v0 описывает характеристический многогранник P.
При условии, что P1, P2 - выпуклые многогранники, P - также выпуклый. Грани многогранника P образуются в результате следующих видов скольжений:
вершина подвижного многогранника скользит по грани неподвижного
грань подвижного скользит по вершине неподвижного
ребро подвижного скользит по ребру неподвижного
грань подвижного скользит по грани неподвижного
ребро подвижного скользит по грани неподвижного
грань подвижного скользит по ребру неподвижного
Три последних случая являются вырожденными и в рамках данной работы рассматриваться не будут, т.е. мы считаем, что исходные данные таковы, что в них не возможны вырожденные скольжения. Рассмотрим каждый из невырожденных случаев скольжений отдельно.
Вершина подвижного многогранника скользит по грани неподвижного
Пуст?/p>