Triviální algoritmus, DDA algoritmus a Bresenhamův algoritmus pro úsečku - Java

Triviální algoritmus, DDA algoritmus a Bresenhamův algoritmus pro úsečku - Java

Vykreslení úsečky je základ počítačové grafiky a existuje pro to řada algoritmů. Některé jsou efektivnější - Bresenhamův algoritmus, některé méně - triviální a DDA algoritmy. A i přesto, že je možné úsečky vykreslit bez vlastní implementace příslušné metody s využitím třídy java.awt.Graphics, je dobré vědět, co se za metodami v této třídě skrývá. Názorně si ukážeme kód v javě pro tyto 3 algoritmy. Implementace v Javě je velmi podobné té v C, takže ani milovníci C# a jiných Cček nepřijdou zkrátka.


Můžete zkusit: Funkční java aplikace využívající všech algoritmů níže + něco k tomu :)

Bresenhamův algoritmus pro úsečku

Pravděpodobně nejefektivnější algoritmus pro vykreslení úsečky. Vychází z DDA algoritmu, narozdíl od něj se pohybuje ale pouze v celých číslech (int), což je nesporná výhoda oproti všem ostatním řešením.

Kód níže je varianta kódu, která pokrývá všechny situace, které mohou nastat - řádné vykreslení ve všech půlkvadrantech (podle směrnice), správné vykreslení při situaci, kdy koncový bod úsečky bude vlevo od počátečního, i tu, kdy úsečka bude vlastně jen jeden bod.

// Bresenhamův algoritmus

if ((x1 == x2) && (y1 == y2)) {           
    drawPixel(x1, y1, barva);

} else {              
    int dx = Math.abs(x2 - x1);
    int dy = Math.abs(y2 - y1);
    int rozdil = dx - dy;

    int posun_x, posun_y;

    if (x1 < x2) posun_x = 1; else posun_x = -1;
    if (y1 < y2) posun_y = 1; else posun_y = -1;

    while ((x1 != x2) || (y1 != y2)) {  

        int p = 2 * rozdil;

        if (p > -dy) {
            rozdil = rozdil - dy;
            x1 = x1 + posun_x;
        }
        if (p < dx) {
            rozdil = rozdil + dx;
            y1 = y1 + posun_y;
        }
        drawPixel(x1, y1, barva);
    }
} 

DDA algoritmus pro úsečku

Výchozí algoritmus pro Bresenhamův. Hlavní rozdíl je v datovém typu čísel - zde se pohybujeme v reálných číslech (tudíž používáme buď double nebo float datové typy). Na pochopení se ale zdá být jednodušší.

Kód níže je varianta kódu, která pokrývá všechny situace, které mohou nastat - řádné vykreslení ve všech půlkvadrantech (podle směrnice), správné vykreslení při situaci, kdy koncový bod úsečky bude vlevo od počátečního, i tu, kdy úsečka bude vlastně jen jeden bod.

// DDA algoritmus

double dx = x2-x1;
double dy = y2-y1;

if (Math.abs(y2 - y1) <= Math.abs(x2 - x1)) {

    if ((x1 == x2) && (y1 == y2)) {
        drawPixel(x1, y1, barva);

    } else {
        if (x2 < x1) {
            int tmp = x2;
            x2 = x1;
            x1 = tmp;

            tmp = y2;
            y2 = y1;
            y1 = tmp;
        }

        double k = (double)dy/dx; 
        int cele_y;           
        double y = (double)y1;

        for (int x = x1 ; x <= x2 ; x++) {
            cele_y = (int)Math.round(y);
            drawPixel(x, cele_y, barva);
            y += k;
        }
    }
} else {

        if (y2 < y1) {
            int tmp = x2;
            x2 = x1;
            x1 = tmp;

            tmp = y2;
            y2 = y1;
            y1 = tmp;
        }

        double k = (double)dx/dy;
        int cele_x;
        double x = (double)x1;
        for (int y = y1; y <= y2; y++) {
            cele_x = (int)Math.round(x);
            drawPixel(cele_x, y, barva);
            x += k;
        }
}

Triviální algoritmus pro úsečku

Nejjednodušší algoritmus pro vykreslení úsečky, jeho logika je na první pohled čistě matematická a zcela jasně vychází ze směrnicového vyjádření přímky (to ostatně všechny algoritmy, ne u všech je to ale na prnví pohled zřejmé).

Kód níže je varianta kódu, která pokrývá všechny situace, které mohou nastat - řádné vykreslení ve všech půlkvadrantech (podle směrnice), správné vykreslení při situaci, kdy koncový bod úsečky bude vlevo od počátečního, i tu, kdy úsečka bude vlastně jen jeden bod.

// Triviální algoritmus

    double dx = x2 - x1;
    double dy = y2 - y1;

    if (Math.abs(y2 - y1) >= Math.abs(x2 - x1)) {

    if ((x1 == x2) && (y1 == y2)) {
        drawPixel(x1, y1, barva);

    } else {
        if (y2 < y1) {
            int tmp = x2;
            x2 = x1;
            x1 = tmp;

            tmp = y2;
            y2 = y1;
            y1 = tmp;
        }

        double k = dx / (double) dy;
        double q = x1 - k * y1;

        for (int y = y1; y < y2; y++) {
            int x = (int) (k * y + q);
            drawPixel(x, y, barva);
        }
    }


} else {
    if (x2 < x1) {
        int tmp = x2;
        x2 = x1;
        x1 = tmp;

        tmp = y2;
        y2 = y1;
        y1 = tmp;
    }

    double k = dy / (double) dx;
    double q = y1 - k * x1;

    for (int x = x1; x < x2; x++) {
        int y = (int) (k * x + q);
        drawPixel(x, y, barva);
    }
}

<< Back to the previous page


Write a comment
 If you cann't see the verification code clearly.
Type the characters into the text field below(*)
 
This website uses cookies for ads, just like any other website. Further information