Geometrie/Ořezávání

Rovinné ořezávání

Ořezávací (clipping) algoritmy umožňují vybrat z kresby pouze ty části, které jsou viditelné v určité oblasti. Ačkoli existují obecné algoritmy, které pracují nad nekonvexním mnohoúhelníkem, bývá ořezávací oblast nejčastěji definována jako obdélník (typickým příkladem je ořezání objektu oknem obrazovky), toto v dalším textu předpokládejme.

V případě rovinného ořezávání bývá ořezávaným objektem polygon, úsečka. Výsledkem ořezání jsou opět tyto objekty. Pokud ořezáváme uzavřené polygony (oblasti), je žádoucí, aby i po ořezání byly uzavřené, tj. "je možno je i po ořezání vyplnit". Z tohoto důvodu je v některých případech potřeba zajistit přidání nových hran (viz níže popis algoritmu Sutherland-Hodgman).

Popis

Ořezávání úsečky

Algoritmů na ořezávání úseček obdélníkovým oknem je několik -- Cohen-Sutherland, Cyrus-Back, Liang-Barsky. Popišme si první z nich, který je také použit v naší implementaci.

Algoritmus Cohen-Sutherland

Základem algoritmu ořezávání úsečky Cohen-Sutherland je pojem ohodnocení bodu hraničními kódy (dále ohodnocení bodu ). Každý z bodů úsečky získá své ohodnocení v závislosti jeho polohy vůči ořezávacímu oknu. Ohodnocení bodu je možné reprezentovat různě (bitové pole, objektem obsahující vlastnosti jako boolean hodnoty,...), podstatné je to, aby bylo pro každý bod určeno, zda se nachází vlevo, vpravo, dole či nahoře od ořezávacího okna. Nechť je dále ohodnocení definováno jako čtveřice 0/1,0/1,0/1,0/1 (LEVO, PRAVO, DOLE, NAHORE -- kde 0 není splněno a 1 je splněno), tj. například 0101 označuje polohu bodu vpravo nahoře od ořezávacího okna.

Ohodnocení bodu hraničními kódy

Ořezávací algoritmus postupně zkoumá tři polohy úsečky vůči ořezávacímu oknu. Polohu úsečky zjistíme porovnáním ohodnocení hraničních bodů úsečky. Označíme-li si hraniční body jako A a B a jejich ohodnocení Val(A) a Val(B), mohou nastat následující případy (pozn: operace průnik a sjednocení probíhají po jednotlivých bitech ohodnocení):

Polohy úseček vůči ořezávacímu oknu

$Val(A)\cup Val(B)=\emptyset$ -- tj. úsečka je celá v ořezávacím okně a není potřeba ji proto ořezávat. Tj. pro obě ohodnocení bodů platí, že jsou 0000 (oba body jsou "v ořezávacím okně").
$Val(A)\cap Val(B)\neq \emptyset$ -- tj. úsečka je celá mimo ořezávací okno a není potřeba ji proto ořezávat. Tento test ovšem některé případy úseček procházejících vnějšími oblastmi neodhalí.
$Val(A)\cap Val(B)=\emptyset$ -- tj. úsečka buď prochází ořezávacím oknem anebo jde o "neodhalený" případ úsečky mimo okno. Úsečka prochází několika oblastmi a je nutné ji ořezat. Provedeme to tak, že zvolíme bod úsečky, který neleží uvnitř (tj. jeho hraniční kód není 0000) a podle nastavené jedničky vybereme hranici, podle které ho úsečku zkrátíme (přesněji algoritmizace níže).

Ořezávání polygonu

Ořezat polygon by bylo možné i pomocí postupného aplikování výše uvedeného algorimu Cohen-Sutherland. Problém však nastává při požadavku zachování uzavřenosti, tj. nesmí dojít k rozpadu hran. Po ořezání musí být případně polygon doplněn o další úsečky (viz. obrázek). Je tedy zřejmé, že algoritmy pro ořezání úsečky se pro ořezávání polygonu příliš nehodí.

Algoritmus Sutherland-Hodgman

Velice jednoduchý postup pro ořezávání polygonu zvolili Sutherland a Hogman. Jejich algoritmus postupně ořezává daný polygon jednotlivými hranicemi okna, při čemž v případě potřeby je k ořezanému polygonu přidána hrana. Jestliže máme rovinou oblast ohraničenou polygonem, pak provedeme nejdřív ořezání podle levé strany okna. Výsledkem bude nový polygon. Tento polygon použijeme pro ořezání pravou stranou okna. Obdobně budeme pokračovat pro horní a dolní stranu okna.

