Úsečka

mapa stránky tlačiť stránku slovensky | english

Úsečka

$$$APPLET

Applet Úsečka medzi koncovými bodmi (x1,y1) a (x2,y2)

Úsečka patrí medzi základné grafické prvky. Kým v analytickej geometrii obsahuje úsečka nekonečne veľa bodov, na rastrovom monitore sa skladá z konečného počtu bodov. Napriek tomu, že je pomerne jednoduchá, jej konštrukcii sa väčšinou venuje veľká pozornosť. Pomocou úsečiek sa totiž vykresľujú zložitejšie grafické objekty, a preto je našou snahou vykresľovať úsečku čo najefektívnejšie.

Najčastejšie sa úsečka zadáva pomocou svojich koncových bodov [x1,y1] a [x2,y2], prípadne jedným bodom [x1,y1] a vektorom rozdielov súradníc [dx, dy] = [x2-x1, y2-y1].

Analytické vyjadrenie priamky, ktorá nie je rovnobežná s osou y, vyjadrujeme v tvare

y = m x + q (m, q ∈ R)

kde m je smernica priamky a q je posun na osi y(tj. ak x = 0 tak dostaneme rovnicu y = q). Koncové body úsečky [x1,y1] a [x2,y2] určujú priamku s parametrami m a q:

(y2-y1) (x2y1-x1y2) m = ---------- a q = ---------------- (x2-x1) (x2-x1)

Rastrový rozklad úsečky

Rastrový rozklad úsečky je založený na vzorkovaní s konštantným krokom podľa osi x alebo y. Závisí to od sklonu úsečky, reprezentovaného smernicou m.

$$$APPLET

Applet Hodnota smernice m pre rôzne sklony úsečky

Ak je |m|<1, tak úsečka má sklon k osi x menší ako 45 stupňov, a preto vzorkujeme podľa osi x s krokom 1 pixel. Pokiaľ je |m|>1, vzorkujeme podľa osi y. Úsečku so smernicou 1 nazývame diagonálnou a vzorkujeme ju ľubovoľnou z osí. Os, podľa ktorej vzorkujeme nazývame riadiacou (hlavnou) osou. Druhú os nazveme vedľajšou osou.

Jednoduchý prírastkový algoritmus

Jednoduchý prírastkový algoritmus je známy aj ako DDA (Digital Differential Analyzer) algoritmus. Tento algoritmus je založený na pravidelnom prírastku dx pre súradnicu x a dy pre súradnicu y, pričom začína v začiatočnom bode úsečky. Vzhľadom k tomu, že vzorkujeme v rastri, býva prírastok na riadiacej osi (v prípade, že úsečka má sklon bližšie k osi x je riadiaca os x ) rovný hodnote 1 (jednému bodu).

$$$APPLET

Applet Prírastok pre x a y súradnicu

Postup je nasledovný. V jednom cykle budeme postupne pripočítavať k súradnici na hlavnej osi jednotku a k súradnici na vedľajšej osi vypočítaný prírastok. Ten má v prípade, že hlavnou osou je x-ová, hodnotu smernice m, v prípade y-ovej osi 1/m. Tieto hodnoty sú reálne a pri vykresľovaní ich zaokrúhľujeme. DDA algoritmus pri výpočte nových súradníc využíva hodnoty predchádzajúceho bodu.

$$$APPLET

Applet Kreslenie čiary z ľavého horného bodu, zvoľ druhý koncový bod,
klávesy 1,2 - zväčšovanie a zmenšovanie veľkosti rastra

Prírastkový algoritmus DDA úsečky [4].

// nakresli úsečku z bodu x1,y1 do x2,y2 
 rasterline(int x1, int y1, int x2, int y2) 
 {

// ak je bod x1, y1 napravo od bodu x2,y2 tak ich vymeň 
     if (x1 > x2) { rasterline(x2, y2, x1, y1); return; }

double y = y1;  // prírastok 
     double m = (double)(y2 - y1) / (x2 - x1);  // smernica

//  ak má m menší sklon ako 45 stupňov k osi x tak riadiaca os je x-ová 
     if (Math.abs(m) <= 1)  
      {  
         for (int i = x1; i <= x2; i++)  
          { 
             // funkcia Math.round(y) zaokrúhli číslo y               
             setpix(i, (int) Math.round(y) ); // zobraz bod na danú súradnicu 
             y += m;  // pripočítaj prírastok 
          } 
       } 
      else        
	{  
	  // inak použi nasledujúcu procedúru, kde riadiaca os bude y 
          rastersteepline(yi, xi, yf, xf);  
       } 
 }

