Trójkącja Delaunay: Trójkąty Bez Punktu Wewnątrz Ich Okręgu

Jednoństwo: żaden punkt wewnątrz żadnego okręgu wpisowego

Rozpatrując zbiór punktów w płaszczyźnie, zazwyczaj istnieje wiele sposobów na połączenie ich w trójkąty, które pokrywają ich wypukłą obłukę. Wariacja Delaunay, nazwana na cześć rosyjskiego i radzieckiego matematyka Borisa Delauna, który opisał ją w 1934 roku, jest tą konkretną triangulacją z niezwykłą właściwością: dla każdego trójkąta w niej zawartego okrąg przechodzący przez jego trzy wierzchołki – okrąg wpisowy – nie zawiera żadnego innego punktu zbioru wewnątrz siebie. Okrąg wpisowy każdego trójkąta jest pusty.

Ta jedna zasada ma potężną konsekwencję: spośród wszystkich możliwych triangulacji zbioru punktów, wariacja Delaunay to ta, która maksymalizuje minimalny kąt. Systematycznie unika długich, wąskich trójkątów strzemieniowych, które powodują niestabilność numeryczną siatek elementów skończonych i sprawiają, że modele terenowe wyglądają na podziałone i nieprawidłowe. Jeśli triangulacja nie jest wariacją Delaunay, istnieje para sąsiednich trójkątów, których wspólny bok można odwrócić do drugiej przekątnej czterościanu, a to odwrócenie zawsze poprawia najgorszy kąt – wariacja Delaunay to stan, w którym takiego poprawnego odwrócenia nie istnieje.

Bowyer-Watson: wstaw punkt, wyrób przestrzeń

Algorytm powyżej jest Bowyera-Watsona, opublikowany niezależnie przez Adriana Bowyra i Davida Wattona w 1981 roku. Buduje on triangulację stopniowo, jeden punkt naraz, i działa dzięki właściwości pustego okręgu wpisowego, która jest lokalna i łatwa do sprawdzenia:

zacznij od jednego dużego "super-trójkąta", który obejmuje wszystkie punkty wejściowe dla każdego nowego punktu p: zły = każdy istniejący trójkąt, którego okrąg wpisowy zawiera p pusta przestrzeń = wieloboczne krawędzie pozostałe po usunięciu wszystkich "złych" trókatów usuń zły trójkąt przerabiaj triangulację: połącz p z każdym brzegiem wielobocznej krawędzi usuń każdy trójkąt, który nadal dotyka wierzchołka super-trójkąta Sprawdzenie, czy punkt leży wewnątrz okręgu wpisowego trójkąta, polega na jednym teście znaku wyznacznika na trzech wierzcholkach i kandydatowym punkcie – tanie, dokładne z arytmetyką całkowitą lub ostrożną liczbą zmiennoprzecinkową, a powód, dla którego inkrementalny kod Delaunay jest wystarczająco krótki, aby zmieścić się na jednym ekranie. Trójkąt super-trójkąta unika konieczności specjalnego przypadku brzegów wypukłego pancerza: wszystko zaczyna się wewnątrz jednego dużego trójkąta, a rogi tego dużego trójkąta są usuwane pod koniec.

start with one huge "super-triangle" that encloses every input point

for each new point p:
    bad = every existing triangle whose circumcircle contains p
    cavity = the boundary polygon left after removing all "bad" triangles
    remove the bad triangles
    re-triangulate: connect p to every edge of the cavity boundary

remove any triangle still touching a super-triangle vertex

Diagramy Woronowa to ta sama informacja, odwrócona do góry nogami

Diagramy Woronowe dzielą płaszczyznę na jedną komórkę dla każdego punktu, w której komórka zawiera wszystkie lokalizacje bliższe temu punktowi niż jakikolwiek inny. Wygląda to na zupełnie inną konstrukcję, ale jest to dokładna dualna graficzna trójkąta Delaunay: połącz środki okręgów opisujących każdy parę trójkątów, które dzielą krawędź Delaunay, a otrzymasz krawędzie Woronowe. Każdy trójkąt Delaunay ma środek okręgu, który jest wierzchołkiem Woronowym, a każda krawędź Delaunay jest przecinana dokładnie jednym pionowym krawędzią Woronową. Oblicz jedną strukturę i druga jest na odległość liniowej.

Delaunay triangle          →  Voronoi vertex   (its circumcenter)
Delaunay edge (shared by
  two triangles)           →  Voronoi edge      (perpendicular, joining
                                                  the two circumcenters)
Delaunay vertex (a point)  →  Voronoi cell      (region closest to it)

Gdzie to się w rzeczywistości wykorzystuje

Metody oparte na elementach skończonych (MESZ) wykorzystują udoskonalanie Delaunay'a, aby wypełnić elementem konstrukcji inżynierskiej dobrze ukształtowane trójkąty lub tetraedry, ponieważ właściwość pustego okręgu obiega bezpośrednio najgorszy kąt, który z kolei ogranicza błąd numeryczny symulacji działającej na siatce. Oprogramowanie terenowe i GIS buduje triangulację Delaunay'a na próbkach wysokości (TIN, trianglowana nieregularna sieć) ponieważ unika długich, cienkich trójkątów, które sprawiają, że krajobraz wygląda sztucznie ostre. Planerzy sieci bezprzewodowych wykorzystują podwojny Voronoi'a, aby modelować komórki pokrycia wokół wież, a biologia obliczeniowa wykorzystuje go do znajdowania najbliższych sąsiadów każdej komórki w tkance. Oba te struktury bezpośrednio odpowiadają na zapytania o najbliższego sąsiada: komórka Voronoi zawierająca punkt zapytania identyfikuje jego najbliższy punkt danych dzięki konstrukcji, a triangulacja Delaunay jest najrzadszą grafową strukturą gwarantującą zawartość prawdziwego krawędzi najbliższego sąsiada dla każdego punktu.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Delaunay & Voronoi i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.