Polygon si zorientujeme, na vstupu do algoritmu máme posloupnost vrcholů tohoto orientovaného polygonu a na výstupu na začátku prázdnou posloupnost. V i-tém kroku vezmeme vždy vrcholy $U_{i}$ a $U_{i+1}$ ze vstupní posloupnosti a do výstupní posloupnosti zapíšeme vrcholy podle následujících pravidel:

Oba vrcholy této úsečky leží vně vůči dané hranici okna. Pak do výstupní posloupnosti nezapíšeme žádný bod.
Počáteční vrchol $U_{i}$ leží vně okna a koncový vrchol $.U_{i+1}$ leží uvnitř okna, pak spočítáme průsečík $B$ strany polygonu s hranicí okna a do výsledné posloupnosti zařadíme tento vypočítaný průsečík.
Oba vrcholy leží uvnitř okna vzhledem k dané hranici okna, pak do výstupní posloupnosti zapíšeme počáteční bod $U_{i}$ .
Počáteční vrchol $U_{i}$ leží uvnitř okna a koncový vrchol $U_{i+1}$ leží vně okna, pak spočítáme průsečík $B$ strany polygonu s hranicí okna a do výstupní posloupnosti přidáme počáteční vrchol $U_{i}$ a bod průsečíku $B$ .

Tento algoritmus použijeme postupně pro všechny strany ořezávacího okna, přičemž na vstupu pro první stranu okna je ořezávaný polygon a pro každou další stranu okna je již polygon oříznutý v předchozím kroku.

Algoritmizace

Ořezávání úsečky, algoritmus Cohen-Sutherland

VSTUP: úsečka, ořezávací okno
VÝSTUP: ořezaná úsečka

Nechť je úsečka určena dvěma body "A" a "B". aktualniBod = "A"

Urči hraniční kódy bodů vůči ořezávacímu oknu.
Pokud nastal jeden z následujících případů, algoritmus ukonči (body "A" a "B" jsou hraničními body ořezané úsečky)
- Oba body jsou uvnitř ořezávacího okna (prázdné sjednocení, viz výše popis algoritmu).
- Úsečka neprochází ořezávacím oknem (neprázdný průnik, viz výše popis algoritmu).
Je nutné úsečku ořezat
- Pokud má aktualniBod hraniční kód 0000 (je uvnitř okna), zaměň aktualniBod za bod, který ještě nebyl uvažován (aktualniBod="B")
Podle nastavené jedničky hraničního kódu bodu ořež úsečku podle odpovídajíci hrany (tj. pokud 1001, začínáme řezat levou hranou).
- aktualniBod=průsečík úsečky a zvolené hrany
Pokračuj bodem 1.

Ořezávání polygonu, algoritmus Sutherland-Hodgman

VSTUP: polygon, ořezávací okno
VÝSTUP: ořezaný polygon

Polygon si zorientujeme, na začátku algoritmu máme tedy posloupnost bodů tohoto orientovaného polygonu a na výstupu na začátku prázdnou posloupnost.

V i-tém kroku vezmeme vždy body $U_{i}$ a $U_{i+1}$ ze vstupní posloupnosti a do výstupní posloupnosti zapíšeme body podle následujících pravidel:

Oba body leží vně vůči dané hranici okna. Pak do výstupní posloupnosti nezapíšeme žádný bod.
Počáteční bod $U_{i}$ leží vně okna a koncový bod $.U_{i+1}$ leží uvnitř okna, pak spočítáme průsečík $B$ strany polygonu s hranicí okna a do výsledné posloupnosti zařadíme tento vypočítaný průsečík.
Oba body leží uvnitř okna vzhledem k dané hranici okna, pak do výstupní

posloupnosti zapíšeme počáteční bod $U_{i}$ .

Počáteční bod $U_{i}$ leží uvnitř okna a koncový bod $U_{i+1}$ leží vně okna, pak spočítáme průsečík $B$ strany polygonu s hranicí okna a do výstupní posloupnosti přidáme počáteční vrchol $U_{i}$ a bod průsečíku $B$ .

Tento algoritmus použiji postupně pro všechny strany ořezávacího okna, přičemž na vstupu pro první stranu okna je ořezávaný polygon a pro každou další stranu okna je již polygon oříznutý v předchozím kroku.

