接触函数的数值分析-表示形状的最有效和最简单的方法

Question

我正在做一个小作业，正如标题所说，这是关于接触函数的数值分析，更具体地说，我正在寻找两个不同形状内的两点之间的最近距离，以便这些形状相互接触(它们是相切的)。

​

我知道这不是100%准确的。

我想知道如何才能以最好、最统一的方式表示不同的形状，才能让这个算法发挥作用。形状主要是凸和凹的多边形和/或不同类型的曲线。

我的主要想法是使用某种样条线: B-spline，或NURB，然后我可以插值它并创建一个多边形。

然后是碰撞检测的问题，对于凸集，我使用Separating Axis Theorem，但如何处理凹多边形和曲线，我不知道。

我用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，选择的解决方案是将它们分解为一组凸面多边形。这方面有很多算法，但我认为多边形三角剖分是最好的选择。它留下了最简单的形状，有几种久经考验的算法可以完成它。

对于曲线，这里有一个很好的answer。用几个简单的多边形进行像素完美的碰撞就足够了(如果你对此感到满意的话)，但分解成具有严格分辨率的顶点并不是一个糟糕的选择(而且它适用于SAT!)

希望我能帮上忙:)