Slajd38 2

Triangulacja Delaunay i diagram Voronoi

Żaden z punktów zbioru wejściowego nie trafia do wnętrza okręgu opisanego na trójkącie powstałym podczas triangulacji. Własność ta jest równoważna kryterium kątów wewnętrznych - własność pustego koła opisanego

/ •*

Kryterium koła opisanego na trójkącie

a)

Operacja triangulacji Delaunay jest dualna (geometrycznie odwrotna) do diagramu Yoronoi Diagram Voronoi zbioru punktów jest dekompozycją przestrzeni na wielokątne obszary wokół każdego punktu w taki sposób, że wszystkie punkty z rejonu otaczającego wybrany punkt wejściowy są bliżej niego niż jakiegokolwiek innego punktu ze zbioru wszystkich punktów wejściowych. Reprezentuje rejon wpływów wokół każdego z danych zbiorów położeń i znajduje wiele zastosowań.

Jeżeli te położenia reprezentują sobą lokalizację np. stacji ratownictwa morskiego, to diagram Voronoi dokonuje rozdziału przestrzeni na komórki wokół każdej ze stacji. Dla każdej z jednostek pływających w pojedynczej komórce pojęcie stacja ratownicza określa najbliższe miejsce, w którym znajdują się służby gotowe nieść pomoc w razie wypadku lub katastrofy morskiej

Dualizm triangulacji Delaunay a) i diagramu Voronoi b)