Đồ họa 2D - Các thuật toán xén hình (Phần 2)

ĐỒ HỌA 2D
CÁC THUẬT TOÁN XÉN HÌNH
Giảng viên : Bùi Tiến Lên
Xén đa giác
Thuật toán Sutherland-Hodegman
Bài toán
Input
Đa giác P
Output
P∩W
Trang 3
P
P
Nửa mặt phẳng trong/ngoài
Mỗi cạnh chia mặt phẳng ra làm hai phần gồm : nửa mặt 
phẳng trong và nửa mặt phẳng ngoài.
Trang 4
Nhận xét
Cửa sổ quan sát là giao của các nửa mặt phẳng trong 
của các cạnh.
Trang 5
cửa sổ
quan sát
Thuật toán
Dùng từng cạnh của cửa sổ lần lượt xén đa giác.
bước 1 : Xén trái
bước 2 : Xén phải
bước 3 : Xén dưới
bước 4 : Xén trên
Trang 6
Thuật toán
Trang 7
Xén đa giác bằng cạnh trái
Input
Đa giác IN = {p0, p1, ... , pn-1}
Output
Đa giác OUT = IN ∩W
Trang 8
Thuật toán xén đa giác bằng cạnh trái
bước 1
OUT = {}
bước 2
p : p0 ... pn-1
s là đỉnh kề trước của p
th1 : p bên trong, s bên trong
Trang 9
th2 : p bên ngoài, s bên trong
th3 : p bên ngoài, s bên ngoài
th4 : p bên trong, s bên ngoài
Trường hợp 1
s
Trang 10
p
OUT = {……………}
Trường hợp 2
Trang 11
p
s
i
OUT = {……………}
Trường hợp 3
p
Trang 12
s
OUT = {……………}
Trường hợp 4
p
s
i
Trang 13
OUT = {……………}
Ví dụ
Xén đa giác ABCDEF bằng cửa sổ hình chữ nhật.
A
B
Trang 14
CD
E
F
Ví dụ
A
B
G
Vì
A ngoài, F trong
Trang 15
CD
E
F
Nên
OUT = {G}
Ví dụ
A
B
G
H
Vì
B trong, A ngoài
Trang 16
CD
E
F
Nên
OUT = {GHB}
Ví dụ
A
B
G
H
Vì
C trong, B trong
Trang 17
CD
E
F
Nên
OUT = {GHBC}
Ví dụ
A
B
G
H
Vì
D ngoài, C trong
Trang 18
CD
E
F
I
Nên
OUT = {GHBCI}
Ví dụ
A
B
G
H
Vì
E ngoài, D ngoài
Trang 19
CD
E
F
I
Nên
OUT = {GHBCI}
Ví dụ
A
B
G
H
Vì
F trong, E ngoài
Trang 20
CD
E
F
I
J
Nên
OUT = {GHBCIJF}
Công thức
Trang 21