[Shool_ĐHMT] Thuật toán DDA vẽ đoạn thẳng

Tháng Mười Hai 16, 2014 nguyenvanquan7826 School Đồ họa máy tính 8 responses

Nội dung
1. Xây dựng thuật toán
2. Lưu đồ thuật toán
3. Code minh họa
4. Code cho mọi trường hợp
Đọc thêm
1. Nguyên lý chung vẽ đoạn thẳng
2. Thuật toán Breshenham vẽ đoạn thẳng
3. Thuật toán Midpoint vẽ đoạn thẳng



1. Xây dựng thuật toán DDA (Digital DifferentialAnalyzer)

Cho 2 điểm đầu mút M1 (x1, y1), M2(x2, y2) và màu vẽ C.
Trong bài nguyên lý chung vẽ đoạn thẳng chúng ta đã xây dựng phương trình đường thẳng có dạng:

y = mx + b. \text{ Trong do: } \begin{cases} m = \frac{y2 - y1}{x2-x1} = \frac{Dy}{Dx} \\ b = y1 - m.x1 \end{cases}

Để đơn giản hóa giải thuật ta xét đường thẳng với m in [0,1] , Dx > 0
Tại mỗi bước ta cho x tăng lên 1 đơn vị tức là x_{i + 1} = x_{i} + 1 \Rightarrow y_{i+1} = y_{i} + m

* Do m là số thực nên muốn y_{i + 1} là số nguyên ta phải làm tròn trước khi truy xuất tọa độ để đưa ra màn hình.
* Với đường thẳng có m > 1 ta sẽ làm ngược lại cho y biến thiên và tính x theo y nghĩa là tại mỗi bước ta có y_{i + 1} = y_{i} + 1 \Rightarrow x_{i+1} = x_{i} + frac{1}{m}
* Với các đoạn thẳng có Dx <0 ta sẽ cho x giảm xuống chứ không tăng.

2. Lưu đồ thuật toán DDA
thuật toán DDA


3. Code minh họa giải thuật

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/* Program create in Linux OS
 * nguyenvanquan7826
 */
 
#include <graphics.h>
#define Round(a) (int)(a+0.5)   // lam tron so
#define DELAY 10
int color = RED;
 
void lineDDA(int x1, int y1, int x2, int y2){       // thuat toan DDA
    int x_unit = 1, Dx = x2 - x1, Dy = y2 - y1;     // Khoi tao cac gia tri ban dau
    int x = x1;
    float y = y1;
    float m = (float)Dy/Dx;     // he so goc m
    putpixel(x, Round(y), color);
     
    while(x < x2){
        delay(10);  // thoi gian tre khi ve 1 diem anh
        x += x_unit;
        y += m;
        putpixel(x,Round(y), color);
    }
}
int main(){
    int gd,gm=VGAMAX; gd=DETECT;
    initgraph(&gd,&gm,NULL);        // khoi tao cua so do hoa
    setbkcolor(WHITE);
    lineDDA(50,150, 300, 200);      // ve duong thang
    getchar();
    return 0;
}

Kết quả minh họa


4. Code cho mọi trường hợp
Code sau sẽ vẽ 8 đoạn thẳng theo 8 hướng, điểm bắt đầu từ tâm.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/* Program create in Linux OS
 * nguyenvanquan7826
 */
 
#include <graphics.h>
#include <stdio.h>
#define Round(a) (int)(a+0.5)
#define DELAY 10
int color = RED;
struct point        // diem gom tung do x va hoanh do y
{
    int x, y;
};
 
void lineDDA(int x1, int y1, int x2, int y2)        // DDA algorithm
{          
    int x_unit = 1, Dx = x2 - x1, Dy = y2 - y1; // Init first value
    int x = x1;
    float y = y1;
    float y_unit = 1;
     
    if (Dx < 0)         
        x_unit = -1;
    if (Dy < 0)
        y_unit = -1;
         
    if (x1 == x2)   // duong thang dung
    {
        while (y != y2)
        {
            delay(DELAY);
            y += y_unit;
            putpixel(x, Round(y), color);
        }  
    }
    else if (y1 == y2)  // duong ngang
    {
        while (x != x2)
        {
            delay(DELAY);
            x += x_unit;
            putpixel(x, Round(y), color);
        }
    }
    else if (x1 != x2 && y1 != y2)// duong xien
    {
        float m = (float) abs(Dy) / abs(Dx);
        x_unit = 1;
        y_unit = m;
        x = x1;
        y = y1;
         
        if (Dx < 0)         
            x_unit = -1;        // ve x giam
        if (Dy < 0)
            y_unit = -m;        // ve y giam
         
        putpixel(x, Round(y), color);
        while(x != x2)
        {
            delay(10);  // thoi gian tre khi ve 1 diem anh
            x += x_unit;
            y += y_unit;
            putpixel(x, Round(y), 1);
        }
    }
}
int main(){
    int gd,gm=VGAMAX; gd=DETECT;
    initgraph(&gd,&gm,NULL);
    setbkcolor(2);
    int x = 200, y = 100;
    char s[] = "nguyenvanquan7826";
    outtextxy(250,100, s);
    point A[9] = {{getmaxx()/2, getmaxy()/2},
                    {A[0].x-x, A[0].y-y},
                    {A[0].x-x, A[0].y+y},
                    {A[0].x+x, A[0].y+y},
                    {A[0].x+x, A[0].y-y},
                    {A[0].x, A[0].y-y},
                    {A[0].x-x, A[0].y},
                    {A[0].x, A[0].y+y},
                    {A[0].x+x, A[0].y},
                };
    for (int i=1; i<9; i++)
    {
        lineDDA(A[0].x, A[0].y, A[i].x, A[i].y);
    }
    getchar();
    return 0;
}

Kết quả minh họa