Декомпозиция на основе триангуляции в событийном моделировании

( 0 Votes ) 
Категория: ИКТМ 2013 Просмотров: 350

УДК 004.09: 519.8


Декомпозиция на основе триангуляции
в событийном моделировании
Р. О. Селезнёв, студент 355м группы
Национальный аэрокосмический университет им. Н.Е.Жуковского «ХАИ»


В данной работе была предложена модель движения твёрдых сфер в прямоугольной рабочей области, основанная на декомпозиции системы с использованием триангуляции [1].
Метод «частица-триангуляция», представленный в работе относится к широкому классу методов имитационного моделирования — методам частиц [2]. Для задач такого класса типичным является этап постановки вычислительного эксперимента.
В методе «частица-триангуляция» в качестве модельных частиц используются круги одинакового радиуса. Для декомпозиции системы предлагается провести триангуляцию над исходным набором модельных частиц. За единицу декомпозиции принимается подсистема, формально состоящая из трёх объектов: самой частицы, двух инцидентных ей частиц и трёх рёбер, соединяющих все частицы». При декомпозиции такого рода модельная частица может столкнуться только с частицами, с которыми она связана ребром триангуляции или с частицей, лежащей по другую сторону от противоположного ребра. При пересечении же частицей противоположного ребра триангуляции, она выходит из подсистемы. С этим событием связано перестроение части триангуляции. Предполагается, что изначально все круги, представляющие частицы, не пересекаются.
В рамках поставленной задачи были разработаны алгоритм декомпозиции системы с помощью триангуляции и алгоритм модели «частица-триангуляция». В основе алгоритма модели «частица- триангуляция» лежит дискретно-событийный подход [3J. Для данного алгоритма проведена оценка сложности. Количество возможных событий на каждой итерации равно 2dj, где dj — количество смежных частиц с і-ой частицей, что в общем случае даёт линейную сложность.
Список использованной литературы:

1. Препарата, Ф. Вычислительная геометрия: введение [Текст] / Пер. с англ. С.А. Вичеса, М.М. Комарова Ц Москва: «Мир», 1989. —478.
2. Хокни, Р. Численное моделирование методом частиц [Текст] / Р. В. Хокни, Дж. В. Иствуд — Москва: «Мир», 1987. — С. 640.
3.Чернышев, Ю. К. Событийное программирование. Применение к решению некоторых задач физики [Текст] / Ю. К. Чернышев // учеб, пособие - Харьков: Нац. аэрокосм, ун-т «Харьк. авиац . ин-т», 2008. - С. 68.

*Научный руководитель к.ф.-м.н., доцент А.В. Карташов