Algorytm Weilera-Athertona
|
Ten artykuł należy dopracować |
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...[1][2]
Opis Algorytmu edytuj
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 a kończący się w punkcie Oznaczmy przez różnicę a przez różnicę
Wtedy 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ę edytuj
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 edytuj
- ↑ Grafika komputerowa I – 3. Obcinanie linii i wielokątów – MIM UW [online], mimuw.edu.pl [dostęp 2024-04-22] (pol.).
- ↑ http://www.pilatinfo.org/tutorial3_eng/intersect.svg