Hình học tính toán (phần 2) - Sự giao nhau của các đường thẳng và Tính toán diện tích

Trong bài viết phần 1 về chủ đề Hình học tính toán, chúng ta đã cùng nghiên cứu về cách sử dụng vector trong các bài toán hình học. Còn trong bài viết này, tôi sẽ giới thiệu những vấn đề liên quan tới đường thẳng, giao điểm và sử dụng kiến thức về đại số tuyến tính để tính toán giao điểm, tính toán diện tích, qua đó áp dụng trong những bài toán hình học của lập trình thi đấu.

Trong Toán học phổ thông, các bạn đã biết có nhiều cách để biểu diễn một đường thẳng, vì thế cũng có nhiều cách biểu diễn đường thẳng trong máy tính, mà tùy vào dữ kiện đề bài ta sẽ chọn cách biểu diễn phù hợp. Dưới đây là một số cách biểu diễn đường thẳng thường dùng trong các bài toán Tin học:

Khi cần chuyển đổi giữa các biểu diễn, ta thực hiện biến đổi tương đương đại số, kết hợp với công thức chuyển đổi giữa vector chỉ phương d⃗(−b,a)vec{d}(-b, a)d(−b,a) và vector pháp tuyến n⃗(a,b)vec{n}(a, b)n(a,b).

1. Tìm giao điểm của hai đường thẳng

Đây là bài toán phổ biến nhất trong các bài toán về giao điểm, nhưng không phải ai cũng có thể thực hiện thành thạo.

Trong trường hợp lý tưởng, ta sẽ có được hai đường thẳng đều được biểu diễn ở dạng Ax+By=CAx + By = CAx+By=C với A,B,CA, B, CA,B,C là các hệ số xác định đường thẳng. Tuy nhiên, không phải lúc nào bài toán cũng tuyệt đẹp như vậy. Nhưng may mắn rằng, ta có thể dễ dàng tìm được biểu diễn tổng quát trên dựa vào hai điểm cho trước thuộc đường thẳng. Ví dụ có hai điểm phân biệt (x1,y1)(x_1,y_1)(x1​,y1​) và (x2,y2),(x_2,y_2),(x2​,y2​), và để tìm A,B,CA,B,CA,B,C cho phương trình trên, ta có công thức:

Đường thẳng dù ở dạng nào, ta cũng có thể chọn được hai điểm phân biệt thuộc đường thẳng và dùng công thức trên để tính A,B,CA, B, CA,B,C.

Giờ, coi như ta đã thu được hai đường thẳng được cho bởi hai phương trình:

