Làm cách nào để kiểm tra xem có bất kỳ điểm nào (hoặc một phần) của một đường thẳng hay chạm vào hình chữ nhật

Question

Tôi muốn kiểm tra xem một dòng (hoặc bất kỳ điểm nào của một đường) nằm trong hình chữ nhật hay cắt hình chữ nhật.

Tôi có (x0, y0) và (x1, y1) làm điểm bắt đầu và kết thúc của một dòng. Ngoài ra, (rìu, ay) và (bx, bởi) là điểm trên bên trái và phía dưới bên phải của hình chữ nhật

Ví dụ,

 ____________ 
    |   | 
---|-----  | Result: true 
    |   | 
    |____________| 

    /
    _/__________ 
|/   | 
/   |  Result: true 
/|   | 
|____________| 


    ____________ 
    |   | 
    | -------- | Result: true 
    |   | 
    |____________| ----------  Result: false 

bất cứ ai có thể đề xuất làm thế nào để làm điều này? Tôi không muốn biết đó là điểm nào, tôi chỉ muốn biết liệu nó có hay không.

Cảm ơn rất nhiều sự giúp đỡ

Answer 1

Các trường hợp đầu tiên và thứ ba là tầm thường - chỉ cần trả về true nếu một trong hai thiết bị đầu cuối của đường nằm trong hộp (ví dụ:> ax và ay, < bx và bằng).

Thứ hai trình bày sự cố - chúng tôi không thể dựa vào điểm cuối của tuyến của chúng tôi nữa. Trong trường hợp này, chúng ta sẽ phải kiểm tra đường thẳng với mỗi cạnh của hình chữ nhật.

Phương trình cho dòng của chúng tôi sẽ là (x1 - x0)*x + (y1 - y0)*y + x0*y0 - x1*y1 = 0 và chúng tôi có thể xây dựng một phương trình tương tự cho mỗi bên của hình chữ nhật bằng các góc. Sau đó, thay thế phương trình cho các cạnh của hình chữ nhật vào dòng của chúng ta sẽ cho chúng ta giao lộ.

Cuối cùng, chúng tôi kiểm tra để đảm bảo rằng điểm nằm trong giới hạn của cạnh của hình chữ nhật, và tương tự như vậy trong đoạn đường chúng tôi đang xem xét.

Có một tài khoản chi tiết hơn về điều này trong this discussion.