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

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

Nội dung
Xây dựng thuật toán
Đọc thêm
1. Nguyên lý chung vẽ đoạn thẳng
2. Thuật toán DDA vẽ đoạn thẳng
3. Thuật toán Breshenham vẽ đoạn thẳng

Xây dựng thuật toán
Cho 2 điểm đầu mút M1(x1, y1), và M2(x2, y2). Phương trình đưởng thẳng đi qua M1, M2 có dạng
$\frac{x-x1}{y-y1} = \frac{x2-x1}{y2-y1} \\ \Leftrightarrow \left ( y2-y1 \right )x - \left ( x2-x1 \right )y + x2y1-x1y2 \\ \Leftrightarrow Ax + By + C = 0 \\ Voi \indent A = Dy, B = -Dx, C = x2y1-x1y2$
Midpoint

Tại bước thứ k+1 ta thực hiện hiện tăng x lên một đơn vị và tìm cách tính y theo x với các số nguyên. Gọi S, P lần lượt là các điểm có tọa độ $(x_{k} + 1, y_{k}) , (x_{k} + 1, y_{k} + 1), M(x_{k} + 1, y_{k} + 0.5)$ là trung điểm của SP (điểm Midpoint), Q là điểm cần tìm. Điểm $Q(x_{k} + 1, y)$ nhận giá trị nào phụ thuộc vào vị trí của điểm Q so với điểm M. Nếu Q nằm dưới M ta lấy điểm S $(y = y_{k})$ , ngược lại lấy điểm P $(y = y_{k} + 1)$ .
Đặt $F(x, y) = Ax + By + C = 0$ . Ta có:
Điểm M thuộc M1M2 <=> F(M) = 0.
Điểm M nằm phía trên M1M2 <=> F(M) < 0.
Điểm M nằm phía dưới M1M2 <=> F(M) > 0.
Để xác định vị trí của M ta xét dấu của hằng số $P_{k} = 2F(M) = 2A(x_{k} + 1) + 2B(y_{k} + 0.5) + 2C$ .
+/ Nếu $P_{k} < 0$ , M nằm phía trên M1M2 khi đó Q nằm dưới M ta lấy điểm S tức là $y = y_{k}$
$=> P_{k+1} = 2A(x_{k} + 1) + 2B(y_{k}) + 2C = 2A(x_{k}) + 2B(y_{k}) + 2C + 2A = P_{k} + 2Dy$
+/ Nếu $P_{k} \geq 0$ , M thuộc hoặc nằm dưới M1M2 khi đó Q nằm trên M ta lấy P tức $y = y_{k} + 1$
$\Rightarrow P_{k+1} = 2A(x_{k} + 1) + 2B(y_{k} + 1) + 2C \\ \indent \indent = 2A(x_{k}) + 2B(y_{k}) + 2C + 2A + 2B \\ \indent \indent = P_{k} + 2(Dy - Dx)$
Bây giờ ta tính giá trị ban đầu P1.
$P_{1} = 2A(x_{1} + 1) + 2B(y_{1} + 0.5) + 2C \\ \indent \indent = 2Ax_{1} + 2By_{1} + 2C + 2A + B\\ \indent \indent = 2(Ax + By + C) + 2Dy - Dx \\ \indent \indent = 2Dy - Dx \\ \indent \indent(Ax + By + C = 0)\\$
Ta nhận thấy thuật toán Midpoint cho kết quả giống hoàn toán với thuật toán Breshenham nhưng cách xây dựng đơn giản hơn rất nhiều.