Thuật Toán Kiểm Tra Tính Giao Nhau Của Hai Đoạn Thẳng
Sau một thời gian dài, mình xin công bố sự quay trở lại của series "Toán học" với bài số 4! Hôm nay, chúng ta sẽ bàn về hình học, một phạm trù cũng hết sức quan trọng trong toán học.
Trong lập trình, loại hình học quen thuộc nhất có lẽ chính là hình học tọa độ, khi đây chính là khu vực hình học làm việc trực tiếp với đại số. Hình học tọa độ là nơi cho ra đời rất nhiều vấn đề trong lập trình, và hôm nay chúng ta sẽ phân tích một vấn đề cơ bản, làm nền tảng cho những vấn đề trong hình học tọa độ.
Bài toán
"Cho 4 điểm A, B, C, D phân biệt với tọa độ nguyên. 2 đoạn thẳng AB, CD có cắt nhau (có điểm chung) hay không?"
Bài toán tưởng chừng như đơn giản, vì bạn có thể lập tức kiểm chứng bằng cách vẽ bằng tay những điểm A, B, C, D và trả lời câu hỏi trên. Tuy nhiên, trong trường hợp bài toán gồm hàng triệu điểm, hay khi giá trị tọa độ của mỗi điểm lên đến hàng triệu, bạn cần đến sự trợ giúp của máy tính. Điều này đòi hỏi chúng ta phải đưa ra câu trả lời tổng quát, hay là code, cho câu hỏi trên.
Bài toán này có nhiều ứng dụng, đặc biệt là để kiểm tra tính lồi của đa giác hay trong các bài toán đồ thị.
Tất nhiên, trước khi mình spoil lời giải bên dưới, các bạn nên tự thử sức và implement code. Chúc các bạn may mắn :)
Phân tích
Kinh nghiệm code viết ba lần sai bảy lượt luôn nhắc nhở chúng ta rằng phải xử lí những trường hợp đặc biệt trước. Bài toán này không phải là trường hợp ngoại lệ.
Trường hợp có 3 điểm thẳng hàng
Bước đầu tiên bạn nên làm là kiểm tra trong 4 điểm đó, có bộ ba điểm nào thẳng hàng không. Cụ thể, bạn sẽ kiểm tra các bộ điểm (A, B, C), (A, B, D), (A, C, D) và (B, C, D).
Mình xin phép để lại phần này cho các bạn tự làm phần code, vì đây là một vấn đề khá quen thuộc rồi. ;) Mình sẽ chỉ phân tích khía cạnh toán học của bài toán này.
Giả sử 3 điểm đó là A, B, C. Chúng ta lại có 2 trường hợp nhỏ ở đây nữa.
1) D nằm trên cùng đường thẳng
Nếu 1 trong 2 điều sau đúng thì output "yes":
- C nằm giữa A và B hoặc D nằm giữa A và B
- A nằm giữa C và D hoặc B nằm giữa C và D
Nếu rơi vào trường hợp còn lại, output "no".
2) D không nằm trên đường thẳng chứa A, B, C
Ở đây còn đơn giản hơn, ta chỉ cần kiểm tra xem C có nằm giữa A và B hay không thôi.
Đến đây thì "sóng gió" đã trôi qua. Bây giờ chúng ta chỉ còn lại những trường hợp "dễ xơi". Hy vọng vậy.
Trường hợp không có 3 điểm nào thẳng hàng
Một khi đã loại trừ hết những khả năng tồn tại bộ ba thẳng hàng, ta sẽ được phép sử dụng bổ đề hữu ích sau nhằm giải bài toán:
AB cắt CD khi và chỉ khi cả 2 điều sau xảy ra:
- A và B nằm khác phía so với CD
- C và D nằm khác phía so với CD
Nếu bạn chưa quen thuộc với khái niệm "nằm khác phía", sau đây là ví dụ cho "A và B nằm khác phía so với đường d"
Đường thằng d chia mặt phẳng ra làm 2 phần, A nằm ở một phần và B nằm ở phần bên kia
Bằng quan sát, bạn sẽ thấy bổ đề trên là đúng khi xét 3 trường hợp sau:
A và B nằm cùng phía so với CD, C và D cũng nằm cùng phía so với AB, nên 2 đoạn thẳng không cắt nhau
A và B nằm khác phía so với CD, nhưng C và D nằm cùng phía so với AB, nên 2 đoạn thẳng không cắt nhau
A và B nằm khác phía so với CD, C và D cũng nằm khác phía so với AB, nên 2 đoạn thẳng cắt nhau
Còn nếu muốn một chứng minh rõ ràng, bạn có thể tự thử sức! (Spoil: Sử dụng phản chứng, tức là giả sử 1 điều là sai: A và B nằm cùng phía so với CD)
Bổ đề sau có thể được viết lại thành:
AB cắt CD khi và chỉ khi cả 2 điều sau xảy ra:
- (C, D, A) có chiều khác so với (C, D, B)
- (A, B, C) có chiều khác so với (A, B, D)
Khái niệm "chiều" ở đây khá là mới, mình xin giải thích ở bài toán con sau.
Bài toán con
"Cho 3 điểm A, B, C phân biệt, không thẳng hàng với tọa độ nguyên. Xác định chiều của (A, B, C)."
(A, B, C) theo chiều kim đồng hồ
(A, B, C) ngược chiều kim đồng hồ
Nhận xét rằng khi A và B cùng/khác chiều so với CD, (C, D, A) và (C, D, B) sẽ cùng/khác chiều. Lấy ví dụ hình trên, nếu C nằm phía trên AB thì (A, B, C) ngược chiều kim đồng hồ, còn nếu C nằm ở phía bên kia, phía dưới AB thì (A, B, C) theo chiều kim đồng hồ.
Ngoài ra, bài toán con cùng chiều - khác chiều này dễ giải quyết hơn là bài toán con cùng phía - khác phía.
Ý tưởng của bài toán con này là sử dụng "dốc" của đoạn thẳng. Dốc của đoạn thẳng AB (hay đường thẳng AB) là hệ số a trong phương trình y = ax + b của đoạn thẳng/đường thẳng AB.
Gọi m là dốc của đoạn AB, n là dốc của đoạn BC. Về mặt lý thuyết, nếu m > n thì (A, B, C) theo chiều kim đồng hồ.
Tuy nhiên, do m và n được biểu thị dưới dạng phân số (m = (yB - yA)/(xB - xA), n = (yC - yB)/(xC - xB)) nên ta phải có cách kiểm tra m > n chính xác hơn.
Sau đây là code C++ xác định chiều của (A, B, C), xử lí được cả những trường hợp đặc biệt khi dốc bằng 0 hay dốc bằng ±∞ (các bạn có thể tự lí luận vì sao nhé)
/*
// Point ở đây là một lớp, có thể được định nghĩa như sau:
struct Point {
int x; // tọa độ x
int y; // tọa độ y
};
*/
string threePointOrientation(Point A, Point B, Point C) {
/*
m là dốc của AB => m = (B.y - A.y) / (B.x - A.x)
n là dốc của BC => n = (C.y - B.y) / (C.x - B.x)
Để tránh trường hợp mẫu số của 2 phân thức trên bằng 0, thay vì sử dụng phép chia,
ta sẽ sử dụng phép nhân để kiểm tra m > n
Biến đổi tương đương:
m > n
<=> (B.y - A.y) / (B.x - A.x) > (C.y - B.y) / (C.x - B.x)
<=> (B.y - A.y) * (C.x - B.x) > (C.y - B.y) * (B.x - A.x)
*/
int check = (B.y - A.y) * (C.x - B.x) - (C.y - B.y) * (B.x - A.x);
return check > 0 ? "clockwise" : "counterclockwise";
}Trở lại với bài toán chính, lúc này ta đã có công cụ chủ đạo để làm bài toán, ta chỉ việc kiểm tra 2 điều sau đây theo như bổ đề trên:
- (C, D, A) có chiều khác so với (C, D, B)
- (A, B, C) có chiều khác so với (A, B, D)
Nếu cả 2 điều trên là đúng, output "yes". Ngược lại, output "no". ☐
Như đã nói trên, một trong những ứng dụng của bài toán tổng quát này là kiểm tra tính lồi của đa giác. Vì thế, hãy thử bài toán thú vị không kém cạnh sau đây:
"Cho đa giác A1A2...An, các điểm có tọa độ nguyên. Đa giác này có phải là đa giác lồi không?"
Tạm kết
Như thường lệ, hy vọng bài viết này giúp ích cho các bạn :)
Nếu bạn đang gặp khó khăn về toán học trong lập trình hay muốn đề xuất chủ đề cho bài viết tiếp theo trong series thì đừng ngần ngại nhé!
