Thứ Ba, ngày 19 tháng 5 năm 2009

Kiểm tra hai hình chử nhật chồng nhau

Có những vấn đề tưởng chừng nhỏ nhưng đôi khi lại làm ta đau đầu. Bài viết này đề cập tới một trong những rắc rối đó. Yêu cầu kiểm tra xem hai hình chử nhật có đè (overlap) lên nhau không coi bộ là một bài toán khá đơn giản. Tuy nhiên ứng dụng của nó rất rộng rãi, đơn cử khá rỏ là hệ điều hành Window khi xử lý với các cửa sổ nó cũng phải liên tục kiểm tra overlap. Với các thông tin về tọa độ đỉnh, chiều dài cạnh đã cho của hai hình chử nhật, chỉ với một đống phép so sách nhập nhằng ta có thể dễ dàng tìm ra đáp án. Trong điều kiện tốc độ tính toán hiện nay của PC dám chắc hầu hết các lập trình viên thông thường cho đây là một bài toán có vẻ như quá tầm thường. Chính vì suy nghĩ đó mà mới có sự phân biệt giữa coder và programmer :), và chắc chắn rằng Window đã không thể tồn tại tới hôm nay nếu nó được tạo ra theo cách làm đó. Vậy giải pháp cho vấn đề là gì? Nó chỉ đơn giản là một phát biểu như sau:

"Nếu bạn thực hiện phép trừ tọa độ x hoặc y tương ứng với các đỉnh đối diện của hai hình chử nhật cho nhau, nếu kết quả có dấu giống nhau thì hai hình chử nhật không overlap theo trục tọa độ đó"

- Mã giả:

if ( (sign(TopLeftX1 - BottomRightX2) != sign(BottomRightX1- TopLeftX2)) &&
(sign(TopLeftY1 - BottomRightY2) != sign(BottomRightY1 - TopLeftY2)) )
return(1);

- Source code C:




Binh Nguyen - Bioz

Cảm nhận:

0 thảo luận:

Đăng nhận xét

chia sẻ cho chúng tôi ý tưởng hay khó khăn của bạn ...