Algorytm Weilera-Athertona

Algorytm Weilera-Athertona pozwala przycinać wielokąt, nie tylko do prostokąta, ale i do innego wielokąta, przy czym oba wielokąty nie muszą być wypukłe. Poza tym niewielka modyfikacja powoduje że może służyć do znajdowania zamiast części wspólnej, unię wielokątów...

Opis Algorytmu

Dwa wielokąty muszą być tak samo zorientowane, zgodnie lub przeciwnie do ruchu wskazówek zegara. Jeśli któryś z wielokątów jest nieodpowiednio zorientowany, należy odwrócić kolejność punktów wielokąta.

Sposób wyznaczania orientacji wielokąta:

Wielokąt składa się z odcinków zaczynających się w punkcie $P_{i}$ a kończący się w punkcie $P_{i+1}.$ Oznaczmy przez $dx_{i}$ różnicę $P_{i+1}.x-P_{i}.x,$ a przez $dy_{i}$ różnicę $P_{i+1}.y-P_{i}.y.$

Wtedy $\Sigma _{i}{(dx_{i}\cdot dy_{i})}$ ma znak zależny od orientacji.

Jako przykład mamy dwa przecinające się wielokąty, z których pierwszy nie jest wypukły. W przypadku wyznaczania unii wielokątów należy zacząć od punktu mającego ekstremalną pozycję w którymś z czterech kierunków branego z dwóch wielokątów. Takimi punktami są: P0 – najbardziej u góry, Q0, Q1 – po lewej, P2 – u dołu, Q3 – po prawej. P1, P4, P5, Q2 tez byłyby dobre jako startowe, choć nie są ekstremalne.

Natomiast nieodpowiednim puntem byłby P3 ponieważ P3, I5, I3 stanową obrys dziury, a nie obrys zewnętrzny.

Zacznijmy od P0. Idziemy do I1, jest to punkt przecięcia, więc zmieniamy wielokąt na Q; idziemy do Q0, Q1, I0, zmieniamy wielokąt, idziemy P1, P2, I2, zmieniamy wielokąt, I4, zmieniamy wielokąt, P4, P5, I6, zmieniamy wielokąt, Q2, Q3, I7, zmieniamy wielokąt i do P0.

Zastały nieodwiedzone P3, I5, I3 – jest to obrys dziury, który może występować, czasem może być kilka dziur dla danego obrysu zewnętrznego.

Wyznaczenie obszarów przecinających się

Tym razem nie zaczynamy od punktu wielokąta, a od punktów przecinania się. Każdy punkt przecięcia zmienia wielokąt, którym przechodzimy. Za pierwszym razem wybieramy wielokąt przeciwny niż byłby wybrany w tym punkcie przy przechodzeniu całego obrysu – unii wielokątów.