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.