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

You can transform the problem as follows:

1) rotate the plane so that the velocity vector becomes horizontal

2) consider the portions of the polygon outlines facing each other (these are two convex polylines); now you have to find the shortest horizontal distance between these two polylines

3) through every vertex of one of the polylines, draw an horizontal line; this will parition the plane into a set of horizontal slices

4) transform every slice using a shear transformation that brings the two vertices defining it onto the Y axis by horizontal moves; this transform preserves horizontal distances

5) while the first polyline is transformed into a straight line (the Y axis), the other polyline is transformed into another polyline; find the vertex(es) closest to the Y axis. This gives you the length of the collision vector.

As a by-product, step 2) will tell you if the polygons do collide, if the ranges of Y values overlap.