+5

Hình học tính toán (phần 1) - Ứng dụng của vectors

I. Lời nói đầu

Như các bạn đã biết, trong chương trình Toán phổ thông, chúng ta đã được nghiên cứu khá nhiều về các bài toán liên quan tới chủ đề Hình học. Tuy nhiên, không chỉ trong môn Toán, mà trong môn Tin học, các bài toán Hình học cũng là một chủ đề khá quen thuộc, thậm chí còn "khó nhai" trong các kì thi lập trình. Hình học tính toán (Computational Geometry) là một nhánh của ngành Khoa học máy tính, chuyên nghiên cứu về thuật toán giải quyết các bài toán liên quan tới đối tượng hình học. Trong Toán học và Công nghệ hiện đại, hình học tính toán có ứng dụng rất rộng rãi trong nhiều lĩnh vực như đồ họa máy tính, thiết kế, mô phỏng,...

Chính vì tầm quan trọng của chủ đề này, mà trong series bài viết sau đây, tôi sẽ giới thiệu tới các bạn những khái niệm từ cơ bản tới nâng cao về hình học tính toán thường xuất hiện trong các kì thi lập trình, sau đó khảo sát một số bài toán và thuật toán căn bản. Những công thức hình học thường được thừa nhận không chứng minh, để giúp cho người đọc nhanh chóng nắm bắt ý tưởng (và thực ra việc chứng minh cũng không quá cần thiết trong lập trình :3).

II. Các khái niệm cơ bản thường dùng

1. Vector

Vector là một đối tượng có cả độ lớn và hướng. Hướng của vector là hướng từ điểm đầu đến điểm cuối của nó.

Một vector thường được biểu diễn bằng một tia (một đoạn thẳng có hướng), hoặc bằng đồ thị dưới dạng một mũi tên nối từ điểm đầu AA tới điểm cuối B,B, và được ký hiệu là AB\overrightarrow{AB}.

2. Hệ tọa độ Descartes

Đây là khái niệm rất căn bản, thường được biết đến với tên gọi quen thuộc là hệ trục tọa độ Oxy,Oxy, hệ tọa độ hai chiều,...

Trong mặt phẳng, ta chọn một điểm OO và hai vector đơn vị (vector có độ dài) là i\vec{i}j\vec{j} vuông góc với nhau. Khi đó, bộ ba (O,i,j)(O, \vec{i}, \vec{j}) được gọi là Hệ tọa độ Descartes vuông góc, hay còn gọi là một mục tiêu Euclid hai chiều, một mục tiêu trực chuẩn.

Ta kí hiệu mục tiêu đó là OxyOxy với OxOxOyOy là hai tia gốc OO có vector chỉ phương lần lượt là i\vec{i}j\vec{j}.

Mục tiêu Euclid

Điểm OO được gọi là gốc tọa độ, đường thẳng OxOx được gọi là trục hoànhOyOy được gọi là trục tung.

Ngoài ra, hệ tọa độ Descartes cũng có thể được phát triển trên không gian ba chiều, bằng cách sử dụng thêm một vector đơn vị k\vec{k} có chiều hướng từ dưới lên trên, sau đó dùng một tia OzOz có vector chỉ phương chính là k\vec{k}.

Hệ trục tọa độ Descartes trong không gian 3 chiều

3. Tọa độ

Tọa độ của vector

Xét mặt phẳng trực chuẩn (O,i,j),(O, \vec{i}, \vec{j}), với một vector v\vec{v} bất kì của mặt phẳng, thì sẽ tồn tại duy nhất một cặp số thực (x,y)(x, y) sao cho v=x.i+y.j\vec{v} = x.\vec{i} + y.\vec{j}. Cặp số (x,y)(x, y) khi đó được gọi là tọa độ của vector v\vec{v} trong mặt phẳng trực chuẩn, kí hiệu là v=(x,y)\vec{v} = (x, y) hoặc v(x,y)\vec{v}(x, y).

Tọa độ của điểm

Xét mặt phẳng trực chuẩn (O,i,j),(O, \vec{i}, \vec{j}), ta lấy một điểm MM. Khi đó tọa độ (x,y)(x, y) của vector OM\overrightarrow{OM} được gọi là tọa độ của điểm M,M, kí hiệu M=(x,y)M = (x, y) hoặc M(x,y)M(x, y).

