I am looking to optimize a collision detection algorithm for cars on the road (preventing a car behind another from crashing into it). Without taking into account intersections.

Consider a directed graph G composed of Edges[] and Nodes[].
Let P be the number of edges with P <= 100
Each Edge is materialized by a spline.

Let N be the total number of cars Car with N <= 5000
Let n be the maximum number of cars per edge, with n <=50.

Car.SplineRatio = 0 if the car is at the start of the spline, Car.SplineRatio = 1, if it is at the end of the spline, Car.SplineRatio = 0.333 if the car is at the first third of the spline, etc…

Segment means Edge in french

I thought, in real time, storing each car pointer present on a Edge in this property:
Edge.Cars[]
When a car leaves a edge we remove the last element from the Segment.Cars[] array, and when it arrives on this edge we add its pointer to index zero of this same array. So, automatically Edge.Cars[] is sorted by Car.SplineRatio ascending.

Doing a raw collision test would have the maximum complexity C1 = N*N,
while doing a collision test by edge and by Edge.Cars[] sorted by Car.SplineRatio increasing, would have the complexity C2 = P *(n-1)
With C1Max = 25000000
and C2Max = 4900

The second algorithm seems nice but do you see any possible improvement?

I have not implemented anything yes since i’m trying first to get the best algorithm possible.