Je také možné každou ořezanou hranu ihned poslat k ořezání další hranicí -- tzv. reentrant polygon clipping, tak si nemusíme pamatovat postupně ořezané polygon a jejich proměnlivý počet vrcholů. Tento způsob je použit v naší implementaci algoritmu.

Kód v jazyce C#

Program se skládá ze 2 komponent. Každou realizoval jeden z nás -- jedna je zodpovědná za prezentaci -- formular, druhá je jádrem -- Kernel, které provádí veškeré výpočty. Pro komunikaci jsme si definovali rozhraní IGeom vypadající následně:

namespace Geom {

	public interface IGeom {

		bool PridejPolygon(ArrayList body); // prida polygon
		bool SmazPolygon(int ID); // smaze polygon daneho ID
		bool ZmenPolygon(object polygon); //object Polygon = objekt polygon z jadra
		ArrayList VratOrezanePolygony(); // vrati ke vsem polygonum s jadra orezane polygony
		ArrayList VratPolygony(); // vrati vsechny polygon, kt. jsou ulozene v jadre
		object VratOkno(); // vrati orezavaci okno
		bool ZmenOkno(object okno); //zmeni orezavaci okno
		bool SmazVsechnyPolygony(); // smaze vsechny polygony

	}

}

Veškeré polygony jsou uloženy v jádře v hash tabulce, která umožňuje rychlý přístup k požadovanému objektu podle jeho ID. Jádro si pouze o polygony žádá při zobrazování, případně žádá jejich modifikaci -- podle operací definovaných v IGeom. Popis níže se už týká jen komponenty Kernel.

Pomocné objekty a metody

Sef -- implementuje rozhraní IGeom, je fasádou k Kernel. Zodpovídá za veškerou funkčnost jádra.
Bod2D -- objekt definující bod v 2D, obsahuje souřadnice
OhodnoceniBodu -- ohodnocení bodu, váže se k bodu
Polygon -- objekt reprezentující polygon (obsahuje seznam bodů)
OrezavaciOkno -- speciální příklad obdélníkového polygonu. Definuje ořezávací okno

Vlastní algoritmus

Oba algoritmy SutherlandHodgman a CohenSutherland jsou specializací abstraktní třídy OrezavacAbstract definující společnou metodu nabízející možnost ořezání:

public abstract Polygon Orez( Polygon polygon );

Při žádosti o ořezání polygonu je podle počtu bodů polygonu objektem Sef zvolen odpovídající algoritmus, pro úsečku CohenSutherland, pro jiné polygony SutherlandHodgman a volána metoda algoritmu Orez( polygon ).

Následuje kód hlavních metod ořezávacích algoritmů.

Algoritmus Cohen-Sutherland - ořezání úsečky

/// <summary>
/// oreze usecku
/// </summary>
/// <param name="polygon">polygon</param>
/// <returns>orezany polygon</returns>
public override Polygon Orez( Polygon polygon )
{
  Polygon orezanyPolygon = new Polygon();
  bool orezano = false;
  Bod2D bod1 = (Bod2D)((Bod2D) polygon.Body[0]).Clone();
  Bod2D bod2 = (Bod2D)((Bod2D) polygon.Body[1]).Clone();
  while( !orezano ) // dokud neni orezano aplikuji algoritmus..
  {
    NastavOhodnoceniBodu( bod1 ) ;NastavOhodnoceniBodu( bod2 );
    // usecka je uvnitr -- konec<br />
    if( bod1.Ohodnoceni.JeUvnitr && bod2.Ohodnoceni.JeUvnitr ) // oba jsou uvnitr
    {
      // pridam orezane body<br />
      orezanyPolygon.Body.Add( bod1 ); orezanyPolygon.Body.Add( bod2 );
      orezano = true;
    } 
    else // nejsou uplne mimo oblast? -- konec
    if( ( bod1.Ohodnoceni.NeprazdnyPrunik( bod2.Ohodnoceni ))) orezano = true;
    else { // existuje prusecik      
      zamenPoradiBodu( ref bod1, ref bod2 ); // zamenim poradi -- pokud je uz jeden na miste
 
     // ZJISTENI SMERNICE
      double k; 
      double jmenovatel = ((double)bod2.X - (double)bod1.X);
      k = (((double)bod2.Y - (double)bod1.Y)) / jmenovatel;
      // najdu pruseciky
      if( bod1.Ohodnoceni.Levo ){ // prusecik s levou hranici
        bod1.Y = (int) (bod1.Y + k * (orezavaciOkno.MinX - bod1.X ));
        bod1.X = orezavaciOkno.MinX;
      }
      else
      if( bod1.Ohodnoceni.Pravo ) // prusecik s pravou hranici
      {
        bod1.Y = (int) (bod1.Y + k * (orezavaciOkno.MaxX - bod1.X ));
        bod1.X = orezavaciOkno.MaxX;
      }
      else // DOLE
      if( bod1.Ohodnoceni.Dole ) // prusecik se spodni hranici
      {
        bod1.X = bod1.X  ;
        bod1.X += (k == 0)? 0: (int)((orezavaciOkno.MinY - bod1.Y )/k);
        bod1.Y = orezavaciOkno.MinY;
      }
      else
      if( bod1.Ohodnoceni.Nahore ) // prusecik s pravou hranici
      {
        bod1.X = bod1.X;
        bod1.X += (k == 0)? 0: (int)((orezavaciOkno.MaxY - bod1.Y )/k);
        bod1.Y = orezavaciOkno.MaxY;
      }
    }
  }
  return orezanyPolygon;
}

