Đồ họa máy tính - Cơ sở lý thuyết thuật toán Midpoint

Thuật toán Midpoint:
Các trường hợp về đường thẳng:


TH 1: xA = xB

TH 2: yA = yB 

TH 3: m=1

TH 4: m= -1

TH 5: 0 < m < 1

TH 6: -1 < m < 0

TH 7: m > 1

TH 8: m < -1
Thuật toán Midpoint vẽ đường thẳng:
Trường hợp 1 ta thấy XA=XB nên đường thẳng sẽ là đường song song với trục OY. Y



XA=XB

O
X
Trường hợp 2 ta thấy YA=YB nên đường thẳng sẽ là đường song song với trục OX.

Y



YA=YB


Trường hợp 5:hệ số góc m nằm trong khoảng 0 < m < 1
0< m< 1:

Thuật toán này đưa ra cách chọn điểm P(xi+1,yi +1) hay điểm Q(xi+1,yi) bằng cách xét vị trí tương đối của trung điểm M (trung điểm của PQ) so với đường thẳng.
Nếu điểm M nằm dưới đường thẳng ( đường thẳng nằm gần điểm P hơn => chọn điểm P.
Ngược lại chọn điểm Q.
Phương trình tổng quát của đường thẳng có dạng: Ax +By +C=0 với:
A=y2 – y1
B= -( x2- x1)
C= x2.y1- x1.y2
Xét hàm F(x,y) = Ax + By + C ta có nhận xét:

< 0 nếu (x,y) nằm phía trên đường thẳng
F(x,y) = = 0 nếu (x,y) thuộc đường thẳng
>0 nếu (x,y) nằm phía dưới đường thẳng
Giả sử tại điểm thứ i ta đã vẽ được điểm (xi,yi), cần chọn điểm kế tiếp là P hay Q:



Đặt pi= F(M) = F(xi+1, yi+ 1/2) =A(xi+1) –B(yi +1/2) +C (1).
Nếu pi < 0 => điểm M nằm phía trên đường thẳng => đường thẳng gần điểm Q hơn => chọn Q.
Nếu pi ≥ 0 => M nằm phía dưới đường thẳng=> chọn P.
Tương tại bước thứ i + 1 ta có :
pi +1= F(xi+1 +1, yi+1 + 1/2)= A(xi+1 +1) +B(yi+1 + 1/2) +C (2).
Lấy (2) - (1):
pi+1 –pi = A(xi+1 +1) +B(yi+1 +1/2) + C- A(x i+1) –B(yi +1/2) –C
=A(xi+1 - xi) + B(yi+1 - yi)
=A + B(yi+1 -yi) vì xi+1 – xi = 1.
→



Nhận xét:
Nếu pi< 0: chọn điểm Q hay chọn yi+1 = yi.
Mà từ (3) suy ra vì yi+1 –yi= 0.


Nếu pi ≥ 0:chọn điểm P hay chọn yi+1=yi +1
Mà từ (3) suy ra vì yi+1 – yi= 1.

Với điểm mút đầu tiên ta thay (x1,y1) vào (1) ta có :
p1 =F(x1+1,y1+1/2) =A(x1+1)+ B(y1+1/2)+ C
=Ax1 + By1 +C +A + B/2= A+B/2 vì Ax1 + By1 +C=0.
→





Trường hợp 6:hệ số góc m nằm trong khoảng -1< m< 0:



Đặt pi= F(M) = F(xi+1, yi-1/2) =A(xi+1) –B(yi -1/2) +C (1).
Nếu pi ≤0 => điểm M nằm phía trên đường thẳng => đường thẳng gần điểm Q hơn => chọn Q.
Nếu pi >0 => M nằm phía dưới đường thẳng=> chọn P