Algorytm Sutherlanda-Hodgmana

Algorytm Sutherlanda-Hodgmana – analityczny algorytm obcinania, który znajduje część wspólną dwóch wielokątów, przy czym wielokąt obcinający musi być wypukły (wielokąt obcinany może być wypukły lub niewypukły); wielokąty są dane jako ciągi wierzchołków.

Chociaż algorytm najczęściej znajduje zastosowanie właśnie dla przypadków dwuwymiarowych, to łatwo uogólnić go na większą liczbę wymiarów i np. w przestrzeni trójwymiarowej można znaleźć część wspólną dowolnego obiektu z wielościanem. Tutaj zostanie opisany algorytm dla dwóch wymiarów.

Opis metody

Algorytm jest iteracyjny i wykorzystuje strategię dziel i zwyciężaj, tzn. dzieli problem na wiele elementarnych, łatwych do rozwiązania podproblemów. Wykorzystuje fakt, iż wielokąt wypukły można przedstawić jako część wspólną półpłaszczyzn wyznaczanych przez boki tego wielokąta. Znalezienie części wspólnej wielokąta i półpłaszczyzny jest bardzo proste.

W jednym kroku algorytmu znajdowana jest część wspólna wielokąta oraz półpłaszczyzny, a otrzymany w ten sposób wielokąt jest przetwarzany w kroku kolejnym:

$W$ = obcinany wielokąt
$W_{o}$ = wypukły wielokąt obcinający
dla wszystkich krawędzi $W_{o}$ wykonuj:
- $L{:}$ = wyznacz prostą, na której leży krawędź
- $W{:}$ = wyznacz część wspólną wielokąta $W$ i półpłaszczyzny zdefiniowanej przez prostą $L$

Przykład obcinania litery W (W jak Wikipedia) przez pięciokąt

Po przejrzeniu wszystkich wierzchołków otrzymuje się ciąg wierzchołków wielokąta będącego częścią wspólną $W$ i półpłaszczyzny. Niestety może zdarzyć się tak, że wielokąt zostanie rozdzielony na dwa lub więcej wielokątów i wówczas pojawiają się dodatkowe krawędzie leżące na prostej $L.$ Można je jednak wyeliminować po zakończeniu całego algorytmu.

Pewnym problemem jest określenie po której stronie prostej $L$ znajduje się wnętrze wielokąta obcinającego $W_{o}.$ Rozwiązanie jest następujące: należy przeglądać wierzchołki $W_{o}$ kolejno, tzn. $(v_{0},v_{1}),(v_{1},v_{2}),\dots ,(v_{i},v_{j}),\dots ,(v_{n},v_{0})$ i na ich postawie wyznaczać równanie prostej, np. w postaci parametrycznej: $v_{i}+t\cdot (v_{j}-v_{i}).$ Wówczas jeśli wierzchołki są podawane w kierunku przeciwnym do ruchu wskazówek zegara, to wektory normalne wszystkich prostych wskazują wnętrze wielokąta.

Część wspólna wielokąta i półpłaszczyzny

Najważniejszym elementem algorytmu jest wyznaczanie części wspólnej wielokąta $W$ i półpłaszczyzny. Polega on na przeglądaniu kolejnych wierzchołków $(v_{0},v_{1}),(v_{1},v_{2}),\dots ,(v_{i},v_{j}),\dots (v_{n},v_{0}),$ lecz w jednej iteracji analizowana jest tylko jedna krawędź. Jeśli pierwszy wierzchołek $v_{i}$ zostanie oznaczony przez $S,$ a drugi $v_{j}$ przez $N,$ to:

Jeśli obydwa wierzchołki leżą wewnątrz $W_{o},$ wówczas zapamiętywany jest tylko wierzchołek $N.$
Jeśli obydwa wierzchołki leżą na zewnątrz, wówczas żaden wierzchołek nie jest zapamiętywany.
W przeciwnym razie krawędź $W$ przecina prostą $L$ i należy obliczyć punkt przecięcia (ozn. $P$ ) odcinka $S{N}$ 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 jest odwrotnie ( $N$ leży wewnątrz, a $S$ na zewnątrz), to zapamiętywane są dwa punkty: $P$ i $N$ (w tej kolejności).

Zobacz też

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.