public void rastersteepline(int x3, int y3, int x4, int y4)  
  {

// ak je bod x3, y3 napravo od bodu x4,y4 tak ich vymeň 
     if (x3 > x4) { rastersteepline(x4, y4, x3, y3); return; }

double y = y3; // prírastok 
     double m = (double)(y4 - y3) / (x4 - x3);  // smernica

for (int i = x3; i <= x4; i++)  
      {  
         // funkcia Math.round(y) zaokrúhli číslo y
         setpix( (int) Math.round(y), i); 
         y += m; 
      } 
  }

V DDA algoritme sme používali reálne čísla, ktoré sme potom zaokrúhľovali. V nasledujúcom algoritme budeme využívať len celočíselné operácie.

$$$APPLET

Applet Bresenhamov algoritmus úsečky, interakcia: zvoľ koncový bod úsečky, klávesy 1,2 zoomovanie rastra

Postup si ukážeme na applete, v ktorom je znázornená časť rastra, pričom zobrazujeme pixle úsečky s riadiacou osou x. Postupujeme z ľavého koncového bodu úsečky (bod A) a máme určiť, či nasledujúci bod úsečky so súradnicou xi+1 má mať rovnakú súradnicu y (tj, yi), alebo súradnicu y o jedna väčšiu (tj. yi+1). Inak povedané či ďalším bodom úsečky bude bod B alebo C. Úlohou algoritmu je určiť, ktorú hodnotu y máme zvoliť, aby sa blížila skutočnej y-súradnici úsečky.

$$$APPLET

Applet Bresenhamov algoritmus úsečky, interakcia: zadaj začiatočný bod úsečky pohybom myši premiestňuj koncový

Bresenhamov algoritmus pre úsečku [4].

Bresenhamov algoritmus pre úsečku [4]. 
// nakresli úsečku z bodu x1,y1 do x2,y2 
public void bresenham_line(int x1, int y1, int x2, int y2)  
 {

// ak je x-ová hodnota súradnice bodu [x1,y1] väčšia ako bodu [x2,y2] tak ich vymeň 
     if ((x1 - x2) > 0) {bresenham_line(x2, y2, x1, y1); return;}

// test sklonu úsečky 
    // funkcia Math.abs(y) určí absolútnu hodnotu y 
     if (Math.abs(y2 - y1) > Math.abs(x2 - x1))  
       { 
          // úsečka zviera s osou y menší ako 45 stupňov 
          bresteepline(y1, x1, y2, x2); return;  
        } 
     // inak úsečka  zviera s osou x menší ako 45 stupňov, teda je riadiaca

// nastavíme pomocné premenné 
     int x = x1, y = y1, sum = x2 - x1,  Dx = 2 * (x2 - x1), Dy = Math.abs(2 * (y2 - y1)); 
     int prirastokDy = ((y2 - y1) > 0) ? 1 : -1;

// kresli úsečku 
     for (int i = 0; i <= x2 -x1; i++)  
      { 
         setpix(x, y); 
         x++; 
         sum -= Dy; 
         if (sum < 0) {y = y + prirastokDy; sum += Dx;} 
     } 
 }

public void bresteepline(int x3, int y3, int x4, int y4)  
 { 
     // ak je x-ová hodnota súradnice bodu [x3,y3] väčšia ako bodu [x4,y4] tak ich vymeň 
     if ((x3 - x4) > 0) {bresteepline(x4, y4, x3, y3); return;}

int x = x3, y = y3, sum = x4 - x3,   Dx = 2 * (x4 - x3), Dy = Math.abs(2 * (y4 - y3)); 
     int prirastokDy = ((y4 - y3) > 0) ? 1 : -1;

for (int i = 0; i <= x4 -x3; i++)  
      { 
         setpix(y, x); 
         x++; 
          sum -= Dy; 
         if (sum < 0) {y = y + prirastokDy; sum += Dx;} 
      } 
 }