Использование триангуляции при моделировании сложных объектов

УДК 519.6

ИСПОЛЬЗОВАНИЕ ТРИАНГУЛЯЦИИ ПРИ
МОДЕЛИРОВАНИИ СЛОЖНЫХ ОБЪЕКТОВ
В.С. Ловкайтес* студент гр. 325
Нацональный аэрокосмическим университет им. Н.Е. Жуковского к ХАИ»

В задачах моделирования и оптимального геометрического проектирования возникает необходимость обрабатывать взаимное поведение большого количества объектов!) условиях, когда теоритические методы наталкиваются на серьезные трудности, а натуральные эксперименты либо чрезмерно трудоемки, либо принципиально невозможны, численное моделирование часто оказывается единственным способом изучения рассматриваемых процессов.Чтобы сократить вычисления, в данной работе предлагается хранить информацию о соседних объектах.

Для этого используется планарная триангуляция. В качестве объектов в данной работе рассматриваются точки двумерного Пространства. На начальном этапе, на наборе точек строится произвольная триангуляция. Для этого в этой работе используется "жадный" алгоритм, шш может использоваться любой другой. Вначале каждая точка описывается своим положением и задается скорость ее движения. После этого объекты начинают двигаться и для моделирования их поведения нам достаточно проверять на возможность столкновения только соседние объекты, то есть те, которые соединены ребрами триангуляции. Каждая частица имеет свою массу и при столкновении отталкиваются по законам упругих тел. Эго позволяет вместо проверок порядка о(п2) выполнить шейное число проверок о(п). Во время движения триангуляция будет перестраиваться При декомпозиции такого рода модельная частица может столкнуться только с частицами, с которыми она связана ребром триангуляции или с частицей, лежащей по другую сторону от противоположного ребра. При пересечении частицей противоположного ребра триангуляции, она выходит из подсистемы. С этим событием связано перестроение части триангуляции. Предполагается, что ни одна частица изначально не пересекает любую другую. В данной роботе рассматривается следующее типы событий:
1) столкновение частиц, связанных ребром триангуляции;
2) пересечение частицей противолежащего ей ребра триангуляции;
3) столкновение частиц, находящихся по разные стороны пересекаемого ребра триангуляции.
В работе предложен алгоритм для пересчета триангуляции, при этом общая сложность алгоритма не увеличивается. В настоящее время разработан алгоритм, моделирующий поведение частиц и ведется его профМімиїи реаяизация.
* Научный руководитель — к.т.н., доцент кафедры 304 А.В. Карташов.