Poczwórna struktura danych (Delaunay / Voronoi)

2 pytania do geometrii obliczeniowej lub algebraistów:

Właśnie zaczynam nurkować w geometrii obliczeniowej i uwielbiam ją =)

Próbuję przeczytać słynny artykuł Guibasa i Stolfiego zatytułowany „Prymitywy do manipulowania ogólnymi poddziałami i obliczaniem diagramów Voronoi” w celu zaimplementowania algorytmu triangulacji Delaunaya. Kusi mnie, aby pominąć wszystkie teoretyczne rzeczy i po prostu przeczytać opis ich czterokładowej struktury danych, aby zaoszczędzić czas. Myślę jednak, że warto zrozumieć całą matematykę zawartą w artykule, jeśli struktura jest szeroko stosowana lub tylko dlatego, że może być piękna.

Matematyka jest dla mnie trochę zagęszczona. Nie jestem całkowicie nieświadomy topologii, ale opis ich algebry krawędzi wymaga znajomości algebry abstrakcyjnej, której nie mam.

Moje dwa pytania brzmią: jakie są inne zastosowania struktury quad-edge oprócz obliczeń Delaunay / Voronoi? Wygląda na niezwykle potężne narzędzie.

Drugie pytanie; Co to jest algebra abstrakcyjna? Byłoby wspaniale, gdybyś mógł podać mi odniesienie do wstępu do algebry abstrakcyjnej, na tyle, żebym mógł zrozumieć część na temat algebry krawędzi.

Dziękuję Ci!

Myślę, że formalizm „algebry krawędzi” Guibasa i Stolfiego jest nieco niepotrzebny.

Wszystko, co jest naprawdę konieczne, to pamiętać o rozróżnieniu między pierwotnymi i podwójnymi wykresami. Każda powierzchnia pierwotnego wykresu ma odpowiadający podwójny wierzchołek f ∗ ; każda krawędź e pierwotnego wykresu ma odpowiadającą podwójną krawędź e ∗ ; a każdy wierzchołek v pierwotnego wykresu ma odpowiadającą podwójną ścianę v ∗ . Pierwotne krawędzie łączą pierwotne wierzchołki i oddzielne pierwotne ściany; podwójne krawędzie łączą podwójne wierzchołki i oddzielne podwójne ściany. Podwójność wszystkiego jest oryginalną rzeczą. Zobacz rysunek 4 w pracy Guibasa i Stolfiego:$f$$f^*$$e$$e^*$$v$$v^*$

Guibas i Stolfi proponują myślenie o każdej krawędzi (pierwotnej lub podwójnej) jako zbiór czterech ukierunkowanych, zorientowanych krawędzi; dla uproszczenia nazywam te strzałki . Każda lotka punktów z jednego punktu końcowego ogona ( → e ) do innego punktu końcowego głowicy ( → E ) , a lokalnie oddziela dwie twarze w lewo ( → e ) i prawo ( → E ) . Wybór punktu końcowego, który ma być nazywany ogonem ( → e ), jest strzałką$\vec{e}$$\text{tail}(\vec{e})$$\text{head}(\vec{e})$$\text{left}(\vec{e})$$\text{right}(\vec{e})$$\text{tail}(\vec{e})$kierunek , a wybór, którą twarz wywołać w jest jego orientacją . (Guibas i Stolfi używają „Org” i „Dest” zamiast „tail” i „head”, ale wolę krótsze etykiety, ponieważ niepotrzebne skróty są złe.)$\text{left}(\vec{e})$

Dla dowolnej strzałki Guibas i Stolfi kojarzą trzy powiązane strzałki:$\vec{e}$

1. : Strzałka opuszczająca ogon ( → e ) następnie w kolejności przeciwnej do ruchu wskazówek zegara po → e .$\text{tailNext}(\vec{e})$$\text{tail}(\vec{e})$$\vec{e}$
2. : „ta sama” strzałka co → e , ale z lewą ( → e ) i prawą ( → e ) zamienioną.$\text{flip}(\vec{e})$$\vec{e}$$\text{left}(\vec{e})$$\text{right}(\vec{e})$
3. : Podwójna strzałka uzyskana przezobrócenie → e ćwierć obrotu przeciwnie do ruchu wskazówek zegara wokół jej punktu środkowego.$\text{rotate}(\vec{e})$$\vec{e}$

Te trzy funkcje spełniają wszelkiego rodzaju wspaniałe tożsamości, takie jak:

• $\text{right}(\text{tailNext}(\vec{e})) = \text{left}(\vec{e})$
• $\text{right}(\text{flip}(\vec{e})) = \text{left}(\vec{e})$
• $\text{right}(\text{rotate}(\vec{e})) = \text{head}(\vec{e})^*$
• $\text{flip}(\text{flip}(\vec{e})) = \vec{e}$
• $\text{rotate}(\text{rotate}(\text{rotate}(\text{rotate}(\vec{e})))) = \vec{e}$
• $\text{tailNext}(\text{rotate}(\text{tailNext}(\text{rotate}(\vec{e})))) = \vec{e}$

$e~Flip$e.Flip

Ponadto, biorąc pod uwagę te trzy funkcje, można zdefiniować kilka innych przydatnych funkcji, takich jak

• $\text{reverse}(\vec{e}) = \text{rotate}(\text{flip}(\text{rotate}(\vec{e})))$
• $\text{leftNext}(\vec{e}) = \text{rotate}(\text{tailNext}(\text{rotate}(\text{rotate}(\text{rotate}(\vec{e})))))$$\vec{e}$$\text{left}(\vec{e})$

Wreszcie, znajomość tych funkcji mówi absolutnie wszystko o topologii podziału, a każdy wieloboczny podział dowolnej powierzchni (orientowalnej lub nie) można zakodować za pomocą tych trzech funkcji.

Poczwórna struktura danych jest szczególnie wygodną reprezentacją wykresu powierzchniowego, który zapewnia dostęp do wszystkich tych funkcji, wraz z kilkoma innymi operacjami w czasie stałym, takimi jak wstawianie, usuwanie, kurczenie, rozszerzanie i przerzucanie krawędzi; dzielenie lub łączenie wierzchołków lub ścian; oraz dodawanie lub usuwanie uchwytów lub zaślepek.

Baw się dobrze!