Để tìm tọa độ của điểm trong hệ trục tọa độ không gian ba chiều, ta cũng làm theo cách hoàn toàn tương tự, chỉ cần bổ sung thêm cao độ của điểm MM theo trục OzOz.

Liên hệ giữa tọa độ của vector và tọa độ của điểm

Trong hình học phẳng, vector AB\overrightarrow{AB} có thể được biểu diễn bằng một cặp số (x,y)(x,y) cho biết tọa độ của vector, được xác định bằng hiệu các tọa độ tương ứng của điểm cuối BB với điểm đầu AA:

{x=xBxAy=yByA\begin{cases}x = x_B - x_A \\ y = y_B - y_A \end{cases}

Lấy ví dụ, một vector từ A(3,1)A(3,1) đến B(2,3)B(2,3) có thể được biểu diễn bởi u=(1,2)\vec{u}=(−1,2).

4. Một số phép toán với vector

3.1. Độ lớn của vector

Độ lớn của một vector được xác định bằng khoảng cách giữa điểm đầu và điểm cuối của nó. Giả sử ta có vector AB=(x,y)\overrightarrow{AB} = (x, y) trong mặt phẳng tọa độ hai chiều, thì độ lớn của nó, kí hiệu là AB|\overrightarrow{AB}| sẽ được xác định dựa trên định lý Pythagoras như sau:

3.2. Phép cộng hai vector

Với hai vector u=(x1,y1)\vec{u} = (x_1, y_1)v=(x2,y2),\vec{v} = (x_2, y_2), tổng của u\vec{u}v\vec{v} được tính bằng công thức:

u+v=(x1+x2,y1+y2)\vec{u} + \vec{v} = (x_1 + x_2, y_1 + y_2)

Phép cộng vector cũng có tính chất giao hoán. Nếu như biểu diễn hình học, thì vector tổng của u\vec{u}v\vec{v} chính là đường chéo của hình bình hành dựng từ hai vector ban đầu trên mặt phẳng tọa độ. Do đó quy tắc tính tổng hai vector còn gọi là quy tắc hình bình hành.

3.3. Phép trừ hai vector

Vector đối

Trước tiên, ta cùng tìm hiểu khái niệm về vector đối.

Cho vector a,\vec{a}, một vector có cùng độ lớn nhưng ngược hướng với a\vec{a} được gọi là vector đối của a,\vec{a}, kí hiệu là a-\vec{a}. Mỗi vector đều có vector đối, chẳng hạn vector đối của AB\overrightarrow{AB}BA,\overrightarrow{BA}, nghĩa là AB=BA-\overrightarrow{AB} = \overrightarrow{BA}.

Tọa độ của vector đối sẽ bằng số đối của tọa độ vector ban đầu.

Hiệu hai vector

Sử dụng khái niệm về vector đối, ta có hiệu của hai vector u\vec{u}v\vec{v} chính là tổng của u\vec{u}v-\vec{v}.

Nếu 2 vector có chung điểm đầu thì vector hiệu có hướng từ điểm cuối của v\vec{v} đến điểm cuối của u\vec{u}. Ví dụ: OAOB=BA\overrightarrow{OA} − \overrightarrow{OB} = \overrightarrow{BA}. Nếu hai vector có chung điểm cuối thì vector hiệu có hướng từ điểm đầu của u\vec{u} đến điểm đầu của v\vec{v}. Ví dụ: AOBO=AB\overrightarrow{AO}−\overrightarrow{BO} =\overrightarrow{AB}.

3.4. Tích vô hướng (dot product)

Hai phép toán khá đặc biệt đối với vector là tích vô hướngtích có hướng. Không giống như cộng và trừ, hai phép toán này hơi khó để tưởng tượng.

Tích vô hướng (còn gọi là tích chấm) có thể biểu diễn bằng cả đại số lẫn hình học. Hai cách biểu diễn này đều tương đương trong hệ tọa độ Descartes.

Theo đại số, tích vô hướng của hai vector là tổng các tích tọa độ tương ứng giữa chúng. Ví dụ, hai vector u(x1,y1)\vec{u}(x_1, y_1)v(x2,y2)\vec{v}(x_2, y_2) có tích vô hướng là:

uv=x1x2+y1y2\vec{u} \cdot \vec{v} = x_1x_2 + y_1y_2

Còn theo hình học, tích vô hướng là tích giữa độ lớn của hai vector và cos\cos của góc hợp giữa chúng. hai vector u(x1,y1)\vec{u}(x_1, y_1)v(x2,y2)\vec{v}(x_2, y_2) có tích vô hướng là:

uv=u×v×cos(θ)\vec{u} \cdot \vec{v} = |\vec{u}| \times |\vec{v}| \times \cos{(\theta)}

với θ\theta là góc hợp bởi u\vec{u}v\vec{v}

Ví dụ: Tính tích vô hướng giữa hai vector u(5,12)\vec{u}(5, 12)v(6,8)\vec{v}(-6, 8):

Tính theo đại số:

Tính theo hình học:

Từ các định nghĩa về tích vô hướng, ta cũng có thể tính được góc θ\theta hợp bởi u\vec{u}v\vec{v} theo công thức:

Ngoài ra, công thức trên không chỉ đúng trong hình học phẳng, mà ta có thể áp dụng tích vô hướng cho các vector có số chiều tùy ý, đẳng thức trên vẫn hoàn toàn chính xác!

3.5. Tích có hướng (cross product)

Trong không gian ba chiều

Tích có hướng là một phép nhân vector trong không gian ba chiều. Nó khác với tích vô hướng ở chỗ, kết quả thu được sẽ là một vector, nghĩa là đại lượng có hướng. Vector này sẽ vuông góc với mặt phẳng chứa hai vector đầu vào của phép nhân.

Định nghĩa tích có hướng như sau:

a×b=nabsin(θ)\vec{a} \times \vec{b} = \vec{n} \cdot |\vec{a}| \cdot |\vec{b}| \cdot \sin(\theta)

Trong đó:

  • θ\theta là góc giữa a\vec{a}b (0θ180)\vec{b} \ (0^{\circ} \le \theta \le 180^{\circ}).
  • n\vec{n} là vector đơn vị vuông góc với a\vec{a}b\vec{b}. Thực tế, có tới hai vector thỏa mãn điều kiện vuông góc là n\vec{n}n,-\vec{n}, do đó hướng của n\vec{n} phụ thuộc vào quy tắc bàn tay phải, được mô tả như hình vẽ dưới đây:

Trong không gian hai chiều

Nếu xét trong hình học phẳng thì vector kết quả lúc này vuông góc và có hướng đi vào/ra mặt phẳng đang xét, do đó ta có thể bỏ qua đặc điểm về hướng, và sử dụng tích có hướng như là một đại lượng vô hướng.

Tương tự tích vô hướng, tích có hướng trong không gian hai chiều cũng có thể được định nghĩa bằng hai cách:

  • Theo đại số, tích có hướng giữa hai vector u(x1,y1)\vec{u}(x_1, y_1)v(x2,y2)\vec{v}(x_2, y_2) được định nghĩa bằng công thức:

  • Theo hình học, tích có hướng giữa hai vector u(x1,y1)\vec{u}(x_1, y_1)v(x2,y2)\vec{v}(x_2, y_2) được định nghĩa bằng công thức: u×v=uvsin(θ);\vec{u} \times \vec{v} = |\vec{u}| \cdot |\vec{v}| \cdot \sin(\theta); với θ\theta là góc hợp bởi hai vector tính từ u\vec{u} tới v\vec{v}ngược chiều kim đồng hồ (góc này được gọi là góc định hướng). Ta lại biết rằng, với một góc α\alpha thỏa mãn 0<α<1800^{\circ} < \alpha < 180^{\circ} thì sin(α)>0\sin(\alpha) > 0 nên nếu θ<180\theta < 180^{\circ} thì tích có hướng dương, ngược lại tích có hướng âm (hoặc có thể xét theo quy tắc: Nếu góc định hướng có chiều ngược kim đồng hồ thì nó mang dấu dương, ngược lại mang dấu âm).

    Ta cũng suy ra được công thức tính sin\sin của góc định hướng giữa hai vector u(x1,y1)\vec{u}(x_1, y_1)v(x2,y2)\vec{v}(x_2, y_2) như sau:

    sinθ=u×vuv=x1y1x2y2(x12+y12)(x22+y22)\sin{\theta} = \frac{\vec{u} \times \vec{v}}{|\vec{u}|\cdot\vec{v}} = \frac{x_1y_1 - x_2y_2}{\sqrt{(x_1^2 + y_1^2)(x_2^2 + y_2^2)}}

Ví dụ: Tính tích có hướng của hai vector u(5,12)\vec{u}(5, 12)v(6,8)\vec{v}(-6, 8):

Tính bằng đại số:

Tính bằng hình học:

Ứng dụng quan trọng thứ nhất của tích có hướng trong hình học phẳng là a×b×sin(θ)\vec{a} \times \vec{b} \times \sin(\theta) bằng với diện tích của hình bình hành có hai cạnh bên là a\vec{a}b\vec{b}:

Do đó, diện tích của một tam giác còn bằng một nửa giá trị tuyệt đối của tích có hướng với hai vector thành phần là hai cạnh của tam giác (*).

Một ứng dụng khác của tích có hướng là khảo sát chiều: Giả sử ta đi từ điểm AA sang điểm BB theo đường thằng và đi tiếp sang điểm CC theo đường thẳng, khi đó:

  • Tích có hướng AB×BC\overrightarrow{AB} \times \overrightarrow{BC} sẽ là số dương nếu như chỗ rẽ tại BB là "rẽ trái" (bẻ góc ngược chiều kim đồng hồ). Đây gọi là công thức CCW.
  • Tích có hướng AB×BC\overrightarrow{AB} \times \overrightarrow{BC} sẽ là số âm nếu như chỗ rẽ tại BB là "rẽ phải" (bẻ góc ngược thuận kim đồng hồ). Đây gọi là công thức CW.
  • Tích có hướng AB×BC\overrightarrow{AB} \times \overrightarrow{BC} sẽ bằng 00 nếu như ba điểm A,B,CA, B, C thẳng hàng.
<center>

Rẽ trái và rẽ phải

</center>

Các công thức nói trên tưởng chừng như vô dụng, nhưng chúng sẽ rất có ý nghĩa trong một số thuật toán cụ thể, chẳng hạn như thuật toán tìm Bao lồi (sẽ nói tới ở một chuyên đề khác).

5. Khoảng cách giữa các điểm và đường thẳng

Tìm khoảng cách giữa hai điểm trên mặt phẳng hai chiều

Đây là công thức rất quan trọng, thường xuyên xuất hiện trong các bài toán về hình học. Để tính khoảng cách giữa hai điểm A(x1,y1)A(x_1, y_1)B(x2,y2)B(x_2, y_2) trên mặt phẳng tọa độ, ta sử dụng công thức sau:

d(A,B)=(x1x2)2+(y1y2)2d(A, B) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}

