Đang chuẩn bị liên kết để tải về tài liệu:
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 ≤. | CHƯƠNG III XÉN HÌNH 3.1. ĐẶT VẤN ĐỀ Cho một miền D G Rn và F là một hình trong Rn F G Rn . Ta gọi F n 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 Ux y e R2 X min x X max r 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 y y1 y 2 - y1 . t t e 0 1 Do đó F có thể được viết dưới dạng F x y e 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à nghiệm của hệ bất phương trình theo t Xmin x1 x2 -x1 .t Xmax Ymin y1 y2 - y1 . t Ymax 0 t 1 Gọi N là tập nghiệm của hệ phương trình trên. Nếu N 0 thì ClipD F 0 Nếu N 0 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 . t1 Py y1 y2 - y1 . t1 Qx x1 x2 - x1 . 12 Qy y1 y2 - y1 . 12 thì ClipD F PQ Hình 3.1 3.2.1.1. Thuật toán Cohen - Sutherland Chia mặt phang 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ổ Bit 2 Qui định vùng nằm bên phải cửa sổ Bit 3 Qui định vùng nằm bên dưới cửa sổ Bit 4 Qui định vùng nằm bên trên cửa sổ Xét điểm P e R2 100 100 101 1 000 000 001 1 010 010 011 1 Hình 3.2 Pleft 1 nãúu Px Xmin 0 Ng ảilaũi PRight 1 nãúu Px X max 0 Ng ảilaũi PBelow . 1 S 0 nãúu Py Ymin Ng ảilarũi PAbove 1 S 0 nãúu Py Ymax Ng ảilarũ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 e 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 0 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