Discussion :

[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 ?

[Guesset]

Bonjour,

Le test de collision ne peut se limiter à un segment. Il faut au moins regarder le segment d'après (voir plus s'il y a un embranchement). La collision peut avoir lieu avec celle qui précède mais c'est son problème .

Comme je l'a déjà évoqué dans un autre fil, la distance peut être simplifiée en supposant le rayon de courbure raisonnable.

Sur un même segment Sn de longueur Ln, la distance entre 2 véhicules a et b (b derrière a : ratio_b < ratio_a) est approximativement (ratio_a - ratio_b) * Ln.

Avec a et b sur deux segments de suite, Lm et Ln, ce n'est guère plus compliqué : ratio_a*Lm + Ln - ratio_b*Ln.

Il y a sans doute mieux, mais cela me semble déjà intéressant. De plus on peut aisément gérer des véhicules de longueurs différentes (la position est celle de l'avant de chaque).

Salutations