Detecting a Collision Between Two Bodies Undergoing Multiple Transformations

Question

I have been searching for an answer to this for a really long time and I have not found any definitive answers as of yet. What I am trying to do is determine if and when two bodies collided between the times t0 and t1. Calculating this is much more straight forward if each body is only either translating or rotating (about center or any point), but when adding multiple transformations on top of each other, things become a bit more messy. I made this animation to illustrate the problem.

As you can see, at times t0 and t1 there are no collisions, but between there are multiple collisions occurring.

One way I thought of for tackling this problem was to reduce the size of the time intervals. So, between t0 and t1 there would be a total of n updates to check for collisions. This works, but the only way I found that I could guarantee no false negatives, i.e. not finding a collision that happened, was to integrate over extremely small time-steps. As you can imagine, this is very costly because it resulted in the tens to hundreds of time-steps per body per update cycle. I am not saying this idea has no merit (it makes calculating the collision response much easier since I know the exact points of contact), but I would need to find a way to calculate the minimum number of time-steps rather than uniformly moving each body forward one unit of distance/rotation until they reach the desired position and orientation.

So, my question is two parts:

1. Is there a better way of determining if and when a collision occurs?
2. If not, is it possible to calculate the minimum number of time-steps?

P.S.

I think the maximum translation per time-step can be the shortest distance between any two points in the body. This would not allow it to hop over anything. When it comes to rotation about the center or orbiting a point I do not know how to determine the minimum angle. It probably has to do with the arc length, but what should that maximum distance be?

EDIT: this is not right. For a triangle, the base would be the shortest distance between two of its points, but the top could pass through something that is less wide than the triangle base.

Answer 1

There is a method of pixel-perfect collision detection for polygons such as this that involves using the dot-product operation. You essentially get the angle between each vertex of the shape and divide the screen into two sides and determine if the shape overlaps the other shape's "side" for any two vertices, and if so, move the shape outside of the other shape's collision area and a collision is detected.

Here is a short article on the method:

https://onense.wordpress.com/2011/11/04/the-dot-product-is-awesome-adventures-in-collision/