Tôi đang viết một chương trình bằng Python. Tôi có một loạt các hình dạng (đa giác, được định nghĩa là một chuỗi các cặp tọa độ) và tôi cần phải biết liệu chúng có chồng chéo lên một hình chữ nhật cụ thể hay không.Sử dụng Python, làm cách nào để tôi biết hình chữ nhật và hình dạng có trùng lặp không?
Có thuật toán dễ dàng để xử lý việc này không? Hoặc, tốt hơn, có một thư viện Python thuần túy có thể xử lý các tính toán này cho tôi không?
Giả sử "hình dạng tùy ý" của bạn thực sự là đa giác (được mô tả là cặp tọa độ), xác định xem chúng trùng nhau (trong bất kỳ ngôn ngữ nào) là một phép tính tương đối nhỏ. Bạn chỉ cần tính toán nếu bất kỳ bên nào của đa giác A cắt bất kỳ phía nào của đa giác B.
Nếu bạn cần một ví dụ, có hướng dẫn khá kỹ lưỡng tại the Drexel Math Forum.
Có một số mô-đun Python có thể hỗ trợ bạn trong việc theo đuổi này, chẳng hạn như Sympy, Numpy, PyGame, v.v, nhưng tất cả đều khá nặng nếu đây là phép tính hình học duy nhất bạn cần thực hiện.
"Giao nhau" không hoạt động, trong trường hợp đa giác A chứa đa giác B. –
@Chris Kiểm tra điểm giao nhau giữa các điểm cuối của cả hai bên bạn đang kiểm tra ('xA1 < = xInt <= xA2 và xB1 <= xInt <= xB2 và yA1 <= yInt <= yA2 và yB1 <= yInt <= yB2') – user470379
@Chris: Nếu bạn muốn bao gồm ngăn chặn, bạn có thể sử dụng đường giao nhau bên trong để đa giác. Nó thêm thời gian tính toán, nhưng không phức tạp. –
Hình dạng riêng của bạn có thực sự là hình dạng độc đáo, hay đúng hơn là đa giác? "Chuỗi các cặp tọa độ" có mô tả các đỉnh của các đa giác này không? Nếu không, nó là gì? –
Làm rõ trong bài toán –