Kiểm tra 2 hình chữ nhật cắt nhau

[man_quangnam]

Class Retangle
{
public int X; //Top Postion
public int Y; //Top Postion
public int Height;
public int Width;
}
//
bool CheckRetangles(Retangle A, Retangle B)
{
////
//// ?????????????????????????????
////

return;
}

I need your help. Thanks so much.

[JackDaiHiep]

Tạm 1 phương án này nhé, nghĩ xem còn cách nào tốt hơn hay không

2 Hình chữ nhật A1B1C1D1 và A2B2C2D2

Nếu 1 cạnh A1 cắt 1 cạnh A2 thì là cắt nhau.

Vậy với 1 cạnh của A1 ta xem nó có cắt cạnh nào của A2 hay không ?

Xét 1 cạnh A1 và 1 cạnh A2 ( Ví dụ là đoạn A1B1 và A2B2 )

1.Lập phương trình đường thẳng của 2 cạnh ( ok ?)
2.Tìm giao điểm
3.Nếu không có giao điểm -> ok
4.Nếu có giao điểm M, xem giao điểm đó có nằm giữa A1B1 hay không( xem đoạn A1M+ B1M > A1B1)
5. Kếtthúc kiểm tra 1 lượt

Good-bye

[man_quangnam]

Mình làm thế này : Kiểm tra 4 đỉnh của hình B có nằm trong hình A không.
Muốn kiểm tra 1 đỉnh có nằm trong hình kia hay ko, mình làm thế này :
Point(X,Y) point;
- Nếu point.X >=A.X & point.X <=A.Width &point.Y >=A.Y & point.Y <=A.Height
===>> point nằm trong A

Mình làm như thế, nghĩ là giải quyết được vấn đề một cách chính xác rồi, nhưng người ra đề không chấp nhận vì giải thuật chưa hay.
Chưa kiểm tra nhưng thấy giải thuật của bạn có vẻ chưa gọn gàng lắm.
Mong mọi người cùng góp ý kiến thêm.

-----------------
Bài này mình post bên Box Giải thuật, không hiểu sao bị lạc qua đây. Nhờ mod chuyển qua dùm để có nhiều người tham gia hơn. Xin cám ơn.

[xuanhau]

Theo mình thì tốt nhất xây dựng giải thuật cho bài toán tổng quát với 2 hình bất kỳ có m và n cạnh đi. Câu trả lời sẽ có !

[trinhdiep]

bool CheckRetangles(Retangle a, Retangle b)
{
if(a.X>b.X||a.Y>b.Y)
return CheckRetangles(Retangle b, Retangle a)
//a và b ngoài nhau
if(a.X+a.Width<b.X||a.Y+a.Height<b.y)
return false;
//a ngoài b
if(a.X+a.Width>b.X+b.Width&&a.Y+a.Height>b.Y+b.Height)return false;
return true;
}

[The Old Man]

Có tính trường hợp sau không?

http://www.vanviet.com/THOISU/Chunhat.jpg

[man_quangnam]

Code của bác trinhdiep ngắn gọn và đẹp thật.
Bác TOM : Bài của bác trinhdiep đã giải quyết được yêu cầu của em.
Cám ơn mọi người rất nhiều.

[nck109]

Code của trinhdiep:


bool CheckRetangles(Retangle a, Retangle b)
{
if(a.X>b.X||a.Y>b.Y)
return CheckRetangles(Retangle b, Retangle a)
//a và b ngoài nhau
if(a.X+a.Width<b.X||a.Y+a.Height<b.y)
return false;
//a ngoài b
if(a.X+a.Width>b.X+b.Width&&a.Y+a.Height>b.Y+b.Height)return false;
return true;
}

Thử nhập dữ liệu như sau:
a.x = 3
a.y = 2
a.w = 3
a.h = 2

b.x = 2
b.y = 3
b.w = 3
b.y = 2

Bắt đầu:

(1)CheckRetangles(a.b)
____if(a.X > b.X || a.Y > b.Y) // a.x = 3 > b.x = 2 ĐÚNG
______(2)return CheckRetangles(b, a)
_________(3)CheckRetangles(b, a)
_____________if(b.x > a.x || b.y > a.x) // b.y = 3 > a.y = 2 ĐÚNG
______________(4) return CheckRetangles(a, b)
...

Chạy tay như thế là đúng hay sai??
(1) chạy 1 lúc sẽ gặp lại nó ở (4)
Vậy là (4) làm tiếp sẽ gặp lại nó ở những bước tiếp theo
Bao giờ kết thúc và cho kết quả?

Tui nghĩ nên sửa lại là

if(a.X>b.X && a.Y>b.Y)
return CheckRetangles(Retangle b, Retangle a)