- Tytuł:
-
Fast point location algorithm on triangular meshes
Algorytm szybkiej lokalizacji punktu na siatkach trójkątnych - Autorzy:
-
Wichulski, M.
Rokicki, J. - Powiązania:
- https://bibliotekanauki.pl/articles/281814.pdf
- Data publikacji:
- 2008
- Wydawca:
- Polskie Towarzystwo Mechaniki Teoretycznej i Stosowanej
- Tematy:
-
algorytmy lokalizacji punktu
mesh generation
Chimera mathod
point location algorithms - Opis:
-
This paper is a study of application of persistent data structures to the planar and, in part, also spatial point location. In practice, a simplified method of building persistent red- black binary search tree is considered. It corresponds to the structure of a two-dimensional cell complex. Subsequent use of the structure for searching a certain point in space is shown. The computational mesh consists of triangular (in two dimensions) or tetrahedral (in three dimensions) cells. This fact allows significant simplifications to both implementation of the total order necessary to build the search tree as well as construction of the red-black binary search tree itself. The performance of the algorithm is verified for various meshes (consisting of up to 1846197 cells). Finally, certain further directions of the research are shown.
Artykuł przedstawia wyniki badań nad zastosowaniem dynamicznych struktur danych (ang. persistent data structures) do planarnej i przestrzennej lokalizacji punktu w siatce obliczeniowej, z wykorzystaniem czerwono-czarnych drzew poszukiwań binarnych, które odpowiadają strukturze dwuwymiarowego kompleksu komórek. Rozważana siatka obliczeniowa składa się z komórek trójkątnych (w dwóch wymiarach) albo czworościennych (w trzech wymiarach). Ten fakt zezwala na znaczne uproszczenia realizacja totalnego porządku niezbędnego do budowy drzewa poszukiwań, jak również konstrukcji samego czerwono-czarnego drzewa poszukiwań binarnych. Wydajność algorytmu jest sprawdzone dla różnych siatek obliczeniowych (zawierających od 1239 do 1846197 komórek). Wyniki eksperymentu numerycznego potwierdzają logarytmiczny czas lokalizacji i liniowo rosnące zużycie pamięci przy wzroście rozmiaru siatki. - Źródło:
-
Journal of Theoretical and Applied Mechanics; 2008, 46, 2; 315-324
1429-2955 - Pojawia się w:
- Journal of Theoretical and Applied Mechanics
- Dostawca treści:
- Biblioteka Nauki
Artykuł