Đồ họa Raster - Các thuật toán vẽ đường thẳng (Phần 4)

ĐỒ HỌA RASTER
CÁC THUẬT TOÁN TÔ MÀU
Giảng viên : Bùi Tiến Lên
Bài toán tô màu
Tô màu là thao tác tìm các điểm sáng “nằm bên trong” 
một vùng khép kín.
Input :
Vùng S
Output : 
{(x1, y1), (x2, y2) … (xn, yn)}
Trang 2
Các hướng tiếp cận
Có hai phương pháp 
- Tô màu theo lân cận
- Tô màu theo dòng quét
Trang 3
Tô màu theo lân cận
Lân cận là gì ?
Có hai loại lân cận : lân cận 4 và lân cận 8.
Lân cận 4
N4(x, y) = {(x-1, y), (x, y+1), (x+1, y), (x, y-1)}
Lân cận 8
N8(x, y) = {(x-1, y), (x-1, y+1), (x, y+1), (x+1, y+1), (x+1, y), 
(x+1, y-1), (x, y-1), (x-1, y-1)}
Trang 5
(x,y) phảitrái
dưới
trên
x
y (x,y)
x
y
trái
Thuật toán đệ qui
bước 1 Kẻ biên vùng cần tô
bước 2 Xác định một điểm (x, y) nằm bên trong vùng cần 
tô
bươc 3 Tô điểm (x, y), sau đó tô loang sang những điểm 
lân cận
Trang 6
x
y
Cài đặt đệ qui
// To loang
void BoundaryFill(CDC *pDC, int x, int y, 
int fill_color, int boundary_color)
{
int color;
color = pDC->GetPixel(x, y);
if((color != fill_color) && (color != boundary_color))
{
pDC->SetPixel(x, y, fill_color);
Trang 7
BoundaryFill(pDC, x-1, y, fill_color, boundary_color);
BoundaryFill(pDC, x, y+1, fill_color, boundary_color);
BoundaryFill(pDC, x+1, y, fill_color, boundary_color);
BoundaryFill(pDC, x, y-1, fill_color, boundary_color);
}
}
Nhận xét thuật toán đệ qui
Ưu điểm
Có thể tô vùng có hình dạng 
bất kỳ.
Khuyết điểm
Không thể dùng để tô các 
vùng có kích thước lớn.
Trang 8
kích thước 
!
Thuật toán cải tiến
bước 1
Cất điểm hạt giống đầu tiên vào kho.
bước 2
Lặp nếu kho không rỗng
- c1 Lấy điểm hạt giống.
- c Tô điểm hạt giống sau đó tô loang sang trái và 
Trang 9
2
sang phải.
- c3 Bổ sung những điểm hạt giống mới vào kho từ 
dòng trên và dòng dưới.
Thuật toán cải tiến
hạt giống : điểm sáng
kho : chứa các điểm hạt giống
Trang 10
Thuật toán cải tiến
biên biên
Minh họa tô loang
Trang 11
Thuật toán cải tiến
Tiêu chuẩn để là điểm hạt giống
1. Điểm này chưa được tô và không phải điểm biên.
2. Điểm này thoả :
- Điểm trái đầu tiên.
- hoặc bên trái của nó là điểm biên (nếu nó không 
phải là điểm trái đầu tiên).
Trang 12
Thuật toán cải tiến
biên biên
Minh họa bổ sung những điểm hạt giống mới
Trang 13
biên biên
biên
hạt giống
Tô theo lân cận - Một số vấn đề
Sử dụng 
lân cận nào ?
Trang 14
Tô theo lân cận - Một số vấn đề
Đường biên
màu gì ?
Trang 15
Tô theo lân cận - Một số vấn đề
Trang 16
Tô màu theo dòng quét
Khái niệm dòng quét
Dòng quét là dòng điểm sáng trên màn hình
y
Trang 18
Tô hình chữ nhật
l r
ty
Trang 19
b
y
Tô hình tam giác
Input
(X1, Y1), (X2, Y2), (X3, Y3)
Cách tô
bước 1 : Sắp xếp các đỉnh
Y ≤ Y ≤ Y
Trang 20
1 2 3
bước 2 : Phân trường hợp
Theo tung độ
Tô hình tam giác
Y1 = Y2 = Y3
1 3 2
Y1 < Y2 = Y3
1
2 3
Trang 21
Y1 = Y2 < Y3
12
3
Y1 < Y2 < Y3
1
2
3
Tô hình tam giác
1 3 2Y1
X X
Trang 22
Tô tam giác (Y1 = Y2 = Y3)
1. Tìm Xmin, Xmax
2. Tô dòng Y1 bắt đầu tại cột Xmin, kết thúc tại cột Xmax
min max
Tô hình tam giác
Tô tam giác (Y1 < Y2 = Y3)
Lặp y : Y1 … Y2
1. Tìm hoành độ giao điểm xl, xr
giữa dòng quét y với các cạnh 
2 3
Y2
y
Trang 23
trái và cạnh phải của tam giác.
2. Tô dòng y bắt đầu tại cột xl, kết 
thúc tại cột xr.1
Y1y
xl xr
Tô hình tam giác
Ví dụ 
Các hoành độ giao điểm của các dòng quét với cạnh 
(2, 2), (11, 6).
6
5
4
2
Trang 24
3
2
1
8
4
17
4
26
4
35
4
44
4
Tô hình tam giác
12
cumoi
1
XX
k
với
kxx
X là đầu x
điểm giao độ hoành tính Cách
−
=
+=
1
2
Trang 25
12 YY −
Tô hình tam giác
2
3
Y2
Y3
Trang 26
1
Y1y
Tô hình đa giác lồi
Cách tô
1. Chia đa giác lồi có n đỉnh 
{p0, p1, ... , pn-1} thành n-2 
tam giác.
- ∆1 p0p1p2
- ∆ p p p
p
0
p
1
p
2
p
3
Trang 27
2 0 2 3
- ...
- ∆i p0pipi+1
- ...
- ∆n-2 p0pn-2pn-1
2. Tô từng tam giác.
p
1
p
2
p
3
p
n-2
p
n-1
p
0
Tô hình đa giác
Nguyên lý chia tam giác
Mọi đa giác không tự cắt đều có thể phân chia thành các 
tam giác.
Trang 28
Thuật toán tô đa giác tổng quát
Thuật toán
bước 1 Tìm ymin và ymax
ymin = min{yi, (xi, yi) ∈ P}
ymax = max{yi, (xi, yi) ∈ P}
bước 2 Tô từng dòng
ymax
y
I1 I2 I3 I4
P
Trang 30
Lặp y : ymin … ymax
c1 Tìm các giao điểm.
c2 Sắp xếp các giao điểm.
c3 Tô các đoạn thẳng.
yminy
Lưu ý
Bỏ cạnh nằm ngang
Trang 31
bỏ
bỏ
Lưu ý
Dòng quét đi qua đỉnh
a
b
c
d
e
Trang 32
f
g
h
I1 I2 I3 I4
Bình thường
y
Lưu ý
Dòng quét đi qua đỉnh
a
b
c
d
e
I1 I2 I3 I4 I5
Lỗi
y
Trang 33
f
g
h
Lưu ý
Cắt bớt cạnh c theo trục y 1 đơn vị
a
b
c
d
e
I1 I2 I3 I41y
1
Trang 34
f
g
h
Ví dụ
6
7
8
9
b
c
d
{(1, 1) (2, 7) (4, 9) (7, 9) (9, 5) (9, 1) (7, 1) (5, 5) (4, 1)}
Trang 351 2 3 4 5 6 7 8 9
1
2
3
4
5
a
e
f
gh
i
Tiền xử lý 1
6
7
8
9
b
d
Loại bỏ các cạnh
c
Trang 361 2 3 4 5 6 7 8 9
1
2
3
4
5
a
e
gh
{c, f, i}
fi
Tiền xử lý 2
6
7
8
9
b
d
Trang 371 2 3 4 5 6 7 8 9
1
2
3
4
5 Xử lý các cạnh
{a, e}a
e
gh
Tô
6
7
8
9
b
d
k=1
k=-3/4
Trang 381 2 3 4 5 6 7 8 9
1
2
3
4
5
a
e
gh
k=1/6
k=0
k=-1/2k=1/4
Thông tin cạnh đa giác
cạnh ylower yupper xlower k
a 1 7 1 1/6
b 7 9 2 1
d 5 9 9 -3/4
e 1 5 9 0
g 1 5 7 -1/2
Trang 39
h 1 5 4 1/4
Thông tin các cạnh đa giác
cạnh ylower yupper xlower k
a 1 6 1 1/6
b 7 9 2 1
d 5 9 9 -3/4
e 1 4 9 0
g 1 5 7 -1/2
Trang 40
h 1 5 4 1/4
Phương trình đoạn thẳng
F(x, y) = (Y2 – Y1)(x – X1) – (X2 – X1)(y – Y1)
(X2,Y2)
Trang 41
(X1,Y1)
Xác định bên trong tam giác như thế nào ? 
(X3,Y3)
Trang 42
(X1,Y1)
(X2,Y2)
Chiều các đỉnh của tam giác
Tính diện tích tam giác
(X2,Y2) (X2,Y2)
( ) ( ) ( )
2
yyxyyxyyx
S 213132321
−+−+−
=
Trang 43
S>0 S<0(X1,Y1)
(X3,Y3)
(X1,Y1)
(X3,Y3)
Thuật toán
1. Tìm xmin, xmax, ymin, ymax
2. Lặp y : ymin … ymax, x : xmin … xmax
Nếu (x, y) nằm bên trong tam giác thì
Tô (x, y)
y
Trang 44xmin xmax
ymin
max