[DHMT]Thuật Toán DDA Vẽ Đường Thẳng

  1. Xây đựng Thuật toán DDA

Giả sử có 2 đầu múc A(x1,y1) B(x2,y2) vẽ đoạn thẳng AB

Xét trường hợp 0<m<=1 với m=Dy/Dx = (y2-y1)/(x2-x1)

Khi ta tăng giá trị xi lên xi+1=xi+Dx với Dx=1 ta có

yi+1=yi+Dy=yi+m*Dx=yi +m

đối với trướng hợp m>1 (Dy>Dx)

Khi tăng yi=yi+Dy với Dy=1

xi+1=xi+Dx=xi+Dy/m=xi+1/m

Tương tự khác trường hợp -1<=m<0

yi+1=yi-m;

Trường hợp m<-1

yi+1=yi-1/m

Tóm lại thuật toán DDA ý tưởng là làm tròn giá trị số thực và cộng số thực.

Giả sử thuật toán DDA việc quyết định chọn yi+1 là yi hay yi+1 dựa vào phương trình đường thẳng y=mx+b. nghĩa là ta tính tọa độ (xi+1,y) với yi+1 là tọa độ làm tròn giá trị của y.

Như vậy ta có: y=m(xi+1)+b và yi+1=round(y)

2. Thuật toán tương ứng có thể đề ra

Nhập A(x1,y1) B(x2,y2)
Tính Dx = x2 – x1 Dy = y2 – y1 Step = Max(|Dx| , |Dy|)

Khởi tạo các giá trị: IncX = Dx/Step; IncY = Dy/Step; {bước tăng khi vẽ}

x = x1; y = y1; {Chọn ñiểm vẽ ñầu tiên} Vẽ ñiểm (x,y);

Cho i chạy từ 1 ñến Step:

x = x + IncX; y = y + IncY;

Vẽ điểm (Round(x),Round(y))

3. Code Mẫu Tổng Quát

int Dx = x2 – x1;
int Dy = y2 – y1;
setPixel(x1, y1);
// Tối ưu
int step=0;
if (abs(Dx) > abs(Dy))
{
step = abs(Dx);
}
else
step = abs(Dy);
double y = y1;
double x = x1;
double x_inc = (double)Dx / step;
double y_inc = (double)Dy / step;
for (int i = 1; i <= step;i++)
{
x += x_inc;
y += y_inc;
setPixel(Round(x), Round(y));
}

Advertisements

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s