Jaki jest najlepszy sposób wdrożenia jednowymiarowego wykrywania kolizji?

Question

Piszę fragment oprogramowania symulacyjnego i potrzebuję skutecznego sposobu testowania kolizji wzdłuż linii.

Symulacja dotyczy pociągu przejeżdżającego przez kilka przełączników na torze. Gdy koło znajdzie się w odległości N cali przełącznika, włącza się, a następnie wyłącza, gdy koło się opuszcza. Ponieważ wszystkie koła mają ten sam rozmiar, a wszystkie przełączniki są tej samej wielkości, mogę je przedstawić jako pojedynczą współrzędną X wzdłuż toru. Przełączniki odległości i odległości między kołami nie zmieniają się względem siebie, po ustawieniu.

Jest to dość trywialny problem, gdy wykonuje się go poprzez brutalną siłą, umieszczając współrzędne X na listach i przechodząc je, ale potrzebuję sposobu, aby zrobić to skutecznie, ponieważ musi być niezwykle dokładny, nawet gdy pociąg jest porusza się z dużą prędkością. Jest mnóstwo tutoriali na temat wykrywania kolizji 2D, ale nie jestem pewien, jak najlepiej sobie z tym poradzić w tym unikalnym scenariuszu 1D.

---

Wygląda na to, że moje dane są nieco zakłopotane.

Symuluję pojedynczą witrynę, a nie cały region. Pociągi mogą być dowolnej długości, z różnymi typami samochodów, ale jest tylko jeden pociąg. Moje dane pociągu mają postać {48,96,508,556,626,674,...}, wskazując odległości od frontu pociągu (0) do środka osi.

(dane pociąg częściej przychodzą do mnie w postaci uporządkowanej listyCarobiektów, z których każdy ma długość i listę liczb całkowitych reprezentujących odległości osi z przodu tego samochodu, ale wszystko zostanie połączone w jedną listę, ponieważ wszystkie osie są dla mnie takie same.)

Moje przełączniki znajdują się w odległości kilkuset stóp i często będą całkowicie pokryte pociągiem. Przełączniki mogą być w dowolnym przedziale czasowym od setki stóp do kilku cali od siebie, i jest w tej samej formie co pociąg: {0,8,512,520,...}, wskazując odległości od początku witryny do środka przełącznika h.

Wreszcie wiem, w jakiej odległości koło aktywuje przełącznik, w calach.

Na przykład, używając powyższych danych próbki i odległości aktywacji 8 cali, pierwszy przełącznik przy X = 0 aktywowałby się, gdy pociąg uderzył X = 40, co oznacza, że ​​pociąg ma 40 cali w miejscu. Gdy pociąg uderzy X = 48, włącza się również przełącznik przy X = 8. Przy X = 56, pierwszy przełącznik gaśnie, a przy X = 64, drugi przełącznik również gaśnie. Różne osie włączają i wyłączają różne przełączniki podczas przekraczania terenu.

Pociąg zwykle pracuje z prędkością poniżej 10 mph, ale może iść znacznie wyżej. (Teraz nasza symulacja jest ograniczona do 30 mph, ale wyższy byłoby świetnie.)

Answer 1

Przetwórz lokalizacje przełączników i zakres czułości na listę segmentów ścieżek. Każdy segment ma długość, a pomiędzy poszczególnymi segmentami zestaw zdarzeń "włącz" lub "wyłącz".

switch_on (0), (length: 8), switch_on (1), // x = zero here 
segment (length: 8), switch_off (0), 
segment (length: 8), switch_off (1), 
segment (length: 488), switch_on (2), 
segment (length: 8), switch_on (3), 
segment (length: 8), switch_off (2), 
segment (length: 8), switch_off (3), 
... 

Dla każdej osi, jego bieżące położenie jest również reprezentowane wraz z segmentem ścieżki, na którym się znajduje.

Jeśli robisz symulację zdarzeń opartych na następny event powinny być zaplanowane na wartości min odległości od osi do końca obecnej odcinka toru. Jest to niezależne od prędkości pociągu i dokładne (nie przeoczysz przełączników, jeśli pociąg jedzie szybciej). Przechowuj zdarzenia w sterty, jeśli to konieczne (często nie jest to warte mniej niż 30 dni, jeśli to konieczne, zaryzykuj planowanie zdarzeń).

