Skoki szablonowe
Skakanie po szablonie , czasami nazywane chodzeniem po szablonie , to algorytm lokalizowania elementu siatki otaczającego dany punkt dla dowolnej siatki strukturalnej. W prostych słowach, biorąc pod uwagę punkt i siatkę strukturalną , ten algorytm pomoże zlokalizować element siatki, który obejmie dany punkt.
Algorytm ten znajduje szerokie zastosowanie w obliczeniowej dynamice płynów (CFD) w zakresie wycinania otworów i interpolacji, gdy dwie siatki leżą jedna w drugiej. Inne warianty problemu byłyby mniej więcej takie: Biorąc pod uwagę miejsce, na jakiej szerokości i długości geograficznej ono leży? Algorytm brutalnej siły znalazłby odległość punktu od każdego punktu siatki i sprawdził, który jest najmniejszy. Innym podejściem byłoby użycie algorytmu wyszukiwania binarnego co dałoby wynik porównywalny pod względem szybkości z algorytmem przeskakiwania szablonów. Połączenie zarówno wyszukiwania binarnego, jak i algorytmu przeskakiwania szablonów zapewni optymalny wynik w możliwie najkrótszym czasie.
Zasada
Rozważmy jeden element siatki dwuwymiarowej siatki, jak pokazano, dla uproszczenia i rozważmy punkt O wewnątrz. Wierzchołki elementu siatki są oznaczone przez A, B, C i D, a wektory AB, BC, CD, DA, OA, OB, OC i OD są reprezentowane. Iloczyn krzyżowy OA i AB da wektor prostopadły do płaszczyzny wychodzącej z ekranu. Mówimy, że wielkość iloczynu krzyżowego jest dodatnia. Można zauważyć, że iloczyny krzyżowe OB i BC, OC i CD; a OD i DA są dodatnie.
Nie dzieje się tak, gdy punkt znajduje się na zewnątrz. Tutaj widzimy, że nie wszystkie iloczyny krzyżowe są dodatnie. Jest to główne kryterium testowania w algorytmie.
Jak to idzie do przodu?
Aby rozpocząć, algorytm potrzebuje elementu siatki zgadywania. Element siatki można znaleźć na podstawie położenia jednego punktu, powiedzmy A. Pozostałe punkty można zlokalizować automatycznie, uzyskując kolejne punkty. Wymagane produkty krzyżowe są następnie znajdowane w zamówieniu
- OA × AB
- OB × pne
- OC × CD
- OD × DA
Każdy z tych iloczynów krzyżowych jest sprawdzany jeden po drugim (w pokazanej kolejności), na którym pierwszy wynik jest ujemny. Jeśli OA × AB jako pierwsze stanie się ujemne, następne przypuszczenie powinno być o krok do przodu wzdłuż DA. Jeśli OB × BC jest najpierw ujemne, przejdź wzdłuż AB o jeden krok, aby znaleźć następne przypuszczenie i tak dalej.
Algorytm zbiegnie się dokładnie w tym elemencie siatki, w którym wszystkie iloczyny krzyżowe są dodatnie.
Zobacz też
- Rudy'ego A. Johnsona; Davy M. Belk (1993). „PODEJŚCIE WIELOSIATOWE DO ROZWIĄZAŃ WBUDOWANYCH SIECI” (PDF (wymagana opłata)) . Raporty techniczne: USAF, Wright Lab., Eglin AFB . AIAA-1993-769 . Źródło 2007-05-31 .
- EG Paterson; RV Wilson; F. Stern (maj 1998). Symulacja CFDSHIP-IOWA i Steady Flow RANS modelu DTMB 5415 (PDF) . I Sympozjum na temat morskich zastosowań CFD. P. 5. Zarchiwizowane od oryginału (PDF) w dniu 27 października 2004 r . Źródło 2007-05-31 .
- Prewitt, Nathan C; Belk, Davy M; Nieśmiały, Wei (2000). „Równoległe obliczanie przesuniętych siatek dla problemów aerodynamicznych z poruszającymi się obiektami”. Postęp w naukach lotniczych . 36 (2): 117. Bibcode : 2000PrAeS..36..117P . doi : 10.1016/S0376-0421(99)00013-5 .