Zagadnienia

3. Obcinanie linii i wielokątów

3.1. Obcinanie odcinków i prostych

Zadanie obcinania polega na

  • wyznaczeniu fragmentu odcinka lub prostej, który leży wewnątrz okna na ekranie (ogólniej: dowolnego wielokąta), lub

  • wyznaczeniu fragmentu odcinka lub prostej, który leży wewnątrz ustalonej bryły wielościennej.

Rozwiązanie jednego z tych zadań może być potrzebne w celu narysowania pewnej części odcinka, a także w konstrukcyjnej geometrii brył, w algorytmach widoczności i w śledzeniu promieni, o czym będzie mowa dalej.

Jeśli problem do rozwiązania polega na wyznaczeniu części wspólnej odcinka (lub prostej) i wielokąta (lub wielościanu) wypukłego, to możemy ten wielokąt (wielościan) przedstawić jako przecięcie pewnej liczby półpłaszczyzn (półprzestrzeni) i sprowadzić zadanie do obcinania półpłaszczyznami (półprzestrzeniami).

3.1.1. Wyznaczanie punktu przecięcia odcinka i prostej

Dane są punkty końcowe odcinka, \bm{p}_{1}=(x_{1},y_{1}) i \bm{p}_{2}=(x_{2},y_{2}), oraz współczynniki a, b, c równania prostej ax+by=c. Mamy znaleźć (jeśli istnieje) punkt wspólny tego odcinka i prostej.

Przedstawienie parametryczne odcinka, \bm{p}=\bm{p}_{1}+t(\bm{p}_{2}-\bm{p}_{1}), czyli

\displaystyle\left[\begin{array}[]{c}x\\
y\end{array}\right]\:=\:\left[\begin{array}[]{c}x_{1}\\
y_{1}\end{array}\right]+t\left[\begin{array}[]{c}x_{2}-x_{1}\\
y_{2}-y_{1}\end{array}\right]\quad\mbox{dla $t\in[0,1]$,} (3.1)

wstawiamy do równania prostej, otrzymując równanie

\displaystyle a(x_{1}+t(x_{2}-x_{1}))+b(y_{1}+t(y_{2}-y_{1}))=c,

którego rozwiązaniem jest

\displaystyle t\:=\:\frac{c-ax_{1}-by_{1}}{a(x_{2}-x_{1})+b(y_{2}-y_{1})}.

Jeśli t\notin[0,1], to prosta i odcinek są rozłączne. W przeciwnym razie możemy obliczyć współrzędne x, y punktu wspólnego. Wzór jest szczególnie prosty w przypadku, gdy równanie prostej obcinającej ma postać x=c (prosta jest wtedy pionowa), lub y=c (prosta jest pozioma).

Prawie identyczne jest wyprowadzenie odpowiednich wzorów w przestrzeni trójwymiarowej, dla danych punktów końcowych (x_{1},y_{1},z_{1}), (x_{2},y_{2},z_{2}) i równania płaszczyzny obcinającej ax+by+cz=d.

3.1.2. Algorytm Sutherlanda-Cohena

Omówimy najbardziej popularną wersję obcinania do okna prostokątnego. Dla dowolnego wielokąta/wielościanu wypukłego zasada działania algorytmu jest identyczna.

Dane są punkty końcowe odcinka i prostokątne okno. Proste, na których leżą krawędzie okna, dzielą płaszczyznę na 9 obszarów. Przyporządkujemy im czterobitowe kody przedstawione na rysunku 3.1a.

Rys. 3.1. Algorytm Sutherlanda-Cohena: podział płaszczyzny na obszary a) podział płaszczyzny na obszary, b) odrzucanie odcinka.

Kody obszarów, do których należą końce odcinka, możemy wyznaczyć na podstawie ich współrzędnych. Zauważmy, że jeśli oba kody na dowolnej pozycji mają jedynkę, to cały odcinek leży poza oknem (rys. 3.1b). Jeśli oba punkty końcowe mają kod 0, to cały odcinek leży wewnątrz okna. Jeśli kody są różne od 0, ale nie mają jedynki jednocześnie na żadnej pozycji, to odcinek może, ale nie musi mieć części wewnątrz okna.

