Niniejszy dokument prezentuje pracę dyplomową magisterską pod tytułem „Implementacje i aplikacje algorytmów triangulacji Delaunaya i DTFE dla N-wymiarowych zbiorów danych”. Celem realizowanym przez autora pracy było stworzenie implementacji triangulacji Delaunaya oraz algorytmu DTFE, który służy do interpolowania pól fizycznych z dyskretnego zbioru danych. Tymi interpolowanymi polami fizycznymi mogą być na przykład pola gęstości, czy też pola wektorów prędkości. Dane te są pozyskiwane z wielkich symulacji kosmologicznych. Symulacje te obliczają położenie pseudocząsteczek, w tym na przykład cząstek ciemnej materii, w oparciu o różne modele kosmologiczne. Cząstki oddziałują wszystkie ze wszystkimi, a położenie, masa i prędkość cząstki na danym etapie rozwoju Wszechświata są danymi wejściowymi do dalszego przetwarzania z wykorzystaniem algorytmu DTFE. Jeśli pseudocząsteczkami jest materia barionowa, to dodatkowo podlega siłom hydrodynamicznym i innym bardziej skomplikowanym procesom fizycznym.
Zaimplementowano przyrostowy algorytm konstrukcji triangulacji Delaunaya dla dowolnej liczby wymiarów, w którym starano się minimalizować użycie pamięci. W przypadku metody DTFE zaimplementowano zarówno wersję interpolowania danych w punkcie, w którym jest komórka siatki, jak i wersję z wykorzystaniem metody Monte-Carlo. Autor zaproponował również nową metodę, w której liczba próbek do metody Monte-Carlo jest obliczana w sposób dynamiczny, bazując na liczbie punktów w komórce siatki i sympleksów w tej komórce.
Algorytmy te zaimplementowane zostały z użyciem języka C i przygotowano te algorytmy do późniejszego zrównoleglania z użyciem biblioteki MPI. Zakres pracy obejmuje przegląd istniejących rozwiązań, teorię, która opisuje problemy związane z triangulacją Delaunaya i DTFE, implementację tych algorytmów oraz wyniki testów przeprowadzonych w trakcie tworzenia zaproponowanego rozwiązania.
The following document presents a master thesis titled „Implementations and applications of Delaunay triangulation and DTFE algorithms for N-dimensional data sets”. The goal realised by the thesis’s author was to create an implementations of Delaunay triangulation and DTFE algorithm, which serves to interpolate physical fields based on discrete data sets. Those interpolated physical fields could be, for example, density fields or velocity vector fields. This data comes from massive cosmological simulations. Such simulations calculate the position of pseudoparticles, including for example particles of dark matter, based on various cosmological models. Every particle interacts with each other and position, mass and velocity of particles at the given stage of Universe’s development are input data for further processing using DTFE algorithm. If we consider pseudoparticles of baryonic matter, then they are also subject to hydrodynamic forces and other, more complicated physical processes.
An incremental algorithm for constructing Delaunay triangulation for any number of dimensions has been implemented, where an attempt has been made to minimise the use of memory. In case of DTFE method two methods of interpolating data at given point have been implemented – one using an interpolation of point in centre of a cell of grid and also variation using Monte-Carlo method. Author has also proposed a new method, where number of samples for Monte-Carlo method is calculated in a dynamic way, based on the number of points in a grid cell and simplexes in this cell.
Those algorithms were implemented using C language and were prepared for later parallelisation using MPI library. The scope of this thesis includes survey of existing solutions, theory, which describes problems related to Delaunay triangulation and DTFE, implementation of those algorithms and the results of tests conducted during creation of proposed solution.
