Collision Time Algorithm

We will be determining the time of collision between two linearly moving line segments where each of the 4 points has its own velocity

Test Program: programming\c++\TestCollisionTime
Files: None

The basics

We are only concerned with the collision of a point with a line segment. The line segment position and velocity has been adjusted so that the point is stationary at (0,0).

Formula of a line segment (0 < S < 1)

X = X₀ + (X₁-X₀)S
Y = Y₀ + (Y₁-Y₀)S

Formula of a moving line segment

You may think of the moving line segment as a line segment that changes its formula linearly over time from formula A to B.

Line segment meanings

A: Inital position of collision line segment
B: Final position of collision line segment
C: Linear interpolation of A and B based on the value of T. C=A at T=0. C=B at T=1.

The formulas for the Y component will be nearly identical so to save room they will not provided.

Line segment formulas

A: X = X_0,0 + (X_1,0-X_0,0)S
B: X = X_0,1 + (X_1,1-X_0,1)S
C: X = X_0,0 + (X_1,0-X_0,0)S + (X_0,1-X_0,0)T + [(X_1,1-X_0,1) - (X_1,0-X_0,0)]TS

Simplify the formulas.

dxA = (X_1,0-X_0,0)
dxB = (X_1,1-X_0,1)
dX = (X_0,1-X_0,0)

Condensed Line segment formulas

A: X = X_0,0 + (dxA)S
B: X = X_0,1 + (dxB)S
C: X = X_0,0 + (dxA)S + (dX)T + (dxB - dxA)TS

Setting T to a value will make C become a formula that contains the point (0,0). This is the time which the line segment collides with the point. Solving for T
We want to find the time T where (X,Y) = (0,0). We have two unknowns (S,T) and have two equations.
X = X_0,0 + (dxA)S + (dX)T + (dxB - dxA)TS
Y = Y_0,0 + (dyA)S + (dY)T + (dyB - dyA)TS

We set the left side of the equation to zero since X=0 then solve for S.

S=	(-X_0,0 - (dX)T )

	[(dxA) + (dxB - dxA)T]

S=	(-Y_0,0 - (dY)T )

	[(dyA) + (dyB - dyA)T]

Plug the suckers together.

	(-X_0,0 - (dX)T )

	[(dxA) + (dxB - dxA)T]

	(-Y_0,0 - (dY)T )

	[(dyA) + (dyB - dyA)T]