Test de collisions de voitures par segment de graphe orienté

[guitz]

Bonjour,

Je cherche à optimiser un algorithme de detection de collision de voitures sur route (éviter qu'une voiture qui précède une autre lui rentre dedans). Sans prendre en compte les intersections.
Soit un graphe orienté G composés de Segments[] et Noeuds[].
Soit P le nombre de segments avec P <= 100
Chaque Segment est matérialisé par une spline.

Soit N le nombre total de voitures Voiture avec N <= 5000
Soit n le nombre max de voiture par segment, avec n <=50.

Voiture.SplineRatio = 0 si la voiture est au début de la spline, Voiture.SplineRatio = 1, si elle est en fin de spline, Voiture.SplineRatio = 0.333 si la voiture est au premier tiers de la spline , etc ...



Je pensais, en temps réel, stocker chaque pointeur de voiture présente sur un Segment dans cette propriété:
Segment.Voitures[]
Quand une voiture quitte un segment on enlève le dernier élément du tableau Segment.Voitures[], et quand elle arrive sur ce segment on ajoute son pointeur à l'index zero de ce même tableau. Ainsi, automatiquement Segment.Voitures[] est trié par Voiture.SplineRatio croissant.

Faire un test brut de collision aurait la complexité maximale C1 = N*N,
alors que faire un test de collision par segment et par Segment.Voitures[] trié par Voiture.SplineRatio croissant, aurait la complexité C2 = P *(n-1)
Avec C1Max = 25000000
et C2Max = 4900

Il n'y a vraiment pas photo, mais est ce que vous voyez une amélioration possible ?
-----

[polo974]

éviter qu'une voiture qui précède une autre lui rentre dedans

C'est étrange comme concept, moi j'aurai dit celle qui suit...

Plus sérieusement
Pour quelle raison arbitraire n'y aurait-il que 50 voitures par segment ?

Sinon, en connaissant l'ordre des voitures, l'une d'elle ne peut collisioner que celle devant elle. Ça devrait limiter les combinaisons.
Enfin, tant qu'il n'y a pas d'intersection ou de possibilité de dépassement.

Au fait, C1=N×(N-1), car peu de chance de s'autopercuter

Et C2 est à mon avis sous estimé, car il manque les cas où la voiture change de segment.

[MissJenny]

on ne voit pas pourquoi une voiture du segment i ne pourrait pas risquer d'entrer en collision avec une voiture du segment i+1 . Je ne pense pas que tu puisses traiter les segments undépendamment les uns des autres.