Algorytm Delaunaya

Algorytm Delaunaya to rodzina metod służących do konstrukcji triangulacji Delaunaya – podziału płaszczyzny (lub przestrzeni wyższych wymiarów) na trójkąty (odpowiednio czworościany), tak aby spełniona była własność Delaunaya: żaden z punktów nie leży wewnątrz okręgu opisanego na dowolnym trójkącie (w przypadku wyższych wymiarów – wewnątrz sfery opisanej na dowolnym simplexie). Algorytm został opracowany na podstawie prac Wojciecha Delaunaya i od tego czasu stał się podstawowym narzędziem geometrii komputerowej oraz wielu dziedzin inżynierii i nauk przyrodniczych.

Historia

Pierwsze formalne opracowanie własności Delaunaya pochodzi z 1934 roku, kiedy to francuski matematyk Wojciech Delaunay opublikował pracę o podziałach przestrzeni. W kolejnych dekadach, wraz z rozwojem komputerów, powstały liczne algorytmy umożliwiające efektywne wyznaczanie triangulacji Delaunaya. Do najważniejszych kontrybucji należą:

algorytm inkrementalny (lata 70.)
algorytm sweepline (algorytm Linde i Shewchuka, 1991)
algorytm podziału i zwyciężania (divide‑and‑conquer, 1986)
algorytm Bowyer‑Watsona (od lat 80.)

Podstawowe własności triangulacji Delaunaya

Własność kołowa – żaden punkt źródłowy nie leży wewnątrz okręgu opisanego na dowolnym trójkącie triangulacji.
Unikalność – przy założeniu ogólnego położenia punktów (brak czterech współliniowych i sześciu współpłaszczyznowych) triangulacja Delaunaya jest jednoznaczna.
Minimalność kąta – wśród wszystkich możliwych triangulacji minimalny kąt w dowolnym trójkącie jest maksymalizowany, co zmniejsza „wąskie” trójkąty.
Dualność z diagramem Voronoi – krawędzie triangulacji Delaunaya są prostopadłe do krawędzi diagramu Voronoi i tworzą jego dual.

Klasyczne algorytmy

Algorytm inkrementalny

Metoda polega na kolejnych wstawieniach punktów do istniejącej triangulacji przy zachowaniu własności Delaunaya. Po wstawieniu nowego punktu usuwa się wszystkie trójkąty, których okrąg opisany zawiera ten punkt, a następnie łączy się nowy punkt z wierzchołkami powstałej „dziury”.

// Pseudokod algorytmu inkrementalnego
Triangulacja D = Triangulacja_Poziomowa(); // trójkąt otaczający wszystkie punkty
dla każdego punktu p w kolejności losowej:
    C = {t ∈ D | p ∈ okrag_opisany(t)};   // trójkąty do usunięcia
    H = granica(C);                       // pętla (hole) otaczająca C
    usuń C z D;
    dla każdego krawędzi e w H:
        dodaj trójkąt (p, e.początek, e.koniec) do D;
zwróć D;

Algorytm sweepline (linia przesuwnikowa)

W tym podejściu przemieszczająca się wzdłuż jednej osi linia (zwykle pionowa) przetwarza kolejno punkty posortowane według współrzędnej x. Struktura danych aktywnych (najczęściej drzewo zbalansowane) przechowuje „przekrój” aktualnego diagramu Voronoi, z którego w czasie rzeczywistym konstruuje się krawędzie triangulacji Delaunaya.

Algorytm podziału i zwyciężania (divide‑and‑conquer)

Zbiór punktów jest dzielony na dwie połowy, każda podzbiorem jest przetwarzana rekurencyjnie, a następnie dwie triangulacje są łączone przy użyciu tzw. mostu Delaunaya, czyli najniższego łącza łączącego dwa podzbiory, które zachowuje własność kołową.

Złożoność obliczeniowa

Średnia złożoność O(n log n) dla algorytmu inkrementalnego (przy losowym porządku wstawiania) oraz algorytmu sweepline.
W najgorszym wypadku – O(n²) – gdy kolejność wstawiania jest niekorzystna (np. rosnąca wzdłuż jednej prostej).
Algorytm podziału i zwyciężania gwarantuje O(n log n) w każdym przypadku.

Zastosowania

Triangulacja Delaunaya oraz jej algorytmy znajdują zastosowanie w wielu dziedzinach:

Grafy i sieci – generowanie siatek do symulacji fizycznych.
Geometria komputerowa – modelowanie powierzchni, interpolacja danych (np. metoda kriging).
Grafika komputerowa – renderowanie terenu, meshing w modelowaniu 3‑D.
Geograficzne Systemy Informacyjne (GIS) – tworzenie warstw topologicznych.
Analiza danych – aproksymacja funkcji, klasteryzacja.
Robotyka i planowanie ruchu – wyznaczanie dróg w przestrzeni o zmiennych przeszkodach.

Implementacje i biblioteki

Wiele otwarto‑źródłowych bibliotek oferuje gotowe implementacje algorytmów Delaunaya, m.in.:

CGAL (Computational Geometry Algorithms Library) – algorytmy wysokiej precyzji w C++.
Qhull – implementacja algorytmu podziału i zwyciężania dla dowolnych wymiarów.
SciPy – funkcja scipy.spatial.Delaunay w Pythonie.
Triangle – biblioteka opracowana przez Jonathan Shewchuka.

Warianty i rozszerzenia

Triangulacja Delaunaya w wyższych wymiarach – zamiast trójkątów używa się simplexów (np. tetraedrów w 3‑D).
Triangulacja ograniczona (constrained Delaunay triangulation, CDT) – wprowadza się krawędzie, które muszą pozostać w wyniku, co jest przydatne w modelowaniu granic.
Triangulacja przybliżona (approximate Delaunay) – redukuje koszty obliczeniowe przy bardzo dużych zbiorach punktów.
Algorytmy dynamiczne – umożliwiają dodawanie i usuwanie punktów w czasie rzeczywistym bez konieczności pełnego przeliczenia triangulacji.

Przykładowy kod (Python + SciPy)

import numpy as np
from scipy.spatial import Delaunay
import matplotlib.pyplot as plt

# Przykładowy zbiór punktów
points = np.random.rand(30, 2)

# Budowa triangulacji Delaunaya
tri = Delaunay(points)

# Wizualizacja
plt.triplot(points[:,0], points[:,1], tri.simplices)
plt.plot(points[:,0], points[:,1], 'o')
plt.title('Triangulacja Delaunaya')
plt.show()

Literatura

O'Rourke, J. Computational Geometry in C. Cambridge University Press, 1998.
de Berg, M., Cheong, O., van Kreveld, M., & Overmars, M. Computational Geometry: Algorithms and Applications. 3rd ed., Springer, 2008.
Shewchuk, J. R. Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator, 1996.
Watson, D. F. Computing the n-Dimensional Delaunay Tessellation with Application to Voronoi Diagrams, 1981.

Algorytm Delaunaya stanowi fundament nowoczesnej geometrii komputerowej i jest nieodłącznym elementem wielu zaawansowanych systemów przetwarzania danych przestrzennych.