Thuật toán tạo dòng

Một đường nối hai điểm. Nó là một yếu tố cơ bản trong đồ họa. Để vẽ một đoạn thẳng, bạn cần có hai điểm mà giữa đó bạn có thể vẽ một đoạn thẳng. Trong ba thuật toán sau, chúng tôi gọi một điểm của dòng là $ X_ {0}, Y_ {0} $ và điểm thứ hai của dòng là $ X_ {1}, Y_ {1} $.

Thuật toán DDA

Thuật toán phân tích vi sai kỹ thuật số (DDA) là thuật toán tạo dòng đơn giản được giải thích từng bước ở đây.

Step 1 - Nhận đầu vào của hai điểm cuối $ (X_ {0}, Y_ {0}) $ và $ (X_ {1}, Y_ {1}) $.

Step 2 - Tính hiệu số giữa hai điểm cuối.

dx = X₁ - X₀
dy = Y₁ - Y₀

Step 3- Dựa trên sự khác biệt được tính toán ở bước 2, bạn cần xác định số bước để đặt pixel. Nếu dx> dy, thì bạn cần nhiều bước hơn trong tọa độ x; ngược lại theo tọa độ y.

if (absolute(dx) > absolute(dy))
   Steps = absolute(dx);
else
   Steps = absolute(dy);

Step 4 - Tính số gia trong tọa độ x và tọa độ y.

Xincrement = dx / (float) steps;
Yincrement = dy / (float) steps;

Step 5 - Đặt pixel bằng cách gia tăng thành công các tọa độ x và y tương ứng và hoàn thành việc vẽ đường thẳng.

for(int v=0; v < Steps; v++)
{
   x = x + Xincrement;
   y = y + Yincrement;
   putpixel(Round(x), Round(y));
}

Bresenham's Line Generation

Thuật toán Bresenham là một thuật toán chuyển đổi quét gia tăng khác. Ưu điểm lớn của thuật toán này là nó chỉ sử dụng các phép tính số nguyên. Di chuyển qua trục x trong các khoảng đơn vị và ở mỗi bước chọn giữa hai tọa độ y khác nhau.

Ví dụ, như trong hình minh họa sau, từ vị trí (2, 3) bạn cần chọn giữa (3, 3) và (3, 4). Bạn muốn điểm gần với dòng gốc hơn.

Tại vị trí mẫu $ X_ {k} + 1, $ các khoảng cách dọc khỏi đường toán học được gắn nhãn là $ d_ {upper} $ và $ d_ {Lower} $.

Từ hình minh họa trên, tọa độ y trên đường toán học tại $ x_ {k} + 1 $ là -

Y = m ($ X_ {k} $ + 1) + b

Vì vậy, $ d_ {upper} $ và $ d_ {Lower} $ được đưa ra như sau:

$$ d_ {low} = y-y_ {k} $$

$$ = m (X_ {k} + 1) + b - Y_ {k} $$

và

$$ d_ {upper} = (y_ {k} + 1) - y $$

$ = Y_ {k} + 1 - m (X_ {k} + 1) - b $

Bạn có thể sử dụng chúng để đưa ra quyết định đơn giản về pixel nào gần đường toán học hơn. Quyết định đơn giản này dựa trên sự khác biệt giữa hai vị trí pixel.

$$ d_ {low} - d_ {upper} = 2m (x_ {k} + 1) - 2y_ {k} + 2b - 1 $$

Hãy thay m bằng dy / dx trong đó dx và dy là sự khác biệt giữa các điểm cuối.

$$ dx (d_ {Lower} - d_ {upper}) = dx (2 \ frac {\ mathrm {d} y} {\ mathrm {d} x} (x_ {k} + 1) - 2y_ {k} + 2b - 1) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + 2dy + 2dx (2b-1) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + C $$

Vì vậy, tham số quyết định $ P_ {k} $ cho bước thứ k dọc theo một dòng được đưa ra bởi:

$$ p_ {k} = dx (d_ {under} - d_ {upper}) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + C $$

Dấu của tham số quyết định $ P_ {k} $ giống với dấu của $ d_ {low} - d_ {upper} $.

