Algorytm Weilera-Athertona
Algorytm Weilera-Athertona umożliwia przycinanie wielokątów, nie tylko do prostokątów, ale także do innych kształtów wielokątnych, a oba wielokąty nie muszą być wypukłe. Dodatkowo, niewielka modyfikacja umożliwia wykorzystanie go do znajdowania uni wielokątów, zamiast tylko ich części wspólnej.
Opis Algorytmu
Aby algorytm działał poprawnie, oba wielokąty muszą być zorientowane w ten sam sposób, czy to zgodnie, czy przeciwnie do ruchu wskazówek zegara. W przypadku, gdy którykolwiek z wielokątów jest źle zorientowany, należy odwrócić kolejność jego punktów.
Sposób ustalania orientacji wielokąta:
Wielokąt składa się z segmentów, które zaczynają się w punkcie
Pi
a kończą w punkcie
Pi+1.
Oznaczmy przez
dxi
różnicę
Pi+1.x – Pi.x,
a przez
dyi
różnicę
Pi+1.y – Pi.y.
Wtedy
Σi(dxi ⋅ dyi)
ma znak zależny od orientacji.
Na przykład, jeżeli mamy dwa przecinające się wielokąty, z których pierwszy nie jest wypukły, w przypadku ustalania unii wielokątów, należy zacząć od punktu, który ma najbardziej ekstremalną pozycję w jednym z czterech kierunków, biorąc pod uwagę oba wielokąty. Takimi punktami są: P0 – najwyżej położony, Q0, Q1 – po lewej, P2 – na dole, Q3 – po prawej. Punkty P1, P4, P5, Q2 również mogą być dobrymi punktami startowymi, choć nie są ekstremalne.
Natomiast punktem nieodpowiednim byłby P3, ponieważ P3, I5, I3 stanowią obrys dziury, a nie obrys zewnętrzny.
Zaczynamy od P0. Przechodzimy do I1, jest to punkt przecięcia, więc zmieniamy wielokąt na Q; idziemy do Q0, Q1, I0, zmieniamy wielokąt, idziemy do P1, P2, I2, zmieniamy wielokąt, I4, zmieniamy wielokąt, P4, P5, I6, zmieniamy wielokąt, Q2, Q3, I7, zmieniamy wielokąt i wracamy do P0.
Nieodwiedzone pozostały punkty P3, I5, I3 – stanowią one obrys dziury, która może występować, a czasami dla jednego obrysu zewnętrznego może być nawet kilka dziur.
Wyznaczenie obszarów przecinających się
Tym razem nie zaczynamy od punktu wielokąta, lecz od punktów przecięcia. Każdy punkt przecięcia zmienia wielokąt, przez który przechodzimy. Za pierwszym razem wybieramy wielokąt przeciwny do tego, który zostałby wybrany w tym punkcie przy przechodzeniu całego obrysu – unii wielokątów.
