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!

reference-request cg.comp-geom algebra

— Bigmonachus
źródło

Wystarczy wypełnić luki: algebra abstrakcyjna to badanie zbiorów elementów, które szanują określone reguły. Jak można się domyślać, reguły, które spełniają te zbiory, są właściwościami takimi jak zamknięcie, elementy tożsamości, istnienie unikatowych inwersji, a wraz z postępem przemienność, asocjatywność itp. Jest to badanie algebry na zestawach, które niekoniecznie zachowują się jak liczby rzeczywiste (dobrym przykładem są permutacje).

— Ross Snider

en.wikipedia.org/wiki/Abstract_algebra

— Kaveh

Wydaje mi się, że moje drugie pytanie było trochę spóźnione. Znam trochę teorii grup. Wiem, co to jest pierścień i pole. To dlatego, że w artykule określają takie algebra: "An Algebra krawędzią jest algebra (E, E * Onext Rot Flip) właściwości spełniające E1-E5 oraz F1-F5"

— bigmonachus

[...] i nie mam pojęcia, co to znaczy. To nie jest algebra nad polem, prawda?

— bigmonachus

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 ; każda krawędź pierwotnego wykresu ma odpowiadającą podwójną krawędź ; a każdy wierzchołek pierwotnego wykresu ma odpowiadającą podwójną ścianę . 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^*$

Pierwotne i podwójne wykresy

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 do innego punktu końcowego , a lokalnie oddziela dwie twarze i . Wybór punktu końcowego, który ma być nazywany 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}$

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

tailNext, rotate and flip

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!

— Jeffε
źródło

Użyłem OmniGraffle.

— Jeffε