Algorytm Weilera–Athertona jest metodą stosowaną do przycinania wielokątów w grafice komputerowej. Umożliwia on obcinanie wielokąta nie tylko do prostokąta, lecz także do innego wielokąta, przy czym żaden z nich nie musi być wypukły. Niewielka modyfikacja algorytmu pozwala ponadto na wykorzystanie go do wyznaczania sumy wielokątów, a nie jedynie ich części wspólnejhttps://www.pilatinfo.org/tutorial3_eng/intersect.svg.
Wyznaczanie orientacji wielokąta Wielokąt składa się z kolejnych odcinków rozpoczynających się w punktach i kończących w punktach . Różnice współrzędnych oznaczmy jako: oraz
Suma przyjmuje znak zależny od orientacji wielokąta – pozwala to określić, czy jego wierzchołki są ułożone zgodnie, czy przeciwnie do ruchu wskazówek zegara.
Przykład działania Rozważmy dwa przecinające się wielokąty, z których pierwszy nie jest wypukły. W przypadku wyznaczania unii wielokątów proces rozpoczyna się od punktu o ekstremalnym położeniu w jednym z czterech kierunków, wybranym spośród punktów obu wielokątów. Przykładowe punkty ekstremalne to: P0 – najwyższy, Q0 i Q1 – najbardziej po lewej, P2 – najniższy, oraz Q3 – najbardziej po prawej stronie. Punkty P1, P4, P5 i Q2 również mogą stanowić punkty początkowe, choć nie są ekstremalne.
Punkt P3 nie jest odpowiedni, ponieważ wraz z punktami I5 i I3 tworzy obrys otworu (dziury), a nie zewnętrzny obrys wielokąta.
mały|Przykład punktów przecięcia dwóch wielokątów
Algorytm rozpoczyna działanie w punkcie P0. Następnie: przechodzi do punktu przecięcia I1, po czym zmienia aktywny wielokąt na Q; kontynuuje do punktów Q0, Q1, I0 i ponownie zmienia wielokąt; dalej przechodzi przez P1, P2, I2, po czym następuje kolejna zmiana wielokąta; następnie I4 → P4 → P5 → I6, zmieniając wielokąt po każdym punkcie przecięcia; w dalszej kolejności punkty Q2, Q3, I7, aż do ponownego powrotu do P0.
Pozostają punkty P3, I5 oraz I3, które wyznaczają obrys otworu. W przypadku bardziej złożonych wielokątów może występować kilka takich wewnętrznych obszarów (dziur) przypisanych do jednego obrysu zewnętrznego.
Wyznaczanie obszarów przecinających się W przypadku wyznaczania obszarów wspólnych dwóch wielokątów algorytm nie rozpoczyna działania od punktu wierzchołkowego, lecz od punktów ich przecięcia. Każdy punkt przecięcia stanowi miejsce, w którym zmieniany jest aktywny wielokąt, po którego obrysie aktualnie przebiega obliczenie.
Podczas pierwszego przejścia wybierany jest wielokąt przeciwny względem tego, który zostałby wybrany w analogicznym punkcie przy wyznaczaniu unii wielokątów. Pozwala to na prawidłowe określenie granic części wspólnej obu figur i rozróżnienie jej od obszarów zewnętrznych.
Przypisy
Kategoria:Algorytmy graficzne