algorithm - collision prediction using minkowski sum

Question

I want to use the minkowski sum to predict the exact point of collision between two convex shapes. By my understanding the point where the velocity vector intersects with the minkowski sum is the amount I have to move my object along the vector so they just touch (I already know they will collide). Here's an example of what I mean (for simplicity reasons I just used rectangles):

I mean I could just calculate the intersection with every line of the convex hull and just use the closest but that seems horribly inefficient. My idea was to calculate the simplex closest to the vector but I have no idea how best to do it. I found a algorithm which calculates the smallest distance between to objects or to be more precise the smallest distance from the minkowski sum to the origin (http://www.codezealot.org/archives/153). One part of the algorithm tries to find the simplex closest to origin which is kinda what I want to do. I tried to change it to my needs but I wasn't successful. To me it sounds like there should be a very simple solution but I am not that good with vector math.

I hope I could make my problem clear since my english is not so good :D

Answer 1

您可以按如下方式转换问题：

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

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

3）通过其中一条折线的每个顶点，画一条水平线；这会将平面划分为一组水平切片

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

5) 当第一条折线转换为直线（Y轴）时，另一条折线转换为另一条折线；找到最靠近 Y 轴的顶点。这为您提供了碰撞矢量的长度。

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