Задача взаимного размещения многогранников. Построение характеристического многогранника. Система плагинов
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?, лежащих внутри характеристического многогранника
Рассмотрим каждый из этих шагов подробней.
Поиск пересекающихся граней
На этом шаге для каждой грани f ищется множество граней, с которыми она пересекается. Вычисляются отрезки, образуемые при пересечении грани f с найденными гранями. Эти отрезки лежат в плоскости грани f. Чтобы ускорить поиск пересекающихся граней, можно использовать, так называемую иерархию ограничивающих объемов [8].
Рис. 7. Пересекающиеся грани
Разрезание граней
После того как для каждой грани найдено множество отрезков, грань необходимо разрезать. Для того чтоб разрезать грань f:
1.В плоскости f строится триангуляция с ограничениями, в которой в качестве входных точек используются вершины грани f, а в качестве структурных ребер - полученные ранее отрезки. Алгоритмы построения триангуляции с ограничениями рассмотрены в [9].
2.Грань f заменяется множеством полученных в результате триангуляции треугольных граней.
Рис. 8. Разрезание граней
Удаление граней, лежащих внутри характеристического многогранника
После разрезания образуется множество граней, которое можно разделить на две группы:
грани, которые образуют поверхность искомого характеристического многогранника.
грани, которые лежат полностью внутри характеристического многогранника.
Грани, принадлежащие второй группе, нужно удалить. Для этого воспользуемся следующим свойством исходных многогранников: они пересекаются тогда и только тогда, когда выделенная точка подвижного многогранника v0 лежит внутри характеристического. Проверку пересечения многогранников можно осуществлять с помощью какого-либо готового алгоритма. Для того чтоб определить, лежит ли грань внутри характеристического многогранника, достаточно проверить лежит ли внутри ее центр.
Таким образом, для каждой грани:
1.С помощью алгоритма проверки пересечений проверяется, пересекаются ли исходные многогранники (неподвижный многогранник ставится в начало координат, подвижный - так, чтоб v0 совпала с центром грани).
2.Если есть пересечение, то грань удаляется.
Рис. 9. Результат удаления частей граней
Оставшееся множество граней - грани искомого характеристического многогранника.
Оценка вычислительной сложности
Пусть неподвижный многогранник P1 содержит V1 вершин, подвижный многогранник P2 - V2 вершин.
Вычислительная сложность дополнительной проверки вершин и ребер равна O(V1 + V2).
Вычислительная сложность построения граней, как было выяснено ранее, равна O(V1*V2).
Алгоритм удаления частей граней состоит из трех шагов, оценим вычислительную сложность каждого из них.
1.Поиск пересекающихся граней.
На вход подается множество граней, количество которых пропорционально V1*V2. Необходимо проверить пересечение каждой грани с каждой. То есть вычислительная сложность этого шага O((V1*V2) )
2.Разрезание граней.
Будем считать, что количество отрезков, образуемых при пересечении грани с другими гранями, мало по сравнению с V1 и V2. В таком случае, вычислительной сложностью триангуляции можно пренебречь. Значит, вычислительная сложность этого шага пропорциональна количеству граней, то есть равна O(V1*V2)
3.Удаление граней.
Считаем, что количество граней полученных на предыдущем шаге так же пропорционально V1*V2. Для каждой грани нужно сделать проверку, пересекаются ли исходные многогранники. Сложность каждой такой проверки O(V1*V2). Значит, вычислительная сложность шага равна O((V1*V2) ).
Итого, вычислительная сложность алгоритма равна O((V1*V2) ).
Время работы алгоритма
Время построения характеристического многогранника для различных входных данных.
Неподвижный многогранникПодвижный многогранник Время (сек.)Количество гранейКоличество вершинКоличество гранейКоличество вершин281620120,0079140729604820,314243212167803905,037682034104998250182,8449982501950947421099
Программная реализация
Особенности программной реализации алгоритма
Алгоритм построения характеристического многогранника был реализован на языке C++ с использованием библиотеки STL. Алгоритм оформлен в виде отдельного модуля с удобным интерфейсом, благодаря чему его легко можно использовать в других программах. Для работы с векторами, многогранниками и другими структурами данных была написана собственная математическая библиотека.
Стоит отметить следующие особенности реализации отдельных шагов алгоритма:
1)Для оптимизации поиска пересекающихся треугольных граней используется дерево ограничивающих параллелепипедов [8].
2)Проверка пересечений отдельных граней и построение отрезков, вдоль которых грани пересекаются, осуществляется с помощью быстрого алгоритма пересечения треугольников Моллера [10].
)Триангуляция с ограничениями строится жадным алгоритмом [9]. Выбор этого алгоритма обусловлен тем, что количество элементов участвующих в построении триангуляции невелико: три точки (вершины грани) и несколько отрезков, полученных при пересечении с другими гранями. В перспективе можно попробовать применить другие способы триангуляции и сравнить полученные результа