Ú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)                       (x2*y1-x1*y2)
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

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