Algoritmus Sutherland-Hodgman - ořezání polygonu

Pozn.: v následujícím kódu je použita varianta algoritmu SutherlandHodgman, kdy dochází k předávání ořezané hrany ihned k ořezání další hranou (tzv. reentrant polygon clipping), tj. nedochází k ukládání mezivýsledku "polygonu ořezaného jednou hranou", jak je popsáno v algoritmu výše. Použitý postup má výhodu i nevýhodu: je optimálnější, avšak jednotlivé kroky nejsou na první pohled tak pochopitelné.

/// <summary>
/// oreze polygon
/// </summary>
/// <param name="polygon">polygon</param>
/// <returns>orezany polygon</returns>
public override Polygon Orez( Polygon polygon )
{
  orezanyPolygon = new Polygon();
  // nastavim
  nova_hranice = new bool[]{ true, true, true, true };
  foreach( Bod2D b in polygon.Body )
    orezVrchol( b, HRANICE.LEVA );
  // uzavreni mnohouhelniku
  ZaverecneOrezani();
  return orezanyPolygon;
}


/// <summary>
/// oreze vrchol vzhledem k dane hranici
/// </summary>
/// <param name="bod"></param>
/// <param name="hranice"></param>
private void orezVrchol( Bod2D bod, HRANICE hranice )
{
  if( nova_hranice[ (int)hranice ] ) // pracuji s 1. bodem dane hranice, ulozim si ho == jako predchudce
  {
    prvni_bod[ (int)hranice ] = bod;
    nova_hranice[ (int)hranice ] = false;
  }
  else // uz mam predchudce, muzu porovnavat
  {
    if( protinaHranici( bod, predchazejiciBod[ (int)hranice ], hranice ) )
    {
       Bod2D prusecik = nalezeniPruseciku( bod, predchazejiciBod[ (int)hranice ], hranice ); // prusecik usecky s hranici, dle kt. orezavam
       if ( hranice < HRANICE.HORNI ) // muzu jeste orezat dalsi hranici
        orezVrchol( prusecik, hranice +1);
       }
       else 
         orezanyPolygon.Body.Add( prusecik ); // mam ho orezany
       }
    }
    // ULOZIM BOD
    predchazejiciBod[ (int)hranice ] = bod;
    if( uvnitr( bod, hranice ) ) // je-li uvnitr, musim orezavat
    {
      if ( hranice < HRANICE.HORNI ) // neorezal jsem ho uz vsema?
        orezVrchol( bod, hranice +1);
      else 
      {
        orezanyPolygon.Body.Add( bod ); // uz jsem ho orezal vs. hranicemi
      }
    } 
}


/// <summary>
/// uzavreni mnohouhelniku
/// </summary>
public void ZaverecneOrezani()
  {
     for( HRANICE hranice = HRANICE.LEVA; hranice <= HRANICE.HORNI; hranice++)
     {
       if( protinaHranici( predchazejiciBod[ (int)hranice ],
       prvni_bod[ (int)hranice ], hranice ))
     {
       Bod2D prusecik = nalezeniPruseciku( predchazejiciBod[ (int)hranice ], 
              prvni_bod[ (int)hranice ], hranice);
       if ( hranice < HRANICE.HORNI )
              orezVrchol( prusecik, hranice +1);
       else orezanyPolygon.Body.Add( prusecik ); // mam ho orezany
     }
  }
}

Autoři

Tento text vypracovali studenti Univerzity Palackého v Olomouci katedry Matematické informatiky jako součást zápočtového úkolu do předmětu Počítačová geometrie.