Algorytm Sutherlanda-Hodgmana
Algorytm Sutherlanda-Hodgmana to analityczny algorytm obcinania, który pozwala na znalezienie części wspólnej dwóch wielokątów. Warto zaznaczyć, że wielokąt obcinający musi być wypukły, podczas gdy wielokąt, który jest obcinany, może być zarówno wypukły, jak i niewypukły. Oba wielokąty są reprezentowane jako ciągi ich wierzchołków.
Choć algorytm ten najczęściej jest używany w kontekście przypadków dwuwymiarowych, można go łatwo rozszerzyć na wyższe wymiary. Na przykład w przestrzeni trójwymiarowej możliwe jest odnalezienie części wspólnej dowolnego obiektu z wielościanem. W dalszej części zostanie omówiony algorytm w kontekście dwóch wymiarów.
Opis metody
Algorytm działa w sposób iteracyjny i wykorzystuje strategię dziel i zwyciężaj, co oznacza, że dzieli problem na wiele mniejszych, łatwiejszych do rozwiązania podproblemów. Kluczowym założeniem jest to, że wielokąt wypukły można przedstawić jako część wspólną półpłaszczyzn, które są określane przez boki tego wielokąta. Odkrycie części wspólnej pomiędzy wielokątem a półpłaszczyzną jest stosunkowo proste.
W każdym kroku algorytmu znajduje się część wspólna wielokąta oraz półpłaszczyzny, a wynikowy wielokąt jest przekazywany do kolejnego kroku:
- W = obcinany wielokąt
- Wo = wypukły wielokąt obcinający
Dla wszystkich krawędzi Wo wykonujemy:
- L = wyznacz prostą, na której leży krawędź W
- W = wyznacz część wspólną wielokąta W i półpłaszczyzny zdefiniowanej przez prostą L
Po przeanalizowaniu wszystkich wierzchołków otrzymujemy ciąg wierzchołków wielokąta będącego częścią wspólną W i półpłaszczyzny. Czasami może się zdarzyć, że wielokąt zostanie podzielony na dwa lub więcej wielokątów, co powoduje pojawienie się dodatkowych krawędzi leżących na prostej L. Można je jednak usunąć po zakończeniu całego algorytmu.
Jednym z problemów jest ustalenie, po której stronie prostej L znajduje się wnętrze wielokąta obcinającego Wo. Rozwiązanie tego problemu polega na przeglądaniu wierzchołków Wo w kolejności:
- (v0, v1), (v1, v2), …, (vi, vj), …, (vn, v0)
Na ich podstawie możemy wyznaczyć równanie prostej, na przykład w postaci parametrycznej:
vi + t ⋅ (vj − vi)
Jeśli wierzchołki są podawane w kierunku przeciwnym do ruchu wskazówek zegara, wtedy wektory normalne wszystkich prostych wskazują wnętrze wielokąta.
Część wspólna wielokąta i półpłaszczyzny
Najważniejszym aspektem algorytmu jest wyznaczanie części wspólnej wielokąta W i półpłaszczyzny. Proces ten polega na przeglądaniu kolejnych wierzchołków, ale w jednej iteracji analizowana jest tylko jedna krawędź. Jeśli pierwszy wierzchołek vi zostanie oznaczony jako S, a drugi jako N, to:
- Jeśli oba wierzchołki leżą wewnątrz Wo, zapamiętujemy tylko wierzchołek N.
- Jeśli oba wierzchołki są na zewnątrz, żaden wierzchołek nie jest zapamiętywany.
- W przeciwnym razie krawędź W przecina prostą L, co wymaga obliczenia punktu przecięcia (oznaczonego jako P) odcinka SN z prostą:
Jeśli S leży wewnątrz, a N na zewnątrz, to zapamiętywany jest tylko punkt przecięcia P. Jeśli sytuacja jest odwrotna (N leży wewnątrz, a S na zewnątrz), zapamiętywane są dwa punkty: P i N (w tej kolejności).
Zobacz też
- obcinanie
- okienkowanie
- rasteryzacja
- usuwanie niewidocznych powierzchni
Bibliografia
James D Foley, Andries van Dam, Steven K Freiner, John F Hughes, Richard L Phillips: Wprowadzenie do grafiki komputerowej. Jan Zabrodzki (tłumaczenie). Warszawa: Wydawnictwa Naukowo-Techniczne, 1995. ISBN 83-204-1840-2. Brak numerów stron w książce.
