tailieunhanh - 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). . XÉN ĐOẠN THẲNG VÀO VÙNG HÌNH CHỮ NHẬT CỦA R2 . 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 . ĐẶ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 . . XÉN ĐOẠN THẲNG VÀO VÙNG HÌNH CHỮ NHẬT CỦA R2 . 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 . 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 . 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 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