I forgot to come back to this question when I arrived at an answer, but this has gotten a decent amount of views over time, so better late (even 2 years late) than never! First, prerequisites:
First, one has to be able to calculate the time of collision (TOC) of two circles. Step 3 of this question Small, High-Speed Object Collisions: Avoiding Tunneling provides an adequate formula.
Next: be able to find a point/circle TOC: simply take the equation linked above and set one of the circles' radii to 0 to represent the point.
Next: be able to find a point/line segment TOC. A simple way to do this (I'm sure there are better ways, this is just a starting point):
- Shift all relative motion to the point, so you have a moving point and a "stationary" line.
- The point's path (described by a line) intersects the line containing the line segment (or it is parallel). For line/line intersection, takes equations Ax + By = C (for line segment...A=y2-y1, B=x1-x2, and C = x1*y2-x2*y1) and paramaterized equation Px + Vxt and Py + Vyt for moving point and solve for t: (C - APx - BPy) / (AVx + BVy). I chose these forms so I don't have deal with horizontal/vertical cases. If the denom is 0, the lines are parallel.
- Once you have a time/point of intersection, check and see if that point lies on the line segment.
"Reduce" the circle to a point, and "grow" the rectangle by radius r of the circle. The result is that the 4 sides (red) of the rect are translated out (orange) and the corners are expanded out and rounded by radius r. We know how to find the TOC for point/circle and point/line segments, so find the earliest TOC of the point with those 8 shapes representing the surface of our new shape (the 4 orange lines and the 4 blue circles). That is your answer. (There may the collisions with parts of the circles that are not on the surface, but your algorithm will ignore those automatically since the point will already have penetrated the surface at an earlier time). If there is no TOC, then there is no collision. Beware of "past" collisions when the objects are moving away from each other.
Start with one rect as the "point" rect and the other as the "side" rect. Find the TOC (if it exists) with each point on the point rect compared to each side of the side rect. That's 16 checks. Switch the rects and repeat for a total of 32 checks. The earliest non-imaginary and non-past TOC (if it exists) is the TOC. Note that any "side-side" collision of two rects can be treated as a "point-side" collision, and that is how this algorithm handles it.
This may all seem extremely inefficient, but keep three things in mind:
- Good broadphase and medium-phase collision detection is important to make sure you are doing all of these expensive calculations as little as possible
- Directional optimizations are possible (e.g. only check a few of those 32 rect/rect pairs that are facing in the appropriate directions)
- These are extreme algorithms, designed for small objects colliding at extraordinary speeds. If the situation truly calls for an algorithm like this (e.g. 2 meter-sized objects colliding at relative speeds of 1000's of km's per second), these "inefficient" algorithms will be much better than most traditional alternatives.