Dla dowolnego wielokąta lub wielościanu określa się kody o liczbie bitów równej liczbie krawędzi albo ścian. Algorytm wyznacza punkt przecięcia odcinka z krawędzią, której odpowiada 1 w którymś kodzie, a następnie zastępuje jeden z punktów (ten, w którego kodzie występuje ta jedynka) przez punkt przecięcia. Nie grozi przy tym dzielenie przez 0 (dlaczego?).

#define NIC   0
#define CAŁY  1
#define CZĘŚĆ 2

char SC_clip ( punkt &$p_1$, punkt &$p_2$ )
{
  char wynik, $c_1$, $c_2$;

  wynik = CAŁY;
  $c_1$ = KodPunktu ( $p_1$ );
  $c_2$ = KodPunktu ( $p_2$ );
  while ( $c_1$ || $c_2$ ) {
    if ( $c_1$ & $c_2$ )
      return NIC;
    if ( !$c_1$ ) {
      zamień ( $p_1$, $p_2$ );
      zamień ( $c_1$, $c_2$ );
    }
    switch ( $c_1$ ) {
  case 0001: case 0101: case 1001: *$p_1$ = punkt przecięcia z prostą $x=x_{\min}$;  break;
  case 0010: case 0110: case 1010: *$p_1$ = punkt przecięcia z prostą $x=x_{\max}$;  break;
  case 0100:       *$p_1$ = punkt przecięcia z prostą $y=y_{\min}$; break;
  case 1000:       *$p_1$ = punkt przecięcia z prostą $y=y_{\max}$;
    }
    $c_1$ =  KodPunktu ( $p_1$ );
    *kod = CZĘŚĆ;
  }
  return wynik;
} /*SC_clip*/

3.1.3. Algorytm Lianga-Barsky'ego

Wadą algorytmu Sutherlanda-Cohena jest to, że obliczane są punkty, które mogą być następnie odrzucone (ponieważ leżą poza oknem). Zabiera to czas, a ponadto wprowadza większe błędy zaokrągleń. Aby otrzymać algorytm pozbawiony tych wad, skorzystamy z parametrycznego przedstawienia odcinka (3.1). Oznaczymy \Delta x=x_{2}-x_{1}, \Delta y=y_{2}-y_{1}. Aby dokonać obcięcia odcinka, zawęzimy przedział zmienności parametru t do przedziału odpowiadającego części wspólnej odcinka z oknem, a dopiero potem wyznaczymy punkty końcowe. Zauważmy, że w ogólności możemy przyjąć na początku inny przedział niż [0,1], co umożliwi obcinanie odcinka który leży na prostej przechodzącej przez punkty (x_{1},y_{1})(x_{2},y_{2}), ale o innych końcach. Możemy nawet przyjąć początkowy przedział [-\infty,+\infty], który reprezentuje całą prostą (ale wtedy procedura obcinania musi wyprowadzić wynik w postaci odpowiednich wartości parametru prostej).

float t1, t2;

char Test ( float p, float q )
{
  float r;

  if ( p < 0 ) {
    r = q/p;
    if ( r > t2 ) return 0;
    else if ( r > t1 ) t1 = r;
  }
  else if ( p > 0 ) {
    r = q/p;
    if ( r < t1 ) return 0;
    else if ( r < t2 ) then t2 = r;
  }
  else if ( q < 0 ) return 0;
  return 1;
} /*Test*/

