Численный анализ контактной функции - самый эффективный и простой способ представления форм

Question

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

I know its not 100% accurate.

I'm wondering how i can represent different shapes in the best, most uniform way for this algorithm to work at all. Shapes being mostly convex and concave polygons and/or different kinds of curves.

My main idea was to use some kind of spline: B-spline, or NURB, then i could interpolate it and create a polygon.

Then there's a problem with collision detection, for convex sets i'm using Теорема о разделении осей , но что делать с вогнутыми многоугольниками и кривыми, я понятия не имею.

Я пишу это на C + +17 и SFML2, никаких других сторонних библиотек (на данный момент, если есть какие-либо, которые мне помогут, пожалуйста, свяжите их в своем комментарии).

Answer 1

Многоугольное хранилище: вы делаете то, что считаете лучшим. Лично я видел много библиотек коллизий, которые включают полигональные объекты, с которыми конечный пользователь может возиться, и в основном они хранятся в виде массива точек против часовой стрелки: {{x1, y1}, {x2, y2 }} или {x1, y1, x2, y2}. Система столкновений отвечает за вычисление векторов нормалей.

Лично мне нравится хранить их в виде ребер ccw: {{x1, y1, dx1, dy1}, {x2, y2, dx2, dy2}}, где x1 + dx1 = x2 и y1 + dy1 = y2. Нормаль просто вычисляется как {-dy, dx}.

Для вогнутых многоугольников и SAT выбранное решение - разложить их на набор выпуклых многоугольников. Для этого существует множество al go, но я думаю, что триангуляция полигонов - ваш лучший выбор. Он оставляет самые простые формы, и есть несколько проверенных алгоритмов для достижения sh этого.

Для кривых, вот хороший ответ . Пиксельные коллизии с несколькими простыми многоугольниками будут достаточно эффективными (если вам это удобно), но разложение на вершины с малым разрешением - неплохой вариант (и он работает с SAT!)

Надеюсь Помогло :)