Thuật toán gọn gàng để tìm khoảng thời gian chồng chéo là gì?

Question

Tôi chắc chắn điều này phải được yêu cầu trước đó, nhưng tôi không tìm thấy nó: Tôi chỉ tìm kiếm các câu hỏi liên quan, nhưng khó hơn.

Tôi đã có bốn điểm, đại diện cho hai dòng như thế này:

 A   C  B D 
|------*---|-----+----|-*---+---|----------| 
0   10   20  30   40 

Vì vậy, trong ví dụ này, AB = {7, 21} và CD = {16,26}. (Các dòng có thể có bất kỳ mối quan hệ nào với nhau và bất kỳ kích thước nào.) Tôi muốn tìm hiểu xem chúng có trùng lặp hay không và bao nhiêu nếu có. (Trong ví dụ, câu trả lời sẽ là 5.) Giải pháp hiện tại của tôi liên quan đến một loạt các bước phức tạp nếu sau đó, và tôi không thể không nghĩ rằng có một giải pháp số học tốt đẹp. Lanhung?

(. PS Thực sự, tôi đang làm ngã bounding-box, nhưng nếu tôi có thể nhận được nó trong một chiều, người kia sẽ giống nhau, rõ ràng)

Answer 1

Hãy thử điều này:

intersects = (max(a,b) > min(c,d)) && (min(a,b) < max(c,d)) 
overlap = min(max(a,b), max(c,d)) - max(min(c,d), min(a,b)) 

Nếu bạn có thể giả định a <= b và c <= d:

intersects = (b > c) && (a < d) 
overlap = min(b, d) - max(c, a) 

bạn cũng có thể tính toán intersects như sau:

intersects = (overlap > 0) 

Answer 2

Đoạn đường là giao điểm của hai tia đối lập (hai đường nửa vô hạn theo hướng ngược nhau). Bạn có hai đoạn thẳng cắt nhau - kết quả là giao điểm của tất cả 4 tia. Vì vậy, bạn có thể nhân tố mã của bạn là ba điểm giao nhau liên tiếp: phần bên trái của các tia đối diện bên trái giao nhau với các bên phải của các tia đối diện.

(Đây là một cách khác để nêu câu trả lời bây giờ chấp nhận.)