Punktem centralnym na diagramie jest zdegenerowana krawędź diagramu Voronoi. Jeśli wygenerujesz diagram Voronoi dla nieregularnej chmury punktów, każdy wierzchołek będzie miał stopień 3. Wierzchołek o stopniu 4 (lub więcej) może wystąpić tylko wtedy, gdy dwa (lub więcej) wierzchołki się pokrywają. Oznacza to, że między nimi jest krawędź zerowa. Ale ta krawędź powinna nadal mieć odpowiednią krawędź w triangulacji Delaunaya. Problem polega na tym, że dowolne z dwóch możliwych krawędzi wybierzesz, ponieważ krawędź o zerowej długości nie ma powiązanego kierunku.
Aby zwizualizować to, o czym mówię, rozważ rozpoczęcie od czterech mniej rozmieszczonych punktów (tak, że zaczynamy tylko od wierzchołków stopnia 3) i stopniowe przekształcanie ich w ich regularne pozycje.
Możemy to zrobić na dwa różne sposoby, które prowadzą do zdegenerowanego przypadku na twoim diagramie. Przekonasz się, że skończysz z dwoma różnymi triangulacjami Delaunaya, które są obowiązującymi limitami dla przypadku zdegenerowanego:
Zakładam, że z jakiegoś powodu w twoim kodzie brakuje tego zdegenerowanego przypadku, ale nie widząc, w jaki sposób obliczasz triangulację Delaunaya z diagramu Voronoi, nie możesz wskazać ci dalej.
Zauważ również, że posiadanie jeszcze wyższych degeneracji (o więcej niż cztery punkty rozmieszczone pod równymi kątami wokół koła) prawdopodobnie wymagałoby dodatkowej uwagi:
Animacje te pokazują również, że (nawet w przypadku nie zdegenerowanym) odpowiednie krawędzie Voronoi i Delaunay niekoniecznie faktycznie przecinają się w ich skończonym zakresie. Może to utrudnić dostrzeżenie, że 2 (lub 3) krawędzie, które triangulują regularny wielokąt na końcu, w rzeczywistości odpowiadają kilku zdegenerowanym krawędziom, które znajdują się na środku. Zauważ też, że w sumie jest 5 różnych triangulacji pięciokąta i 14 triangulacji sześciokąta (chociaż nie wiem, czy wszystkie 14 można uzyskać przez odkształcenie triangulacji nie zdegenerowanej).
Edytuj (wg OP)
Diagramy Voronoi obliczone za pomocą Boost.polygon umożliwiają przejście przez każdy wierzchołek Voronoi i każdą krawędź połączoną z tymi wierzchołkami (zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara). W ten sposób można utworzyć jeden trójkąt dla każdej pary krawędzi (dwie połączone krawędzie połączą się z 3 komórkami).
