Algorytm Sutherlanda-Hodgmana
Z Wikipedii
Algorytm Sutherlanda-Hodgmana jest analitycznym algorytmem 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.
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 znajdywana 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
- Wo = wypukły wielokąt obcinający
- dla wszystkich krawędzi Wo 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
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 Wo. Rozwiązanie jest następujące: należy przeglądać wierzchołki Wo 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.
[edytuj] 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. Przeglądane są kolejne wierzchołki w sposób , w jednej iteracji analizowana jest tylko jedna krawędź; oznaczmy pierwszy wierzchołek vi przez S, drugi vj przez N: