Generator triangulacji Delaunaya

Generator Triangulacji Delaunaya zamienia dowolny zbiór punktów 2D w unikalną triangulację, która maksymalizuje najmniejszy kąt wewnętrzny — złoty standard w modelowaniu terenu, siatkowaniu metodą elementów skończonych, interpolacji najbliższego sąsiada oraz na zajęciach z geometrii obliczeniowej. Wklej współrzędne (lub wybierz wzorzec na szybki start), a narzędzie uruchomi algorytm Bowyera-Watsona po stronie serwera, pokoloruje każdy trójkąt według jego jakości oraz pokaże na żądanie właściwość pustego okręgu opisanego, otoczkę wypukłą i dual Woronoja.

Jak czytać wygenerowaną siatkę

Co wyróżnia ten generator triangulacji Delaunaya

Co to jest triangulacja Delaunaya?

Dla danego zbioru punktów 2D istnieje zazwyczaj wiele sposobów na połączenie ich w triangulację (całkowite pokrycie ich otoczki wypukłej trójkątami bez nakładania się i szczelin). Triangulacja Delaunaya, nazwana na cześć rosyjskiego matematyka Borisa Delaunaya (1934), to ta, która spełnia właściwość pustego okręgu opisanego: dla każdego trójkąta w siatce okrąg przechodzący przez jego trzy wierzchołki nie zawiera żadnych innych punktów wejściowych. Ta jedna właściwość ma niezwykłą konsekwencję: spośród wszystkich triangulacji tego samego zbioru punktów, triangulacja Delaunaya maksymalizuje najmniejszy kąt wewnętrzny. Mówiąc prostym językiem, tworzy ona najbardziej „szerokie” i „zrównoważone” trójkąty, jak to tylko możliwe.

Jak działa algorytm Bowyera-Watsona

1. Otocz wszystkie punkty wejściowe bardzo dużym supertrójkątem.
2. Wstawiaj po jednym punkcie wejściowym na raz. Dla każdego nowego punktu znajdź każdy istniejący trójkąt, którego okrąg opisany zawiera ten nowy punkt — są to „złe” trójkąty.
3. Usuń złe trójkąty. Otwór, który po sobie pozostawiają, ma wielokątną granicę.
4. Połącz nowy punkt z każdą krawędzią tej granicy, tworząc nowe trójkąty.
5. Po wstawieniu wszystkich punktów usuń wszelkie trójkąty, które nadal stykają się z wierzchołkiem supertrójkąta. To, co pozostaje, to triangulacja Delaunaya pierwotnego zbioru punktów.

Gdzie wykorzystuje się triangulację Delaunaya

• Modelowanie terenu (GIS): próbki wysokościowe (zazwyczaj rozmieszczone nieregularnie, jak stacje terenowe) są łączone w nieregularną sieć trójkątów (TIN) w celu obsługi zapytań o wysokość, cieniowania i wizualizacji 3D.
• Analiza elementów skończonych: dobrze ukształtowane trójkąty Delaunaya zapewniają stabilne rozwiązania numeryczne dla równań różniczkowych cząstkowych w mechanice, przepływie ciepła i elektromagnetyzmie.
• Grafika komputerowa: generowanie siatek do renderowania, riggowania postaci i proceduralnego terenu — gwarancja braku wąskich trójkątów w triangulacji Delaunaya pozwala uniknąć artefaktów rozciągania tekstur.
• Interpolacja naturalnego sąsiada: gładkie powierzchnie są rekonstruowane z rozproszonych próbek poprzez obliczanie naturalnych sąsiadów każdego punktu zapytania za pomocą dualu Woronoja.
• Zajęcia z geometrii obliczeniowej: kanoniczny algorytm mający głębokie powiązania z otoczkami wypukłymi, diagramami Woronoja, lokalizacją punktów oraz metodą dziel i rządź.
• Slicery do druku 3D i ścieżki narzędzi CNC: dwuwymiarowa triangulacja Delaunaya (oraz jej trójwymiarowy odpowiednik — tetrahedralizacja Delaunaya) leży u podstaw wielu strategii cięcia na warstwy i wypełnienia.

