Poczwórna struktura danych (Delaunay / Voronoi)

18

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!

Bigmonachus
źródło
3
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
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

Odpowiedzi:

32

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:fafamimivv

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 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ąmiogon(mi)głowa(mi)lewo(mi)dobrze(mi)ogon(mi)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.)lewo(mi)

Dla dowolnej strzałki Guibas i Stolfi kojarzą trzy powiązane strzałki:mi

  1. : Strzałka opuszczająca ogon ( e ) następnie w kolejności przeciwnej do ruchu wskazówek zegara poe .tailNext(mi)ogon(mi)mi
  2. : „ta sama” strzałka coe , ale z lewą ( e ) i prawą ( e ) zamienioną.trzepnięcie(mi)milewo(mi)dobrze(mi)
  3. : Podwójna strzałka uzyskana przezobróceniee ćwierć obrotu przeciwnie do ruchu wskazówek zegara wokół jej punktu środkowego.obracać się(mi)mi

tailNext, rotate and flip

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

  • right(tailNext(e))=left(e)
  • right(flip(e))=left(e)
  • right(rotate(e))=head(e)
  • flip(flip(e))=e
  • rotate(rotate(rotate(rotate(e))))=e
  • tailNext(rotate(tailNext(rotate(e))))=e

mi faljape.Flip

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

  • rewers(mi)=obracać się(trzepnięcie(obracać się(mi)))
  • leftNext(mi)=obracać się(tailNext(obracać się(obracać się(obracać się(mi)))))milewo(mi)

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ε