{A1x+B1y=C1 (1)A2x+B2y=C2 (2)begin{cases}A_1x + B_1y = C_1 (1) A_2x + B_2y = C_2 (2) end{cases} {A1​x+B1​y=C1​ (1)A2​x+B2​y=C2​ (2)​

Để tìm giao điểm của hai đường thẳng, ta chỉ cần giải hệ phương trình hai ẩn x,yx, yx,y. Cách làm như sau:

Như vậy, ta thu được giao điểm của hai đường thẳng đã cho.

Cài đặt

struct Line { double A, B, C; }; // Trả về giao điểm hai đường thẳng. // Riêng hai trường hợp song song hoặc trùng nhau thì ném ngoại lệ. pair < int, int > find_line_intersection(Line line1, Line line2) { double det = line1.A * line2.B - line2.A * line1.B; // Hai đường thẳng song song hoặc trùng nhau. if (det == 0) { if (line1.A * line2.C == line2.A * line1.C) { throw "Coincident lines"; } else { throw "Parallel lines"; } } else { double x = line2.B * line1.C - line1.B * line2.C / det; double y = line1.A * line2.C - line2.A * line1.C / det; return {x, y}; } }

2. Tìm giao điểm của hai đoạn thẳng

Bài toán tiếp theo là cho bốn điểm A,B,C,DA, B, C, DA,B,C,D trên mặt phẳng, cần xác định xem hai đoạn thẳng ABABAB và CDCDCD có giao điểm duy nhất hay không, nếu có thì đưa ra tọa độ của giao điểm đó.

Sử dụng những kiến thức về tích có hướng, ta có thể thực hiện công việc này không mấy khó khăn. Tuy nhiên, trước tiên cần phải xem xét liệu trong số bốn điểm đã cho, có tồn tại ba điểm nào thẳng hàng hay không.

Nhắc lại về hàm CW và CCW

Kiến thức các bạn cần lưu ý ở đây là: Với góc ααα thỏa mãn 0°<α<180°0°<α<180°0°<α<180° thì sin⁡(α)>0sin(α)>0sin(α)>0 nên nếu góc ngược chiều kim đồng hồ θ<180°θ<180°θ<180° thì tích có hướng dương, ngược lại tích có hướng âm (đã đề cập ở bài viết trước).

Xét ba điểm A,B,C;A, B, C;A,B,C; Giả sử ta đi từ điểm AAA sang điểm BBB theo đường thằng và đi tiếp sang điểm CCC theo đường thẳng, khi đó:

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

Trường hợp tồn tại ba điểm thẳng hàng

Nếu tồn tại 333 trong 444 đ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:

Trường hợp không tồn tại ba điểm thẳng hàng

Nếu không tồn tại 333 trong 444 điểm đầu mút thẳng hàng thì 222 đoạn thẳng ABABAB và CDCDCD giao nhau khi:

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

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

Hình minh họa:

Cài đặt

const double eps = 1e-9; // Xác định dấu của tích có hướng. 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); }

3. Tìm đường tròn đi qua ba điểm

Ta biết rằng, từ ba điểm không thẳng hàng, luôn luôn tồn tại duy nhất một đường tròn đi qua ba điểm đó. Để tìm được tâm của đường tròn này, ta ứng dụng chính bài toán xác định giao điểm đường thẳng.

Quan sát hình vẽ dưới đây:

Giả sử ba điểm cho trước là X,Y,Z;X, Y, Z;X,Y,Z; ta sẽ tìm đường trung trực của hai đoạn XYXYXY và YZ,YZ,YZ, sau đó tìm giao điểm của hai đường trung trực này, đó sẽ chính là tâm của đường tròn đi qua ba điểm X,Y,ZX, Y, ZX,Y,Z.

Đường trung trực của một đoạn thẳng chính là đường thẳng vuông góc với đoạn thẳng tại trung điểm của nó. Để tìm đường trung trực của đoạn thẳng XY,XY,XY, ta làm như sau:

Ví dụ

Với 222 điểm X(2,−3)X(2,−3)X(2,−3) và Y(1,0);Y(1,0);Y(1,0); để tìm đường trung trực của đoạn XY,XY,XY, ta thực hiện như sau:

Vậy phương trình đường trung trực của đoạn thẳng XYXYXY là: −x+3y=−6-x + 3y = -6−x+3y=−6.

Làm tương tự với đoạn thẳng YZ,YZ,YZ, 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.

Cài đặt

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); } }; // Ax + By = C. struct Line { 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); }

1. Diện tích tam giác

Có khá nhiều công thức giải tích để tính diện tích tam giác, tùy vào dữ kiện đề bài cho mà ta có thể lựa chọn cách tính phù hợp. Dưới đây là một số cách thường dùng:

Cài đặt

2. Diện tích đa giác

Ta đã biết rằng, đa giác là một đường gấp khúc khép kín. Trong lập trình, một đa giác sẽ được biểu diễn bằng một dãy các đỉnh liên tiếp nhau A1,A2,A3,…,AnA_1, A_2, A_3, dots, A_nA1​,A2​,A3​,…,An​ với tọa độ xác định trên hệ tọa độ Descartes.

Khi đó, diện tích đại số (có thể âm hoặc dương) của một đa giác không tự cắt được tính bằng công thức:

S=(x1−x2)(y1+y2)+(x2−x3)(y2+y3)+⋯+(xn−x1)(yn+y1)2S = frac{(x_1 - x_2)(y_1 + y_2) + (x_2 - x_3)(y_2 + y_3) + cdots + (x_n - x_1)(y_n + y_1)}{2} S=2(x1​−x2​)(y1​+y2​)+(x2​−x3​)(y2​+y3​)+⋯+(xn​−x1​)(yn​+y1​)​

Và diện tích của đa giác sẽ chính bằng giá trị ∣S∣|S|∣S∣.

Việc xét diện tích đại số của đa giác có thể giúp chúng ta xác định được các đỉnh của đa giác này đang được liệt kê theo chiều nào. Nếu diện tích đại số là số dương (S>0S > 0S>0) thì dãy các đỉnh được liệt kê theo chiều ngược chiều kim đồng hồ (và ngược lại).