tworzenie zdarzenie będzie O (nie-o-osiowe). Większość kroków obejmuje jedną lub dwie zmiany stanu przełącznika i aktualizację pozycji. Przy każdym zdarzeniu jedna oś spowoduje włączenie lub wyłączenie jednego przełącznika (przełączniki, które byłyby równoczesne zgodnie z danymi powodują dwa zdarzenia, zerowy odstęp czasowy) i wszystkie czasy osi do końca ich segmentów muszą być porównywane. Możesz założyć, że wszystkie osie poruszają się z tą samą prędkością, czy też nie; nie ma znaczenia, jeśli chodzi o przetwarzanie zdarzeń, tylko oblicza czas potrzebny do osiągnięcia następnego przełącznika właściwego dla danej osi.

Jeśli korzystasz ze stałej symulacji krokowej, przetwarzaj wszystkie zdarzenia, które miały miejsce do końca etapu, a następnie jedno zdarzenie, aby przesunąć osie do punktu, do którego docierają na końcu krok.

Answer 2

Czy posortowaną listę współrzędnych wszystkie przełączniki i wykorzystaj binarne przeszukiwanie na liście, aby znaleźć najbliższego przełącznika. Następnie sprawdź, jak daleko jest i czy nie jest kolizja.

O (log n)

Innym rozwiązaniem jest wykorzystanie faktu, że pociąg porusza się wzdłuż toru i można tylko kiedykolwiek zbliży się do dwóch przełączników, jeden z tyłu i jeden do przodu.

Skonstruuj listę podwójnie połączonych wszystkich węzłów i ustaw dodatkowy węzeł do oznaczenia pociągu we właściwej lokalizacji na liście połączonej. Następnie sprawdź tylko odległość do przełącznika, do którego pociąg zmierza.

O (1)

zaoszczędzenia pamięci przechowywać posortowane współrzędne w tablicy i po prostu śledzić których indeksy pociągu znajduje się pomiędzy nimi.

Answer 3

Przechowuj listę przełączników jako podwójnie połączoną listę wskazaną przez Ben.

Trzymaj wskaźnik w obiekcie koła (lub struktury, przy założeniu, że istnieje) do następnego i poprzedniego przełącznika przełącznika w stosunku do aktualnej pozycji. Wymień je, gdy koło zostanie umieszczone na torze.

Podczas poruszania się po każdym przełączniku, zamień "następny" i "poprzedni" przełącznik w swoim obiekcie koła na nowe "następne" i "poprzednie", które można szybko uzyskać, analizując podwójnie połączoną listę.

Pozwala to uniknąć wszystkich wyszukiwań, z wyjątkiem ewentualnego początkowego umieszczenia koła.

Dodatkowo, „włącznik” struktura może być używane do przechowywania bliskości wyżeł z powrotem do wszystkich kół, które są wymienione jako „Poprzednia” lub „Dalej”. (Tutaj jest muteks, więc uważaj na to, kto to aktualizuje.) To może zapewnić szybką aktualizację tego, kto zbliża się do danego przełącznika i jego odległość od niego.

Answer 4

Zakładając, że odległości między osiami są zawsze większe niż odległość aktywacji, a trasy nie zmieniają się często po wejściu pociągu, powinieneś być w stanie przyspieszyć działania dzięki wstępnemu obliczeniu. Zasadniczo dla każdego przełącznika obliczyć listę odległości przejazdu pociągu, przy której będzie się przełączać, a następnie przechodzić przez listy w miarę postępu pociągu.

Pseudokod:

axles = {48,96,508,556,626,674,...} 
switches ={0,8,512,520,...} 
activate = 8 
float toggledist[num_switches] 
boolean switchState[num_switches]={false,false,false,...} 
int idx[num_switches] 

for (i in switches) 
    n = 0 
    for (a in axles) 
    toggledist[n++] = switches[i]+axles[a]-activate 
    toggledist[n++] = switches[i]+axles[a]+activate 

travel= 0.0f; 

each (cycle) 
    travel += TrainVelocity*time; 
    for (i in switches) 
    while (trigger>=toggledist[idx[i]]) 
     switchState[i]=!switchState[i]; 
     //additional processing for switch change here, if needed 
     idx[i]++;