¶ Hình học tính toán phần 2: Sự giao nhau của đường thẳng và các ứng dụng

Tác giả:

• Lê Minh Hoàng - Phổ thông Năng khiếu, ĐHQG-HCM

Reviewer:

• Trần Quang Lộc - ITMO University
• Hoàng Xuân Nhật - Đại học Khoa học Tự nhiên, ĐHQG-HCM
• Hồ Ngọc Vĩnh Phát - Đại học Khoa học Tự nhiên, ĐHQG-HCM

Trong phần 1, chúng ta đã tìm hiểu cách sử dụng vector để giải các bài toán hình học. Bây giờ chúng ta sẽ học cách sử dụng một vài kiến thức đại số tuyến tính cơ bản để tìm giao điểm của đường thẳng, sau đó áp dụng để giải quyết một số bài toán khác.

Lưu ý: một số hình ảnh được chụp từ Desmos, và đều có link Desmos tương ứng ở dưới mỗi hình, các bạn có thể nhấn vào link để tương tác với hình và các tham số.

Một trong những bài toán con phổ biến nhất trong các bài toán hình học là giao điểm đường thẳng. Mặc dù phổ biến nhưng nhiều người vẫn gặp rắc rối với nó.

Đầu tiên, ta có câu hỏi nhỏ là: đường thẳng được cho dưới dạng nào? và chúng ta muốn sử dụng ở dạng nào? Ở trường hợp lý tưởng thì đường thẳng sẽ ở dạng , với là các hệ số xác định đường thẳng. Tuy nhiên, ta hiếm khi được cho đường thẳng ở dạng này, nhưng ta có thể dễ dàng có được từ hai điểm cho trước. Ví dụ có hai điểm phân biệt và , và để tìm cho phương trình trên, ta đặt:

Bất kể đường thẳng được cho dưới dạng nào, ta luôn có thể chọn được hai điểm phân biệt thuộc đường thẳng, sau đó tính .

Tiếp theo, giả sử ta có hai đường thẳng, được cho bởi hai phương trình:

Để tìm giao điểm của hai đường thẳng, ta chỉ cần giải hệ hai phương trình với hai ẩn :

