Podział wielokątów na trójkąty

Kolega rr- rzucił dzisiaj na kanale #warsztat ciekawy problem rysowania dowolnych wielokątów za pomocą samych trójkątów. Jak wiadomo, karty graficzne posługują się właśnie trójkątami, zatem w celu wyświetlenia wielokąta należy go odpowiednio podzielić. Matematycy dowodzą, że jest to zawsze możliwe, i podają prosty sposób dla wielokątów wypukłych: należy po prostu narysować wszystkie przekątne wychodzące z jednego wierzchołka. Nie jest trudno przełożyć ten przepis na kod.

Co jednak z dowolnymi wielokątami? Tu sprawa wydaje się bardziej skomplikowana, chociaż – jak się ukazuje – rysowanie przekątnych można na ten przypadek uogólnić. Wpadłem jednak na inny pomysł, polegający na odpowiednim “chodzeniu” po wierzchołkach naszego wielokąta i “odcinaniu” od niego kolejnych trójkątów brzegowych. Wygląda to mniej więcej tak:

1. Startujemy od dowolnego wierzchołka wielokąta.
2. Mając i-ty wierzchołek sprawdzamy, czy da się go połączyć z (i+2)-im (modulo liczba wierzchołków) tak, aby powstały przy tym odcinek mieścił się w wielokącie:
   • jeśli tak, to z wierzchołków: i-tego, (i+1)-ego i (i+2)-ego tworzymy nowy trójkąt, wierzchołek (i+1)-szy usuwamy z wielokąta i przechodzimy do (i+2)-ego
   • jeśli nie da się tak połączyć wierzchołków, przechodzimy do wierzchołka (i+1)-ego i próbujemy dalej
3. Po wykonaniu pełnego cyklu kontynuujemy przechodzenie po wielokącie, usuwanie wierzchołków i tworzenie trójkątów – aż do momentu, gdy sam nasz wielokąt stanie się trójkątem. Będzie to oczywiście ostatni składający się na niego trójkąt.

Na tym rysunku można prześledzić, jak wyglądają kolejne cykle spaceru po krawędziach wielokąta – oznaczyłem je różnymi kolorami:

Z tym sposobem wiąże się oczywiście problem stwierdzenia, czy dany odcinek należy do wielokąta – co w ogólności nie musi być takie proste ani efektywne (może mieć złożoność liniową). Dodatkowo wielokąt może być “wredny” i niezbyt dobrze poddawać się operacji obcinania trójkątów. Na szczęście można udowodnić, że w każdym cyklu da się przynajmniej jeden taki trójkąt wyodrębnić. Te dwa fakty powodują, że cała operacja może mieć złożoność sięgającą nawet O(n³), chociaż pewnie da się ją zaimplementować lepiej.
Jest naturalnie bardzo możliwe, że algorytm ten jest znany od dawna, a ja po prostu nie przeczesałem Internetu dość dokładnie w poszukiwaniu już istniejącego opisu. Jednak biorąc pod uwagę to, co przed chwilą powiedziałem o jego możliwej “efektywności”, nie jest to znów takie pewne ;-) Istnieje aczkolwiek szansa, że może się on przydać komuś, kto implementuje bibliotekę graficzną 2D w oparciu o API w rodzaju DirectX czy OpenGL.

Wielokąty radarowe

Dane liczbowe przedstawiać można na wiele sposobów. Najbardziej kompletnym jest zwykle tabelka, ale o wiele ładniejszą jest odpowiedni wykres. Czasem sztuką jest dobrać jego odpowiedni typ, gdyż rodzajów wykresów jest wbrew pozorom bardzo dużo. Jeżeli ktoś nie wierzy, niech sprawdzi w dowolnym arkuszu kalkulacyjnym :)

Jednym z ciekawszych jest wykres radarowy. W nim ze środka wykresu na zewnątrz wypuszczone są osie (różna może być ich liczba), na których z kolei zaznaczone są wartości. W najprostszej wersji wygląda to jak pajęczyna z napaćkanymi punktami i w sumie nie jest specjalnie sugestywne.
Ciekawiej zaczyna się robić, jeżeli punkty na poszczególnych osiach połączymy ze sobą i zamalujemy wnętrze tak powstałego wielokąta. Jeżeli bowiem wartości na osiach przedstawiają pewne właściwości jednego obiektu lub zjawiska, to powstała figura niejako opisuje go w sposób całościowy. Weźmy na przykład taki wykres, w którym w subiektywny sposób ocenimy sobie różne charakterystyki jakiegoś hipotetycznego kawałka kodu źródłowego:

Figura taka ma jeszcze jedną istotną cechę: powierzchnię. Na pierwszy rzut oka dość ciężko określić, w jaki sposób zależy od wartości na poszczególnych osiach. Czy na przykład gwałtowny wzrost jednej zmiennej przy identycznych wartościach pozostałych da ostatecznie większe pole wielokąta niż równomierny przyrost na wszystkich osiach?
Nie jest to oczywiste i dlatego wydaje się całkiem interesujące :) Naturalnie znając wszystkie wartości, rzeczone pole policzyć jest bardzo łatwo.

Dlaczego jednak wspominam o tym wszystkim? Otóż uważam, że gry w których przedstawia się graczowi bardzo dużo danych – a więc na przykład ekonomiczne, strategiczne czy RPG – są zwykle dość ubogie pod względem sposobów prezentacji tych danych. Prawie zawsze królują w nich nieśmiertelne tabelki i czasami tylko jakieś wykresy liniowe czy słupkowe.
A przecież można by nieco się wysilić i zafundować graczowi jakąś bardziej atrakcyjną formę. W końcu jeśli ktoś nie lubi odmóżdżających strzelanek to jeszcze nie znaczy, że uśmiecha mu się wpatrywanie się w rzędy numerków ;P