Grafika komputerowa: wypełnianie figur

W bibliotece SDL2 występują dwie funkcje do wypełniania prostokątów:

SDL_RenderFillRect(r,rect)
r – wskaźnik struktury SDL_Renderer z kontekstem graficznym
rect – wskaźnik struktury SDL_Rect, która definiuje prostokąt

SDL_RenderFillRects(r,R,n)
r – wskaźnik struktury SDL_Renderer z kontekstem graficznym
R – tablica o elementach typu SDL_Rect, które definiują prostokąty
n – liczba prostokątów w tablicy R

Pierwsza rysuje pojedynczy prostokąt zdefiniowany przez strukturę SDL_Rect, a druga rysuje ciąg prostokątów, których definicję przechowuje tablica struktur SDL_Rect. Poniższy program przedstawia prostą animację wykorzystującą funkcję SDL_RenderFillRects():

C++

// Wypełnienia 1
//--------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

// Liczba prostokątów
const int N = 10;

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Obszary", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy kontekst graficzny
  SDL_Renderer * r = SDL_CreateRenderer(w,0,SDL_RENDERER_PRESENTVSYNC);
  if(!r)
  {
     cout << "SDL_CreateRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Zmienne
  double alpha;   // Kąt obrotu
  SDL_Rect R[N];  // Tablica prostokątów
  int cr,cg,cb,dr,dg,db; // Kolor prostokątów
  int xs,ys;      // Środek elipsy
  int rx,ry;      // Promienie elipsy
  int i;

  // Inicjujemy zmienne;
  alpha = 0;

  xs = W_W / 2;
  ys = W_H / 2;

  rx = 5 * xs / 7;
  ry = 5 * ys / 7;

  for(i = 0; i < N; i++)
  {
    R[i].w = rand() % 40 + W_W / N;
    R[i].h = rand() % 40 + W_H / N;
    R[i].x = xs + rx * cos(alpha + i * 2 * M_PI / N) - R[i].w / 2;
    R[i].y = ys + ry * sin(alpha + i * 2 * M_PI / N) - R[i].h / 2;
  }
  cr = rand() % 256;
  cg = rand() % 256;
  cb = rand() % 256;
  do dr = -3 + rand() % 7; while(!dr);
  do dg = -3 + rand() % 7; while(!dg);
  do db = -3 + rand() % 7; while(!db);

  // Animacja
  SDL_Event event;
  while(1)
  {
    // Usuwamy treść poprzedniego okna
    SDL_SetRenderDrawColor(r,0,0,0,255);
    SDL_RenderClear(r);

    // Rysujemy prostokąty
    for(i = 0; i < N; i++)
    {
      SDL_SetRenderDrawColor(r,cr,cg,cb,255);
      SDL_RenderFillRects(r,R,N);
      SDL_SetRenderDrawColor(r,255,255,255,255);
      SDL_RenderDrawRects(r,R,N);
    }

    // Modyfikujemy współrzędne i kolory
    alpha += M_PI / 360;
    if(alpha > 2 * M_PI) alpha -= 2 * M_PI;

    for(i = 0; i < N; i++)
    {
      R[i].x = xs + rx * cos(alpha + i * 2 * M_PI / N) - R[i].w / 2;
      R[i].y = ys + ry * sin(alpha + i * 2 * M_PI / N) - R[i].h / 2;
    }

    if((cr + dr < 0) || (cr + dr > 255)) dr = - dr;
    if((cg + dg < 0) || (cg + dg > 255)) dg = - dg;
    if((cb + db < 0) || (cb + db > 255)) db = - db;
    cr += dr;
    cg += dg;
    cb += db;

    // Uaktualniamy treść okna na ekranie
    SDL_RenderPresent(r);

    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Prostokąty łatwo możemy wypełniać liniami poziomymi (lub pionowymi), uzyskując w ten sposób dodatkowe efekty. Poniższy program wykorzystuje podany w poprzednim rozdziale algorytm Bresenhama do uzyskania efektów gradientowych:

C++

// Wypełnienia 2
//--------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

// Liczba prostokątów
const int N = 15;

// Funkcja rysuje odcinek algorytmem Bresenhama
//---------------------------------------------
void SDL_RenderBresenhamLine(SDL_Renderer * r, int x1, int y1, int x2, int y2,
                             int r1, int g1, int b1, int r2, int g2, int b2)
{
  int dx,dy,kx,ky,e,i,cr,cg,cb;

  // Przyrosty w osiach x i y
  if(x1 <= x2) kx = 1; else kx = -1;
  if(y1 <= y2) ky = 1; else ky = -1;

  // Odległości pomiędzy punkatami startowym a końcowym wzdłuż osi
  dx = x2 - x1; if(dx < 0) dx = -dx;
  dy = y2 - y1; if(dy < 0) dy = -dy;

  // Rysujemy punkt startowy
  SDL_SetRenderDrawColor(r,r1,g1,b1,255);

  // Wybieramy wersję algorytmu Bresenhama
  if(dx >= dy)
  {
    // Wersja podstawowa

    e = dx / 2;   // Wyrażenie błędu

    for(i = 1; i <= dx; i++)
    {
      x1 += kx;   // Ruch w kierunku szybkim
      e -= dy;    // Nowe wyrażenie błędu
      if(e < 0)
      {
        y1 += ky; // Ruch w kierunku wolnym
        e += dx;
      }

      // Wyliczamy składowe koloru piksela
      cr = r1 + i * (r2 - r1) / dx;
      cg = g1 + i * (g2 - g1) / dx;
      cb = b1 + i * (b2 - b1) / dx;

      // Ustawiamy kolor piksela
      SDL_SetRenderDrawColor(r,cr,cg,cb,255);

      // Rysujemy kolejny piksel
      SDL_RenderDrawPoint(r,x1,y1);
    }
  }
  else
  {
    // Wersja z zamienionymi współrzędnymi

    e = dy / 2;   // Wyrażenie błędu

    for(i = 1; i <= dy; i++)
    {
      y1 += ky;   // Ruch w kierunku szybkim
      e -= dx;    // Nowe wyrażenie błędu
      if(e < 0)
      {
        x1 += kx; // Ruch w kierunku wolnym
        e += dy;
      }

      // Wyliczamy składowe koloru piksela
      cr = r1 + i * (r2 - r1) / dy;
      cg = g1 + i * (g2 - g1) / dy;
      cb = b1 + i * (b2 - b1) / dy;

      // Ustawiamy kolor piksela
      SDL_SetRenderDrawColor(r,cr,cg,cb,255);

      // Rysujemy kolejny piksel
      SDL_RenderDrawPoint(r,x1,y1);
    }
  }
}

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Obszary", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy kontekst graficzny
  SDL_Renderer * r = SDL_CreateRenderer(w,0,SDL_RENDERER_PRESENTVSYNC);
  if(!r)
  {
     cout << "SDL_CreateRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Zmienne
  double alpha;   // Kąt obrotu
  SDL_Rect R[N];  // Tablica prostokątów
  int cr1,cg1,cb1,dr1,dg1,db1;
  int cr2,cg2,cb2,dr2,dg2,db2;
  int r1,g1,b1,r2,g2,b2;
  int xs,ys;      // Środek elipsy
  int rx,ry;      // Promienie elipsy
  int i,j;

  // Inicjujemy zmienne;
  alpha = 0;

  xs = W_W / 2;
  ys = W_H / 2;

  rx = 5 * xs / 7;
  ry = 5 * ys / 7;

  for(i = 0; i < N; i++)
  {
    R[i].w = rand() % 40 + W_W / N;
    R[i].h = rand() % 40 + W_H / N;
    R[i].x = xs + rx * cos(alpha + i * 2 * M_PI / N) - R[i].w / 2;
    R[i].y = ys + ry * sin(alpha + i * 2 * M_PI / N) - R[i].h / 2;
  }
  cr1 = rand() % 256;
  cg1 = rand() % 256;
  cb1 = rand() % 256;
  do dr1 = -3 + rand() % 7; while(!dr1);
  do dg1 = -3 + rand() % 7; while(!dg1);
  do db1 = -3 + rand() % 7; while(!db1);
  cr2 = rand() % 256;
  cg2 = rand() % 256;
  cb2 = rand() % 256;
  do dr2 = -3 + rand() % 7; while(!dr2);
  do dg2 = -3 + rand() % 7; while(!dg2);
  do db2 = -3 + rand() % 7; while(!db2);

  // Animacja
  SDL_Event event;
  while(1)
  {
    // Usuwamy treść poprzedniego okna
    SDL_SetRenderDrawColor(r,0,0,0,255);
    SDL_RenderClear(r);

    // Rysujemy prostokąty
    for(i = 0; i < N; i++)
      for(j = 0; j < R[i].h; j++)
      {
         r1 = cr1 + j * (cr2 - cr1) / R[i].h;
         g1 = cg1 + j * (cg2 - cg1) / R[i].h;
         b1 = cb1 + j * (cb2 - cb1) / R[i].h;
         r2 = cr2 + j * (cr1 - cr2) / R[i].h;
         g2 = cg2 + j * (cg1 - cg2) / R[i].h;
         b2 = cb2 + j * (cb1 - cb2) / R[i].h;

         SDL_RenderBresenhamLine(r,R[i].x,R[i].y+j,R[i].x+R[i].w - 1,R[i].y+j,r1,g1,b1,r2,g2,b2);
      }

    // Modyfikujemy współrzędne i kolory
    alpha += M_PI / 360;
    if(alpha > 2 * M_PI) alpha -= 2 * M_PI;

    for(i = 0; i < N; i++)
    {
      R[i].x = xs + rx * cos(alpha + i * 2 * M_PI / N) - R[i].w / 2;
      R[i].y = ys + ry * sin(alpha + i * 2 * M_PI / N) - R[i].h / 2;
    }

    if((cr1 + dr1 < 0) || (cr1 + dr1 > 255)) dr1 = - dr1;
    if((cg1 + dg1 < 0) || (cg1 + dg1 > 255)) dg1 = - dg1;
    if((cb1 + db1 < 0) || (cb1 + db1 > 255)) db1 = - db1;
    cr1 += dr1;
    cg1 += dg1;
    cb1 += db1;

    if((cr2 + dr2 < 0) || (cr2 + dr2 > 255)) dr2 = - dr2;
    if((cg2 + dg2 < 0) || (cg2 + dg2 > 255)) dg2 = - dg2;
    if((cb2 + db2 < 0) || (cb2 + db2 > 255)) db2 = - db2;
    cr2 += dr2;
    cg2 += dg2;
    cb2 += db2;

    // Uaktualniamy treść okna na ekranie
    SDL_RenderPresent(r);

    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Na początek: podrozdziału strony

W grafice komputerowej trójkąt jest podstawowym elementem graficznym, który wykorzystywany jest do tworzenia innych, bardziej złożonych figur. Jak wypełnić trójkąt? Rozważmy najpierw dwa przypadki:

Trójkąt płaski u spodu

Podstawa trójkąta jest równoległa do osi OX układu współrzędnych. Trójkąt będziemy wypełniać liniami poziomymi. Linii będzie tyle, ile wynosi wysokość trójkąta plus 1:

Jeśli mamy dane współrzędne wierzchołków, to dla tego przypadku wysokość można bardzo łatwo obliczyć (pamiętaj, że oś OY jest na ekranie skierowana w dół).

Obliczamy nachylenie obu boków trójkąta:

Za punkty startowe linii przyjmujemy (x₁,y₁)‒(x₁,y₁). Po narysowaniu każdej linii współrzędne y zwiększamy o 1, a współrzędne x modyfikujemy o wartość s_L (punkt startowy) i s_R (punkt końcowy). Aby uniknąć błędów numerycznych, zmienne muszą być typu double.

Poniższy program wykorzystuję tę metodę do rysowania trójkąta:

C++

// Wypełnienia 3
//--------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Obszary", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy kontekst graficzny
  SDL_Renderer * r = SDL_CreateRenderer(w,0,SDL_RENDERER_PRESENTVSYNC);
  if(!r)
  {
     cout << "SDL_CreateRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Zmienne
  int x1,y1,x2,y2,x3,y3,dx1,dy1,y;
  int cr,cg,cb,dr,dg,db;
  double lx1,lx2,sL,sR;

  x1 = rand() % W_W;
  y1 = rand() % W_H;

  x2 = 0;
  x3 = W_W - 1;
  y2 = y3 = W_H - 1;

  do dx1 = -3 + rand() % 7; while(!dx1);
  do dy1 = -3 + rand() % 7; while(!dy1);

  cr = rand() % 255;
  cg = rand() % 255;
  cb = rand() % 255;
  do dr = -3 + rand() % 7; while(!dr);
  do dg = -3 + rand() % 7; while(!dg);
  do db = -3 + rand() % 7; while(!db);

  // Animacja
  SDL_Event event;
  while(1)
  {
    // Usuwamy treść poprzedniego okna
    SDL_SetRenderDrawColor(r,0,0,0,255);
    SDL_RenderClear(r);

    // Rysujemy trójkąt
    lx1 = lx2 = x1;
    sL =  (x2 - x1) / (double) (y2 - y1);
    sR =  (x3 - x1) / (double) (y3 - y1);

    SDL_SetRenderDrawColor(r,cr,cg,cb,255);

    for(y = y1; y <= y2; y++)
    {
      SDL_RenderDrawLine(r,lx1,y,lx2,y);
      lx1 += sL;
      lx2 += sR;
    }

    // Modyfikujemy położenie wierzchołka i kolory
    if((x1 + dx1 < 0) || (x1 + dx1 >= W_W)) dx1 = - dx1;
    if((y1 + dy1 < 0) || (y1 + dy1 >= W_H)) dy1 = - dy1;
    x1 += dx1;
    y1 += dy1;

    if((cr + dr < 0) || (cr + dr > 255)) dr = - dr;
    if((cg + dg < 0) || (cg + dg > 255)) dg = - dg;
    if((cb + db < 0) || (cb + db > 255)) db = - db;
    cr += dr;
    cg += dg;
    cb += db;

    // Uaktualniamy treść okna na ekranie
    SDL_RenderPresent(r);

    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Trójkąt płaski u góry

Tym razem podstawa jest u góry trójkąta:

Sposób rysowania trójkąta niczym nie różni się od poprzedniego. Jedynie rozpoczynamy rysowanie od podstawy, a zatem od odcinka (x₂,y₂)‒(x₂,y₃). Współrzędne x są odpowiednio zwiększane o przyrosty s_L i s_P. Współrzędne y są zwiększane od y₂ do y₁.

C++

// Wypełnienia 3
//--------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Obszary", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy kontekst graficzny
  SDL_Renderer * r = SDL_CreateRenderer(w,0,SDL_RENDERER_PRESENTVSYNC);
  if(!r)
  {
     cout << "SDL_CreateRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Zmienne
  int x1,y1,x2,y2,x3,y3,dx1,dy1,y;
  int cr,cg,cb,dr,dg,db;
  double lx1,lx2,sL,sR;

  x1 = rand() % W_W;
  y1 = rand() % W_H;

  x2 = 0;
  x3 = W_W - 1;
  y2 = y3 = 0;

  do dx1 = -3 + rand() % 7; while(!dx1);
  do dy1 = -3 + rand() % 7; while(!dy1);

  cr = rand() % 255;
  cg = rand() % 255;
  cb = rand() % 255;
  do dr = -3 + rand() % 7; while(!dr);
  do dg = -3 + rand() % 7; while(!dg);
  do db = -3 + rand() % 7; while(!db);

  // Animacja
  SDL_Event event;
  while(1)
  {
    // Usuwamy treść poprzedniego okna
    SDL_SetRenderDrawColor(r,0,0,0,255);
    SDL_RenderClear(r);

    // Rysujemy trójkąt
    lx1 = x2;
    lx2 = x3;
    sL =  (x2 - x1) / (double) (y2 - y1);
    sR =  (x3 - x1) / (double) (y3 - y1);

    SDL_SetRenderDrawColor(r,cr,cg,cb,255);

    for(y = y2; y <= y1; y++)
    {
      SDL_RenderDrawLine(r,lx1,y,lx2,y);
      lx1 += sL;
      lx2 += sR;
    }

    // Modyfikujemy położenie wierzchołka i kolory
    if((x1 + dx1 < 0) || (x1 + dx1 >= W_W)) dx1 = - dx1;
    if((y1 + dy1 < 0) || (y1 + dy1 >= W_H)) dy1 = - dy1;
    x1 += dx1;
    y1 += dy1;

    if((cr + dr < 0) || (cr + dr > 255)) dr = - dr;
    if((cg + dg < 0) || (cg + dg > 255)) dg = - dg;
    if((cb + db < 0) || (cb + db > 255)) db = - db;
    cr += dr;
    cg += dg;
    cb += db;

    // Uaktualniamy treść okna na ekranie
    SDL_RenderPresent(r);

    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Dowolny trójkąt

Zadanie narysowania dowolnego trójkąta sprowadza się do rozdzielenia go na dwa trójkąty, które już umiemy narysować: płaski na spodzie i płaski u góry:

Aby narysować oba trójkąty, musimy znaleźć współrzędne punktu P₄. Korzystamy tutaj z twierdzenia Talesa i układamy odpowiednią proporcję:

Współrzędna y₄ jest taka sama jak współrzędna y₂. Wystarczy zatem policzyć tylko współrzędną x₄:

Podsumujmy:

Mamy współrzędne trzech punktów P₁, P₂ i P₃, które są wierzchołkami trójkąta do narysowania. Wierzchołki porządkujemy względem ich współrzędnych y tak (pamiętaj, że oś OY jest skierowana w dół), aby:

Sprawdzamy, czy:

Jeśli tak, to wszystkie trzy punkty leżą na linii poziomej, wystarczy zatem narysować linię od najmniejszej współrzędnej x do największej współrzędnej x na wysokości y₁.

Sprawdzamy następnie, czy trójkąt jest płaski u góry. Jeśli tak, to rysujemy tylko ten wariant. W przeciwnym razie wyliczamy współrzędne punktu P₄:

Rysujemy linie poziome pierwszego trójkąta o płaskim spodzie (P₁, P₂, P₄) od y₁ do y₂ - 1 (aby uniknąć podwójnego rysowania ostatniej linii). Następnie rysujemy trójkąt o płaskiej górze (P₂, P₄, P₃) od y₂ do y₃.

Poniższy program pokazuje, jak to zrobić:

C++

// Wypełnienia 4
//--------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

// Liczba trójkątów
const int N = 10;

// Funkcja rysująca dowolny trójkąt
//---------------------------------
void SDL_RenderFillTriangle(SDL_Renderer * r, int x1, int y1, int x2, int y2, int x3, int y3)
{
  int a,b;
  double lx1,lx2,x4,sL,sP;

  // Porządkujemy punkty wg współrzędnych y
  if(y2 < y1)
  {
      swap(y2,y1);
      swap(x2,x1);
  }
  if(y3 < y1)
  {
      swap(y3,y1);
      swap(x3,x1);
  }
  if(y3 < y2)
  {
      swap(y3,y2);
      swap(x3,x2);
  }
  // sprawdzamy, czy punkty współliniowe
  if(y1 == y3)
  {
    a = b = x1;
    if(x2 < a) a = x2;
    if(x2 > b) b = x2;
    if(x3 < a) a = x3;
    if(x3 > b) b = x3;
    SDL_RenderDrawLine(r,a,y1,b,y1);
  }
  else
  {

    if(y1 < y2)
    {
      x4 = x1 + (x3 - x1) * (y2 - y1) / (double)(y3 - y1);
      lx1 = lx2 = x1;
      sL =  (x2 - x1) / (double) (y2 - y1);
      sP =  (x4 - x1) / (double) (y2 - y1);

      for(int y = y1; y < y2; y++)
      {
        SDL_RenderDrawLine(r,lx1,y,lx2,y);
        lx1 += sL;
        lx2 += sP;
      }

      sL = (x2 - x3) / (double) (y2 - y3);

      for(int y = y2; y <= y3; y++)
      {
        SDL_RenderDrawLine(r,lx1,y,lx2,y);
        lx1 += sL;
        lx2 += sP;
      }
    }
    else
    {
      lx1 = x1;
      lx2 = x2;
      sL = (x1 - x3) / (double) (y1 - y3);
      sP = (x2 - x3) / (double) (y2 - y3);
      for(int y = y1; y <= y3; y++)
      {
        SDL_RenderDrawLine(r,lx1,y,lx2,y);
        lx1 += sL;
        lx2 += sP;
      }
    }
  }
}

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Obszary", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy kontekst graficzny
  SDL_Renderer * r = SDL_CreateRenderer(w,0,SDL_RENDERER_PRESENTVSYNC);
  if(!r)
  {
     cout << "SDL_CreateRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Zmienne
  SDL_Point T[N][3];
  int dx[N][3],dy[N][3],i,j;
  int cr[N],cg[N],cb[N],dr[N],dg[N],db[N];

  for(i = 0; i < N; i++)
  {
    for(j = 0; j < 3; j++)
    {
      T[i][j].x = rand() % W_W;
      T[i][j].y = rand() % W_H;
      do dx[i][j] = -5 + rand() % 11; while(!dx[i][j]);
      do dy[i][j] = -5 + rand() % 11; while(!dy[i][j]);
    }
    cr[i] = rand() % 256;
    cg[i] = rand() % 256;
    cb[i] = rand() % 256;
    do dr[i] = -3 + rand() % 7; while(!dr[i]);
    do dg[i] = -3 + rand() % 7; while(!dg[i]);
    do db[i] = -3 + rand() % 7; while(!db[i]);
  }

  // Animacja
  SDL_Event event;
  while(1)
  {
    // Usuwamy treść poprzedniego okna
    SDL_SetRenderDrawColor(r,0,0,0,255);
    SDL_RenderClear(r);

    // Rysujemy trójkąty
    for(i = 0; i < N; i++)
    {
      SDL_SetRenderDrawColor(r,cr[i],cg[i],cb[i],255);
      SDL_RenderFillTriangle(r,T[i][0].x,T[i][0].y,T[i][1].x,T[i][1].y,T[i][2].x,T[i][2].y);
    }

    // Modyfikujemy współrzędne i kolory
    for(i = 0; i < N; i++)
    {
      for(j = 0; j < 3; j++)
      {
        if((T[i][j].x + dx[i][j] < 0) || (T[i][j].x + dx[i][j] >= W_W)) dx[i][j] = - dx[i][j];
        if((T[i][j].y + dy[i][j] < 0) || (T[i][j].y + dy[i][j] >= W_H)) dy[i][j] = - dy[i][j];
        T[i][j].x += dx[i][j];
        T[i][j].y += dy[i][j];
      }
      if((cr[i] + dr[i] < 0) || (cr[i] + dr[i] > 255)) dr[i] = - dr[i];
      if((cg[i] + dg[i] < 0) || (cg[i] + dg[i] > 255)) dg[i] = - dg[i];
      if((cb[i] + db[i] < 0) || (cb[i] + db[i] > 255)) db[i] = - db[i];
      cr[i] += dr[i];
      cg[i] += dg[i];
      cb[i] += db[i];
    }

    // Uaktualniamy treść okna na ekranie
    SDL_RenderPresent(r);

    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Algorytm Bresenhama do wypełniania trójkąta

Wadą przedstawionego powyżej algorytmu rysowania trójkątów jest konieczność wykonywania obliczeń na liczbach zmiennoprzecinkowych. Co prawda współczesne procesory radzą sobie z tym problemem całkiem nieźle, jednak rysowanie trójkątów można wykonać bez operacji zmiennoprzecinkowych wykorzystując algorytm Bresenhama, a to udostępnia tę metodę prostszym procesorom. Co prawda algorytm ten nie był projektowany do wypełniania obszarów, lecz daje się łatwo dostosować do tego zadania. Zaletą algorytmu Bresenhama jest duża szybkość działania oraz operacje tylko na liczbach całkowitych.

Trójkąt mamy zadany trzema wierzchołkami P₁, P₂ i P₃:

Rozpoczynamy od posortowania wierzchołków trójkąta wg rosnących współrzędnych y:

Jeśli y₁ = y₃, to trójkąt sprowadza się do linii poziomej leżącej na wysokości y₁ i rozciągającej się od najmniejszej współrzędnej x do największej współrzędnej x. Rysujemy taką linię i zadanie kończymy.

Jeśli y₁ = y₂, to trójkąt jest płaski u góry:

Rysujemy linię poziomą na wysokości y₁ od x₁ do x₂.

Uruchamiamy algorytm Bresenhama dla obu odcinków P₁-P₃ i P₂-P₃. Algorytm jest tak skonstruowany, iż zatrzymuje się przy wykonaniu kroku w kierunku y. Otrzymujemy w ten sposób współrzędne x początku i końca odcinka poziomego leżącego na wysokości y. Operację należy wykonać (y₃ - y₁ - 1) razy, rysując za każdym razem linie poziome. Po narysowaniu trójkąta, kończymy.

Trzecia możliwość to trójkąt zbudowany z dwóch trójkątów, górnego i dolnego:

Tutaj nie musimy wyznaczać punktu P₄. Rozpoczynamy od postawienia punktu w wierzchołku P₁. Następnie uruchamiamy algorytm Bresenhama dla odcinków P₁-P₂ oraz P₁-P₃. Algorytm zatrzymuje się przy kroku w kierunku y. Otrzymujemy kolejne linie poziome, które rysujemy. Operację wykonujemy do momentu osiągnięcia przez algorytm punktu P₂. Uruchamiamy ponownie algorytm Bresenhama od punktu P₂ do P₃ (linia od P₁ do P₃ jest kontynuowana z poprzedniego kroku). Rysujemy kolejne linie poziome. Kończymy po osiągnięciu punktu P₃.

Poniższy program pokazuje praktyczne zastosowanie tej procedury. Prześledź go dokładnie.

Algorytm Bresenhama jest tutaj zaimplementowany w postaci dwóch funkcji: InitBresenham() i ContBresenham(). Pierwsza funkcja inicjuje parametry potrzebne w drugiej funkcji, która z kolei wylicza współrzędne początku linii. Parametry są przekazywane do funkcji poprzez referencje.

C++

// Wypełnienia 5
//--------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

// Liczba trójkątów
const int N = 30;

// Funkcja inicjuje algorytm Bresenhama
//-------------------------------------
void InitBresenham(int x1, int y1, int x2, int y2, int & dx, int & dy, int & kx, int & ky, int & e)
{

  // Przyrosty w osiach x i y
  if(x1 <= x2) kx = 1; else kx = -1;
  if(y1 <= y2) ky = 1; else ky = -1;

  // Odległości pomiędzy punkatami startowym a końcowym wzdłuż osi
  dx = x2 - x1; if(dx < 0) dx = -dx;
  dy = y2 - y1; if(dy < 0) dy = -dy;

  // Wybieramy wersję algorytmu Bresenhama
  if(dx >= dy) e = dx / 2; else e = dy / 2;
}

// Funkcja kontynuuje algorytm Bresenhama
//---------------------------------------
void ContBresenham(int & x, int & y, int & dx, int & dy, int & kx, int & ky, int & e)
{
  if(dx >= dy)
    while(1)
    {
      x += kx;   // Ruch w kierunku szybkim
      e -= dy;   // Nowe wyrażenie błędu
      if(e < 0)
      {
        y += ky; // Ruch w kierunku wolnym
        e += dx;
        break;
      }
    }
  else
  {
    y += ky;   // Ruch w kierunku szybkim
    e -= dx;   // Nowe wyrażenie błędu
    if(e < 0)
    {
      x += kx; // Ruch w kierunku wolnym
      e += dy;
    }
  }
}

// Funkcja rysująca dowolny trójkąt
//---------------------------------
void SDL_RenderFillTriangle(SDL_Renderer * r, int x1, int y1, int x2, int y2, int x3, int y3)
{
  int a,b,dx1,dy1,dx2,dy2,kx1,ky1,kx2,ky2,e1,e2,x,y,i;

  // Porządkujemy punkty wg współrzędnych y
  if(y2 < y1)
  {
      swap(y2,y1);
      swap(x2,x1);
  }
  if(y3 < y1)
  {
      swap(y3,y1);
      swap(x3,x1);
  }
  if(y3 < y2)
  {
      swap(y3,y2);
      swap(x3,x2);
  }
  // sprawdzamy, czy punkty współliniowe
  if(y1 == y3)
  {
    a = b = x1;
    if(x2 < a) a = x2;
    if(x2 > b) b = x2;
    if(x3 < a) a = x3;
    if(x3 > b) b = x3;
    SDL_RenderDrawLine(r,a,y1,b,y1);
  }
  else
  {

    if(y1 == y2) // Trójkąt płaski u góry
    {
      SDL_RenderDrawLine(r,x1,y1,x2,y2);
      InitBresenham(x1,y1,x3,y3,dx1,dy1,kx1,ky1,e1);
      InitBresenham(x2,y2,x3,y3,dx2,dy2,kx2,ky2,e2);

      // Rysujemy linie poziome
      for(i = y1; i < y3; i++)
      {
          ContBresenham(x1,y1,dx1,dy1,kx1,ky1,e1);
          ContBresenham(x2,y2,dx2,dy2,kx2,ky2,e2);
          SDL_RenderDrawLine(r,x1,y1,x2,y2);
      }
    }
    else
    {
        SDL_RenderDrawPoint(r,x1,y1);
        InitBresenham(x1,y1,x2,y2,dx1,dy1,kx1,ky1,e1);
        x = x1;
        y = y1;
        InitBresenham(x,y,x3,y3,dx2,dy2,kx2,ky2,e2);
        for(i = y1; i < y2; i++)
        {
          ContBresenham(x1,y1,dx1,dy1,kx1,ky1,e1);
          ContBresenham(x,y,dx2,dy2,kx2,ky2,e2);
          SDL_RenderDrawLine(r,x1,y1,x,y);
        }
        InitBresenham(x2,y2,x3,y3,dx1,dy1,kx1,ky1,e1);
        for(i = y2; i < y3; i++)
        {
          ContBresenham(x2,y2,dx1,dy1,kx1,ky1,e1);
          ContBresenham(x,y,dx2,dy2,kx2,ky2,e2);
          SDL_RenderDrawLine(r,x2,y2,x,y);
        }
    }
  }
}

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Obszary", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy kontekst graficzny
  SDL_Renderer * r = SDL_CreateRenderer(w,0,SDL_RENDERER_PRESENTVSYNC);
  if(!r)
  {
     cout << "SDL_CreateRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Zmienne
  SDL_Point T[N][3];
  int dx[N][3],dy[N][3],i,j;
  int cr[N],cg[N],cb[N],dr[N],dg[N],db[N];

  for(i = 0; i < N; i++)
  {
    for(j = 0; j < 3; j++)
    {
      T[i][j].x = rand() % W_W;
      T[i][j].y = rand() % W_H;
      do dx[i][j] = -5 + rand() % 11; while(!dx[i][j]);
      do dy[i][j] = -5 + rand() % 11; while(!dy[i][j]);
    }
    cr[i] = rand() % 256;
    cg[i] = rand() % 256;
    cb[i] = rand() % 256;
    do dr[i] = -3 + rand() % 7; while(!dr[i]);
    do dg[i] = -3 + rand() % 7; while(!dg[i]);
    do db[i] = -3 + rand() % 7; while(!db[i]);
  }

  // Animacja
  SDL_Event event;
  while(1)
  {
    // Usuwamy treść poprzedniego okna
    SDL_SetRenderDrawColor(r,0,0,0,255);
    SDL_RenderClear(r);

    // Rysujemy trójkąty
    for(i = 0; i < N; i++)
    {
      SDL_SetRenderDrawColor(r,cr[i],cg[i],cb[i],255);
      SDL_RenderFillTriangle(r,T[i][0].x,T[i][0].y,T[i][1].x,T[i][1].y,T[i][2].x,T[i][2].y);
    }

    // Modyfikujemy współrzędne i kolory
    for(i = 0; i < N; i++)
    {
      for(j = 0; j < 3; j++)
      {
        if((T[i][j].x + dx[i][j] < 0) || (T[i][j].x + dx[i][j] >= W_W)) dx[i][j] = - dx[i][j];
        if((T[i][j].y + dy[i][j] < 0) || (T[i][j].y + dy[i][j] >= W_H)) dy[i][j] = - dy[i][j];
        T[i][j].x += dx[i][j];
        T[i][j].y += dy[i][j];
      }
      if((cr[i] + dr[i] < 0) || (cr[i] + dr[i] > 255)) dr[i] = - dr[i];
      if((cg[i] + dg[i] < 0) || (cg[i] + dg[i] > 255)) dg[i] = - dg[i];
      if((cb[i] + db[i] < 0) || (cb[i] + db[i] > 255)) db[i] = - db[i];
      cr[i] += dr[i];
      cg[i] += dg[i];
      cb[i] += db[i];
    }

    // Uaktualniamy treść okna na ekranie
    SDL_RenderPresent(r);

    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Na początek: podrozdziału strony

Wielokąt wypukły (ang. convex polygon) jest figurą geometryczną na płaszczyźnie, której wszystkie przekątne zawierają się wewnątrz tego wielokąta:


Wielokąt wypukły		Wielokąt niewypukły

Wielokąty można wypełniać przez podział na trójkąty i wypełnienie tych trójkątów, co rozwiązaliśmy w poprzednim podrozdziale. Wielokąt wypukły daje się dosyć łatwo podzielić na trójkąty. Wielokąt powinien być tak zdefiniowany, aby jego kolejne wierzchołki były połączone bokami, tworząc łamaną zamkniętą:

Kierunek obiegu wierzchołków jest dowolny.

Wybieramy pierwszy wierzchołek P₁ (dla wygody, w rzeczywistości można wybrać dowolny z wierzchołków wielokąta):

Następnie wybieramy dwa następne wierzchołki P₂ i P₃. Otrzymujemy pierwszy trójkąt:

Idziemy kolejno wzdłuż pozostałych wierzchołków. Każdy nowy trójkąt otrzymujemy z pierwszego wierzchołka P₁, z ostatnio wybranego i z kolejnego na obwodzie wielokąta. Dla przykładowego wielokąta otrzymamy w ten sposób trójkąty:

Δ(P₁,P₂,P₃), Δ(P₁,P₃,P₄), Δ(P₁,P₄,P₅), Δ(P₁,P₅,P₆):

Oczywiście możliwe są inne podziały.

Zajmijmy się teraz problemem wygenerowania wielokąta wypukłego. Wykorzystamy tutaj prostą własność: wielokąt jest wypukły, jeśli wszystkie wewnętrzne kąty wierzchołkowe są mniejsze od kąta półpełnego π radianów (120° w mierze stopniowej). Dodatkowo suma S wszystkich kątów wewnętrznych w n-kącie wynosi:

Jest tak dlatego, iż n-kąt zawiera n-2 trójkąty, a suma kątów wewnętrznych każdego trójkąta jest równa π [rad]:

Wielokąty wypukłe utworzymy w następujący sposób:

Najpierw generujemy n-kąt foremny, n > 3. Sposób generacji takiego wielokąta opisaliśmy już wcześniej.

Wszystkie kąty wewnętrzne są mniejsze od π. Wybieramy pierwszy bok wielokąta (możemy wybrać dowolny bok, ale dla wygody wybieramy pierwszy od wierzchołka P₁ do P₂):

Na boku tym wybieramy jeden punkt P':

Punkt P' wybieramy, tak aby dzielił odcinek w stosunku ^m/_(m+n), gdzie m i n są wylosowanymi dwoma liczbami naturalnymi większymi od 0. Współrzędne policzymy z odpowiednich proporcji (twierdzenie Talesa):

Do wyznaczonego w ten sposób punktu P' przenosimy wierzchołek P₂, co zniekształca wielokąt foremny:

Identyczną operację wykonujemy dla następnego boku:

Gdy przetworzymy w ten sposób wszystkie boki wielokąta, otrzymamy wielokąt wypukły (wykonane przekształcenia wierzchołków nie wpływają na wypukłość wielokąta, spróbuj to uzasadnić), który nie jest wielokątem foremnym:

Obliczenia najlepiej wykonywać na liczbach zmiennoprzecinkowych, aby zminimalizować błędy zaokrągleń. Dokonujemy podziału na trójkąty:

Trójkąty wypełniamy i otrzymujemy wypełniony wielokąt wypukły:

Poniższy program wykorzystuje opisaną tutaj metodę do rysowania wypełnionego sześciokąta wypukłego:

C++

// Wypełnienia 6
//--------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

// Funkcja inicjuje algorytm Bresenhama
//-------------------------------------
void InitBresenham(int x1, int y1, int x2, int y2, int & dx, int & dy, int & kx, int & ky, int & e)
{

  // Przyrosty w osiach x i y
  if(x1 <= x2) kx = 1; else kx = -1;
  if(y1 <= y2) ky = 1; else ky = -1;

  // Odległości pomiędzy punkatami startowym a końcowym wzdłuż osi
  dx = x2 - x1; if(dx < 0) dx = -dx;
  dy = y2 - y1; if(dy < 0) dy = -dy;

  // Wybieramy wersję algorytmu Bresenhama
  if(dx >= dy) e = dx / 2; else e = dy / 2;
}

// Funkcja kontynuuje algorytm Bresenhama
//---------------------------------------
void ContBresenham(int & x, int & y, int & dx, int & dy, int & kx, int & ky, int & e)
{
  if(dx >= dy)
    while(1)
    {
      x += kx;   // Ruch w kierunku szybkim
      e -= dy;   // Nowe wyrażenie błędu
      if(e < 0)
      {
        y += ky; // Ruch w kierunku wolnym
        e += dx;
        break;
      }
    }
  else
  {
    y += ky;   // Ruch w kierunku szybkim
    e -= dx;   // Nowe wyrażenie błędu
    if(e < 0)
    {
      x += kx; // Ruch w kierunku wolnym
      e += dy;
    }
  }
}

// Funkcja rysująca dowolny trójkąt
//---------------------------------
void SDL_RenderFillTriangle(SDL_Renderer * r, int x1, int y1, int x2, int y2, int x3, int y3)
{
  int a,b,dx1,dy1,dx2,dy2,kx1,ky1,kx2,ky2,e1,e2,x,y,i;

  // Porządkujemy punkty wg współrzędnych y
  if(y2 < y1)
  {
      swap(y2,y1);
      swap(x2,x1);
  }
  if(y3 < y1)
  {
      swap(y3,y1);
      swap(x3,x1);
  }
  if(y3 < y2)
  {
      swap(y3,y2);
      swap(x3,x2);
  }
  // sprawdzamy, czy punkty współliniowe
  if(y1 == y3)
  {
    a = b = x1;
    if(x2 < a) a = x2;
    if(x2 > b) b = x2;
    if(x3 < a) a = x3;
    if(x3 > b) b = x3;
    SDL_RenderDrawLine(r,a,y1,b,y1);
  }
  else
  {

    if(y1 == y2) // Trójkąt pła  SDL_RenderDrawLine(r,x1,y1,x2

,y2);
      InitBresenham(x1,y1,x3,y3,dx1,dy1,kx1,ky1,e1);
      InitBresenham(x2,y2,x3,y3,dx2,dy2,kx2,ky2,e2);

      // Rysujemy linie poziome
      for(i = y1; i < y3; i++)
      {
          ContBresenham(x1,y1,dx1,dy1,kx1,ky1,e1);
          ContBresenham(x2,y2,dx2,dy2,kx2,ky2,e2);
          SDL_RenderDrawLine(r,x1,y1,x2,y2);
      }
    }
    else
    {
        SDL_RenderDrawPoint(r,x1,y1);
        InitBresenham(x1,y1,x2,y2,dx1,dy1,kx1,ky1,e1);
        x = x1;
        y = y1;
        InitBresenham(x,y,x3,y3,dx2,dy2,kx2,ky2,e2);
        for(i = y1; i < y2; i++)
        {
          ContBresenham(x1,y1,dx1,dy1,kx1,ky1,e1);
          ContBresenham(x,y,dx2,dy2,kx2,ky2,e2);
          SDL_RenderDrawLine(r,x1,y1,x,y);
        }
        InitBresenham(x2,y2,x3,y3,dx1,dy1,kx1,ky1,e1);
        for(i = y2; i < y3; i++)
        {
          ContBresenham(x2,y2,dx1,dy1,kx1,ky1,e1);
          ContBresenham(x,y,dx2,dy2,kx2,ky2,e2);
          SDL_RenderDrawLine(r,x2,y2,x,y);
        }
    }
  }
}

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Obszary", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy kontekst graficzny
  SDL_Renderer * r = SDL_CreateRenderer(w,0,SDL_RENDERER_PRESENTVSYNC);
  if(!r)
  {
     cout << "SDL_CreateRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Zmienne
  SDL_Point P[7];    // Sześciokąt
  SDL_Point T[4][3]; // 4 trójkąty podziałowe
  int cr,cg,cb,dr,dg,db,dx,dy;
  int i;
  double alpha = M_PI * rand() / (double)RAND_MAX;

  // Generujemy sześciokąt foremny
  int rr = 50 + rand() % (W_H / 3); // promień okręgu opasającego
  for(i = 0; i < 6; i++)
  {
    P[i].x = W_W / 2 + rr * cos(alpha + i * M_PI / 3);
    P[i].y = W_H / 2 + rr * sin(alpha + i * M_PI / 3);
  }

  P[6] = P[0];

  // Zniekształcamy wielokąt
  int m,n;
  for(i = 1; i < 6; i++)
  {
    m = 1 + rand() % 7;
    n = 1 + rand() % 7;
    P[i].x = P[i-1].x + m * (P[i].x - P[i-1].x) / (double)(m + n);
    P[i].y = P[i-1].y + m * (P[i].y - P[i-1].y) / (double)(m + n);
  }

  // Przesunięcia
  do dx = -3 + rand() % 7; while(!dx);
  do dy = -3 + rand() % 7; while(!dy);

  // Kolory
  cr = rand() % 256;
  cg = rand() % 256;
  cb = rand() % 256;
  do dr = -3 + rand() % 7; while(!dr);
  do dg = -3 + rand() % 7; while(!dg);
  do db = -3 + rand() % 7; while(!db);

  // Animacja
  SDL_Event event;
  while(1)
  {
    // Usuwamy treść poprzedniego okna
    SDL_SetRenderDrawColor(r,0,0,0,255);
    SDL_RenderClear(r);

    // Dzielimy wielokąt na 4 trójkąty
    for(i = 0; i < 4; i++)
    {
      T[i][0] = P[0]; // wierzchołek
      T[i][1] = P[i + 1];
      T[i][2] = P[i + 2];
    }

    // Wypełniamy trójkąty
    SDL_SetRenderDrawColor(r,cr,cg,cb,255);
    for(i = 0; i < 4; i++)
      SDL_RenderFillTriangle(r,T[i][0].x,T[i][0].y,T[i][1].x,T[i][1].y,T[i][2].x,T[i][2].y);

    // Rysujemy obrys wielokata
    SDL_SetRenderDrawColor(r,255,255,255,255);
    SDL_RenderDrawLines(r,P,7);

    // Modyfikujemy współrzędne
    for(i = 0; i < 6; i++)
      if((P[i].x + dx < 0) || (P[i].x + dx >= W_W))
      {
        dx = - dx;
        break;
      }
    for(i = 0; i < 6; i++)
      if((P[i].y + dy < 0) || (P[i].y + dy >= W_H))
      {
        dy = - dy;
        break;
      }
    for(i = 0; i < 6; i++)
    {
      P[i].x += dx;
      P[i].y += dy;
    }
    P[6] = P[0];

    // Modyfikujemy kolory
    if((cr + dr < 0) || (cr + dr > 255)) dr = - dr;
    if((cg + dg < 0) || (cg + dg > 255)) dg = - dg;
    if((cb + db < 0) || (cb + db > 255)) db = - db;
    cr += dr;
    cg += dg;
    cb += db;

    // Uaktualniamy treść okna na ekranie
    SDL_RenderPresent(r);

    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Na początek: podrozdziału strony

Istnieje algorytm, który wypełnia dowolny wielokąt liniami poziomymi. Kształt wielokąta jest tutaj nieistotny. Może nawet posiadać wewnętrzne otwory.

Algorytm wykorzystuje listy oraz sortowanie kubełkowe.

Lista (ang. list) jest sekwencyjną strukturą danych, która składa się z ciągu elementów tego samego typu. Dostęp do elementów listy jest sekwencyjny – tzn. z danego elementu listy możemy przejść do elementu następnego lub do poprzedniego. Dojście do elementu i-tego wymaga przejścia przez kolejne elementy od pierwszego do docelowego. Takie zachowanie się tej struktury jest konsekwencją budowy jej elementów. Oprócz samych danych każdy element listy przechowuje zwykle dwa wskaźniki – do elementu następnego listy oraz do elementu poprzedzającego na liście. Nazwijmy te wskaźniki odpowiednio:

next – wskazuje kolejny element, (ang. next – następny)
prev – wskazuje poprzedni element (ang. prev od słówka previous – poprzedni)

W przeciwieństwie do tablicy elementy listy nie muszą leżeć obok siebie w pamięci. Zatem lista nie wymaga ciągłego obszaru pamięci i może być rozłożona w różnych jej segmentach – w porównaniu do tablic jest to niewątpliwie zaletą.

Wskaźniki przechowywane w każdym elemencie pozwalają powiązać te elementy w ciąg:

Po tak określonej liście możemy się poruszać w obu kierunkach, które wyznaczają pola next i prev. Listę o takiej własności nazywamy listą dwukierunkową (ang. doubly linked list). Pierwszy element listy nie posiada poprzednika, zatem w polu prev przechowuje wskaźnik pusty (czyli zero – adres zero nie wskazuje żadnego elementu). Podobnie ostatni element listy nie posiada następnika i jego pole next zawiera wskaźnik pusty.

Listy można zaprogramować samodzielnie, jednak lepiej jest skorzystać z gotowych rozwiązań, które udostępnia nam język C++ – z biblioteki STL (ang. Standard Template Library). Jest to biblioteka obiektowa. Jednym z jej obiektów jest lista. Zaletą stosowania STL jest to, iż nie musimy sami programować własności tych obiektów. Wszystko jest gotowe i sprawdzone, tylko korzystać!

Aby uzyskać w programie C++ dostęp do list, dołączamy plik nagłówkowy:

#include <list>

Następnie definiujemy strukturę elementów listy. Załóżmy, że jest nam potrzebna lista, której elementy będą przechowywały znak i liczbę całkowitą. Definiujemy zatem strukturę:

typedef struct
{
  char a;
  int b;
} listel;

Powyższa definicja wprowadza do programu nowy typ danych o nazwie listel. Każda dana typu listel jest strukturą zawierającą dwa pola, a – pole typu char i b – pole typu int. W definicji tej struktury nie umieszczamy wskaźników next i prev, ponieważ zrobi to biblioteka STL. Elementy listy w STL są tzw. pojemnikami (ang. conteners). Użytkownik definiuje sobie zawartość takiego pojemnika jako dowolny typ danych (typy proste int, double, itp. też mogą być używane). Następnie należy poinformować kompilator, że będziemy używać listy STL, której elementy będą zawierały naszą strukturę. Robimy to następująco:

list<listel> L;

Powyższa definicja tworzy listę L o elementach przechowujących naszą strukturę listel. Nowo utworzona lista jest pusta, tzn. nie zawiera jeszcze żadnego elementu. Elementy należy do listy dodać. Można to zrobić na kilka sposobów za pomocą funkcji składowych klasy list. Na przykład funkcja push_front() umieszcza nowy element na początku listy, a funkcja push_back() umieszcza nowy element na końcu listy. Po umieszczeniu elementu lista się powiększa. Liczbę elementów na liście możesz odczytać za pomocą funkcji size(). Wypróbuj poniższy program:

C++

// Listy STL 1
//------------

#include <iostream>
#include <list>

using namespace std;

// Definiujemy zawartość elementów listy

typedef struct
{
  char a;
  int  b;
} listel;

int main()
{
  // Tworzymy listę o elementach typu listel
  list<listel> L;
  int i;
  // Na liście umieszczamy 10 elementów
  for(i = 0; i < 10; i++)
  {
    listel el;
    el.a = 'A' + i;
    el.b = i;
    L.push_front(el);
  }
  // Wyświetlamy liczbę elementów
  cout << L.size();

  return 0;
}

Dostęp do elementów listy uzyskuje się przez tzw. iterator. Jest to wskaźnik, który wskazuje dane zawarte w elemencie listy. Poniższy program pokazuje sposób tworzenia i wykorzystania iteratora:

C++

// Listy STL 2
//------------

#include <iostream>
#include <list>

using namespace std;

// Definiujemy zawartość elementów listy

typedef struct
{
  char a;
  int  b;
} listel;

int main()
{
  // Tworzymy pustą listę o elementach typu listel
  list<listel> L;
  int i;
  // Na liście umieszczamy 10 elementów
  for(i = 0; i < 10; i++)
  {
    listel el;
    el.a = 'A' + i;
    el.b = i;
    L.push_front(el);
  }
  // Wyświetlamy zawartość kolejnych elementów listy
  for(list<listel>::iterator it = L.begin(); it != L.end(); it++)
    cout << it->a << " : " << it->b << endl;

  return 0;
}

W ostatniej pętli programu zastosowano iterator:

list<listel>::iterator it = L.begin();	–	zostaje utworzona zmienna it, która jest iteratorem listy elementów typu listel. Zmiennej it nadajemy adres pierwszego elementu listy za pomocą wywołania funkcji L.begin().
it != L.end();	–	to jest warunek kontynuacji pętli. Funkcja L.end() zwraca adres poza ostatnim elementem listy. Dopóki iterator nie przyjmie tego adresu, wskazuje element na liście i pętla będzie kontynuowana.
it++	–	to wygląda jak zwiększanie o 1. Jednak niech cię to nie zmyli. W rzeczywistości język C++ potrafi zmienić definicję prawie każdego operatora. Nazywamy to przeciążaniem operatorów (ang. operator overloading). W tym przypadku operator zwiększania został przeciążony i tutaj oznacza przesunięcie adresu w iteratorze na kolejny element listy.

Gdy uruchomisz program, zwróć uwagę na kolejność elementów listy. Jest odwrotna, ponieważ nowe elementy zostały wstawione przed starsze. Aby otrzymać kolejność zgodną z porządkiem wstawiania, wymień L.push_front() na L.push_back().

Elementy z listy możesz usuwać na kilka sposobów:

lista.pop_front() – usuwa pierwszy element listy
lista.pop_back() – usuwa ostatni element listy
lista.erase(it) – usuwa element listy wskazany iteratorem. Po tej operacji iterator wskazuje następny element za usuniętym.

C++

// Listy STL 3
//------------

#include <iostream>
#include <list>

using namespace std;

// Definiujemy zawartość elementów listy

typedef struct
{
  char a;
  int  b;
} listel;

int main()
{
  // Tworzymy pustą listę o elementach typu listel
  list<listel> L;
  int i;
  // Na liście umieszczamy 10 elementów
  for(i = 0; i < 10; i++)
  {
    listel el;
    el.a = 'A' + i;
    el.b = i;
    L.push_back(el);
  }
  // Usuwamy pierwszy element
  L.pop_front();

  // Usuwamy ostatni element
  L.pop_back();

  // Usuwamy 3 element od początku
  list<listel>::iterator it = L.begin();
  for(i = 0; i < 3; i++) it++;
  L.erase(it);

  // Wyświetlamy zawartość kolejnych elementów listy
  for(it = L.begin(); it != L.end(); it++)
    cout << it->a << " : " << it->b << endl;

  return 0;
}

Listy możemy w prosty sposób sortować. Należy jedynie udostępnić funkcję, która będzie w pożądany sposób porównywać dwa elementy listy. Funkcja ta otrzymuje w swoich parametrach dwa elementy listy, które ma porównać. Funkcja ma zwrócić wartość true, jeśli pierwszy element poprzedza drugi lub false w przypadku przeciwnym.

Posortujemy naszą listę rosnąco względem pól b:

C++

// Listy STL 4
//------------

#include <iostream>
#include <list>
#include <cstdlib>
#include <ctime>

using namespace std;

// Definiujemy zawartość elementów listy

typedef struct
{
  char a;
  int  b;
} listel;

// Funkcja porównująca
//--------------------
bool Compare(listel e1, listel e2)
{
    return e1.b < e2.b;
}

int main()
{
  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Tworzymy pustą listę o elementach typu listel
  list<listel> L;
  int i;
  list<listel>::iterator it;

  // Na liście umieszczamy 6 elementów
  // o losowej wartości pola b
  for(i = 0; i < 6; i++)
  {
    listel el; // Element listy
    el.a = 'A' + i;
    el.b = rand() % 10;
    L.push_back(el);
  }
  cout << "PRZED SORTOWANIEM:" << endl;

  // Wyświetlamy zawartość kolejnych elementów listy
  for(it = L.begin(); it != L.end(); it++)
    cout << it->a << " : " << it->b << endl;

  // Sortujemy listę
  L.sort(Compare);

  cout << endl << "PO SORTOWANIU:" << endl;

  // Wyświetlamy zawartość kolejnych elementów listy
  for(it = L.begin(); it != L.end(); it++)
    cout << it->a << " : " << it->b << endl;

  return 0;
}

Dwie listy uporządkowane można połączyć w jedną listę uporządkowaną:

C++

// Listy STL 5
//------------

#include <iostream>
#include <list>
#include <cstdlib>
#include <ctime>

using namespace std;

// Definiujemy zawartość elementów listy

typedef struct
{
  char a;
  int  b;
} listel;

// Funkcja porównująca
//--------------------
bool Compare(listel e1, listel e2)
{
    return e1.b < e2.b;
}

int main()
{
  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Tworzymy puste listy o elementach typu listel
  list<listel> L1,L2;
  int i;
  list<listel>::iterator it1,it2;

  // Na listach umieszczamy 6 elementów
  // o losowej wartości pola b
  for(i = 0; i < 6; i++)
  {
    listel el1,el2; // Elementy list
    el1.a = 'A';
    el2.a = 'B';
    el1.b = rand() % 10;
    el2.b = rand() % 10;
    L1.push_back(el1);
    L2.push_back(el2);
  }

  // Sortujemy obie listy
  L1.sort(Compare);
  L2.sort(Compare);

  cout << "PRZED SCALENIEM:" << endl;

  // Wyświetlamy zawartość kolejnych elementów list
  it1 = L1.begin();
  it2 = L2.begin();
  while(it1 != L1.end())
  {
    cout << it1->a << " : " << it1->b << "  -  "
         << it2->a << " : " << it2->b << endl;
    it1++;
    it2++;
  }

  // Scalamy L2 z L1
  L1.merge(L2,Compare);

  cout << endl << "PO SCALENIU:" << endl;

  // Wyświetlamy zawartość kolejnych elementów listy L1
  for(it1 = L1.begin(); it1 != L1.end(); it1++)
    cout << it1->a << " : " << it1->b << endl;

  return 0;
}

Poniżej podajemy opis algorytmu wypełniania wielokątów liniami skanującymi.

Wielokąt składa się z ciągu odcinków, które tworzą jego boki. Wielokąt przecinamy liniami równoległymi do osi OX o współrzędnych y_i rosnących od y_min do y_max, gdzie y_min i y_max jest zakresem współrzędnych y wierzchołków wielokąta (pamiętaj, że na powierzchni graficznej oś OY jest zawsze zwrócona w dół):

Linię poziomą, którą przecinamy wielokąt nazwijmy linią skanującą (ang. scan linie).

Obliczamy punkty przecięcia linii skanującej z krawędziami wielokąta. Obliczone punkty sortujemy rosnąco: x₁, x₂, x₃ i x₄. Kolejne pary punktów łączymy liniami poziomymi:

Pierwsze podejście do konstrukcji algorytmu będzie następujące (specjalnie pomijamy specyfikację wejścia i wyjścia, gdyż nie jest to jeszcze gotowy algorytm):

K01:	Na podstawie listy łamanych skonstruuj listę krawędzi wielokąta
K02:	Przeglądnij listę krawędzi i wyznacz y_min i y_max
K03:	Dla y = y_min, y_min+1,...,y_maxwykonuj kroki K04...K06
K04:	Wyznacz X - zbiór współrzędnych x punktów przecięcia krawędzi z listy z linią skanującą y
K05:	Posortuj rosnąco zbiór X
K06:	Kolejne pary punktów ze zbioru X połącz linią poziomą na wysokości y.
K07:	Zakończ

Na pozór wszystko wygląda OK. Jednakże musimy rozważyć kilka przypadków szczególnych.

Krawędź pozioma

Problem pojawi się, gdy linia skanująca przechodzi przez poziomą krawędź wielokąta. Jak policzyć punkt przecięcia?

Umawiamy się - na liście krawędzi wielokąta nie umieszczamy krawędzi poziomych, czyli takich, dla których zachodzi równość współrzędnych y punktu początkowego i końcowego. Nic się złego nie stanie, ponieważ wszystkie boki wielokąta łączą się kolejno ze sobą w łamaną. Zatem z krawędzią poziomą są połączone z obu stron krawędzie, które nie są poziome.

Linia skanująca przecina wierzchołek wielokąta

Wierzchołek łączy dwie krawędzie, zatem na współrzędnej x wierzchołka otrzymamy dwa punkty przecięcia linii skanującej - po jednym dla każdej z krawędzi. Poniższy rysunek przedstawia możliwe przypadki:

Pierwszy wierzchołek jest stalaktytem - obie złączone w nim krawędzie są powyżej linii skanującej. Do zbioru X zostaną wprowadzone dwa punkty x₁ i x₂ o równej wartości. Jak widać nie stanowi to problemu Linia pozioma od x₁ do x₂ będzie pojedynczym punktem.

Drugi wierzchołek jest stalagmitem - obie złączone w nim krawędzie leżą poniżej linii skanującej. Do zbioru X będą wstawione dwie współrzędne x₄ i x₅. To również nie stanowi problemu. Linie poziome x₃-x₄ oraz x₅-x₆ są prawidłowe.

Trzeci wierzchołek wprowadza problem - otrzymamy dwie współrzędne x₆ i x₇. Algorytm narysuje złą linię od x₇ do x₈. Nie narysuje za to właściwej linii od x₈ do x₉. I dodatkowo zostanie współrzędna x₉, z którą nie wiadomo co zrobić. Wniosek może być tylko jeden - w przypadku wierzchołka nie będącego stalaktytem ani stalagmitem należy do zbioru X wprowadzać tylko jedną współrzędną x. Technicznie można to zrealizować przez wyrzucanie krawędzi, gdy linia skanująca osiągnie współrzędną y jej dolnego końca. Jednakże przy takim podejściu nie będą rysowane dolne krawędzie obszaru oraz punkt końcowy stalaktytu - w sumie jest to nawet pożądane, ponieważ przy wielu przyległych wielokątach unikamy powtórnego rysowania linii na liniach już narysowanych, co w niektórych przypadkach może nawet prowadzić do błędów w grafice.

Nasz algorytm możemy teraz nieco usprawnić:

K01:	Dla kolejnych krawędzi wielokąta wykonuj kroki K02...K04
K02:	Jeśli krawędź jest pozioma, to pomiń ją i przejdź do następnej krawędzi
K03:	Dodaj krawędź do listy krawędzi
K04:	Na podstawie listy krawędzi wyznacz y_min i y_max
K05:	Dla y = y_min, y_min+1,...,y_maxwykonuj kroki K07...K09
K06:	Wyznaczaj punkty przecięcia linii skanującej z kolejnymi krawędziami, pomijając krawędzie, w których linia skanująca przechodzi przez dolny wierzchołek. Wyznaczone punkty umieszczaj w zbiorze X.
K07:	Posortuj rosnąco zbiór X
K08:	Kolejne pary współrzędnych ze zbioru X połącz linią poziomą na wysokości y, przy czym lewą współrzędną x zaokrąglij w górę, prawą zaokrąglij w dół.
K09:	Zakończ

Podział krawędzi

Na obecnym etapie naszego algorytmu wyznaczanie punktów przecięcia linii skanującej wymaga sprawdzenia wszystkich krawędzi wielokąta. Jeśli krawędzi tych jest dużo, może to być dosyć kosztowne. Ale przecież linia skanująca nie przecina wszystkich krawędzi:

Linia skanująca porusza się w dół. Kolorem niebieskim zaznaczyliśmy krawędzie wielokąta, które algorytm już przetworzył (dla przejrzystości na rysunku nie ma wypełnienia). Do tych krawędzi w algorytmie już nigdy nie wrócimy, zatem nie ma sensu ich dalej sprawdzać na punkty przecięcia z linią skanującą.

Kolorem zielonym zaznaczyliśmy krawędzie, do których algorytm jeszcze nie doszedł - tych krawędzi też nie musimy sprawdzać.

Pozostają krawędzie zaznaczone kolorem czerwonym - to krawędzie, które aktualnie przecina linia skanująca. Nazwiemy je krawędziami aktywnymi. Kandydatami na krawędzie aktywne są tylko krawędzie zielone. Krawędź staje się aktywna, gdy linia skanująca osiąga jej górny koniec (o mniejszej współrzędnej y), a przestaje być aktywna, gdy linia skanująca osiąga dolny koniec (punkt końcowy o większej współrzędnej y).

Wynika z tego, iż powinniśmy dla każdej krawędzi zapamiętać współrzędne y dolnego i górnego końca.

Narzucającym się rozwiązaniem jest stworzenie dwóch list:

Listy krawędzi jeszcze nie przetworzonych przez algorytm - na początku lista ta będzie zawierała wszystkie krawędzie wielokąta (z wyjątkiem krawędzi poziomych). Nazwijmy ją LK - lista krawędzi.
Listy krawędzi aktywnych, czyli takich, które aktualnie są przecinane przez linię skanującą. Na początku pracy algorytmu lista ta będzie pusta. Nazwijmy ją LKA - lista krawędzi aktywnych.

W trakcie skanowania pobieramy z LK wszystkie krawędzie, których punkt początkowy (górny) ma współrzędną y równą współrzędnej y linii skanującej i wstawiamy je do LKA. Z kolei z LKA wyrzucamy wszystkie krawędzie, dla których punkt dolny ma współrzędną y równą współrzędnej y linii skanującej - te krawędzie zostały już przeskanowane i nie będą dalej potrzebne.

Wyznaczanie współrzędnej x punktu przecięcia krawędzi z linią skanującą

Kolejna optymalizacja dotyczy wyznaczania punktów przecięcia linii skanującej z krawędzią aktywną. Możemy oczywiście wykorzystać do tego celu wzory matematyczne:

Jeśli x₁ = x₂, to krawędź jest pionowa i zawsze mamy x = x₁.

Jeśli y = y₁, to linia skanująca osiągnęła pierwszy punkt krawędzi i x = x₁.

W pozostałych przypadkach wykorzystujemy prostą proporcję (z twierdzenia Talesa):

Jednakże takie podejście wymaga wykonywania dużej liczby obliczeń. A przecież możemy wykorzystać bardzo proste spostrzeżenie:

Jeśli pewna krawędź jest przecinana przez linię skanującą o współrzędnej y, to zapewne będzie również przecinana przez następną linię skanującą o współrzędnej (y + 1). Przy umieszczaniu krawędzi na liście LK wystarczy wyliczyć stały przyrost dx dla kolejnych wartości y linii skanującej:

Kolejną wartość współrzędnej x przecięcia linii skanującej z krawędzią otrzymamy ze wzoru:

Możemy teraz określić pożądaną postać danych dla elementów list LK i LKA:

Element listy LK powinien zawierać współrzędne y punktu początkowego i końcowego krawędzi oraz współrzędną x punktu początkowego i przyrost dx dla danej krawędzi (dx jako liczba zmiennoprzecinkowa).
Element listy LKA powinien zawierać współrzędną y punktu końcowego krawędzi, aktualną współrzędną x punktu przecięcia krawędzi z linią skanującą oraz przyrost dx (x i dx jako liczby zmiennoprzecinkowe, aby zminimalizować błędy zaokrągleń).

Ograniczanie listy krawędzi

Ostatnie usprawnienie dotyczy wybierania elementów list LK i LKA. Aby uniknąć przeglądania całej listy od początku do końca, elementy powinny być posortowane:

Lista LK jest posortowana rosnąco względem współrzędnych y punktów początkowych krawędzi - wtedy wybór elementów dla listy LKA sprowadza się do sprawdzania i przenoszenia początkowych elementów listy LK do LKA, jeśli współrzędna y linii skanującej jest równa współrzędnej y punktu początkowego krawędzi w LK.
Lista LKA jest posortowana rosnąco względem współrzędnych y punktów końcowych krawędzi - wtedy z listy LKA usuwamy początkowe elementy, o współrzędnej y punktu końcowego mniejszej od współrzędnej y linii skanującej - krawędzie już przeskanowane.

Sortowanie obu list może być wykonywane już na etapie wstawiania do nich nowych krawędzi. Od zastosowanego algorytmu sortującego zależy klasa złożoności operacji wypełniania wielokąta.

Wielokąt będzie rysowany w obszarze okna graficznego. Umówmy się, że ogólnie będziemy mówić o prostokącie obcinania (ang. clip rectangle), który definiuje wyświetlany obszar. Typowo prostokąt ten pokrywa całą powierzchnię okna graficznego, ale może pokrywać tylko część tego okna:

clip.x = 0
clip.y = 0
clip.w = W_W
clip.h = W_H

Listę LK można ograniczyć tylko do krawędzi, które wpadają w poziomy pas prostokąta obcinania (krawędzie zielone na poniższym rysunku):

Krawędzie przecinające brzeg pasu obcinania obcinamy do fragmentów leżących wewnątrz tego pasa:

Listę krawędzi LK można posortować w czasie O(n) algorytmem sortowania kubełkowego, który tutaj szczególnie się nadaje z uwagi na ograniczoną liczbę wartości współrzędnych y punktów początkowych krawędzi - szerokość pasa obcinania jest ograniczona wysokością w pionie powierzchni graficznej.

Pełny algorytm wypełniania wielokąta przez skanowanie liniami poziomymi

Wejście

F	-	lista łamanych, które definiują wielokąt. Łamane powinny tworzyć figurę zamkniętą.
color	-	kolor wypełnienia
clip	-	prostokąt obcinania.

Wyjście

Wypełnienie obszaru wewnątrz wielokąta pikselami o zadanym kolorze

Dane pomocnicze

x₁,x₂	-	współrzędne x punktów początkowego i końcowego krawędzi
y₁,y₁	-	współrzędne y punktów początkowego i końcowego krawędzi
y_min	-	minimalna wartość współrzędnych y punktów tworzących wielokąt
y_max	-	maksymalna wartość punktów tworzących wielokąt
LK	-	tablica kubełków o wartościach równych kolejnym współrzędnym od y_min do y_max. Każdy kubełek jest listą krawędzi, których górny punkt posiada współrzędną y równą wartości kubełka. Element E listy zawiera następujące dane: y - współrzędna y punktów początkowego i końcowego krawędzi x - współrzędna x punktu początkowego dx - przyrost x dla kolejnych y tej krawędzi
LKA	-	lista krawędzi aktywnych. Każdy element E zawiera: y - współrzędną y punktu końcowego x - aktualną współrzędną x punktu przecięcia z linią skanującą dx - przyrost x dla kolejnych y

Lista kroków

K01:	Utwórz tablicę pustych kubełków LK o rozmiarze równym wysokośc prostokąta obcinania clip	; pierwszy kubełek LK[0] odnosi się do y = clip.y
K02:	y_min ← clip.y + clip.h	; ustawiamy wartości początkowe zakresu y
K03:	y_max ← clip.y
K04:	Dopóki istnieją nieprzetworzone krawędzie w F, wykonuj kroki K05...K19	; przechodzimy przez kolejne krawędzie wielokąta
K05:	Wyznacz współrzędne punktu początkowego x₁,y₁ oraz punktu końcowego x₂,y₂krawędzi.
K07:	Jeśli (y₁ < clip.y) i (y₂ < clip.y), to przejdź do następnego obiegu pętli K04	; pomijamy krawędzie leżące pod pasem obcinania
K08:	Jeśli (y₁ ≥ clip.y + clip.h) i (y₂ ≥ clip.y + clip.h), to przejdź do następnego obiegu pętli K04	; oraz nad pasem obcinania
K09:	Twórz element listy E.
K10:	Jeśli y_min > y₁, to y_min ← y₁	; ustalamy wstępne minimum
K11:	Jeśli y_max < y₂, to y_max ← y₂	; i maksimum dla y
K12:	E.x ← x₁	; współrzędna początkowa x
K13:		; przyrost x dla kolejnych y
K14:	Jeśli y₁ ≥ clip.y, to przejdź do kroku K15	; sprawdzamy, czy krawędź rozpoczyna się pod pasem obcinania
K15:	E.x ← E.x + E.dx · (clip.y - y₁)	; jeśli tak, obliczamy dla niej nowy punkt startowy x
K16:	y₁ ← clip.y	; przesuwamy współrzędną y punktu początkowego krawędzi
K17:	Jeśli y₂ ≥ clip.y + clip.h, to y₂ ← clip.y + clip.h	; obcinamy krawędź wybiegającą poza pas obcinania
K18:	E.y ← y₂
K19:	Jeśli y₁ ≠ y₂, to wstaw E do kubełka LK[y₁ - clip.y]	; umieszczamy nie poziomą krawędź we właściwym kubełku
K20:	Utwórz pustą listę LKA
K21:	Jeśli y_min < clip.y, to y_min ← clip.y	; korygujemy zakres y
K22:	Jeśli y_max > clip.y + clip.h - 1, to y_max← clip.y + clip.h - 1
K23	Dla y = y_min,y_min+1,...,y_maxwykonuj kroki K24...K31	; przebiegamy zakres współrzędnych y linią skanującą
K24:	Usuń z listy LKA wszystkie krawędzie, dla których E.y = y	; usuwamy krawędzie przeskanowane
K25:	Jeśli kubełek LK[y - clip.y] jest pusty, to przejdź do kroku K28
K26:	Posortuj kubełek LK[y - clip.y] wg E.x.	; przenosimy krawędzie aktywne z LK do LKA
K27:	Scal zawartość kubełka LK[y - clip.y] z listą LKA	; przenosimy do LKA krawędzie, które osiągnęła linia skanująca
K28:	Połącz linią w kolorze color na wysokości y współrzędne x kolejnych par elementów listy LKA. Lewą współrzędną zaokrąglij w górę, prawą zaokrąglij w dół	; wypełniamy linią
K29:	Dla każdego elementu listy LKA oblicz nowe E.x ← E.x + E.dx	; wyznaczamy współrzędną punktu przecięcia dla y + 1
K30:	Posortuj listę LKA względem rosnących współrzędnych E.x jej elementów
K31:	Zakończ

Na podstawie tego algorytmu napiszemy funkcję SDL_RenderFillPoly(), która wypełnia dowolny wielokąt liniami poziomymi. Prześledź pilnie poniższy przykładowy program. Funkcja korzysta z obiektów STL.

C++

// Wypełnienia 7
//--------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <list>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

// Liczba wierzchołków wielokąta.
// Ostatni wierzchołek jest pierwszym, aby wielokąt był zamknięty
const int N = 30;

// Element list LK i LKA
typedef struct
{
  int y;
  double x, dx;
} LKElement;

// Prostokąt obcinania
SDL_Rect clip = {0,0,W_W,W_H};

// Funkcja służy do porównań elementów list LK i LKA
//--------------------------------------------------
bool CompareLKElements(LKElement a, LKElement b)
{
   return a.x < b.x;
}

// Funkcja wypełnia wielokąt liniami poziomymi.
// r - wskaźnik do struktury SDL_Renderer z kontekstem graficznym
// f - tablica punktów definiujących wierzchołki wielokąta
// n - liczba wierzchołków w tablicy (ostatni jest pierwszym)
//----------------------------------------------------------------
void SDL_RenderFillPoly(SDL_Renderer * r, SDL_Point * f, int n)
{
  list<LKElement> LK[clip.h];  // tablica kubełków
  list<LKElement> LKA;         // lista krawędzi aktywnych

  int y1clip = clip.y;              // współrzędna y początku pasa obcinania
  int y2clip = y1clip + clip.h - 1; // współrzędna y końca pasa obcinania
  int ymax   = y1clip;
  int ymin   = y2clip;
  int xp, xk, yp, yk, x1, x2, y1, y2, y, i;

  for(i = 0; i < n-1; i++)
  {
    xp = f[i].x;   yp = f[i].y;   // współrzędne początku krawędzi
    xk = f[i+1].x; yk = f[i+1].y; // współrzędne końca krawędzi
    if(yp > yk)
    {
      x1 = xk; y1 = yk; x2 = xp; y2 = yp;
    }
    else
    {
      x1 = xp; y1 = yp; x2 = xk; y2 = yk;
    }
    // Tworzymy element listy
    if(((y1 >= y1clip) || (y2 >= y1clip)) && ((y1 <= y2clip) || (y2 <= y2clip)))
    {
      LKElement E;
      if(ymin > y1) ymin = y1;
      if(ymax < y2) ymax = y2;
      E.x  = x1;
      E.dx = (x2 - x1) / (double)(y2 - y1);
      if(y1 < y1clip)
      {
        E.x += E.dx * (y1clip - y1);
        y1 = y1clip;
      }
      E.y = y2;
      // Element dodajemy do właściwego mu kubełka
      if(y1 != y2) LK[y1 - y1clip].push_front(E);
    }
  }

  if(ymin < y1clip) ymin = y1clip;
  if(ymax > y2clip) ymax = y2clip;

  for(y = ymin; y <= ymax; y++)
  {
    list<LKElement>::iterator i = LKA.begin();
    while(i != LKA.end()) if(i->y == y) i = LKA.erase(i); else i++;
    if(LK[y - y1clip].size())
    {
      LK[y - y1clip].sort(CompareLKElements);
      LKA.merge(LK[y - y1clip],CompareLKElements);
    }

    bool selector = false;

    for(list<LKElement>::iterator i = LKA.begin(); i != LKA.end(); i++)
    {
      if(selector)
      {
        x2 = (int)floor(i->x);
        SDL_RenderDrawLine(r,x1,y,x2,y);
      }
      else x1 = (int)ceil(i->x);
      selector = !selector;
      i->x += i->dx;
    }
    LKA.sort(CompareLKElements);
  }
  LKA.clear();
}

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Obszary", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy kontekst graficzny
  SDL_Renderer * r = SDL_CreateRenderer(w,0,SDL_RENDERER_PRESENTVSYNC);
  if(!r)
  {
     cout << "SDL_CreateRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Zmienne
  SDL_Point P[N];    // Wielokąt
  int cr,cg,cb,dr,dg,db,dx[N-1],dy[N-1];
  int i;

  // Generujemy wierzchołki
  for(i = N - 2; i >= 0; i--)
  {
    P[i].x = rand() % W_W;
    P[i].y = rand() % W_H;;
  }

  P[N-1] = P[0];

  // Przesunięcia
  for(i = N - 2; i >= 0; i--)
  {
    do dx[i] = -3 + rand() % 7; while(!dx[i]);
    do dy[i] = -3 + rand() % 7; while(!dy[i]);
  }

  // Kolory
  cr = rand() % 256;
  cg = rand() % 256;
  cb = rand() % 256;
  do dr = -3 + rand() % 7; while(!dr);
  do dg = -3 + rand() % 7; while(!dg);
  do db = -3 + rand() % 7; while(!db);

  // Animacja
  SDL_Event event;
  while(1)
  {
    // Usuwamy treść poprzedniego okna
    SDL_SetRenderDrawColor(r,0,0,0,255);
    SDL_RenderClear(r);

    // Rysujemy wielokąt
    SDL_SetRenderDrawColor(r,cr,cg,cb,255);
    SDL_RenderFillPoly(r,P,N);

    // Rysujemy obrys wielokata
    SDL_SetRenderDrawColor(r,255,255,255,255);
    SDL_RenderDrawLines(r,P,N);

    // Modyfikujemy współrzędne
    for(i = N - 2; i >= 0 ; i--)
    {
      if((P[i].x + dx[i] < 0) || (P[i].x + dx[i] >= W_W)) dx[i] = - dx[i];
      P[i].x += dx[i];
      if((P[i].y + dy[i] < 0) || (P[i].y + dy[i] >= W_H)) dy[i] = - dy[i];
      P[i].y += dy[i];
    }
    P[N-1] = P[0];

    // Modyfikujemy kolory
    if((cr + dr < 0) || (cr + dr > 255)) dr = - dr;
    if((cg + dg < 0) || (cg + dg > 255)) dg = - dg;
    if((cb + db < 0) || (cb + db > 255)) db = - db;
    cr += dr;
    cg += dg;
    cb += db;

    // Uaktualniamy treść okna na ekranie
    SDL_RenderPresent(r);

    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Na początek: podrozdziału strony

Do wypełniania kół wykorzystamy opisany już wcześniej algorytm Bresenhama – znajdujemy początki i końce linii poziomych, które sukcesywnie zamalowują wnętrze koła. Wykorzystujemy przy tym symetrię koła:

Linie zewnętrzne górne i dolne rysujemy tuż przed zmianą współrzędnej y - linie wypełniające koło przebiegają następująco:
– górna od (-x,y) do (x,y)
– dolna od (-x,-y) d0 (x -y)
Linie wewnętrzne górne i dolne rysujemy tuż przed zmianą współrzędnej x:
– górna od (-y,x) do (y,x)
– dolna od (-y,-x) do (y,-x)
Linię dolną rysujemy tylko dla x > 0. Obie linie wewnętrzne rysujemy tylko dla x ≠ y. W przeciwnym razie linie wewnętrzne byłyby rysowane po narysowanych liniach zewnętrznych. Do wyliczonych w ten sposób współrzędnych linii należy dodać współrzędne środka okręgu, aby otrzymać ich współrzędne ekranowe.

Algorytm w postaci listy kroków wygląda następująco:

Wejście

x_s, y_s	-	współrzędne środka okręgu
r	-	promień okręgu

Wyjście

Narysowanie na powierzchni graficznej wypełnionego koła o środku w punkcie (x_s, y_s), o promieniu r i w kolorze color

Dane pomocnicze

x, y	-	współrzędne punktów na obwodzie okręgu o środku w początku układu współrzędnych
e	-	wyrażenie błędu dla narysowanego punktu P = (x, y.)
e₁	-	wyrażenie błędu dla punktu P₁ = (x + 1, y)
e₂	-	wyrażenie błędu dla punktu P₂ = (x + 1, y - 1)

Lista kroków

K01:	x ← 0	; ustalamy współrzędne punktu startowego
K02:	y ← r
K03:	e ← 0	; wstępne wyrażenie błędu
K04:	Dopóki x ≤ y, wykonuj kroki K05...K15
K05:	Rysuj linię od (-y+x_s,x+y_s) do (y+x_s,x+y_s)	; linia wewnętrzna górna
K06:	Rysuj linię od (-y+x_s,-x+y_s) do (y+x_s,-x+y_s)	; linia wewnętrzna dolna
K07:	e₁ ← e + 2x + 1	; wyliczamy wyrażenie błędu dla P₁
K08:	e₂ ← e₁ - 2y + 1	; wyliczamy wyrażenie błędu dla P₂
K09:	Jeśli e₁ + e₂ < 0, to idź do kroku K14
K10:	Rysuj linię od (-x+x_s,y+y_s) do (x+x_s,y+y_s)	; rysujemy linię zewnętrzną górną
K11:	Rysuj linię od (-x,+x_s-y+y_s) do (x+x_s,-y+y_s)	; oraz zewnętrzną dolną
K12:	y ← y - 1	; współrzędną y zmniejszamy tylko wtedy, gdy suma e₁ i e₂ jest nieujemna
K13:	e ← e₂ i idź do kroku K15	; za nowe e przyjmujemy e₂ dla P₂
K14:	e ← e₁	; za nowe e przyjmujemy e₁ dla P₁
K15:	x ← x + 1	; x musimy zwiększać na końcu, aby linie zewnętrzne były rysowane prawidłowo
K16:	Zakończ

Poniższy program animuje koło wypełniane powyższym algorytmem

C++

// Wypełnienia 8
//--------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

// Funkcja rysuje wypełnione koło
// r - wskaźnik kontekstu graficznego
// xs,ys - współrzędne środka koła
// rs - promień koła
//-------------------------------
void SDL_RenderFillCircle(SDL_Renderer * r, int xs, int ys, int rs)
{
  int x,y,e,e1,e2;

  e = x = 0;
  y = rs;
  while (x <= y)
  {
    SDL_RenderDrawLine(r,-y+xs,x+ys,y+xs,x+ys);
    SDL_RenderDrawLine(r,-y+xs,-x+ys,y+xs,-x+ys);
    e1 = e + 2 * x + 1;
    e2 = e1 - 2 * y + 1;
    if(e1 + e2 < 0) e = e1;
    else
    {
      SDL_RenderDrawLine(r,-x+xs,y+ys,x+xs,y+ys);
      SDL_RenderDrawLine(r,-x+xs,-y+ys,x+xs,-y+ys);
      y--;
      e = e2;
    }
    x++;
  }
}

// Funkcja rysuje okrąg algorytmem Bresenhama
//-------------------------------------------
void SDL_RenderCircle(SDL_Renderer * r, int xs, int ys, int rs)
{
  int x,y,e,e1,e2;
  SDL_Point P[8];

  // Inicjujemy zmienne
  e = x = 0;
  y = rs;

  while(x <= y)
  {
      // Rysujemy 8 pikseli
      P[0].x =  x + xs; P[0].y =  y + ys;
      P[1].x =  y + xs; P[1].y = -x + ys;
      P[2].x = -x + xs; P[2].y = -y + ys;
      P[3].x = -y + xs; P[3].y =  x + ys;
      P[4].x =  y + xs; P[4].y =  x + ys;
      P[5].x =  x + xs; P[5].y = -y + ys;
      P[6].x = -y + xs; P[6].y = -x + ys;
      P[7].x = -x + xs; P[7].y =  y + ys;
      SDL_RenderDrawPoints(r,P,8);

      // Obliczamy wyrażenia błędów
      e1 = e + 2 * x + 1;
      e2 = e1 - 2 * y + 1;

      x++; // krok w osi x
      if(e1 + e2 < 0) e = e1;
      else
      {
        y--; // krok w osi y
        e = e2;
      }
  }
}

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Obszary", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy kontekst graficzny
  SDL_Renderer * r = SDL_CreateRenderer(w,0,SDL_RENDERER_PRESENTVSYNC);
  if(!r)
  {
     cout << "SDL_CreateRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Zmienne
  int xs,ys,rr,dx,dy,cr,cg,cb,dr,dg,db;

  // Losujemy położenie koła i parametry ruchu
  rr = 30 + rand() % (W_H / 3);
  xs = W_W / 2;
  ys = W_H / 2;
  do dx = -2 + rand() % 5; while(!dx);
  do dy = -2 + rand() % 5; while(!dy);

  // Kolory
  cr = rand() % 256;
  cg = rand() % 256;
  cb = rand() % 256;
  do dr = -3 + rand() % 7; while(!dr);
  do dg = -3 + rand() % 7; while(!dg);
  do db = -3 + rand() % 7; while(!db);

  // Animacja
  SDL_Event event;
  while(1)
  {
    // Usuwamy treść poprzedniego okna
    SDL_SetRenderDrawColor(r,0,0,0,255);
    SDL_RenderClear(r);

    // Rysujemy wypełnione koło
    SDL_SetRenderDrawColor(r,cr,cg,cb,255);
    SDL_RenderFillCircle(r,xs,ys,rr);

    // Rysujemy okrąg
    SDL_SetRenderDrawColor(r,255,255,255,255);
    SDL_RenderCircle(r,xs,ys,rr);

    // Modyfikujemy współrzędne
    if((xs - rr + dx < 0) || (xs + rr + dx >= W_W)) dx = - dx;
    if((ys - rr + dy < 0) || (ys + rr + dy >= W_H)) dy = - dy;
    xs += dx;
    ys += dy;

    // Modyfikujemy kolory
    if((cr + dr < 0) || (cr + dr > 255)) dr = - dr;
    if((cg + dg < 0) || (cg + dg > 255)) dg = - dg;
    if((cb + db < 0) || (cb + db > 255)) db = - db;
    cr += dr;
    cg += dg;
    cb += db;

    // Uaktualniamy treść okna na ekranie
    SDL_RenderPresent(r);

    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Na początek: podrozdziału strony

Podobnie jak dla kół, tutaj również wykorzystamy opisany wcześniej algorytm Bresenhama. Zasada jest bardzo prosta - wyznaczamy kolejne punkty obrysu elipsy aż do momentu wykrycia zmiany współrzędnej y - wtedy współrzędna x wyznacza końce linii wypełniającej elipsę i możemy ją w prosty sposób narysować. Linie wypełniające rysujemy zawsze parami - w symetrii względem osi OX.

Wejście

x_s, y_s	-	współrzędne środka owalu
r_x	-	promień owalu na osi OX
r_y	-	promień owalu na osi OY

Wyjście

Narysowanie na powierzchni graficznej owalu o środku w punkcie (x_s, y_s), o promieniach r_x, r_y

Dane pomocnicze

x, y	-	współrzędne punktów na obwodzie okręgu o środku w początku układu współrzędnych
e	-	wyrażenie błędu dla punktu P
e₁	-	wyrażenie błędu dla punktu P₁
e₂	-	wyrażenie błędu dla punktu P₂

Lista kroków

K01:	x ← 0	; ustalamy współrzędne punktu startowego
K02:	y ← r_y
K03:	e ← 0
K04:	Dopóki r_y²x ≤ r_x²y wykonuj kroki K05...K13	; górna część ćwiartki elipsy
K05:	e₁ ← e + 2r_y²x + r_y²	; wyrażenie błędu dla P₁(x+1,y)
K06:	e₂ ← e₁ - 2r_x²y + r_x²	; wyrażenie błędu dla P₂(x+1,y-1)
K07:	Jeśli e₁ + e₂ < 0, to idź do kroku K12
K08:	Rysuj linię od (-x+x_s,y+y_s) do (x+x_s,y+y_s)	; rysujemy linie wypełniające
K09:	Rysuj linię od (-x+x_s,-y+y_s) do (x+x_s,-y+y_s)
K10:	e ← e₂	; wybieramy P₂(x+1,y-1)
K11:	y ← y - 1 i idź do kroku K13
K12:	e ← e₁	; wybieramy P₁(x+1,y)
K13:	x ← x + 1	; w górnej części ćwiartki x zawsze jest zwiększane o 1
K14:	Dopóki y ≥ 0 wykonuj kroki K15...K23	; przechodzimy do dolnej części ćwiartki
K15:	Rysuj linię od (-x+x_s,y+y_s) do (x+x_s.y+y_s)	; rysujemy linie wypełniające
K16:	Rysuj linię od (-x+x_s,-y+y_s) do (x+x_s.-y+y_s)
K17:	e₁ ← e - 2r_x²y + r_x²	; wyrażenie błędu dla P₁(x,y-1)
K18:	e₂ ← e₁ + 2r_y²x + r_y²	; wyrażenie błędu dla P₂(x+1,y-1)
K19:	y ← y - 1	; w dolnej części ćwiartki y zawsze jest zmniejszane o 1
K20:	Jeśli e₁ + e₂ ≥ 0, to idź do kroku K23
K21:	e ← e₂	; wybieramy punkt P₂(x+1,y-1)
K22:	x ← x + 1 i kontynuuj następny obieg pętli K14
K23:	e ← e₁	; wybieramy P₁(x,y-1)
K24:	Zakończ

C++

// Wypełnienia 9
//--------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

// Funkcja rysuje elipsę algorytmem Bresenhama
//-------------------------------------------
void SDL_RenderEllipse(SDL_Renderer * r, int xs, int ys, int rx, int ry)
{
  int x,y,e,e1,e2,rx2,ry2,fx,fy;
  SDL_Point P[4];

  // Inicjujemy punkt startowy
  x = e = 0;
  y = ry;
  rx2 = rx * rx;
  ry2 = ry * ry;
  fx = 0;
  fy = rx2 * ry;

  while(fx <= fy)
  {
    // Rysujemy górne punkty ćwiartki
    P[0].x = x + xs;  P[0].y = y + ys;
    P[1].x = x + xs;  P[1].y = -y + ys;
    P[2].x = -x + xs; P[2].y = y + ys;
    P[3].x = -x + xs; P[3].y = -y + ys;
    SDL_RenderDrawPoints(r,P,4);

    // Wyliczamy wyrażenia błędów
    e1 = e  + (fx << 1) + ry2;
    e2 = e1 - (fy << 1) + rx2;

    fx += ry2;

    // W górnej części ćwiartki x jest zawsze zwiększane
    x++;

    if(e1 + e2 < 0) e = e1; // Punkt P1
    else
    {
        y--;
        fy -= rx2;
        e = e2;             // Punkt P2
    }
  }

  // Teraz dolna część ćwiartki

  while(y >= 0)
  {
    // Rysujemy dolne punkty ćwiartki
    P[0].x = x + xs;  P[0].y = y + ys;
    P[1].x = x + xs;  P[1].y = -y + ys;
    P[2].x = -x + xs; P[2].y = y + ys;
    P[3].x = -x + xs; P[3].y = -y + ys;
    SDL_RenderDrawPoints(r,P,4);

    // Wyliczamy wyrażenia błędów
    e1 = e  - (fy << 1) + rx2;
    e2 = e1 + (fx << 1) + ry2;

    fy -= rx2;

    // W dolnej części ćwiartki y jest zawsze zmniejszane
    y--;

    if(e1 + e2 >= 0) e = e1; // Punkt P1
    else
    {
      x++;
      fx += ry2;
      e = e2;                // Punkt P2
    }
  }
}

// Funkcja rysuje wypełnioną elipsę algorytmem Bresenhama
//-------------------------------------------------------
void SDL_RenderFillEllipse(SDL_Renderer * r, int xs, int ys, int rx, int ry)
{
  int x,y,e,e1,e2,rx2,ry2,fx,fy;

  // Inicjujemy punkt startowy
  x = e = 0;
  y = ry;
  rx2 = rx * rx;
  ry2 = ry * ry;
  fx = 0;
  fy = rx2 * ry;

  while(fx <= fy)
  {
    // Wyliczamy wyrażenia błędów
    e1 = e  + (fx << 1) + ry2;
    e2 = e1 - (fy << 1) + rx2;

    fx += ry2;

    // W górnej części ćwiartki x jest zawsze zwiększane
    x++;

    if(e1 + e2 < 0) e = e1; // Punkt P1
    else
    {
      SDL_RenderDrawLine(r,-x+xs,y+ys,x+xs,y+ys);
      SDL_RenderDrawLine(r,-x+xs,-y+ys,x+xs,-y+ys);
      y--;
      fy -= rx2;
      e = e2;             // Punkt P2
    }
  }

  // Teraz dolna część ćwiartki

  while(y >= 0)
  {
    SDL_RenderDrawLine(r,-x+xs,y+ys,x+xs,y+ys);
    SDL_RenderDrawLine(r,-x+xs,-y+ys,x+xs,-y+ys);

    // Wyliczamy wyrażenia błędów
    e1 = e  - (fy << 1) + rx2;
    e2 = e1 + (fx << 1) + ry2;

    fy -= rx2;

    // W dolnej części ćwiartki y jest zawsze zmniejszane
    y--;

    if(e1 + e2 >= 0) e = e1; // Punkt P1
    else
    {
      x++;
      fx += ry2;
      e = e2;                // Punkt P2
    }
  }
}

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Obszary", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy kontekst graficzny
  SDL_Renderer * r = SDL_CreateRenderer(w,0,SDL_RENDERER_PRESENTVSYNC);
  if(!r)
  {
     cout << "SDL_CreateRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  // Inicjujemy generator pseudolosowy
  srand(time(NULL));

  // Zmienne
  int xs,ys,rx,ry,dx,dy,cr,cg,cb,dr,dg,db;

  // Losujemy położenie koła i parametry ruchu
  rx = 30 + rand() % (W_W / 3);
  ry = 30 + rand() % (W_H / 3);
  xs = W_W / 2;
  ys = W_H / 2;
  do dx = -2 + rand() % 5; while(!dx);
  do dy = -2 + rand() % 5; while(!dy);

  // Kolory
  cr = rand() % 256;
  cg = rand() % 256;
  cb = rand() % 256;
  do dr = -3 + rand() % 7; while(!dr);
  do dg = -3 + rand() % 7; while(!dg);
  do db = -3 + rand() % 7; while(!db);

  // Animacja
  SDL_Event event;
  while(1)
  {
    // Usuwamy treść poprzedniego okna
    SDL_SetRenderDrawColor(r,0,0,0,255);
    SDL_RenderClear(r);

    // Rysujemy wypełnioną elipsę
    SDL_SetRenderDrawColor(r,cr,cg,cb,255);
    SDL_RenderFillEllipse(r,xs,ys,rx,ry);

    // Rysujemy elipsę
    SDL_SetRenderDrawColor(r,255,255,255,255);
    SDL_RenderEllipse(r,xs,ys,rx,ry);

    // Modyfikujemy współrzędne
    if((xs - rx + dx < 0) || (xs + rx + dx >= W_W)) dx = - dx;
    if((ys - ry + dy < 0) || (ys + ry + dy >= W_H)) dy = - dy;
    xs += dx;
    ys += dy;

    // Modyfikujemy kolory
    if((cr + dr < 0) || (cr + dr > 255)) dr = - dr;
    if((cg + dg < 0) || (cg + dg > 255)) dg = - dg;
    if((cb + db < 0) || (cb + db > 255)) db = - db;
    cr += dr;
    cg += dg;
    cb += db;

    // Uaktualniamy treść okna na ekranie
    SDL_RenderPresent(r);

    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Wypełnianie figur

Wypełnianie prostokątów

Wypełnianie trójkątów

Trójkąt płaski u spodu

Trójkąt płaski u góry

Dowolny trójkąt

Podsumujmy:

Algorytm Bresenhama do wypełniania trójkąta

Wypełnianie wielokątów wypukłych

Wypełnianie wielokątów dowolnych

Krawędź pozioma

Linia skanująca przecina wierzchołek wielokąta

Podział krawędzi

Wyznaczanie współrzędnej x punktu przecięcia krawędzi z linią skanującą

Ograniczanie listy krawędzi

Pełny algorytm wypełniania wielokąta przez skanowanie liniami poziomymi

Wejście

Wyjście

Dane pomocnicze

Lista kroków

Wypełnianie kół

Wejście

Wyjście

Dane pomocnicze

Lista kroków

Wypełnianie Elips

Wejście

Wyjście

Dane pomocnicze

Lista kroków