Geometrie/Vyplňování

Vyplňování oblastí

Cílem těchto algoritmů je vyplnit určitou uzavřenou oblast. Rozlišujeme dva základní způsobu popisu hranice oblasti:

Geometricky určené hranice (pro vektorová zařízení)
Hranice nakreslená v rastru (pro rastrová zařízení)

Druhy algoritmů pro vyplňování

řádkové vyplňování
semínkové vyplňování

Popis

Vyplňování geometricky určené hranice

Základní metodou je řádkové vyplňování. Každým řádkem rastru vedeme pomyslnou vodorovnou čáru a hledáme průsečíky s hranicí oblasti. Nalezené průsečíky se seřadí podle souřadnice x. Dvojice mezi lichým a sudým průsečíkem definují úsečku ležící uvnitř oblasti.

Na jednoduché oblasti na obrázku si všimněte typických poloh rozkladového řádku a hraničních čar. Mnohoúhelník tvořící hranici je určen 7 vrcholy A až G. Hledání vnitřních úseček probíhá shora dolů. Vedle obrázku jsou vypsány hraniční úsečky, které daný řádek protíná.

První rozkladový řádek protíná celkem 4 hraniční čáry, takže dojde k nakreslení dvou úseček. Ty mají v tomto případě obě nulovou délku, neboť leží ve vrcholech C a G. Grafické systémy by měly nakreslit úsečku nulové délky jako jeden pixel.

Druhý řádek je zpracován obdobně. Ve třetím řádku musí být vyloučena hrana DE, neboť má s rozkladovým řádkem nekonečně mnoho průsečíků. Zbylá čtveřice průsečíku opět určuje 2 vnitřní úsečky.

Problém nastává na čtvrtém řádku, kde je nalezen lichý počet průsečíků. Tuto situaci způsobuje vrchol B. Standardním řešením tohoto problému je zkrácení hranice BC o jeden pixel zdola ve směru osy y. Toto zdánlivé rozpojení hranice nemá vliv na činnost algoritmu. Naopak se ukazuj, že systematické zkrácení všech hran vede ke snížení počtu průsečíků a nemá na funkčnost metody vliv. Další obrázek ukazuje, že po takové úpravě zbudou například na třetím řádku pouze dva průsečíky namísto nadbytečných čtyř.

Pokud se pracuje v rastru (snad vždy) a koncové body hraničních úseček jsou určeny celými čísly, může dojít k tomu, že při různých sklonech hraničních úseček nemusí při zkrácení zdola o jeden pixel vyjít x-ová souřadnice nového koncového bodu celočíselná. Proto není úplně vhodné úsečky při výpočtu zkracovat, ale při výpočtu průsečíků vynechávat ty, jež jsou v koncovém bodě hraniční úsečky. Řešení všech možných poloh řádků s hranicí tedy vyžaduje předzpracování jednotlivých hraničních úseček. Celkově popisuje metodu řádkového vyplňování algoritmus v sekci Algoritmizace.

Pro výpočet průsečíku lze použít parametrické rovnice úsečky. Úsečka mezi body A[xa,ya] a B[xb,yb] je X[x,y] = A + (B-A) • t, t je z <0,1>, x = ax + (bx-ax) • t, y = ay + (by-ay) • t. Z toho, že známe y (souřadnice zpracovávaného řádku) vypočítáme t = (y-ay)/(by-ay). Dosazením t hned dostáváme x = ax + (bx-ax) (y-ay)/ (by-ay). Průsečík s úsečkou je platný pouze když t je z <0,1>, pokud vynecháváme průsečíky s koncovým bodem tak pouze když t je z <0,1).

Uvedená metoda lze použít i pro oblasti ohraničené libovolnou křivkou (nikoli jen mnohoúhelníkem), pouze se modifikuje část, jež počítá průsečíky.

Rozšíření řádkového algoritmu – šrafování

