W temacie o wyznaczaniu kolizji wielu kul, wspomniałem że optymalnym rozwiązaniem byłoby (prawdopodobnie) wyznaczenie od razu listy wszystkich kolizji w zadanych warunkach początkowych.
Zatem mamy zadanie:
jak zbudować/wyznaczyć tę listę kolizji dla n kul, posortowaną wg czasu?
Lista zawiera pary ciał, plus czas ich kolizji:
n, m, t;
ponadto zakładamy, że kule są zamknięte w pudełku, zatem w przypadku braku kolizji danej kuli z inną i tak wystąpi odbicie od ściany - co też nazywamy kolizją.
W związku z tym nietrudno zauważyć, że długość tej listy będzie mieścić się w granicach od n/2 do n.
Minimum = n/2 wystąpi w przypadku braku kolizji ze ścianami, natomiast pełne n otrzymamy gdy kule odbijają się tylko od ścian zbiornika.
Dane startowe (dla wersji 2D): r_i =(x,y), v_i = (vx,vy); i = 1..n;
rozmiary i masy kul są jednakowe: promień dowolny, np. R = 1.
Zatem wynikiem działania algorytmu ma być posortowana lista zderzeń o elementach: (i,j, t),
gdzie: i, j - numery kul od 1..n, ewentualnie: j = 0 dla odbicia od ściany; t - czas (pierwszej) kolizji kuli i.
Z warunków zadania widać że: każde i, jak i j może wystąpić tylko jeden raz w liście (pomijając j=0).