Serwis Edukacyjny
Nauczycieli
w I-LO w Tarnowie

Do strony głównej I LO w Tarnowie

Materiały dla uczniów liceum

  Wyjście       Spis treści       Poprzedni       Następny  

©2019 mgr Jerzy Wałaszek
I LO w Tarnowie

logo

Autor artykułu: mgr Jerzy Wałaszek

 

 

SDL2

Wypełnianie figur

Rozdziały:
    Instalacja
    Typy danych
    Grafika rastrowa
    Okno
    Kontekst graficzny
    Punkty
    Odcinki
    Figury
    Algorytm Bresenhama
    Wypełnianie figur
    Wypełnianie obszarów
    Wypełnianie obszarów algorytmem Smitha
    Przezroczystość
    Zdarzenia

     Interfejs SDL2 wg nazw
     Interfejs SDL2 wg kategorii
W rozdziale:
Wypełnianie prostokątów
Wypełnianie trójkątów
Wypełnianie wielokątów wypukłych
Wypełnianie wielokątów dowolnych
Wypełnianie kół
Wypełnianie elips

 

Wypełnianie prostokątów

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():

 

// 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:

 

// 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;
}

 

 

Wypełnianie trójkątów

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 (x1,y1)‒(x1,y1). Po narysowaniu każdej linii współrzędne y zwiększamy o 1, a współrzędne x modyfikujemy o wartość sL (punkt startowy) i sR (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:

 

// 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 (x2,y2)‒(x2,y3). Współrzędne x są odpowiednio zwiększane o przyrosty sL i sP. Współrzędne y są zwiększane od y2 do y1.

 

// 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 P4. Korzystamy tutaj z twierdzenia Talesa i układamy odpowiednią proporcję:

Współrzędna y4 jest taka sama jak współrzędna y2. Wystarczy zatem policzyć tylko współrzędną x4:

Podsumujmy:

Mamy współrzędne trzech punktów P1, P2 i P3, 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 y1.

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 P4:

Rysujemy linie poziome pierwszego trójkąta o płaskim spodzie (P1, P2, P4) od y1 do y2 - 1 (aby uniknąć podwójnego rysowania ostatniej linii). Następnie rysujemy trójkąt o płaskiej górze (P2, P4, P3) od y2 do y3.

Poniższy program pokazuje, jak to zrobić:

 
// 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 P1, P2 i P3:

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

Jeśli y1 = y3, to trójkąt sprowadza się do linii poziomej leżącej na wysokości y1 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 y1 = y2, to trójkąt jest płaski u góry:

 

Rysujemy linię poziomą na wysokości y1 od x1 do x2.

Uruchamiamy algorytm Bresenhama dla obu odcinków P1-P3 i P2-P3. 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ć (y3 - y1 - 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 P4. Rozpoczynamy od postawienia punktu w wierzchołku P1. Następnie uruchamiamy algorytm Bresenhama dla odcinków P1-P2 oraz P1-P3. 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 P2. Uruchamiamy ponownie algorytm Bresenhama od punktu P2 do P3 (linia od P1 do P3 jest kontynuowana z poprzedniego kroku). Rysujemy kolejne linie poziome. Kończymy po osiągnięciu punktu P3.

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.

 
// 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;
}

 

 

Wypełnianie wielokątów wypukłych

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 P1 (dla wygody, w rzeczywistości można wybrać dowolny z wierzchołków wielokąta):

Następnie wybieramy dwa następne wierzchołki P2 i P3. 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 P1, z ostatnio wybranego i z kolejnego na obwodzie wielokąta. Dla przykładowego wielokąta otrzymamy w ten sposób trójkąty:

Δ(P1,P2,P3), Δ(P1,P3,P4), Δ(P1,P4,P5), Δ(P1,P5,P6):

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 P1 do P2):

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 P2, 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:

 
// 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; }

 

 

Wypełnianie wielokątów dowolnych

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:

 

// 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:

 

// 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.

 

// 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:

 

// 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ą:

 

// 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 yi rosnących od ymin do ymax, gdzie ymin i ymax 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: x1, x2, x3 i x4. 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 ymin i ymax
K03: Dla y = ymin, ymin+1,...,ymax wykonuj 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 x1 i x2 o równej wartości. Jak widać nie stanowi to problemu Linia pozioma od x1 do x2 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 x4 i x5. To również nie stanowi problemu. Linie poziome x3-x4 oraz x5-x6 są prawidłowe.

Trzeci wierzchołek wprowadza problem - otrzymamy dwie współrzędne x6 i x7. Algorytm narysuje złą linię od x7 do x8. Nie narysuje za to właściwej linii od x8 do x9.  I dodatkowo zostanie współrzędna x9, 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, pomiń ją i przejdź do następnej krawędzi
K03:     Dodaj krawędź do listy krawędzi
K04: Na podstawie listy krawędzi wyznacz ymin i ymax
K05: Dla y = ymin, ymin+1,...,ymax wykonuj 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 x1 = x2, to krawędź jest pionowa i zawsze mamy x = x1.

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

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