Šrafování je rozšířeno především v technických aplikacích. Rozšíření algoritmu je poměrně jednoduché. V případě vodorovných šraf stačí změnit krok změny souřadnice z hodnoty 1 na m (m je přirozené číslo) a získáme oblast s vyplněnou vodorovnými šrafami s roztečí m. Při šrafování přerušovanou čarou je vhodné určit vztažný bod, vůči němu bude čárkování nanášeno, abychom docílili toho, že jednotlivé odpovídající si úseky čárkování na dvou čarách byly nad sebou. Za vztažný bod volíme buď počátek soustavy souřadnic, nebo jeden z vrcholů hranice.

V praxi se však často uplatňuje šrafování pod obecným úhlem, než vodorovné. Metodu zkombinujeme ještě s transformací otáčení. Nejprve otočíme všechny hraniční úsečky oblasti o úhel -alfa. Na takto upravenou hranici použijeme běžný algoritmus vodorovného šrafování, s tím, že vy vypočítané vnitřní úseky před vykreslením otočíme zpět o úhel alfa.

Semínkové vyplňování

Tento algoritmus se dá použít pouze pro rastrové zařízení.

Mějme dánu oblast ohraničenou nějakým uzavřeným polygonem. Pro určení této oblasti nám poté stačí určit jeden vnitřní bod této oblasti (tzv. startovací bod). Startovací bod může uživatel určit snadno pomocí myši.Ze znalosti vnitřního bodu pak snadno určíme, zda sousední body leží uvnitř oblasti nebo na hranici oblasti. Podle způsobu určování sousedních bodů máme dva způsoby vyplňování.

Na obrázku 1) je metoda používající čtyř sousedních bodů (tzv. čtyř-směrové vyplňování), na obrázku 2) je metoda používající osmi sousedních bodů (tzv. osmi-směrové vyplňování). Oblasti, které lze vyplnit čtyř-směrovým vyplňováním se nazývají čtyř-směrové oblasti. Oblasti, které lze vyplnit osmi-směrovým vyplňováním se nazývají osmi-směrové oblasti.

Algoritmizace

Algoritmus semínkového vyplňování

Otestuj zda bod již nebyl vyplněn nebo neleží na hranici.
Pokud ano skončí, pokud ne vyplň tento bod a urči všechny sousední body.
Pro všechny sousední body znovu použij tento algoritmus.

Tento rekurzívní algoritmus není vhodný pro implementaci vzhledem k jeho paměťové náročnosti. Proto se používá modifikovaný algoritmus, který používá rekurze pouze ve směrech nahoru a dolů a na řádcích používá sekvenční vyplnění pomocí cyklu dokud nenarazí na hranici.

Algoritmus řádkového vyplňování

Pro všechny hraniční úsečky ověř:
1. je-li vodorovná, vynech ji (případně vykresli)
2. uprav orientaci shora dolů
3. aktualizuj mezní souřadnice hranice ymax a ymin
Pro y od ymin do xmax proveď:
1. nalezni průsečíky hraničních úseček s řádkem y, vynech ty, jež prochází koncovým bodem hraniční úsečky
2. uspořádej všechny průsečíky podle souřadnice x.
3. vykresli úseky mezi lichými a sudými průsečíky.
Vykresli hranici oblasti je-li třeba.

Kód v jazyce C#

Pomocné objekty a metody

Raster

třída pro uchování dat o rastru

metody:

void SetPixel(int x,int y,Color c) - nastaví barvu pixelu na pozici x, y
Color GetPixel(int x,int y) - vrátí barvu pixelu na pozici x, y
void DrawLine(Point p1, Point p2,Color c) - nakreslí čáru do rastru
void DrawPoly(Point[] p,Color c) - nakreslí uzavřený polygon do rastru

Pomocná třída

public class PointComparer: IComparer
{
 int IComparer.Compare(object p1, object p2)
 {
   return Compare((Point)p1,(Point)p2);
 }
 public int Compare(Point p1, Point p2)
 {
   return p1.X.CompareTo(p2.X);
 }
}

Pomocná metoda

 Point[] Rotate(Point[] p,double angle)
 {
   Point[] ret = new Point[p.Length];
   double c = Math.Cos(angle);
   double s = Math.Sin(angle);
   for (int i=0;i<p.Length;i++)
   {
     Point q = p[i];
     ret[i] = new Point((int)Math.Round(q.X*c-q.Y*s),(int)Math.Round(q.X*s+q.Y*c));
   }
   return ret;
 }