Công thức trên còn được gọi là công thức khoảng cách Euclid, để phân biệt với công thức khoảng cách Mahattan.

Tìm khoảng cách giữa một điểm và một đường thẳng trên mặt phẳng hai chiều

Tìm khoảng cách giữa điểm và đường thẳng cũng là một vấn đề rất thường gặp trong các bài toán hình học.

Hình 1: Khoảng cách giữa điểm và đường thẳng

Lấy ví dụ, ta có ba điểm A,B,CA, B, C và cần tìm khoảng cách từ CC đến đường thẳng đi qua AABB. Bước đầu tiên, các bạn hãy tính hai vector AB\overrightarrow{AB}AC\overrightarrow{AC}. Sau đó, ta tính tích có hướng AB×AC,\overrightarrow{AB} \times \overrightarrow{AC}, lấy giá trị tuyệt đối của kết quả rồi chia cho ABAB. Kết quả thu được chính là khoảng cách cần tìm.

Chứng minh: Xét ΔABC,\Delta ABC, đặt hh là đường cao kẻ từ CC (khoảng cách từ CC tới ABAB) và đáy tương ứng là ABAB. Ta có công thức:

SΔABC=h.AB22SΔABC=h.AB(1)S_{\Delta ABC} = \frac{h.AB}{2} \Leftrightarrow 2S_{\Delta ABC} = h.AB (1)