x1,x2  -  współrzędne x punktów początkowego i końcowego krawędzi
y1,y1  - współrzędne y punktów początkowego i końcowego krawędzi
ymin  - minimalna wartość współrzędnych y punktów tworzących wielokąt
ymax  - maksymalna wartość punktów tworzących wielokąt
LK  -  tablica kubełków o wartościach równych kolejnym współrzędnym od ymin do ymax.
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ści prostokąta obcinania clip ; pierwszy kubełek LK[0] odnosi się do y = clip.y
K02: ymin ← clip.y + clip.h ; ustawiamy wartości początkowe zakresu y
K03: ymax ← 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 x1,y1 oraz końcowego x2,y2 krawędzi.  
K07:     Jeśli (y1 < clip.y) i (y2 < clip.y), przejdź do następnego obiegu pętli K04 ; pomijamy krawędzie leżące pod pasem obcinania
K08:     Jeśli (y1 ≥ clip.y + clip.h) i (y2 ≥ clip.y + clip.h), przejdź do następnego obiegu pętli K04 ; oraz nad pasem obcinania
K09:     Twórz element listy E.  
K10:     Jeśli ymin > y1, to ymin ← y1 ; ustalamy wstępne minimum
K11:     Jeśli ymax < y2, to ymax ← y2 ; i maksimum dla y
K12:     E.x ← x1 ; współrzędna początkowa x
K13:
    E.dx ←   x2 - x1
y2 - y1
; przyrost x dla kolejnych y
K14:     Jeśli y1 ≥ clip.y, przejdź do kroku K15 ; sprawdzamy, czy krawędź rozpoczyna się pod pasem obcinania
K15:     E.x ← E.x + E.dx • (clip.y - y1) ; jeśli tak, obliczamy dla niej nowy punkt startowy x
K16:     y1 ← clip.y ; przesuwamy współrzędną y punktu początkowego krawędzi
K17:     Jeśli y2 ≥ clip.y + clip.h, to y2 ← clip.y + clip.h ; obcinamy krawędź wybiegającą poza pas obcinania
K18:     E.y ← y2  
K19:     Jeśli y1 ≠ y2, wstaw E do kubełka LK[y1 - clip.y] ; umieszczamy nie poziomą krawędź we właściwym kubełku
K20: Utwórz pustą listę LKA  
K21: Jeśli ymin < clip.y, to ymin ← clip.y ; korygujemy zakres y
K22: Jeśli ymax > clip.y + clip.h - 1, ymax ← clip.y + clip.h - 1  
K23 Dla y = ymin,ymin+1,...,ymax wykonuj 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, 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.

 

// 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;
}

 

 

Wypełnianie kół

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

xs, ys  -  współrzędne środka okręgu
r  - promień okręgu

Wyjście

Narysowanie na powierzchni graficznej wypełnionego koła o środku w punkcie (xs, ys), 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.)
e1  - wyrażenie błędu dla punktu P1 = (x + 1, y)
e2  - wyrażenie błędu dla punktu P2 = (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+xs,x+ys) do (y+xs,x+ys) ; linia wewnętrzna górna
K06:     Rysuj linię od (-y+xs,-x+ys) do (y+xs,-x+ys) ; linia wewnętrzna dolna
K07:     e1 ← e + 2x + 1 ; wyliczamy wyrażenie błędu dla P1
K08:     e2 ← e1 - 2y + 1 ; wyliczamy wyrażenie błędu dla P2
K09:     Jeśli e1 + e2 < 0, idź do kroku K14  
K10:     Rysuj linię od (-x+xs,y+ys) do (x+xs,y+ys) ; rysujemy linię zewnętrzną górną
K11:     Rysuj linię od (-x,+xs-y+ys) do (x+xs,-y+ys) ; oraz zewnętrzną dolną
K12:     y ← y - 1 ; współrzędną y zmniejszamy tylko wtedy, gdy suma e1 i e2 jest nieujemna
K13:     e ← e2 i idź do kroku K15 ; za nowe e przyjmujemy e2 dla P2
K14:     e ← e1 ; za nowe e przyjmujemy e1 dla P1
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

 
// 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;
}

 

 

Wypełnianie Elips

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

xs, ys  -  współrzędne środka owalu
rx  - promień owalu na osi OX
ry  - promień owalu na osi OY

Wyjście

Narysowanie na powierzchni graficznej owalu o środku w punkcie (xs, ys), o promieniach rx, ry

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
e1  - wyrażenie błędu dla punktu P1
e2  - wyrażenie błędu dla punktu P2

Lista kroków

K01: x ← 0 ; ustalamy współrzędne punktu startowego
K02: y ← ry  
K03: e ← 0  
K04: Dopóki ry2x ≤ rx2y wykonuj kroki K05...K13 ; górna część ćwiartki elipsy
K05:     e1 ← e + 2ry2x + ry2 ; wyrażenie błędu dla P1(x+1,y)
K06:     e2 ← e1 - 2rx2y + rx2 ; wyrażenie błędu dla P2(x+1,y-1)
K07:     Jeśli e1 + e2 < 0, idź do kroku K12  
K08:     Rysuj linię od (-x+xs,y+ys) do (x+xs,y+ys) ; rysujemy linie wypełniające
K09:     Rysuj linię od (-x+xs,-y+ys) do (x+xs,-y+ys)  
K10:     e ← e2 ; wybieramy P2(x+1,y-1)
K11:     y ← y - 1 i idź do K13  
K12:     e ← e1 ; wybieramy P1(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+xs,y+ys) do (x+xs.y+ys) ; rysujemy linie wypełniające
K16:     Rysuj linię od (-x+xs,-y+ys) do (x+xs.-y+ys)  
K17:     e1 ← e - 2rx2y + rx2 ; wyrażenie błędu dla P1(x,y-1)
K18:     e2 ← e1 + 2ry2x + ry2 ; wyrażenie błędu dla P2(x+1,y-1)
K19:     y ← y - 1 ; w dolnej części ćwiartki y zawsze jest zmniejszane o 1
K20:     Jeśli e1 + e2 ≥ 0, idź do kroku K23  
K21:     e ← e2 ; wybieramy punkt P2(x+1,y-1)
K22:     x ← x + 1 i kontynuuj następny obieg pętli K14  
K23:     e ← e1 ; wybieramy P1(x,y-1)
K24: Zakończ

 

// 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;
}

 

 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2019 mgr Jerzy Wałaszek

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.