Algorytm Sutherlanda-Hodgmana

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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[edytuj | edytuj kod]

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:

  1. = obcinany wielokąt
  2. = wypukły wielokąt obcinający
  3. dla wszystkich krawędzi wykonuj:
    •  := wyznacz prostą, na której leży krawędź
    •  := wyznacz część wspólną wielokąta i półpłaszczyzny zdefiniowanej przez prostą
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ą 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 . Można je jednak wyeliminować po zakończeniu całego algorytmu.

Pewnym problemem jest określenie po której stronie prostej znajduje się wnętrze wielokąta obcinającego . Rozwiązanie jest następujące: należy przeglądać wierzchołki kolejno, tzn. i na ich postawie wyznaczać równanie prostej, np. w postaci parametrycznej: . 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[edytuj | edytuj kod]

Najważniejszym elementem algorytmu jest wyznaczanie części wspólnej wielokąta i półpłaszczyzny. Polega on na przeglądaniu kolejnych wierzchołków , lecz w jednej iteracji analizowana jest tylko jedna krawędź. Jeśli pierwszy wierzchołek zostanie oznaczony przez , a drugi przez , to:

  1. Jeśli obydwa wierzchołki leżą wewnątrz , wówczas zapamiętywany jest tylko wierzchołek .
    Sutherland-Hodgman caseA.svg
  2. Jeśli obydwa wierzchołki leżą na zewnątrz, wówczas żaden wierzchołek nie jest zapamiętywany.
    Sutherland-Hodgman caseC.svg
  3. W przeciwnym razie krawędź przecina prostą i należy obliczyć punkt przecięcia (ozn. ) odcinka z prostą:
    • jeśli leży wewnątrz, a na zewnątrz, to zapamiętywany jest tylko punkt przecięcia ;
      Sutherland-Hodgman caseB.svg
    • Jeśli jest odwrotnie ( leży wewnątrz, a na zewnątrz), to zapamiętywane są dwa punkty: i (w tej kolejności).
      Sutherland-Hodgman caseD.svg

Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  • 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.