char LB_clip ( punkt *p1, punkt *p2 )
{
  float dx, dy;

  t1 = 0;  t2 = 1;  dx = p2->x - p1->x;
  if ( Test ( -dx, p1->x - $x_{\min}$ ) )
    if ( Test ( dx, $x_{\max}$ - p1->x ) ) {
      dy = p2->y - p1->y;
      if ( Test ( -dy, p1->y - $y_{\min}$ ) )
        if ( ( Test ( dy, $y_{\max}$ - p1->y ) ) {
          if ( t2 != 1 ) { p2->x += t2*dx;  p2->y += t2*dy; }
          if ( t1 != 0 ) { p1->x += t1*dx;  p1->y += t1*dy; }
          return 1;
        }
    }
  return 0;
} /*LB_clip*/

Wartością funkcji jest 1 jeśli przynajmniej część odcinka jest widoczna i 0 w przeciwnym razie. Zasada działania algorytmu wiąże się z interpretacją prostych, na których leżą krawędzie okna, jako zbiorów algebraicznych. Funkcja f(x,y)=ax+by-c, której zbiorem miejsc zerowych jest taka prosta, jest dodatnia w półpłaszczyźnie zawierającej okno (to jest zapewnione przez odpowiedni wybór znaku współczynników a, b, c). Parametr q funkcji Test otrzymuje wartość tej funkcji w punkcie p_{1} kolejno dla każdej krawędzi okna. Po wykryciu, że przedział zmienności parametru t jest pusty, funkcja ma wartość 0. W przeciwnym razie, po obcięciu wszystkimi krawędziami okna, procedura oblicza punkty końcowe części odcinka widocznej w oknie (uwaga na kolejność obliczania tych punktów; w pewnej książce wykryłem błąd, polegający na zmianie kolejności).

Algorytm Lianga-Barsky'ego, podobnie jak algorytm Sutherlanda-Cohena, może być łatwo zmodyfikowaniy w celu obcinania odcinków do dowolnych wielokątów lub wielościanów wypukłych.

3.1.4. Obcinanie prostych

Jeśli mamy wyznaczyć część wspólną danej prostej i prostokątnego okna, to możemy użyć algorytmu Lianga-Barsky'ego. Opierając się na przedstawieniu prostej w postaci niejawnej, za pomocą równania liniowego ax+by=c, możemy to zadanie wykonać jeszcze trochę szybciej. W tym celu trzeba obliczyć wartości funkcji f(x,y)=ax+by-c w wierzchołkach okna, a następnie, badając znaki wartości funkcji f w tych punktach, wyznaczyć punkty przecięcia prostej tylko z tymi krawędziami okna, które są przez prostą przecięte. Zysk z takiego podejścia to kilka zaoszczędzonych działań arytmetycznych, co (w przypadku średnim) przekłada się na prawie o połowę krótszy czas działania. Ponieważ procedury obcinania należą do oprogramowania podstawowego w bibliotekach graficznych (często są one implementowane sprzętowo) i wywoływane wiele razy, więc każde ich przyspieszenie jest istotne.

3.2. Obcinanie wielokątów

3.2.1. Algorytm Sutherlanda-Hodgmana

Zajmiemy się wyznaczaniem części wspólnej wielokąta i półpłaszczyzny. Wyznaczanie przecięcia dwóch wielokątów, z których przynajmniej jeden jest wypukły (np. jest prostokątnym oknem) można wykonać za pomocą kilkakrotnego obcinania do półpłaszczyzny.

Założymy, że brzeg wielokąta jest jedną łamaną zamkniętą. Jeśli tak nie jest (wielokąt ma dziury i łamanych jest więcej), to każdą łamaną trzeba obciąć osobno. Brzeg wielokąta obciętego przez opisany niżej algorytm Sutherlanda-Hodgmana też jest łamaną zamkniętą, zorientowaną zgodnie z brzegiem wielokąta danego.

Rys. 3.2. Algorytm Sutherlanda-Hodgmana.

W algorytmie Sutherlanda-Hodgmana kolejno przetwarzamy boki wielokąta (odcinki łamanej zamkniętej). Zmienna s reprezentuje punkt końcowy poprzedniego odcinka. Wywoływana przez poniższą procedurę funkcja Inside ma wartość true jeśli punkt podany jako argument leży we ,,właściwej” półpłaszczyźnie. Funkcja Intersect oblicza punkt przecięcia odcinka (o końcach podanych jako parametry). Procedura Output ma za zadanie wyprowadzić kolejny wierzchołek obciętego wielokąta, co może polegać na wstawieniu go do tablicy.

void SH_clip ( int n, punkt w[] );
{
  punkt p, q, s;
  char is, ip;

  s = w[n-1];
  is = Inside ( s );
  for ( i = 0; i < n; i++ ) {
    p = w[i];  ip := Inside ( p );
    if ( is ) {
      if ( ip ) Output ( p );
      else {
        q = Intersect ( s, p );
        Output ( q );
      }
    }
    else if ( ip ) {
      q = Intersect ( s, p );
      Output ( q );
      Output ( p );
    }
    s = p;
    is = ip;
  }
} /*SH_clip*/
Rys. 3.3. Wyniki obcinania wielokątów niewypukłych.

Zauważmy, że jeśli wielokąt nie jest wypukły, to jego część wspólna z półpłaszczyzną (albo oknem) może nie być spójna. Dostajemy wtedy na wyjściu łamaną, której krawędzie mają wspólne części (i części te są przeciwnie zorientowane). Jeśli po obcięciu wypełniamy wielokąt algorytmem przeglądania liniami poziomymi, to obecność tych ,,fałszywych krawędzi” nie ma znaczenia, choć jeśli brzeg półpłaszczyzny jest ukośny (tj. nie jest prostą pionową ani poziomą), to po zaokrągleniu współrzędnych wierzchołków do liczb całkowitych błędy mogą się ukazać (w postaci błędnie zamalowanych pikseli).

3.2.2. Algorytm Weilera-Athertona

W różnych zastosowaniach zdarza się potrzeba wyznaczenia części wspólnej, sumy lub różnicy dwóch wielokątów dowolnych, tj. niekoniecznie wypukłych. Umożliwia to algorytm Weilera-Athertona, który dopuszcza jako dane wielokąty, których brzegi mogą składać się z wielu zamkniętych łamanych; wielokąty takie mogą być niejednospójne, tj. z dziurami, albo nawet niespójne.

Rys. 3.4. Algorytm Weilera-Athertona.

Podstawowe wymaganie, konieczne aby wynik był dobrze określony, to właściwe zorientowanie brzegu. Dla ustalenia uwagi przyjmiemy umowę, że każda krawędź jest zorientowana w ten sposób, że poruszając się wzdłuż niej zgodnie z orientacją mamy wnętrze wielokąta po prawej stronie (rys. 3.4). Aby wyznaczyć przecięcie wielokątów, kolejno

  1. Konstruujemy reprezentacje dwóch grafów zorientowanych; wierzchołkami i krawędziami każdego z nich są wierzchołki i zorientowane krawędzie jednego z wielokątów.

  2. Znajdujemy wszystkie punkty przecięcia krawędzi jednego wielokąta z krawędziami drugiego. Dzielimy krawędzie, na których leżą te punkty, na kawałki; dołączamy w ten sposób nowe wierzchołki do grafu, zachowując uporządkowanie punktów podziału krawędzi w grafie. Wprowadzamy dodatkowe powiązanie między wierzchołkami grafów, które odpowiadają temu samemu punktowi (przecięcia). Tworzy się w ten sposób jeden graf, którego krawędzie reprezentują kawałki brzegu jednego lub drugiego wielokąta.

  3. Znajdujemy wierzchołek grafu, który jest wierzchołkiem przecięcia wielokątów. Może to być wierzchołek odpowiadający punktowi przecięcia brzegów wielokątów, a jeśli takiego nie ma, to możemy sprawdzić, czy jakiś wierzchołek leży wewnątrz drugiego wielokąta, korzystając z reguły parzystości. Wybieramy wychodzącą ze znalezionego wierzchołka krawędź, która jest krawędzią przecięcia (wyboru dokonujemy na podstawie orientacji brzegów).

    Zaczynając od znalezionego wierzchołka, obchodzimy graf, aż do trafienia ponownie na wierzchołek, z którego wyszliśmy. W każdym wierzchołku, który odpowiada przecięciu brzegów, wybieramy krawędź wielokąta innego niż ten, po którego krawędzi poruszaliśmy się. Odwiedzone wierzchołki wyprowadzamy; ich ciąg reprezentuje odpowiednio zorientowany fragment (zamkniętą łamaną) przecięcia wielokątów danych.

    Algorytm kończy działanie po stwierdzeniu braku nieodwiedzonego wierzchołka należącego do brzegu wielokątów.

Mając algorytm, który wyznacza przecięcie wielokątów, łatwo możemy otrzymać algorytm wyznaczania sumy lub różnicy; dany brzeg określa wielokąt, ale także jego dopełnienie — wystarczy tylko odwrócić orientację wszystkich krawędzi. W ten sposób sumę wielokątów otrzymamy jako dopełnienie przecięcia ich dopełnień.

Ważne dla poprawnej implementacji algorytmu jest uwzględnienie przypadków, gdy wielokąty mają wspólne wierzchołki lub gdy ich krawędzie mają wspólne odcinki. Pewne punkty mogą też być końcami więcej niż dwóch krawędzi wielokąta. Istotna jest możliwość wykonywania działań na wielokątach otrzymanych za pomocą tego algorytmu, i wtedy takie sytuacje zdarzają się często.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.