Co to są zdegenerowane wielokąty?

9

Co to są zdegenerowane wielokąty? Jak sprawdzić, czy dana para wielokątów jest zdegenerowana, czy nie?

algorithms computational-geometry

— Alice
źródło

2

Kontekst? Nie wierzę, że „zdegenerowany wielokąt” ma standardową definicję.

— Peter Shor,

Jeśli mam dwa wypukłe wielokąty, co by się zdegenerowało? jeśli mają wspólną stronę lub nakładają się? czy żaden? lub obie?

— Alice,

1

Domyślam się, że są to wielokąty, w których dwa sąsiednie wierzchołki są takie same.

— Yuval Filmus

9

Wielokąt jest zdegenerowany, jeśli niektóre z jego wierzchołków leżą na sobie. np. trójkąt (0,0), (0,1), (0,0) jest zdegenerowany. Ma 3 boki i 3 wierzchołki, ale dwa z nich powtarzają się. Możliwe jest wielokrotne powtórzenie wierzchołka (na przykład (0,0), (0,0), (0,0) to kolejny zdegenerowany trójkąt). Z definicji sprawdzenie, czy wielokąt jest zdegenerowany, jest łatwe.

Ale jakie są zastosowania zdegenerowanych wielokątów? Jedna aplikacja z akceleracji graficznej (rysunek 3D) wygląda następująco:

Na rysunku 3D procesory graficzne zwykle używają triangulacji do renderowania obrazów. (Prostym) powodem używania trójkątów jest to, że są to najprostsze możliwe obiekty 2D, więc nie wymagają dużego sprzętu.

Jeśli chcemy narysować złożony obraz 3D, z powodu tego ograniczenia GPU musimy go rozłożyć na wiele trójkątów. Ale jeśli wywołamy GPU, aby renderować każdy trójkąt osobno, byłoby to bardzo wolne (z powodu liczby połączeń). Tak więc pasek trójkąta służy do zmniejszenia liczby połączeń z GPU. Dobre objaśnienie trójkątnych pasków można znaleźć w Dokumentacji Microsoft: Trójkątne paski , a także wiki dla: Trójkątne paski .

Problem pojawia się, gdy chcemy narysować dwa oddzielne obiekty w jednym pasku. W tym przypadku pomagają zdegenerowane trójkąty. GPU może wykryć zdegenerowane trójkąty i pominąć ich rysowanie. Możemy więc połączyć dwa oddzielne paski z jednym zdegenerowanym trójkątem.

Ogólnie rzecz biorąc, jeśli mamy różnych komponentów, tak że mamy już odpowiadające im trójkątne paski, możemy je narysować za pomocą tylko jednego połączenia z GPU. Powoduje to dodatkowe zużycie pamięci, ale jest to kompromis między liczbą wywołań procesora graficznego w celu renderowania a kosztem użycia dodatkowego, zdegenerowanego trójkąta. $n$

— Wędrująca logika
źródło

1

Czy możesz wyjaśnić, czy zdegenerowane oznacza tylko sąsiednie równe wierzchołki, czy też definicja obejmuje niesąsiadujące równe wierzchołki? (Szczere pytanie - nie tylko próba poprawienia odpowiedzi)

— Erik Hermansen

0

Zdegenerowany wielokąt to taki, który ma zerowy obszar.

— Gabriel Rohweder
źródło

Jeśli odpowiedź user742 jest prawidłowa, nie byłoby to prawdą. Weź kwadrat. Jeśli dwa i tylko dwa wierzchołki są takie same, to jest to trójkąt, a zatem obszar wynosi> 0.

— HankCa

i dobrze to wyjaśniłeś. trójkąt nie jest zdegenerowany.

— Gabriel Rohweder

0

Jak zauważyli inni, to zależy. Ogólnie rzecz biorąc, wielokąt nie jest zdegenerowany, jeśli nie ma żadnych anomalnych punktów, ale to tylko odsuwa problem o jeden krok wstecz; czym jest „anomalia”?

Prawdziwa odpowiedź jest taka, że wielokąt ulega degeneracji, jeśli narusza specyfikację. Nieco niegrzeczna odpowiedź jest taka, że wielokąt jest zdegenerowany, jeśli jest to przypadek krawędziowy, którego algorytm nie jest w stanie obsłużyć.

Oto przykład ze świata GIS. Specyfikacja prostych funkcji OGC zawiera bardzo dokładną definicję tego, co sprawia, że wielokąt jest „prawidłowy”. Cytując z sekcji 6.1.11.1:

Asercje dotyczące wielokątów (reguły definiujące prawidłowe wielokąty) są następujące:

a) Wieloboki są topologicznie zamknięte;

b) Granica wielokąta składa się z zestawu liniowych pierścieni, które tworzą jego granice zewnętrzne i wewnętrzne;

c) Żadne dwa pierścienie na krzyżu granicznym i pierścienie na granicy wielokąta nie mogą przecinać się w punkcie, ale tylko jako styczna, np.
$\begin{aligned} \forall P \in Polygon, \forall c_{1}, c_{2} \in P.Boundary, c_{1} \neq c_{2}, \\ \forall p, q \in Point, p, q \in c_{1}, p \neq q, \\ [p \in c_{2}] \Rightarrow [\exists δ > 0 | [| p - q | < δ] \Rightarrow [q \notin c_{2}]] \end{aligned}$ $\begin{align*} & \forall P \in \hbox{Polygon}, \forall c_1, c_2 \in \hbox{P.Boundary}, c_1 \ne c_2,\\ & \forall p, q \in \hbox{Point},\,p,q \in c_1, p \ne q,\\ & \left[ p \in c_2 \right] \Rightarrow \left[ \exists \delta > 0 | \left[\left|p-q\right|<\delta\right]\ \Rightarrow \left[ q \not\in c_2 \right] \right] \end{align*}$ ;

Uwaga: ten ostatni warunek mówi, że w punkcie wspólnym dla dwóch krzywych punkty w pobliżu nie mogą być wspólne. To wymusza, aby każdy wspólny punkt był punktem styczności.

d) Wielokąt nie może mieć linii cięcia, kolców ani przebić, np .: $\forall P \in \hbox{Polygon}, P = \hbox{P.Interior.Closure}$ ;

e) Wnętrze każdego wielokąta jest połączonym zestawem punktów;

f) Zewnętrzna część wielokąta z 1 lub więcej otworami nie jest połączona. Każdy otwór określa połączony element zewnętrzny.

W powyższych stwierdzeniach wnętrze, zamknięcie i strona zewnętrzna mają standardowe definicje topologiczne. Kombinacja (a) i (c) sprawia, że wielokąt jest regularnie zamykanym zestawem punktów.

— Pseudonim
źródło