Mà theo nhận định (*) ở mục 3.5, thì diện tích một tam giác bằng một nửa giá trị tuyệt đối của tích có hướng với hai vector thành phần là hai cạnh của tam giác, tức là:

2SΔABC=AB×AC (2)2S_{\Delta ABC} = |\overrightarrow{AB} \times \overrightarrow{AC}| \ (2)

Từ (1)(1)(2)(2) suy ra:

h=AB×ACABh = \frac{|\overrightarrow{AB} \times \overrightarrow{AC}|}{AB}

Nhưng nếu ta chỉ muốn tìm khoảng cách từ đoạn thẳng ABAB tới điểm CC thay vì cả đường thẳng thì sao? Trong trường hợp này, ta cần tìm khoảng cách từ CC tới điểm gần nó nhất trên đoạn thẳng AB,AB, mà điểm gần nhất có thể là một trong hai đầu mút của đoạn thẳng thay vì là một điểm nào đó trên đường thẳng. Trong hình 1 ở trên, điểm gần CC nhất trên đường thẳng ABAB không nằm giữa AABB mà là nằm tại BB.

Có vài cách khác nhau để xử lý trường hợp này, một trong số đó là tích vô hướng. Đầu tiên, kiểm tra xem điểm gần nhất trên đường thẳng ABAB có ra khỏi BB hay không bằng cách tính BABC\overrightarrow{BA} \cdot \overrightarrow{BC}. Nếu tích này âm, nghĩa là góc giữa BA\overrightarrow{BA}BC\overrightarrow{BC} là góc tù (do với góc α\alpha thỏa mãn 90°<α<270°90°< \alpha <270° thì cos(α)<0\cos(α)<0), do đó điểm gần CC nhất trên đoạn ABAB sẽ là BB.