Cài đặt

// Tính diện tích đa giác với dãy đỉnh truyền vào bởi một vector kiểu pair. double polygon_area(vector < pair < double, double > > vertices) { // Thêm đỉnh đầu tiên vào cuối vector để xét tích cuối cùng trên tử số. vertices.push_back(vertices[0]); int n = vertices.size() - 1; double area = 0; for (int i = 0; i <= n; ++i) area += (vertices[i].first - vertices[i + 1].first) * (vertices[i].second + vertices[i + 1].second); return abs(area) / 2.0; }

1. Phép tịnh tiến

Xét một phép tịnh tiến theo vector (a,b)(a, b)(a,b). Phép tịnh tiến này sẽ biến một điểm O(0,0)O(0, 0)O(0,0) thành điểm O′(a,b),O'(a, b),O′(a,b), điểm I(1,0)I(1, 0)I(1,0) sẽ biến thành điểm I′(a+1,b)I'(a + 1, b)I′(a+1,b) và điểm J(0,1)J(0, 1)J(0,1) sẽ biến thành điểm J′(a,b+1)J'(a, b + 1)J′(a,b+1).

Tổng quát, phép tịnh tiến theo vector (a,b)(a, b)(a,b) sẽ biến điểm (x,y)(x, y)(x,y) thành điểm (x‾,y‾);(overline{x}, overline{y});(x,y​); trong đó:

{x‾=x+ay‾=y+bbegin{cases}overline{x} = x + a overline{y} = y + b end{cases} {x=x+ay​=y+b​

2. Phép quay

Cho trước điểm A(x,y);A(x, y);A(x,y); để quay điểm AAA ngược chiều kim đồng hồ một góc αalphaα quanh gốc tọa độ, ta sử dụng công thức:

{x′=xcos⁡α−ysin⁡αy′=ysin⁡α+ycos⁡αbegin{cases}x' = x cos alpha - y sin alpha y' = y sin alpha + y cos alphaend{cases} {x′=xcosα−ysinαy′=ysinα+ycosα​

Tuy nhiên, cần lưu ý trong các ngôn ngữ lập trình, số đo góc sử dụng trong các hàm lượng giác sẽ là radian (rad) chứ không phải độ, do đó các bạn cần lưu ý công thức chuyển đổi giữa hai đơn vị này:

π rad=180°⇒{rad=độ×π180độ=rad×180πpi rad = 180° Rightarrow begin{cases} rad = frac{text{độ} times pi}{180} text{độ} = frac{rad times 180}{pi} end{cases} π rad=180°⇒{rad=180độ×π​độ=πrad×180​​

Ngoài ra, chúng ta cũng có thể xây dựng công thức quay một điểm AAA quanh một điểm CCC bất kì khác gốc tọa độ, bằng cách tịnh tiến hệ tọa độ sao cho điểm CCC trùng với gốc tọa độ, rồi lại thực hiện phép quay như đã nêu ở trên.

Ví dụ

Cho 222 điểm A(1,4)A(1,4)A(1,4) và C(2,2),C(2,2),C(2,2), để quay AAA ngược chiều kim đồng hồ một góc 45°45°45° quanh C,C,C, ta thực hiện như sau:

Vậy quay A(1,4)A(1,4)A(1,4) ngược chiều kim đồng hồ một góc 45°45°45° quanh C(2,2),C(2,2),C(2,2), ta được điểm B(−32-2+2,2-2+2)B(−32-sqrt{2}+2,2-sqrt{2}+2)B(−32-2​+2,2-2​+2).

Cài đặt

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); } }; 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; }

3. Phép đối xứng

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

Ví dụ

Cho điểm X(1,−3)X(1, -3)X(1,−3) và đường thẳng (d):4x−3y=−5;(d): 4x - 3y = -5;(d):4x−3y=−5; để tìm điểm X′X'X′ đối xứng với XXX qua (d),(d),(d), ta thực hiện như sau:

Hình minh họa:

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); } }; // Ax + By = C. struct Line { 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; }

©️ Tác giả: Vũ Quế Lâm từ Viblo

Link nội dung: https://www.sachhayonline.com/giao-diem-2-duong-thang-a56307.html