Delaunay a Woronoj: dwie strony tego samego medalu

Diagram Woronoja dzieli płaszczyznę na komórki (jedna komórka na punkt wejściowy), gdzie każda komórka zawiera wszystkie punkty położone bliżej jej punktu centralnego niż jakiegokolwiek innego. Połącz punkty, których komórki dzielą wspólną granicę, a otrzymasz dokładnie triangulację Delaunaya. I odwrotnie, środki okręgów opisanych sąsiednich trójkątów Delaunaya, połączone odcinkami linii, tworzą krawędzie Woronoja. Włącz opcję „Dual Woronoja” w tym narzędziu, aby zobaczyć pomarańczowe przerywane linie nałożone na ten sam wykres — każda krawędź Delaunaya przecina dokładnie jedną krawędź Woronoja pod kątem prostym.

Jakość, wąskie trójkąty i zagęszczanie siatki

Triangulacja Delaunaya maksymalizuje globalny minimalny kąt wewnętrzny, ale nie naprawi fundamentalnie złego rozkładu punktów. Jeśli Twoje punkty wejściowe są prawie współliniowe, skupione w klastry lub pozostawiają duże puste obszary, niektóre trójkąty nadal będą wąskie (minimalny kąt poniżej 20°). Rozwiązaniem jest wstawianie punktów Steinera: algorytmy takie jak algorytm Rupperta czy drugi algorytm Chewa iteracyjnie dodają nowe punkty w środkach okręgów opisanych wąskich trójkątów, wykonując triangulację za każdym razem na nowo, aż każdy trójkąt spełni docelowy próg jakości. Ten generator pokazuje, które trójkąty są wąskie, dzięki czemu wiesz, gdzie dodać punkty Steinera, jeśli chcesz uzyskać dokładniejszą siatkę.

Praktyczny przykład

Kliknij gotowy wzorzec „Okrąg + środek”. Narzędzie umieszcza 18 punktów wokół okręgu i 1 punkt w centrum, po czym dokonuje ich triangulacji. Wynikiem jest idealny wachlarz 18 trójkątów równoramiennych zbiegających się w środku — każdy z nich ma kąty 10° przy obwodzie oraz 80°–80° w środku. Najgorszy minimalny kąt wynosi 10°, wszystkie trójkąty są oznaczone jako wąskie, a histogram pokazuje wszystkie elementy w przedziale 0°–10°. Ten przykład doskonale uczy: nawet optymalna triangulacja Delaunaya może zawierać wąskie trójkąty, gdy zmuszają do tego dane wejściowe. Teraz kliknij „Losowa chmura” — ten sam algorytm generuje dobrze ukształtowane trójkąty, ponieważ punkty są rozłożone równomiernie, a histogram przesuwa się w prawo.

Powszechne błędy poznawcze

• „Triangulacja Delaunaya jest unikalna”: zazwyczaj tak, ale jeśli cztery punkty wejściowe leżą na tym samym okręgu (są współokręgowe), istnieją dwie prawidłowe triangulacje Delaunaya dla tej grupy. Generator spójnie wybiera jedną z nich.
• „Więcej punktów zawsze oznacza lepszą jakość”: dodanie źle rozmieszczonych punktów może wprowadzić nowe wąskie trójkąty. Algorytmy punktów Steinera rozmieszczają nowe punkty ostrożnie — w środkach okręgów opisanych — dzięki czemu poprawa jakości jest gwarantowana.
• „Triangulacja Delaunaya to to samo co otoczka wypukła”: nie. Otoczka wypukła to zewnętrzna granica; triangulacja Delaunaya wypełnia wnętrze trójkątami.
• „Wszystkie triangulacje wyglądają mniej więcej tak samo”: różnica jest diametralna. Jedno „odwrócenie” (flip) krawędzi Delaunaya może zmienić trójkąt o kącie 25° w trójkąt o kącie 5°. Mapa cieplna jakości w tym narzędziu doskonale uwidacznia tę różnicę.

Najczęściej zadawane pytania