Bài giảng Đồ họa Raster: Các thuật toán tô màu - Bùi Tiến Lên

Ồ Ọ Ồ Ọ

Đ H A RASTER Đ H A RASTER

CÁC THU T TOÁN TÔ MÀU 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 Bài toán tô màu

” m t vùng ể n m bên trong ằ ộ

Tô màu là thao tác tìm các đi m sáng “ khép kín. Input :

Vùng S

Output :

{(x1, y1), (x2, y2) … (xn, yn)}

Trang 22 Trang

ng ti p c n Các hCá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 33 Trang

Tô màu theo lân c nậ Tô màu theo lân c nậ

Lân c n là gì ? ậ 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)}

trái trên

y y trái (x,y) (x,y) ph iả

dư iớ

Trang 55 Trang

x x

ậThu t toán ậ Thu t toán

ệ qui đđ qui ệ

ầ

ộ đi m ể (x, y) n m bên trong vùng c n tô ằ ầ

bư c 1ớ K biên vùng c n tô ẻ bư c 2ớ Xác đ nh m t ị bươc 3 Tô đi m ể (x, y), sau đó tô loang sang nh ng ữ đi m lân c n ậ ể

y

x

Trang 66 Trang

ệ qui Cài Cài đđ t ặ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); 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);

}

}

Trang 77 Trang

Nh n xét thu t toán Nh n xét thu t toán

ậ ậ

ậ ậ

ệ qui đđ qui ệ

Ưu đi mể

Có th tô vùng có hình d ng b t

đ tô các vùng

ể

ạ

ấ

ể

kỳ.

Khuy t ế đi mể Không th dùng ể ớ ớ

có kích thư c l n.

kích thöôùc ! kích thöôùc !

Trang 88 Trang

Thu t toán c i ti n Thu t toán c i ti n

ả ế ả ế

ậ ậ

bư c 1ớ

kho. C t ấ đi m ể h t gi ng ố đ u tiên vào ạ ầ

bư c 2ớ

L pặ n u ế kho không r ngỗ

ạ

ạ ố sau đó tô loang sang trái và ố . - c1 L y ấ đi m ể h t gi ng - c2 Tô đi m ể h t gi ng

kho t sang ph i.ả ổ ữ đi m ể h t gi ng ố m i vào ớ ạ ừ

- c3 B sung nh ng dòng trên và dòng dư i.ớ

Trang 99 Trang

Thu t toán c i ti n 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 1010 Trang

Thu t toán c i ti n Thu t toán c i ti n

ả ế ả ế

ậ ậ

biên

biên

Minh h a tô loang ọ

Trang 1111 Trang

Thu t toán c i ti n Thu t toán c i ti n

ả ế ả ế

ậ ậ

ể

ợ ả đi m biên. ể

ể ể

đi m biên (n u nó không ph i là ể ế ả

đi m trái 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 2. Đi m này tho : ả - Đi m trái đ u tiên. ầ ể - ho c bên trái c a nó là ặ ủ đ u tiên). ầ ể

Trang 1212 Trang

Thu t toán c i ti n 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ớ ạ

biên

biên

biên

h t gi ng ạ ố

Trang 1313 Trang

Tô theo lân c n - M t s v n Tô theo lân c n - M t s v n

ộ ố ấ đđềề ộ ố ấ

ậ ậ

S d ng ử ụ lân c n nào ? ậ

Trang 1414 Trang

Tô theo lân c n - M t s v n Tô theo lân c n - M t s v n

ộ ố ấ đđềề ộ ố ấ

ậ ậ

ờ

Đư ng biên màu gì ?

Trang 1515 Trang

Tô theo lân c n - M t s v n Tô theo lân c n - M t s v n

ộ ố ấ đđềề ộ ố ấ

ậ ậ

Trang 1616 Trang

Tô màu theo dòng quét Tô màu theo dòng quét

Khái ni m 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 1818 Trang

Tô hình ch nh t ữ ậ Tô hình ch nh t ữ ậ

l

r

t y

y

b

Trang 1919 Trang

Tô hình tam giác Tô hình tam giác

Input

(X1, Y1), (X2, Y2), (X3, Y3)

đ nhỉ

ờ ư ng h p ợ

Cách tô bư c 1 : S p x p các ớ ắ ế Y2 £ Y1 £ Y3 bư c 2 : Phân tr ớ Theo tung độ

Trang 2020 Trang

Tô hình tam giác Tô hình tam giác

Y1 = Y2 = Y3 Y1 < Y2 = Y3

2 3

1 3 2

1

Y1 < Y2 < Y3 3 Y1 = Y2 < Y3 3

2

1 2 1

Trang 2121 Trang

Tô hình tam giác Tô hình tam giác

1 3 2

Y1

Xmin Xmax

min, k t thúc t ế

max

i c t X i c t X ầ ạ ộ ạ ộ Tô tam giác (Y1 = Y2 = Y3) 1. Tìm Xmin, Xmax 2. Tô dòng Y1 b t ắ đ u t

Trang 2222 Trang

Tô hình tam giác Tô hình tam giác

2 3

l, xr gi a ữ

Y2

y

Tô tam giác (Y1 < Y2 = Y3) L pặ y : Y1 … Y2 1. Tìm hoành đ giao ộ ớ

đi m xể ạ

dòng quét y v i các c nh trái và c nh ph i c a tam giác. ạ

ả ủ

2. Tô dòng y b t ắ đ u t

ầ ạ ộ l, k t ế i c t x

y Y1

thúc t

ạ ộ r. i c t x