double det = A1 * B2 - A2 * B1; if (det == 0) { // Lines are parallel or coincident if (A1 * C2 == A2 * C1) { // Lines are coincident } else { // Lines are parallel } } else { double x = (B2 * C1 - B1 * C2) / det; double y = (A1 * C2 - A2 * C1) / det; }

Để biết được công thức ở đoạn code trên từ đâu ra, ta nhân phương trình thứ nhất với , và nhân phương trình thứ hai với :

Kế tiếp, lấy phương trình thứ nhất trừ phương trình thứ hai:

Cuối cùng, chia cả hai vế cho , ta sẽ có phương trình giải :

Phương trình giải thu được bằng biến đổi tương tự:

Như vậy ta sẽ có được toạ độ giao điểm của hai đường thẳng, nhưng sẽ thế nào nếu đây là hai đoạn thẳng? Trong trường hợp này, ta cần kiểm tra xem giao điểm tìm được có nằm trên hai đoạn thẳng hay không. Nếu đoạn thẳng nối hai điểm và , để kiểm tra xem có thuộc đoạn thẳng hay không, ta chỉ cần kiểm tra và làm tương tự cho .

Ta cũng nên cẩn thận với vấn đề về độ chính xác của số thực. Nếu giao điểm nằm ngay trên đầu mút của đoạn thẳng, hoặc nếu đoạn thẳng nằm ngang hoặc thẳng đứng, một phép so sánh tầm thường có thể có vấn đề. Trong những trường hợp đó, ta có thể thực hiện so sánh với một giá trị sai số nào đó (thường là ) hoặc sử dụng phân số.

Ngoài ra, ta còn có thể sử dụng tích có hướng để kiểm tra hai đoạn thẳng giao nhau với ưu điểm là không phụ thuộc vào sai số khi tọa độ các đỉnh đều là số nguyên.

¶ Kiểm tra giao điểm của 2 đoạn thẳng (sử dụng tích có hướng)

¶ CW và CCW

Nhắc lại phần 1: Với góc thỏa mãn thì nên nếu góc ngược chiều kim đồng hồ thì tích có hướng dương, ngược lại tích có hướng âm.

Để biết thứ tự của bộ 3 điểm , ta tính tích có hướng :

• Nếu thì ngược chiều kim đồng hồ (CCW).
• Nếu thì cùng chiều kim đồng hồ (CW).
• Nếu thì thẳng hàng.

||

¶ Kiểm tra giao điểm của 2 đoạn thẳng

¶ Tồn tại 3 điểm thẳng hàng

Nếu tồn tại 3 trong 4 điểm đầu mút thẳng hàng, ta kiểm tra xem có tồn tại đầu mút của đoạn thẳng này thuộc đoạn thẳng kia hay không:

• Nếu có thì rõ ràng là 2 đoạn thẳng giao nhau tại ít nhất 1 điểm (tại đầu mút vừa xét).

||

• Nếu không thì rõ ràng là 2 đoạn thẳng không thể giao nhau.

||

¶ Không tồn tại 3 điểm thẳng hàng

Nếu không tồn tại 3 trong 4 điểm đầu mút thẳng hàng thì 2 đoạn thẳng và giao nhau khi:

• và nằm khác phía đối với đường thẳng và
• và nằm khác phía đối với đường thẳng .

Để và nằm khác phía đối với đường thẳng thì:

• ngược chiều kim đồng hồ và cùng chiều kim đồng hồ hoặc
• cùng chiều kim đồng hồ và ngược chiều kim đồng hồ.

Từ đó, ta có hệ sau:

||

Nhấn vào đây để tương tác với hình trên Desmos.

const double eps = 1e-9; int sign(double x) { if (x > eps) return 1; if (x < -eps) return -1; return 0; } double cross(Vec AB, Vec AC) { return AB.x * AC.y - AC.x * AB.y; } double dot(Vec AB, Vec AC) { return AB.x * AC.x + AB.y * AC.y; } bool intersect(Point A, Point B, Point C, Point D) { int ABxAC = sign(cross(B - A, C - A)); int ABxAD = sign(cross(B - A, D - A)); int CDxCA = sign(cross(D - C, A - C)); int CDxCB = sign(cross(D - C, B - C)); if (ABxAC == 0 || ABxAD == 0 || CDxCA == 0 || CDxCB == 0) { // C on segment AB if ABxAC = 0 and CA.CB <= 0 if (ABxAC == 0 && sign(dot(A - C, B - C)) <= 0) return true; if (ABxAD == 0 && sign(dot(A - D, B - D)) <= 0) return true; if (CDxCA == 0 && sign(dot(C - A, D - A)) <= 0) return true; if (CDxCB == 0 && sign(dot(C - B, D - B)) <= 0) return true; return false; } return (ABxAC * ABxAD < 0 && CDxCA * CDxCB < 0); }

Từ điểm không thẳng hàng, có duy nhất một đường tròn đi qua điểm đó. Nhưng làm thế nào để tìm được tâm của nó? Vấn đề này hoá ra là một ứng dụng đơn giản của bài toán giao điểm đường thẳng.

Chúng ta sẽ tìm đường trung trực của 2 đoạn và , sau đó tìm giao điểm của hai đường này, điểm đó chính là tâm của đường tròn.

Nhấn vào đây để tương tác với hình trên Desmos.

Trong hình học phẳng, đường trung trực của một đoạn thẳng là đường vuông góc với đoạn thẳng tại trung điểm của đoạn thẳng đó.

Các bước để tìm đường trung trực của đoạn :

• Bước 1: tìm phương trình đường thẳng , giả sử có dạng .
• Bước 2: tìm trung điểm của đoạn bằng cách lấy trung bình cộng của hoành độ và trung bình cộng của tung độ.
• Bước 3: viết phương trình đường thẳng của đường thẳng vuông góc với đường thẳng có dạng là .

Nhấn vào đây để tương tác với hình trên Desmos.

• Bước 4: ta thay tọa độ của trung điểm vào phương trình đường thẳng ở bước để tìm và xác định đường trung trực.

¶ Ví dụ

Cho điểm và , để tìm đường trung trực của đoạn , ta thực hiện như sau:

• Bước 1: Tìm phương trình đường thẳng , ta đặt:

phương trình đường thẳng có dạng:

• Bước 2: Đặt là trung điểm của đoạn , ta có:

• Bước 3: Phương trình đường thẳng của đường thẳng vuông góc với đường thẳng có dạng:

• Bước 4: Thay tọa độ của trung điểm vào phương trình :

Vậy phương trình đường trung trực của đoạn là:

Làm tương tự cho đoạn , chúng ta sẽ có hai phương trình của hai đường trung trực, và có thể tìm giao điểm của chúng như đã đề cập ở trên.

struct Point { double x, y; Point() { x = y = 0.0; } Point(double x, double y) : x(x), y(y) {} Point operator + (const Point &a) const { return Point(x + a.x, y + a.y); } Point operator - (const Point &a) const { return Point(x - a.x, y - a.y); } Point operator * (double k) const { return Point(x * k, y * k); } Point operator / (double k) const { return Point(x / k, y / k); } }; struct Line { // Ax + By = C double a, b, c; Line(double a = 0, double b = 0, double c = 0) : a(a), b(b), c(c) {} Line(Point A, Point B) { a = B.y - A.y; b = A.x - B.x; c = a * A.x + b * A.y; } }; Line Perpendicular_Bisector(Point A, Point B) { Point M = (A + B) / 2; Line d = Line(A, B); // the equation of a perpendicular line has the form: -Bx + Ay = D double D = -d.b * M.x + d.a * M.y; return Line(-d.b, d.a, D); }

Để lấy đối xứng một điểm qua một đường thẳng (trục đối xứng), ta tìm giao điểm của trục đối xứng và đường thẳng vuông góc với trục đối xứng đi qua , sau đó lấy đối xứng với qua .

¶ Ví dụ

Cho điểm và đường thẳng , để tìm điểm đối xứng với qua , ta thực hiện như sau:

• Bước 1: Gọi đường thẳng đi qua và vuông góc với trục đối xứng có dạng: .

• Bước 2: Để tìm , ta chỉ cần thay toạ độ của vào phương trình:

• Bước 3: xác định giao điểm của hai đường và :

• Bước 4: xác định đối xứng với qua bằng công thức: ( là trung điểm và nên ).

||

Nhấn vào đây để tương tác với hình trên Desmos.

struct Line { // Ax + By = C double a, b, c; Line(double a = 0, double b = 0, double c = 0) : a(a), b(b), c(c) {} }; Point intersect(Line d1, Line d2) { double det = d1.a * d2.b - d2.a * d1.b; // det != 0 because d1 is perpendicular to d2 return Point((d2.b * d1.c - d1.b * d2.c) / det, (d1.a * d2.c - d2.a * d1.c) / det); } Point Symmetry(Point X, Line d) { // the equation of a perpendicular line has the form: -Bx + Ay = D double D = -d.b * X.x + d.a * X.y; Line d2 = Line(-d.b, d.a, D); Point Y = intersect(d, d2); Point X2 = Point(2 * Y.x - X.x, 2 * Y.y - X.y); return X2; }

Cho điểm , để quay điểm ngược chiều kim đồng hồ một góc quanh gốc tọa độ, ta đơn giản sử dụng công thức:

Lưu ý: vì các ngôn ngữ lập trình sử dụng radian(rad) làm đơn vị chuẩn khi làm việc với các hàm số lượng giác nên ở trong desmos, mình sử dụng đơn vị của số đo góc là radian thay vì độ(°).

Công thức chuyển đổi giữa radian và độ:

độđộ

Bảng chuyển đổi một số giá trị thường dùng:

Nhấn vào đây để tương tác với hình trên Desmos.

Để quay điểm quanh một điểm khác không phải gốc tọa độ, ta tịnh tiến hệ tọa độ sao cho trùng với gốc tọa độ, quay bằng công thức trên rồi tịnh tiến hệ tọa độ về vị trí ban đầu.

¶ Ví dụ

Cho điểm và , để quay ngược chiều kim đồng hồ 1 góc quanh , ta thực hiện như sau:

• Bước 1: tịnh tiến hệ tọa độ sao cho trùng với gốc tọa độ. Lúc này, điểm có tọa độ mới là .

• Bước 2: quay ngược chiều kim đồng hồ 1 góc quanh gốc tọa độ được điểm :

• Bước 3: tịnh tiến hệ tọa độ về vị trí ban đầu. Điểm có tọa độ mới là:

Vậy quay ngược chiều kim đồng hồ 1 góc quanh , ta được điểm

||

Nhấn vào đây để tương tác với hình trên Desmos.

Point Rotations(Point A, Point C, double rad) { Point A2 = A - C; Point B2 = Point(A2.x * cos(rad) - A2.y * sin(rad), A2.x * sin(rad) + A2.y * cos(rad)); Point B = B2 + C; return B; }

• Kiểm tra giao điểm của 2 đoạn thẳng (sử dụng tích có hướng)
• Đường tròn đi qua 3 điểm
• 2 đường thẳng vuông góc
• Phép đối xứng
• Phép quay (quanh tâm O)
• Phép quay (quanh điểm bất kì)

Học phải đi đôi với hành, do đó mình đề xuất cho các bạn Codeforces Gym 100168. Tuy đề bài trong gym được viết bằng tiếng Nga nhưng rất ngắn gọn và đi thẳng vào bài toán nên các bạn có thể dễ dàng google translate.

Bên dưới là một số bài tập có liên quan đến bài viết này, mình đã tóm tắt yêu cầu bài toán để các bạn có thể hiểu đề dễ dàng hơn.

• Codeforces Gym - 100168K: cho 2 đường thẳng có dạng , tìm giao điểm
• CSES - Line Segment Intersection: kiểm tra 2 đoạn thẳng có giao nhau hay không
• Codeforces Gym - 100168M: cho 2 điểm, viết phương trình đường thẳng
• Codeforces Gym - 100168N: cho 1 điểm và 1 vector pháp tuyến, viết phương trình đường thẳng
• Codeforces Gym - 100168P: kiểm tra điểm thuộc đường thẳng
• Codeforces Gym - 100168Q: kiểm tra điểm thuộc tia
• Codeforces Gym - 100168R: kiểm tra điểm thuộc đoạn
• Codeforces Gym - 100168S: kiểm tra 2 điểm có nằm cùng 1 phía với bờ là 1 đường thẳng có dạng
• CSES - Point Location Test: xác định vị trí của 1 điểm với 1 đường thẳng
• CSES - Point in Polygon: xác định vị trí của 1 điểm với 1 đa giác
• Codeforces - Robo-Footballer (vận dụng)