Tekst źródłowy strony Algorytm Weilera-Athertona

{{dopracować|przypisy=2022-10|definicja|styl}}
'''Algorytm Weilera-Athertona''' pozwala przycinać [[wielokąt]], nie tylko do [[prostokąt]]a, ale i do innego wielokąta, przy czym oba wielokąty nie muszą być [[Zbiór wypukły|wypukłe]]. Poza tym niewielka modyfikacja powoduje że może służyć do znajdowania zamiast części wspólnej, [[Suma zbiorów|unię wielokątów]]...<ref>{{Cytuj | url=https://mst.mimuw.edu.pl/lecture.php?lecture=gk1&part=Ch3 | tytuł=Grafika komputerowa I – 3. Obcinanie linii i wielokątów – MIM UW<!-- Tytuł wygenerowany przez bota --> | opublikowany=mimuw.edu.pl | język=pl | data dostępu=2024-04-22}}</ref><ref>http://www.pilatinfo.org/tutorial3_eng/intersect.svg</ref>

== Opis Algorytmu ==
Dwa wielokąty muszą być tak samo [[orientacja (matematyka)|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 [[odcinek|odcinków]] zaczynających się w punkcie <math>P_i</math> a kończący się w punkcie <math>P_{i+1}.</math> Oznaczmy przez <math>dx_i</math> różnicę <math>P_{i+1}.x-P_i.x,</math> a przez <math>dy_i</math> różnicę <math>P_{i+1}.y-P_i.y.</math>

Wtedy <math>\Sigma_i{(dx_i \cdot dy_i)}</math> 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.

[[Plik:Weiler-Atherton.svg|Punkty przecinania się dwóch wielokątów]]

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.

== Przypisy ==
{{Przypisy}}

[[Kategoria:Algorytmy graficzne]]