Tương tự, nếu ABAC\overrightarrow{AB} \cdot \overrightarrow{AC}, điểm gần CC nhất là AA. Nếu cả hai tích vô hướng đều lớn hơn hoặc bằng 0,0, thì điểm gần CC nhất sẽ nằm giữa AABB.

Cài đặt

// Struct lưu vector và định nghĩa một số phép toán: Tích chấm, tích chéo, độ dài.
struct Vector
{
    double x, y;
    
    Vector(double _x, double _y)
    {
        x = _x;
        y = _y;
    }
	
    double dot_product(const Vector &other)
    {
        return x * other.x + y * other.y;
    }
	
    double cross_product(const Vector &other)
    {
        return x * other.y - y * other.x;
    }
	
    double length() const
    {
        return sqrt(x * x + y * y);
    }
}

typedef Vector Point;

// Tính vector AB = B - A.
Vector operator - (const Point &B, const Point &A) 
{ 
    return Vector(B.x - A.x, B.y - A.y);
}

// Nếu is_segment = true tức là AB là một đoạn thẳng thay vì đường thẳng.
double line_point_dist(const Point &A, const Point &B, const Point &C, bool is_segment) 
{
    double dist = abs((B - A).cross_product(C - A)) / (A - B).length();
	
    if (is_segment) 
    {
        double dot1 = (A - B).dot_product(C - B);
        if (dot1 < 0) 
            return (B - C).length();
			
        double dot2 = (B - A).dot_product(C - A);
        if (dot2 < 0) 
            return (A - C).length();
    }
	
    return dist;
}

III. Luyện tập

Các bạn có thể tham khảo contest Codeforces Gym 100168, một contest gồm toàn các bài tập liên quan tới hình học (mặc dù tiếng Nga nhưng rất ngắn gọn nên có thể dùng Google Dịch được ngay).

Một số bài tập có liên quan đến nội dung bài viết này có thể tóm tắt như sau:

  • Codeforces Gym - 100168L: Tính độ dài (độ lớn) vector.
  • Codeforces Gym - 100168D: Tính diện tích tam giác.
  • CSES - Polygon Area: tính diện tích đa giác Codeforces Gym - 100168F: Tính khoảng cách từ 1 điểm đến một đường thẳng có dạng ax+by+c=0ax+by+c=0.
  • Codeforces Gym - 100168G: Tính khoảng cách từ một điểm đến một đường thẳng đi qua hai điểm
  • Codeforces Gym - 100168H: Tính khoảng cách từ một điểm đến một tia.
  • Codeforces Gym - 100168I: Tính khoảng cách từ một điểm đến một đoạn thẳng.

IV. Tài liệu tham khảo


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.