algorithm - 使用 minkowski 和进行碰撞预测

Question

我想使用 minkowski 和来预测两个凸形之间的准确碰撞点。根据我的理解，速度矢量与 minkowski 和相交的点是我必须沿着矢量移动我的对象的量，以便它们刚好接触(我已经知道它们会发生碰撞)。这是我的意思的一个例子(为了简单起见，我只使用了矩形):

我的意思是我可以只计算与凸包的每条线的交点，然后只使用最接近的线，但这看起来效率极低。我的想法是计算最接近向量的单纯形，但我不知道如何最好地做到这一点。我找到了一种算法，可以计算对象之间的最小距离，或者更准确地说，是从 minkowski 和到原点 (http://www.codezealot.org/archives/153) 的最小距离。算法的一部分试图找到最接近原点的单纯形，这正是我想要做的。我试图将其更改为我的需要，但我没有成功。对我来说，这听起来应该有一个非常简单的解决方案，但我对向量数学不是很好。

我希望我能说清楚我的问题，因为我的英语不太好:D

Answer 1

您可以将问题转化为:

1) 旋转平面使速度矢量变为水平

2) 考虑相互面对的多边形轮廓部分(这是两条凸折线)；现在你必须找到这两条折线之间的最短水平距离

3) 通过其中一条折线的每个顶点，绘制一条水平线；这会将平面分成一组水平切片

4) 使用剪切变换对每个切片进行变换，通过水平移动将定义它的两个顶点带到 Y 轴上；这个变换保留了水平距离

5) 在第一条折线转化为直线(Y轴)的同时，另一条折线转化为另一条折线；找到最接近 Y 轴的顶点。这为您提供了碰撞矢量的长度。

作为副产品，步骤 2) 会告诉您多边形是否发生碰撞，Y 值的范围是否重叠。