CHƯƠNG III XÉN HÌNH

ĐẶT VẤN ĐỀ Cho một miền D ⊂ Rn và F là một hình trong Rn (F ⊂ Rn). Ta gọi F ∩ D là hình có được từ F bằng cách xén vào trong D và ký hiệu là ClipD(F). Bài toán đặt ra là xác định ClipD(F). 3.2. XÉN ĐOẠN THẲNG VÀO VÙNG HÌNH CHỮ NHẬT CỦA R2 3.2.1. Cạnh của hình chữ nhật song song với các trục tọa độ Lúc này: D = ⎨( x, y ) ∈ R 2 |⎩ ⎧ X min ≤ x ≤ X max ⎫ ⎬ Y min ≤ y ≤...
Nội dung trích xuất từ tài liệu:
CHƯƠNG III XÉN HÌNH CHƯƠNG III XÉN HÌNH3.1. ĐẶT VẤN ĐỀ Cho một miền D ⊂ Rn và F là một hình trong Rn (F ⊂ Rn). Ta gọi F ∩ D là hình cóđược từ F bằng cách xén vào trong D và ký hiệu là ClipD(F). Bài toán đặt ra là xác định ClipD(F).3.2. XÉN ĐOẠN THẲNG VÀO VÙNG HÌNH CHỮ NHẬT CỦA R23.2.1. Cạnh của hình chữ nhật song song với các trục tọa độ Lúc này: X min ≤ x ≤ X max ⎫ ⎧ D = ⎨( x, y ) ∈ R 2 | ⎬ Y min ≤ y ≤ Y max ⎭ ⎩và F là đoạn thẳng nối 2 điểm (x1,y1), (x2,y2) nên phương trình của F là: ⎧ x = x1 + ( x 2 − x1). t t ∈ [0,1] ⎨ ⎩ y = y1 + ( y 2 − y1). t Do đó, F có thể được viết dưới dạng: F = {(x,y) ∈ R2 | x = x1 + (x2 -x1).t; y = y1 + (y2 -y1).t; 0 ≤ t ≤ 1} Khi đó, giao điểm của F và D chính là Anghiệm của hệ bất phương trình (theo t): P y yMax ⎧Xmin ≤ x1 + (x2 - x1). t ≤ Xmax ⎪ Q ⎨ Ymin ≤ y1 + (y2 - y1). t ≤ Ymax ⎪ yMin 0≤ t ≤1 ⎩ B Gọi N là tập nghiệm của hệ phương trình xMin xMax Xtrên. Hình 3.1 Nếu N = ∅ thì ClipD(F) = ∅ Nếu N ≠ ∅ thì N = [t1, t2] (t1 ≤ t2) Gọi P, Q là 2 giao điểm xác định bởi: Chương III. Xén hình ⎧ Px = x1 + ( x 2 − x1). t 1 ⎧ Qx = x1 + ( x 2 − x1). t 2 ⎨ ⎨ ⎩ Py = y1 + ( y 2 − y1). t 1 ⎩Qy = y1 + ( y 2 − y1). t 2thì: ClipD(F) = PQ (Hình 3.1)3.2.1.1. Thuật toán Cohen - Sutherland• Chia mặt phẳng ra làm 9 vùng, mỗi vùng đánh một mã nhị phân 4 bit (hình 3.2). Bit 1: Qui định vùng nằm bên trái cửa sổ 100 101 100 Bit 2: Qui định vùng nằm bên phải cửa sổ 1 0 0 000 001 000 Bit 3: Qui định vùng nằm bên dưới cửa sổ 0 0 1 Bit 4: Qui định vùng nằm bên trên cửa sổ 010 010 011 1 0 0• Xét điểm P ∈ R2 : Hình 3.2 ⎧1 nãúuP < X min Pleft =⎨ x ⎩0 Ngæåüc laûi ⎧1 nãúuP > X max PRight =⎨ x ⎩0 Ngæåüc laûi ⎧1 nãúuPy < Y min PBelow = ⎨ ⎩0 Ngæåüc laûi ⎧1 nãúuPy > Y max PAbove = ⎨ ⎩0 Ngæåüc laûi• Xét đoạn thẳng AB, ta có các trường hợp sau: i/ Nếu Mã(A) = Mã(B) = 0000 thì AB ∈ D ⇒ ClipD(F) = AB ii/ Nếu Mã(A) AND Mã(B) ≠ 0000 thì đoạn AB nằm hoàn toàn bên ngoài hình chữ nhật ⇒ ClipD(F) = ∅ Chú ý: Phép toán AND là phép toán Logic giữa các bit. iii/ Nếu (Mã(A) AND Mã(B) = 0000) và (Mã(A) ≠ 0000 hoặc Mã(B) ≠ 0000) thì: Giả sử Mã(A) ≠ 0000 ⇔ A nằm ngoài hình chữ nhật. ♦ Nếu Aleft = 1 : thay A bởi điểm nằm trên đoạn AB và cắt cạnh trái (nối dài) của hình chữ nhật. 33 Chương III. Xén hình ♦ Nếu Aright = 1: thay A bởi điểm nằm trên đoạn AB cắt cạnh phải (nối dài) của hình chữ nhật. ♦ Nếu ABelow = 1: thay A bởi điểm nằm trên đoạn AB và cắt cạnh dưới (nối dài) của hình chữ nhật. ♦ Nếu AAbove = 1: thay A bởi điểm nằm trên đoạn AB và cắt cạnh trên (nối dài) của hình chữ nhật. Chú ý: Quá trình này được lặp lại: Sau mỗi lần lặp, ta phải tính lại mã của A.Nếu cần, phải đổi vai trò của A và B để đảm bảo A luôn luôn nằm bên ngoài hình chữnhật. Quá trình sẽ dừng khi xẩy ra một trong 2 trường hợp: i/ hoặc ii/3.2.1.2. Thuật toán chia nhị phân• Ý tưởng của thuật toán này tương tự như thuật toán tìm nghiệm bằng phương pháp chia nhị phân.• Mệnh đề: Cho M: trung điểm của đoạn AB, Mã(A) ≠ 0000, Mã(B) ≠ 0000, Mã(M) ≠ 0000 thì ta có: [Mã(A) AND Mã(M)] ≠ 0000 hoặc [Mã(M) AND Mã(B)] ≠ 0000. Ý nghĩa hình học của mệnh đề: Nếu cả ba điểm A, B, M đều ở ngoài hình chữnhật thì có ít nhất một đoạn hoàn toà ...