Алгоритм построения характеристического многогранника для случая выпуклых исходных объектов. Оценка вычислительной сложности. Построение характеристического многогранника, при условии, что исходные объекты необязательно выпуклые. Система плагинов.
Аннотация к работе
В компьютерном моделировании наиболее распространенный способ представления трехмерных объектов - аппроксимация их с помощью многогранников. Взаимное размещение многогранников - это широкий класс геометрических задач, включающий в себя такие задачи как: - проверку пересечения многогранников, каким-либо образом размещенных в пространстве, - определение, можно ли один или несколько многогранников поместить внутрь другого без пересечений, - оптимальное размещение, т.е. размещение многогранников таким образом, чтоб не было пересечений и некоторый функционал достиг минимума, - вычисление расстояния между двумя многогранниками, - поиск траектории движения подвижного многогранника от одной точки к другой, такой чтоб он не пересекался с неподвижным многогранником и другие. Алгоритмы решения этих задач имеют широкую область применения, включающую программные тренажеры, компьютерные игры, приложения для решения задач упаковки и раскроя, программы для управления роботами. В рамках этой работы будет рассматриваться одна