network of triangles such that the circle passing through the vertices of any triangle does not contain, in its interior, the vertex of any other triangle |
taka siatka trójkątów, dla której okrąg przechodzący przez wierzchołki dowolnego trójkąta nie zawiera w swoim wnętrzu wierzchołka żadnego innego trójkąta |
Triangulacja jest podziałem płaszczyzny na trójkąty spełniające następujące warunki:
- każde dwa trójkąty z mają wspólny bok lub nie mają części wspólnej wcale,
- każdy trójkąt ma część wspólną jedynie ze skończenie wieloma trójkątami,
- wnętrze okręgu opisanego na dowolnym trójkącie nie zawiera wierzchołków żadnego trójkąta.
Triangulacja Delanuay'a jest wykorzystywana do tworzenia sieci nieregularnych trójkątów na bazie punktów pomiarowych. Charakteryzuje się tym, że żaden z punktów zbioru nie trafia do wnętrza okręgu opisanego na trójkącie jakiegokolwiek innego trójkąta powstałego podczas triangulacji. Triangulacja Delaunay’a oparta jest na poligonach Thiessena lub diagramach Voronoi mających tę własność, że każdy punkt położony wewnątrz wieloboku ma najbliżej do punktu węzłowego, stanowiącego w kolejnym etapie przetwarzania wierzchołek trójkąta. Obrazowo można powiedzieć, że diagramy Voronoi przedstawiają strefy wpływu wokół każdego z danych punktów. Wynik triangulacji Delaunay’a jest unikalny tzn. nie zależy od kolejności punktów.
Dla czterech punktów tworzacych czworokat wypukly istnieja dwa podzialy na trójkaty, z których tylko jeden jest triangulacja Delaunay’a.
Rys. 23.4.10 Triangulacją Delaunay’a.
W sieci A jeden z punktów trafia do wnętrz okręgu opisanego na trzech innych punktach, co jest niezgodne z warunkiem triangulacji Delaunay’a. Poprawnie jest skonstruowana sieć B, w której żaden z punktów wejściowych nie trafia do wnętrza okręgu opisanego na trójkącie.