1

xl xr

Trang 2323 Trang

Tô hình tam giác 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).

2

6 5 4 3 2 1

8 4 17 4 26 4 35 4 44 4

Trang 2424 Trang

Tô hình tam giác Tô hình tam giác

Caùch tính hoaønh ñoä giao ñieåm

2 x

cu

moi

X laø ñaàu 1 = + x x k

vôùi

- = 1 k - X 2 Y 2 X 1 Y 1

Trang 2525 Trang

Tô hình tam giác Tô hình tam giác

3

Y3

2

Y2

y Y1

1

Trang 2626 Trang

a giác l Tô hình đđa giác l Tô hình

iồ iồ

p0

Cách tô 1. Chia đa giác l

đ nh {p

i có n

ỉ

p3

0, ồ p1, ... , pn-1} thành n-2 tam giác.

p1

p2

- D

1 p0p1p2 2 p0p2p3

-

...

p0

- D

i p0pipi+1

p1

-

...

pn-1

- D

p2

1. Tô t ng tam giác.

pn-2

n-2 p0pn-2pn-1 ừ

p3

- D

Trang 2727 Trang

a giác Tô hình đđa giác Tô hình

Nguyên lý chia tam giác c t M i ọ đa giác không t ự ắ đ u có th phân chia thành các tam giác. ề ể

Trang 2828 Trang

ậ

ậThu t toán tô Thu t toán tô

đđa giác t ng quát a giác t ng quát ổ ổ

ậThu t toán ậ Thu t toán

I1

I2 I3

I4

P}

ymax

P}

y

bư c 1ớ Tìm ymin và ymax ymin = min{yi, (xi, yi) ˛ ymax = max{yi, (xi, yi) ˛

ừ

P

bư c 2ớ Tô t ng dòng L pặ y : ymin … ymax

ắ

đi m.ể

ẳ

ạ

c1 Tìm các giao đi m.ể c2 S p x p các giao ế c3 Tô các đo n th ng.

y ymin

Trang 3030 Trang

LLưưu ýu ý

B c nh n m ngang ằ ỏ ạ

bỏ

bỏ

Trang 3131 Trang

LLưưu ýu ý

Dòng quét đi qua đ nhỉ

b

d

c a e

y I2 I3 I1 I4

Bình thư ngờ

h f

g

Trang 3232 Trang

LLưưu ýu ý

Dòng quét đi qua đ nhỉ

L iỗ

b

y d I1 I4 I5

I2 I3 c e a

h f

g

Trang 3333 Trang

LLưưu ýu ý

C t b t c nh c theo tr c y ắ ớ ạ ụ 1 đơn vị

b

d 1 1y I1 I2 I3 I4

c e a

h f

g

Trang 3434 Trang

Ví dụVí dụ

{(1, 1) (2, 7) (4, 9) (7, 9) (9, 5) (9, 1) (7, 1) (5, 5) (4, 1)}

9

c

8

b

7

6

5

d

4

3

a

e

2

1

h g

8

1

2

3

4

5

6

7

9

i f

Trang 3535 Trang

Ti n x lý 1 ề ử Ti n x lý 1 ề ử

9

c

8

b

7

6

d

5

ạ

4

3

Lo i b các c nh ạ ỏ {c, f, i} a

e

2

1

h g

8

1

2

3

4

5

6

7

9

i f

Trang 3636 Trang

Ti n x lý 2 ề ử Ti n x lý 2 ề ử

9

8

b

7

6

5

d

ạ

4

3

a X lý các c nh ử {a, e}

e

2

1

1

2

3

4

5

6

7

8

9

h g

Trang 3737 Trang

TôTô

9

8

b

k=1

7

d

k=-3/4

6

5

4

a

k=1/6

k=-1/2

3

e

k=1/4

k=0

2

1

1

2

3

4

5

6

7

8

9

h g

Trang 3838 Trang

a giác đđa giác

Thông tin c nh ạ Thông tin c nh ạ

caïnh

k

ylower

yupper

xlower

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

h

1

5

4

1/4

Trang 3939 Trang

a giác đđa giác

Thông tin các c nh ạ Thông tin các c nh ạ

caïnh

k

ylower

yupper

xlower

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

h

1

5

4

1/4

Trang 4040 Trang

PhPhươương trình

o n th ng ng trình đđo n th ng ạ ạ

ẳ ẳ

F(x, y) = (Y2 – Y1)(x – X1) – (X2 – X1)(y – Y1)

(X2,Y2)

(X1,Y1)

Trang 4141 Trang

ịnh bên trong tam giác nh Xác Xác đđ nh bên trong tam giác nh ị

ế th nào ? ế ưư th nào ?

(X3,Y3)

(X2,Y2)

(X1,Y1)

Trang 4242 Trang

ủ

ềChi u các ề Chi u các

ủnh c a tam giác đđ nh c a tam giác ỉ ỉ

Tính di n tích tam giác ệ

)

)

)

+

+

- - -

( yx 1 2

y 3

y 1

( yx 3 1

y 2

=

S

( yx 2 3 2 (X2,Y2)

(X2,Y2)

(X3,Y3)

(X3,Y3)

(X1,Y1)

(X1,Y1)

S>0 S<0

Trang 4343 Trang

ậThu t toán ậ Thu t toán

1. Tìm xmin, xmax, ymin, ymax 2. L pặ y : ymin … ymax, x : xmin … xmax

thì N uế (x, y) n m bên trong tam giác ằ

Tô (x, y)

ymax

ymin

Trang 4444 Trang

xmin xmax