Куликов А.И.
Взаимное размещение многоугольников на плоскости
ВЗАИМНОЕ РАЗМЕЩЕНИЕ МНОГОУГОЛЬНИКОВ НА ПЛОСКОСТИ.
А.И. Куликов
ИВМиМГ СО РАН, Новосибирск
kulikov@nmsf.sscc.ru
В работе рассматриваются две задачи размещения двух простых многоугольников один из которых неподвижен, а другой может перемещаться путём параллельного переноса и вращения.
Первая задача заключается в том, чтобы найти все возможные положения подвижного многоугольника, при которых он находится внутри неподвижного, касаясь его по крайней мере в двух точках. Получено явное аналитическое решение этой задачи.
Вторая задача состоит в том, что при заданном перемещении подвижного многоугольника необходимо определить находится ли он внутри неподвижного. Для случая когда неподвижный многоугольник выпуклый получено явное аналитическое решение.
С целью оптимизации в обеих задачах используется аппарат предвычислений. Определение находится ли один многоугольник внутри другого выполняется за логарифмическое время.
Эти алгоритмы могут использоваться при навигации и проверки столкновений, в компьютерных играх, программных тренажерах.
ЛИТЕРАТУРА
1. Luis Barba, Stefan Langerman. Optimal detection of intersections between convex polyhedral, 2014.
2. Куликов А.И. Некоторые задачи вычислительной геометрии. Изогеометрическое сглаживание и геометрический поиск. International Conference Graphicon, Novosibirsk Akademgorodok, 2005.
К списку докладов