Em giải bài tập về hình học trong lập trình python thì gặp một vấn đề mà em không thể giải quyết được, mong các bậc tiền bối giúp đỡ.
Em bị rối chỗ tìm giao điểm của 2 hình tam giác mà phương pháp này là thuật toán ngắn gọn và nhanh thì em tìm trên mạng rất rườm rà, chạy tốn thời gian rất nhiều. Em muốn thuật toán tìm giao điểm nhanh có thể trên thư viện shapely.geometry mà trên thư viện này chỉ trả về True False thôi. xin mọi người giúp em
Thuật toán tìm giao điểm của 2 hình tam giác
Hi @badaukf213
Tìm giao điểm của 2 tam giác là giao điểm gì à cậu? 
Ý cậu là tìm miền giao nhau giữa 2 tam giác, hay tìm điểm cắt giữa các cạnh?
Ngoài ra, nếu 2 tam giác trùng nhau, cậu kỳ vọng sẽ trả về gì? Nếu một tam giác nằm trọn vẹn trong tam giác còn lại, cậu sẽ kỳ vọng trả về gì?
4 Likes
tìm giao điểm ý mình là tìm giao điểm của các cạnh tam giác ý :))
Ohm, vậy thì cậu chỉ cần tìm giao điểm giữa các cạnh của 2 tam giác là được mà Cậu chỉ cần một hàm tìm giao điểm giữa 2 đoạn thẳng, sau đó gọi nó 9 lần là được.
Ngoài ra, nếu 2 tam giác trùng cạnh nhau, cậu sẽ trả về gì thế? Về lý thuyết, có vô số điểm nằm trên 1 đoạn thẳng.
3 Likes
mình dùng intersects để kiểm tra true false nên cái đó yên tâm rồi. ngoài ra còn xét trường hợp nếu trùng nhau nữa nên còn tính phần giao nhau thôi 
giải sử cho 2 tam giác này thì giao điểm là điểm G
sử dụng triệt để thư viện shapely.geometry thì tuyệt vời
Mình đoán là bạn đang làm bài này với code Python.
Bạn có thể duyệt qua tất cả các cạnh của 2 tam giác và lấy giao của chúng. Bạn có thể lấy giao của 2 đoạn thẳng một cách dễ dàng, chỉ mất O(1). Độ phức tạp là O(n^2), không tốn nhiều thời gian của bạn.
2 Likes
mình cám ơn bạn nhiều mà mình đang hỏi chỗ đó đó bạn:))
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?