Chương 2 Các thuật toán đồ hoạ cơ sở
Bài toán: Input: Cho đoạn thẳng AB: A(xA; yA), B(xB; yB). Output: Vẽ đoạn thẳng AB trên màn hình. Giải quyết bài toán Thuật toán làm tròn số Thuật toán Bresenham
Bạn đang xem trước 20 trang tài liệu Chương 2 Các thuật toán đồ hoạ cơ sở, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Chương 2
Các thuật toán đồ hoạ cơ sở
Giảng viên: Ths.Vũ Minh Yến
Tổ HTTT- Khoa CNTT
Nội dung
2.1. Các thuật toán vẽ đoạn thẳng
2.2. Các thuật toán vẽ đường tròn
2.3. Các thuật toán vẽ elip
2.4. Các thuật toán clipping
2.5. Các thuật toán tô màu
2.1. Các thuật toán vẽ đoạn thẳng
Bài toán:
Input: Cho đoạn thẳng AB: A(xA; yA), B(xB; yB).
Output: Vẽ đoạn thẳng AB trên màn hình.
Giải quyết bài toán
Thuật toán làm tròn số
Thuật toán Bresenham
Thuật toán làm tròn số
Phương trình đường thẳng AB (xA ≠ xB):
Đặt
Khi đó phương trình đường thẳng AB:
AA
AB
AB yxx
xx
yyy +−
−
−
= )(
AB
AB
xx
yy
m
−
−
=
( ) AA yxxmy +−=
Thuật toán làm tròn số
Chia thành 4 trường hợp:
TH1: AB song song với Oy
TH2: AB song song với Ox
TH3: |m|≤1
TH4: |m|>1
m
=
1
m
=
-1
(1)
y
O x
(4)
(3)
(3)
(2)
(4)
Thuật toán làm tròn số
TH1: xA=xB (giả sử yA < yB)
Bước 1: x=xA; y=yA;
Bước 2: Vẽ điểm (x; y);
Bước 3: y=y+1;
Bước 4: Nếu y<=yB thì: Bước 2;
Bước 5: Kết thúc.
A
y
O x
B
xA=xB
yA
yB
Thuật toán làm tròn số
TH2: yA=yB (Tương tự TH1)
(Giả sử xA< xB)
Bước 1: x=xA; y=yA;
Bước 2: Vẽ điểm (x; y);
Bước 3: x=x+1;
Bước 4: Nếu x<=xB thì: Bước 2;
Bước 5: Kết thúc.
A
y
O
B
xA
yA=yB
xB
Thuật toán làm tròn số
TH3: |m| ≤ 1
Bước 1: Nếu xA > xB thì: Hoán
đổi vị trí A,B
(Đảm bảo xA < xB)
Bước 2: x=xA; y=yA;
Bước 3: Vẽ điểm (x; y);
Bước 4: x=x+1;
y=Round(m(x-xA)+yA);
Bước 5: Nếu x≤ xB thì: Bước 3;
Bước 6: Kết thúc;
m
=
1
m
=
-1
y
O x
A
B
xA xB
Thuật toán làm tròn số
TH4: |m| > 1 tương tự TH3
khi đổi vai trò x, y.
Bước 1: Nếu yA > yB thì: Hoán
đổi vị trí A,B
(Đảm bảo yA < yB)
Bước 2: x=xA; y=yA;
Bước 3: Vẽ điểm (x; y);
Bước 4: y=y+1;
x=Round(1/m(y-yA)+xA);
Bước 5: Nếu y≤ yB thì: Bước 2;
Bước 6: Kết thúc;
m
=
1
m
=
-1
y
O x
A
B
yA
yB
Thuật toán Breseham
TH1 xA=xB, TH2: yA=yB:
giống phương pháp
làm tròn số.
Còn lại: chia làm 4
trường hợp
TH3: 0 < m ≤ 1
TH4: -1 ≤ m <0
TH5: m > 1
TH6: m < -1
m
=1
(3)
(4)
(5)
(6)
O x
y
Thuật toán Breseham
TH3: 0 < m ≤ 1
y
xO(0,0)
d1
d2
yi
yi+1= ?
xi xi+1=xi+1
Thuật toán Breseham
Cơ sở toán học xây dựng thuật toán:
Giả sử ta có điểm thứ i: (xi; yi)
Xác định điểm thứ i+1: (xi+1; yi+1)=?
Ta có: 0< m ≤ 1
⇒ Nếu ∆x=1⇒ ∆y≤1, trong đó ∆x=xi+1-xi; ∆y=yi+1-yi
Như vậy:
xi+1= xi+1
yi+1= yi nếu d1 ≤ d2
yi+1= yi+1 nếu d1>d2
α ≤ 450
Thuật toán Breseham
Xét d1= y(xi+1) - yi
⇔ d1=m(xi+1-xA)+yA-yi
=m(xi+1-xA)+yA-yi
=mxi-yi+m(1-xA)+yA
Xét d2= yi+1 - y(xi+1)
= yi+1- m(xi+1-xA)-yA
=-mxi+yi-m(1-xA)-yA+1
Xét Pi=dx(d1-d2)
= dx(2mxi-2yi+2m(1-xA)+2yA-1)
= 2dy.xi-2dx.yi+ 2dy(1-xA)+2dx.yA-dx
Thuật toán Breseham
Tương tự ta có
Pi+1= 2dy.xi+1-2dx.yi+1+ 2dy(1-xA)+2dy.yA-dx
Xét ∆P=Pi+1-Pi
=2dy(xi+1-xi) – 2dx(yi+1-yi)
=2dy-2dx(yi+1-yi)
Giả sử Pi≥0 ⇔ d1-d2 ≥ 0 ⇔ d1 ≥ d2 ⇔ yi+1=yi+1
⇒ ∆P=2dy-2dx=const1
Giả sử Pi<0 ⇔ d1-d2<0 ⇔ d1<d2 ⇔ yi+1=yi
⇒ ∆P=2dy=const2
Thuật toán Breseham
Xét P1= 2dy.x1-2dx.y1+ 2dy(1-xA)+2dx.yA-dx
= 2dy.xA-2dx.yA+2dy-2dy.xA+2dx.yA-dx
= 2dy-dx=const
Thuật toán Bresenham
Thuật toán:
Bước 1: Nếu xA>xB thì: Hoán đổi A, B
Bước 2: dx=xB-xA; dy=yB-yA;
const1=2dy-2dx; const2=2dy;
p=2dy-dx; x=xA; y=yA;
Bước 3: Vẽ điểm (x,y)
Bước 4: x=x+1;
Bước 5: Nếu p>0 thì: y=y+1; p=p+const1;
còn lại: p=p+const2;
Bước 6: Nếu x ≤ xB thì: Bước 3;
Bước 7: Kết thúc
Thuật toán Breseham
TH4: -1 ≤m <0
Sinh viên tự xây dựng
thuật toán tương tự TH3:
const1=2dy+2dx;
const2=2dy; p1=2dy+dx;
Nếu p>0 thì: p=p+const2;
Còn lại: y=y-1; p=p+const1;
Thuật toán Breseham
TH5: m > 1
Đổi vai trò x, y cho nhau
ta có TH3.
TH6: m < -1
Đổi vai trò x, y cho nhau
ta có TH4.
(5) (6)
y
O x
2.2. Các thuật toán vẽ đường tròn
Xét đường tròn tâm O(0;0),
bán kính r.
Phương trình đại số:
x2+y2=r2
Phương trình lượng giác:
Với
Xét đường tròn tâm A(xA; yA),
bán kính r:
(A;r) là ảnh của (O;r) qua phép
tịnh tiến
Ta có:
=
=
α
α
sin
cos
ry
rx
[ ]piα 2;0∈
O x
y
x
y
M
α
r
OA
+=
+=
A
A
yyy
xxx
1
1
x
y
O
A
M(x;y)
M1(x1;y1)
xA
yA
2.2. Các thuật toán vẽ đường tròn
Tính chất đối xứng:
Xét điểm M1(x,y)∈(O;r) , khi đó:
M2(y,x)
M3(y,-x)
M4(x,-y)
M5(-x,-y)
M6(-y,-x)
M7(-y,x)
M8(-x,y)
M1
M2
M3
M4M5
M6
M7
M8
O
y
x
2.2. Các thuật toán vẽ đường tròn
Bài toán:
Input: Cho tâm O(0,0), bán kính r
Output: Vẽ đường tròn tâm O, bán kính r.
Giải quyết bài toán:
Thuật toán làm tròn số
Thuật toán xấp xỉ
Thuật toán Bresenham
Thuật toán làm tròn số
Theo phương trình đại số:
Cung AB:
Xét trên cung AB: nếu ∆x=1 thì
|∆y|≤1 nên lấy cơ sở theo x
Thuật toán:
Bước 1: x=0; y=r;
Bước 2: Vẽ 8 điểm:
M1(x,y), M2(y;x),M3(y;-x), M4(x;-y),
M5(-x;-y), M6(-y;-x), M7(-y;x), M8(-x;y)
Bước 3: x=x+1; y= round( )
Bước 4: Nếu x ≤ y thì: Bước 2;
Bước 5: Kết thúc.
B
O
y
x
A[ ]2/;0,22 rxxry ∈−=
22 xr −
Thuật toán làm tròn số
Theo phương trình lượng giác:
Bước 1: alpha=0; step=1/r;
x=r; y=0;
Bước 2: Vẽ tám điểm: ...
Bước 3: alpha=alpha+step;
x=r.cos(alpha); y=r.sin(alpha);
Bước 4: Nếu x>=y: Bước 2;
Bước 5: Kết thúc.
O x
y
x
y
M
α
r
Thuật toán xấp xỉ
Ta có phương trình (O;r):
Xét đạo hàm theo đối số α:
=
=
α
α
sin
cos
ry
rx [ ]piα 2;0∈
==
−=−=
xry
yrx
α
α
cos'
sin'
Thuật toán xấp xỉ
Xét đạo hàm tại điểm thứ i:
⇔
Xét đạo hàm tại điểm thứ i+1:
⇔
Thuật toán:
Bước 1: stepα=1/r;
x=r; y=0;
Bước 2: Vẽ 8 điểm
Bước 3: x=x-y.stepα;
y=x.stepα + y;
Bước 4:
Nếu x≥y thì: Bước 2;
Bước 5: Kết thúc;
1
1
1
1
0
'
1 lim
+
+
+
+
→
+
≈
−
≈
−
−
=
−
i
ii
ii
ii
step
i
x
step
yy
yyy
α
ααα
iii ystepxy +≈ ++ α.11
i
ii
ii
ii
step
i
y
step
xx
xx
x
−≈
−
≈
−
−
=
+
+
+
→ +
α
ααα
1
1
1
0
' lim
αstepyxx iii .1 −≈+
Thuật toán Bresenham
y
xO
d2≈
≈d1
xi xi+1
yi
yi-1
Giả sử ta có điểm
thứ i: (xi; yi)
Tính điểm thứ i+1:
(xi+1; yi+1)=?
Thuật toán Bresenham
d1 = yi2 - y(xi+1)2
= yi2 - (R2- (xi + 1)2 )
d2 = y(xi+1)2 - (yi - 1)2
= (R2- (xi + 1)2 ) - (yi - 1)2
Pi = d1 - d2
= 2(xi+1)2 + 2yi2 - 2yi- 2R2 + 1
Tương tự ta có:
Pi+1= 2(xi+2)2 + 2yi+12- 2yi+1 - 2R2+1
Thuật toán Bresenham
Xét ∆P = Pi+1 - Pi
= 4xi + 6 + 2(yi+12 - yi2 ) - 2(yi+1 - yi)
Nếu Pi < 0: yi+1 = yi
Pi+1 = Pi + 4xi +6
Nếu Pi >= 0: yi+1 = yi - 1.
Pi+1 = Pi + 4(xi - yi ) + 10.
Xét P1 khi đó: ( x1 ; y1) =(0;R)
P1= 2(x1+1)2 + 2y12 - 2y1- 2R2 + 1
= 3 - 2R.
Thuật toán Bresenham
Thuật toán:
Bước 1: x=0; y=R; p=3-2R;
Bước 2: Vẽ tám điểm
Bước 3: Nếu p>0 thì: p=4(x-y)+10; y=y-1;
còn lại: p=p+ 4x+6
Bước 4: x=x+1;
Bước 5: Nếu x≤ y thì: Bước 2;
Bước 6: Kết thúc.
2.3. Các thuật toán vẽ elip
Phương trình elip tâm O(0;0), bán kính a, b:
Tính chất đối xứng
0),( 222222 =−+= bayaxbyxF
xO
y
M1(x,y)
M3(-x,-y) M2(x,-y)
M1(-x,y)
A
B
2.3. Các thuật toán vẽ elip
Xét cung AB:
Vecto gradient tại M có
độ dốc bằng 1.
Ta có:
Vậy M chia AB thành 2 cung:
Cung AM: ∆x=1 ⇒ ∆y≤1 ⇒ Lấy cơ sở theo x
Cung MB: ∆x=1 ⇒ ∆y≥1 ⇒ Lấy cơ sở theo y
)(MFGrad
O
A
B
M
j
y
Fi
x
FyxFGrad
∂
∂
+
∂
∂
=),(
y
F
x
F
∂
∂
=
∂
∂
⇒
⇒=⇔=⇔ x
a
b
xMx
a
byyaxb 2
2
2
2
22 ;22
2.3. Các thuật toán vẽ elip
Thuật toán làm tròn số:
Tính trên cung AM:
Bước 1: x=0; y=b;
Bước 2: Vẽ 4 điểm
Bước 3: x=x+1;
Bước 4: Nếu y≥ xb2/a2 thì: Bước 2;
Bước 5: Kết thúc.
Tính trên cung MB: tương tự như tính trên cung AM khi
đổi vai trò x và y.
( ) ;/ 22 xaaby −=
)(MFGrad
O
A
B
M
2.3. Các thuật toán vẽ elip
Thuật toán Bresenham: (xét tương tự đường tròn)
Tính trên cung AM:
Giả sử có điểm thứ i (xi; yi).
Tính điểm thứ i+1 (xi+1; yi+1)=?
>−
≤
=
+=
+
+
21
21
1i
i1i
1
y
1; xx
ddy
ddy
i
i
y
xO
d2≈
≈d1
xi xi+1
yi
2.3. Các thuật toán vẽ elip
Thuật toán Vanaken:
2.4. Các thuật toán clipping
Bài toán:
Input:
Cho cửa sổ: (x1; y1), (x2; y2)
Cho đoạn thẳng AB: (xA;yA), (xB; yB)
Output:
Hiển thị phần đoạn thẳng AB
trong cửa sổ.
O x
y
Thuật toán Cohen-Surtheland
Xét điểm P(x; y):
Quy ước: KOD(P)=b4b3b2b1 (bi={0;1})
b1=1: nếu x < x1
b2=1: nếu x > x2
b3=1: nếu y < y1
b4=1: nếu y > y2
KOD(P)=0000 ⇔ P thuộc cửa
sổ
TH1: Nếu
KOP(A)=KOD(B)=0000: AB
nằm hoàn toàn trong cửa sổ.
TH2: Nếu KOD(A) and
KOD(B)0000: AB nằm hoàn
toàn ngoài cửa sổ.
0000
0100 0110
0010
101010001001
0001
0101
y1
y2
x1 x2
Thuật toán Cohen-Surtheland
TH3: Còn lại: AB có ít nhất
một đầu nằm ngoài cửa sổ,
giả sử là A.
Khi đó, KOD(A)=b4b3b2b1
Xác định A1(xA1;yA1)=?:
Nếu b1=1: A1=AB∩(x=x1)
Nếu b2=1: A1=AB∩(x=x2)
0000
0100 0110
0010
101010001001
0000
0101
y1
y2
x1 x2
A
A1
B( )
+−
−
−
=
=
AA
AB
AB
A
A
yxx
xx
yyy
xx
1
1
1
1
( )
+−
−
−
=
=
AA
AB
AB
A
A
yxx
xx
yyy
xx
2
2
1
1
Thuật toán Cohen-Surtheland
Nếu b3=1: A1=AB∩(y=y1)
Nếu b4=1: A1=AB∩(y=y2)
Gán A=A1 ta được đoạn AB mới.
( )
+−
−
−
=
=
AA
AB
AB
A
A
xyy
yy
xx
x
yy
1
1
1
1
( )
+−
−
−
=
=
AA
AB
AB
A
A
xyy
yy
xx
x
yy
2
2
1
1
Thuật toán Cohen-Surtheland
Thuật toán:
Bước 1: Tính KOD(A), KOD(B)
Bước 2: Nếu KOD(A)=
KOD(B)=0000: Vẽ AB và thực
hiện Bước 6;
Bước 3: Nếu KOD(A) and
KOD(B) 0000: Bước 6;
Bước 4: Còn lại:
Tính A1=AB ∩ cửa sổ và A=A1
Nếu b1=1: A=A1=AB∩(x=x1)
( )
=
+−
−
−
=
1
1
xx
yxx
xx
yyy
A
AA
AB
AB
A
Nếu b2=1: A=A1=AB∩ (x=x2)
Nếu b3=1: A=A1=AB ∩ (y=y1)
Nếu b4=1: A=A1=AB ∩ (y=y2)
Bước 5: Bước 1;
Bước 6: Kết thúc.
( )
=
+−
−
−
=
1
1
yy
xyy
yy
xx
x
A
AA
AB
AB
A
( )
=
+−
−
−
=
2
2
xx
yxx
xx
yyy
A
AA
AB
AB
A
( )
=
+−
−
−
=
2
2
yy
xyy
yy
xx
x
A
AA
AB
AB
A
Thuật toán Liang-Basky
Phương trình đoạn AB dạng tham số:
Điểm M(x, y) thuộc cửa sổ
⇔
Điểm M(x,y) vừa thuộc cửa sổ vừa thuộc đoạn AB:
≤≤
≤≤
21
21x
yyy
xx
∈−=+=
−=+=
]1;0[; tyydytdyyy
xxdxtdxxx
ABA
ABA
≤≤
≤+≤
≤+≤
10
21
21
t
ytdyyy
xtdxxx
A
A
(1)
Thuật toán Liang-Basky
(1)
≤≤
+−≤
−≤−
+−≤
−≤−
⇔
10
2
1
2
1
t
yytdy
yytdy
xxtdx
xxtdx
A
A
A
A
;;
;;
;;
;;
234
133
222
111
yyqdyp
yyqdyp
xxqdxp
xxqdxp
A
A
A
A
+−==
−=−=
+−==
−=−=
Đặt:
≤≤
∈≤
⇔⇒
10
4;1)2(
t
iqtp ii
}4;1,0|{
}4;1,0|{
∈<=
∈≥=
ipiL
ipiK
i
i
≤≤
∈≥
∈≤
⇔⇒
10
/
/
)3(
t
Lipqt
Kipqt
ii
ii
(2)
(3)
(4)
Đặt:
Thuật toán Liang-Basky
{ }
{ }
∈
≥
∈
≤
⇔⇒
Li
p
q
t
Ki
p
q
t
i
i
i
i
0max
1min
)4(
U
U
Đặt
{ }
{ }
∈=
∈=
0max
1min
2
1
U
U
Li
p
q
t
Ki
p
q
t
i
i
i
i
12 ttt ≤≤⇒
Thuật toán Liang-Basky
;0;1
;;
;;
;;
;;
;;
21
244
133
222
111
==
+−==
−=−=
+−==
−=−=
−=−=
tt
yyqdyp
yyqdyp
xxqdxp
xxqdxp
yydyxxdx
A
A
A
A
ABAB
=
=
22
11
;max
,min
t
p
q
t
t
p
q
t
i
i
i
i
Thuật toán:
Bước 1:
Bước 2: i=1→4:
Nếu pi>0:
Nếu pi<0:
Bước 3: Nếu t1≥ t2:
Tính A1B1:
Vẽ A1B1
Bước 4: Kết thúc.
+=
+=
+=
+=
dytyy
dxtxx
B
dytyy
dxtxx
A
AB
AB
AA
AA
2
2
1
1
1
1
1
1
1
1
2.5. Các thuật toán tô màu
Thuật toán vết dầu loang
Thuật toán tô màu theo đường biên
Thuật toán tô màu theo dòng quét.
Thuật toán vết dầu loang
Bài toán:
Input:
Miền khép kín xác định bởi mầu biên: mb
Một điểm M(x; y) thuộc miền cần tô
Mầu tô: mt
Output: Tô màu miền khép kín trên bằng mầu tô.
Thuật toán vết dầu loang
Mô tả:
1514
251613
18171211
19(x,y)8910
242017
232126
22345
Thuật toán vết dầu loang
Thuật toán:
Void Tomauloang(x, y, mb, mt)
{
if (màu(x,y)!=mb and màu(x,y)!=mt)
{
Tô_màu_điểm(x,y, mt);
Tomauloang(x,y-1,mb,mt);
Tomauloang(x+1,y,mb,mt);
Tomauloang(x,y+1,mb,mt);
Tomauloang(x-1,y,mb,mt);
}
}
Thuật toán tô màu theo đường biên
Bài toán: giống thuật toán vết dầu loang
Input:
Miền khép kín xác định bởi mầu biên: mb
Một điểm M(x; y) thuộc miền cần tô
Mầu tô: mt
Output: Tô màu miền khép kín trên bằng mầu tô.
Thuật toán tô màu theo đường biên
Xét miền cần tô là
miền lồi theo trục
Oy
x2
(x,y)x1
(x
,
y)
x2x1
x1
O
y
Thuật toán tô màu theo đường biên
Thuật toán: (áp dụng với i={1, -1})
Bước 1: Tìm biên trái nhất và biên phải nhất
x1=x; x2=x;
while (màu(x1-1,y)mb) x1=x1-1;
while (màu(x2+1,y)mb) x2=x2+1;
Bước 2: Vẽ đoạn (x1,y) và (x2,y) bằng màu tô (mt)
Bước 3: Tính điểm phát triển tiếp theo:
while(màu(x1,y+i)=mb) x1=x1+1;
Bước 4: Nếu x1<=x2:
x=x1; y=y+i;
Bước1;
Bước 5: Kết thúc.
Thuật toán tô màu theo dòng quét
Tô màu hình thang cơ bản
Tô màu n giác
Thuật toán tô màu theo dòng quét
Tô màu hình thang cơ bản:
Định nghĩa hình thang cơ bản: là hình thang có đáy song
song với một trục toạ độ.
Thuật toán:
Bước 1: y=y1;
Bước 2: Tính xM1, xM2
Bước 3: Nối M1 và M2 bằng mt
Bước 4: y=y+1;
Bước 5: Nếu y≤y2: Bước 2;
Bước 6: Kết thúc.
xAyy
yy
xAxD
xM +−
−
−
= )1(
121
xByy
yy
xBxC
xM +−
−
−
= )1(
122
D C
BA
xA xD xC xBO
y
x
y2
y1
(d)M1 M2y
Thuật toán tô màu theo dòng quét
Tô màu hình thang cơ bản:
Áp dụng: Tô màu đa giác A1A2...A9
Gọi thủ tục tô màu hình
thang cơ bản cho các hình
1, 2, 3, 4, 5, 6, 7, 8
A1
A2
A3
A4
A5
A6
A7
A8
A9
1 2
3
4
5
6
7
8
Thuật toán tô màu theo dòng quét
Tô màu n giác tổng quát:
Bài toán:
Input:
Cho các đỉnh của n giác:
A1 , A2 , ... , An
Cho màu tô (mt)
Output: Tô màu n giác
trên bằng màu mt.
A1
A3A2
A4
A5
A6
A7
A8
A9
O
y
ymax
ymin
M1 M2 M3 M4
M1 M2 M3 M4
M1 M2
M1 M2=M3 M4
Thuật toán tô màu theo dòng quét
Tô màu n giác tổng quát:
Thuật toán:
Bước 1: Tìm ymin, ymax của tung độ các đỉnh n giác.
Bước 2: y=ymin; (d)
Bước 3: Xác định các giao điểm của dòng quét (d) với
cạnh n giác, và sắp xếp tăng dần theo hoành độ, giả sử
là: M1, M2, ..., M2k
Bước 4: Nối các giao điểm M2i+1 và M2i+2 bằng mt
với i={0,1,... ,k-1}
Bước 5: Nếu y≤ ymax: Bước 3;
Bước 6: Kết thúc.
Thuật toán tô màu theo dòng quét
Tô màu n giác tổng quát:
Cài đặt: tham khảo tài liệu