Vlastní algoritmy

Semínkové vyplňování 4-směrové

void SeedFill4(Point point, Color c)
{
 if(point.X < 0 || point.Y < 0 || point.X >= raster.Width || point.Y >= raster.Height) return;
 Color barva = raster.GetPixel(point.X,point.Y);
 if(barva.R == c.R && barva.G == c.G && barva.B == c.B ) return;
 raster.SetPixel(point.X,point.Y,c);
 SeedFill4(new Point(point.X+1,point.Y),c);
 SeedFill4(new Point(point.X-1,point.Y),c);
 SeedFill4(new Point(point.X,point.Y+1),c);
 SeedFill4(new Point(point.X,point.Y-1),c);
}

Semínkové vyplňování 8-směrové

void SeedFill8(Point point, Color c)
{
 if(point.X < 0 || point.Y < 0 || point.X >= raster.Width || point.Y >= raster.Height) return;
 Color barva = raster.GetPixel(point.X,point.Y);
 if(barva.R == c.R && barva.G == c.G && barva.B == c.B ) return;
 raster.SetPixel(point.X,point.Y,c);
 SeedFill8(new Point(point.X+1,point.Y),c);
 SeedFill8(new Point(point.X-1,point.Y),c);
 SeedFill8(new Point(point.X,point.Y+1),c);
 SeedFill8(new Point(point.X,point.Y-1),c);
 SeedFill8(new Point(point.X+1,point.Y+1));
 SeedFill8(new Point(point.X-1,point.Y-1));
 SeedFill8(new Point(point.X-1,point.Y+1));
 SeedFill8(new Point(point.X+1,point.Y-1));
}

Poznámka: V našem programu je algoritmus řešen pomocí fronty, jelikož umožňuje lepší animaci vyplňování a zejména nedochází k přetečení programového zásobníku u vyplňování velkých oblastí.

Řádkové vyplňování

void FillPolygon(Point[] points, Color c, int hatchStep, double angle)
{
  if (points.Length<2) return;
  int ymax = points[0].Y-1; // nastaveni pocatecnich hodnot
  int ymin = points[0].Y+1;
   int pointsCount = 0;
  Point[] p = new Point[points.Length*2+2];
  points = Rotate(points,-angle); // rotace bodu pro srafovani
  for (int i=0;i<points.Length;i++)
  {
    Point p1,p2;
    int j = (i==points.Length-1)? 0:i+1; 
    if (points[i].Y==points[j].Y) continue;
    if (points[i].Y>points[j].Y)
    {
      p[pointsCount++] = points[j];
      p[pointsCount++] = points[i];
      ymax = Math.Max(ymax,points[j].Y);
      ymin = Math.Min(ymin,points[i].Y);
    }
    else
    {
      p[pointsCount++] = points[i];
      p[pointsCount++] = points[j];
      ymax = Math.Max(ymax,points[i].Y);
      ymin = Math.Min(ymin,points[j].Y);
    }
  }
  int intersCount;
  Point[] inters = new Point[points.Length+1];
  for (int y=ymin;y<=ymax;y+=hatchStep)
  {
    intersCount=0;
    inters = new Point[points.Length+1];
    for (int l=0;l<pointsCount-1;l+=2)
    {
      float t = (y-p[l].Y)/(float)(p[l+1].Y-p[l].Y);
      if (t>=0 && t<1)
      {
        float f = (p[l].X+(p[l+1].X-p[l].X)*t);
        int x = (int)Math.Round(f);
        inters[intersCount++] = new Point(x,y);
      }
    }
    inters = Rotate(inters,angle);
    Array.Sort(inters,0,intersCount,new PointComparer());
    for (int k = 0;k<intersCount-1;k+=2)
    {
      raster.DrawLine(inters[k].X,inters[k].Y,inters[k+1].X,inters[k+1].Y,c);
    }
  }
}

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.