Nếu $ p_ {k} $ là âm, thì hãy chọn pixel dưới, nếu không thì chọn pixel trên.

Hãy nhớ rằng, các thay đổi tọa độ xảy ra dọc theo trục x trong các bước đơn vị, vì vậy bạn có thể làm mọi thứ với các phép tính số nguyên. Tại bước k + 1, tham số quyết định được đưa ra là -

$$ p_ {k +1} = 2dy.x_ {k + 1} - 2dx.y_ {k + 1} + C $$

Trừ $ p_ {k} $ cho số tiền này, chúng tôi nhận được -

$$ p_ {k + 1} - p_ {k} = 2dy (x_ {k + 1} - x_ {k}) - 2dx (y_ {k + 1} - y_ {k}) $$

Tuy nhiên, $ x_ {k + 1} $ giống với $ (xk) + 1 $. Vì vậy -

$$ p_ {k + 1} = p_ {k} + 2dy - 2dx (y_ {k + 1} - y_ {k}) $$

Trong đó, $ Y_ {k + 1} - Y_ {k} $ là 0 hoặc 1 tùy thuộc vào dấu của $ P_ {k} $.

Tham số quyết định đầu tiên $ p_ {0} $ được đánh giá tại $ (x_ {0}, y_ {0}) $ được đưa ra là -

$$ p_ {0} = 2dy - dx $$

Bây giờ, hãy ghi nhớ tất cả các điểm và tính toán ở trên, đây là thuật toán Bresenham cho độ dốc m <1 -

Step 1 - Nhập hai điểm cuối của dòng, lưu điểm cuối bên trái trong $ (x_ {0}, y_ {0}) $.

Step 2 - Vẽ đồ thị $ (x_ {0}, y_ {0}) $.

Step 3 - Tính các hằng số dx, dy, 2dy, và (2dy - 2dx) và nhận giá trị đầu tiên cho tham số quyết định là -

$$ p_ {0} = 2dy - dx $$

Step 4 - Tại mỗi $ X_ {k} $ dọc theo dòng, bắt đầu từ k = 0, thực hiện kiểm tra sau:

Nếu $ p_ {k} $ <0, điểm tiếp theo để vẽ biểu đồ là $ (x_ {k} +1, y_ {k}) $ và

$$ p_ {k + 1} = p_ {k} + 2dy $$ Nếu không,

$$ (x_ {k}, y_ {k} +1) $$

$$ p_ {k + 1} = p_ {k} + 2dy - 2dx $$

Step 5 - Lặp lại bước 4 (dx - 1) lần.

Với m> 1, hãy tìm xem bạn có cần tăng x trong khi tăng y mỗi lần hay không.

Sau khi giải, phương trình cho tham số quyết định $ P_ {k} $ sẽ rất giống nhau, chỉ là x và y trong phương trình được hoán đổi cho nhau.

Thuật toán điểm giữa

Thuật toán điểm giữa là do Bresenham và được Pitteway và Van Aken sửa đổi. Giả sử rằng bạn đã đặt điểm P tại tọa độ (x, y) và hệ số góc của đường thẳng là 0 ≤ k ≤ 1 như trong hình minh họa sau.

Bây giờ bạn cần quyết định đặt điểm tiếp theo tại E hay N. Điều này có thể được chọn bằng cách xác định giao điểm Q gần nhất với điểm N hoặc E. Nếu giao điểm Q gần điểm N nhất thì N được coi là điểm tiếp theo; nếu không thì E.

Để xác định điều đó, trước tiên hãy tính trung điểm M (x + 1, y + ½). Nếu giao điểm Q của đoạn thẳng với đường thẳng đứng nối E và N nằm dưới M thì lấy E làm điểm tiếp theo; nếu không thì lấy N làm điểm tiếp theo.

Để kiểm tra điều này, chúng ta cần xem xét phương trình ngầm định -

F (x, y) = mx + b - y

Với m dương tại X bất kỳ,

Nếu y nằm trên đường thẳng thì F (x, y) = 0
Nếu y nằm trên đường thẳng thì F (x, y) <0
Nếu y nằm dưới dòng thì F (x, y)> 0