Hình học 2D cơ bản
Chúng ta sẽ giới hạn phạm vi các bài toán hình học cần giải quyết trong mặt phẳng hai chiều, như vậy sẽ liên quan đến các kiến thức cơ bản của hình học tính toán 2D. Khi nghiên cứu, thường đặt hình trong hệ tọa độ vuông góc hoặc hệ tọa độ cực, như vậy sẽ thuận tiện hơn rất nhiều khi giải quyết vấn đề.
Kiến thức nền tảng
Nếu bạn chưa nắm rõ:
- Kiến thức hình học cơ bản
- Hệ tọa độ vuông góc trong mặt phẳng
- Vector (bao gồm cả tích vector)
- Hệ tọa độ cực và tọa độ cực
Hãy đọc trước Vector và Tọa độ cực.
Biểu diễn hình học
Điểm
Trong hệ tọa độ vuông góc, điểm được biểu diễn bằng hoành độ và tung độ, ví dụ điểm \((5,2)\), điểm \((-1,0)\),... Vì tọa độ là cặp số có thứ tự, nên có thể dùng std::pair để lưu trữ, hoặc định nghĩa struct riêng.
Trong hệ tọa độ cực, điểm được biểu diễn bằng bán kính và góc cực, cách lưu trữ cũng tương tự như hệ tọa độ vuông góc.
Vector
Vì biểu diễn tọa độ của vector giống như điểm, nên chỉ cần lưu trữ như điểm.
Trong hệ tọa độ cực cũng tương tự.
Đường thẳng
Việc biểu diễn đường thẳng trong hệ tọa độ cực khá phức tạp, nên ở đây chỉ bàn về trường hợp trong hệ tọa độ vuông góc.
Đường thẳng và tia
Khi giải toán học, ta thường dùng phương trình để biểu diễn đường thẳng. Có nhiều dạng phương trình như tổng quát \(Ax+By+C=0\), dạng góc \(y=kx+b\), dạng đoạn chắn \(\dfrac{x}{a}+\dfrac{y}{b}=1\), v.v... Tuy nhiên, khi giải các bài toán hình học tính toán, dùng phương trình sẽ làm tăng độ phức tạp.
Trong hình học tính toán, thường dùng một điểm trên đường thẳng và vector chỉ phương để biểu diễn một đường thẳng; với tia, dùng điểm đầu và vector chỉ phương. Vector chỉ phương là một vector không bằng 0 và song song với đường thẳng, thường lấy là vector đơn vị. Với một đường thẳng, có hai vector đơn vị song song, chọn cái nào tùy bài toán; với tia, vector chỉ phương thường cùng hướng với tia.
Đoạn thẳng
Chỉ cần lưu hai đầu mút của đoạn thẳng.
Đa giác
Dùng mảng lưu các đỉnh của đa giác theo một thứ tự nhất định. Với đa giác đơn giản, thường lưu theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ.
Đặc biệt, với hình chữ nhật mà các cạnh song song với trục tọa độ, chỉ cần lưu hai đỉnh đối diện.
Đường cong đặc biệt
Một số đường cong đặc biệt như đồ thị hàm số thường lưu bằng phương trình. Với đường tròn, chỉ cần lưu tâm và bán kính.
Công thức cơ bản
Định lý sin
Trong tam giác \(\triangle \text{ABC}\), nếu các cạnh đối diện các góc \(A,B,C\) lần lượt là \(a,b,c\), thì:
Trong đó \(R\) là bán kính đường tròn ngoại tiếp tam giác.
Định lý cos
Trong tam giác \(\triangle \text{ABC}\), nếu các cạnh đối diện các góc \(A,B,C\) lần lượt là \(a,b,c\), thì:
Chứng minh các công thức trên xin được bỏ qua, đều là kiến thức SGK Toán lớp 10-11.
Các thao tác cơ bản
Xác định vị trí điểm so với đường thẳng
Giả sử ta có điểm \(P\) trên đường thẳng và vector chỉ phương \(\mathbf v\), muốn biết điểm \(Q\) nằm ở phía nào của đường thẳng. "Phía nào" ở đây là so với hướng của vector chỉ phương, tức là ta đứng nhìn theo hướng vector chỉ phương.
Ta dùng tính chất của tích vector, tính \(\mathbf v\times \overrightarrow {PQ}\). Theo quy tắc bàn tay phải, nếu tích vector âm thì \(Q\) ở bên phải đường thẳng; nếu bằng \(0\) thì \(Q\) nằm trên đường thẳng; nếu dương thì \(Q\) ở bên trái.
Thí nghiệm loại trừ nhanh và kiểm tra giao nhau (cross test)
Giả sử muốn kiểm tra hai đoạn thẳng có cắt nhau không.
Đầu tiên xét các trường hợp đặc biệt. Nếu hai đoạn thẳng song song thì không thể cắt nhau, kiểm tra bằng cách so sánh hệ số góc.
Nếu hai đoạn thẳng trùng hoặc một phần trùng, hoặc giao nhau tại đầu mút, chỉ cần kiểm tra ba điểm thẳng hàng.
Có những trường hợp rõ ràng là không cắt nhau, gọi là "hai đoạn thẳng quá xa nhau". Định nghĩa "vùng của một đoạn thẳng" là hình chữ nhật có các cạnh song song với trục tọa độ, lấy đoạn thẳng làm đường chéo. Nếu hai đoạn thẳng không có vùng giao nhau, chắc chắn không cắt nhau.
Ví dụ hai đoạn thẳng:
Vùng chiếm dụng của chúng:
Như vậy có thể nhanh chóng xác định hai đoạn thẳng không cắt nhau.
Đây gọi là thí nghiệm loại trừ nhanh. Trường hợp trên gọi là không qua thí nghiệm loại trừ nhanh.
Không qua thí nghiệm loại trừ nhanh là điều kiện đủ nhưng không cần thiết để hai đoạn thẳng không giao nhau, cần kiểm tra thêm.
Vì nếu hai đoạn thẳng \(a,b\) cắt nhau, thì hai đầu mút của \(b\) phải nằm ở hai phía khác nhau của đường thẳng chứa \(a\); tương tự với \(a\). Ta kiểm tra vị trí hai đầu mút của một đoạn so với đường thẳng chứa đoạn kia, nếu khác phía thì hai đoạn cắt nhau, ngược lại thì không. Vị trí điểm so với đường thẳng đã nói ở trên.
Đây gọi là kiểm tra giao nhau (cross test). Nếu hai đoạn \(a,b\) có hai đầu mút nằm ở hai phía khác nhau của đường thẳng chứa đoạn kia, và ngược lại, thì hai đoạn qua kiểm tra giao nhau, tức là cắt nhau.
Lưu ý: nếu hai đoạn thẳng đồng phẳng nhưng không cắt nhau cũng có thể qua kiểm tra giao nhau, nên cần kết hợp với thí nghiệm loại trừ nhanh.
Kiểm tra điểm nằm trong đa giác
Trong hình học tính toán, đây gọi là bài toán PIP (Point in Polygon), đã có nhiều phương pháp giải quyết, dưới đây là hai phương pháp phổ biến.
Thuật toán chiếu tia (Ray casting algorithm)
Xem ý tưởng gốc tại đây.
Đầu tiên xét các trường hợp đặc biệt, như "điểm này quá xa đa giác". Tương tự kiểm tra hai đoạn thẳng cắt nhau, xét hình chữ nhật nhỏ nhất bao toàn bộ đa giác, nếu điểm không nằm trong hình chữ nhật này thì chắc chắn không nằm trong đa giác. Hình chữ nhật này dễ tìm, chỉ cần lấy min/max hoành độ và tung độ của các đỉnh đa giác, ghép lại thành bốn đỉnh.
Còn trường hợp điểm nằm trên cạnh hoặc đỉnh đa giác, cũng dễ kiểm tra.
Tiếp theo, từ điểm cần kiểm tra, vẽ một tia bất kỳ. Nếu tia này cắt đa giác tại số lẻ giao điểm, thì điểm nằm trong đa giác; nếu số chẵn thì nằm ngoài. Gọi là quy tắc chẵn lẻ (Even-odd rule).
Theo định lý đường Jordan, mỗi lần tia cắt một cạnh đa giác, trạng thái trong/ngoài đa giác sẽ đổi, nên chỉ cần đếm số giao điểm.
Nên chọn tia có hệ số góc vô tỉ để tránh trùng với cạnh đa giác.
Trong code gốc, dùng đỉnh cuối của đa giác làm một điểm trên tia, khi đếm giao điểm, nếu tia đi qua cạnh hoặc đỉnh đa giác thì quy ước cùng phía, dùng kiểm tra giao nhau.
Lưu ý
Thuật toán chiếu tia chỉ áp dụng cho đa giác đơn giản. Với đa giác tự cắt, định lý Jordan không áp dụng, nên không xác định được.
Thuật toán số vòng quay (Winding number algorithm)
Số vòng quay là khái niệm toán học, là số lần đường cong kín đi quanh điểm đó theo chiều ngược kim đồng hồ. Nếu số vòng quay bằng \(0\), điểm nằm ngoài đa giác.
Cách tính: nối điểm cần kiểm tra với tất cả các đỉnh đa giác, tính tổng các góc giữa các cạnh liên tiếp (có hướng). Nếu tổng góc là \(0\), điểm nằm ngoài; ngược lại nằm trong.
Tìm giao điểm hai đường thẳng
Đầu tiên kiểm tra hai đường thẳng có cắt nhau không, chỉ cần kiểm tra vector chỉ phương có song song không. Nếu song song thì không có giao điểm; nếu trùng nhau thì vô số giao điểm.
Nếu hai đường thẳng cắt nhau, chỉ có một giao điểm. Đã lưu một điểm trên mỗi đường và vector chỉ phương, chỉ cần tìm khoảng cách từ điểm đó đến giao điểm, rồi dịch chuyển theo vector chỉ phương.
Dùng định lý sin để tính khoảng cách, có thể dùng tích vector để xây dựng định lý sin.
Từ hình vẽ, \(|\mathbf a\times \mathbf b|=|\mathbf a||\mathbf b|\sin \beta\), \(|\mathbf u\times \mathbf b|=|\mathbf u||\mathbf b|\sin \theta\).
Chia hai vế:
Có thể thấy, \(\left|\dfrac{|\mathbf u|\sin \theta}{\sin \beta}\right|=l\). Nếu giá trị dương thì dịch theo hướng \(\mathbf a\), ngược lại thì ngược hướng.
Nhân \(T\) với \(\mathbf a\) sẽ tự động ra vector đơn vị.
Chỉ cần lấy điểm \(B\) trừ \(T\mathbf a\) là ra giao điểm.
Tính chu vi và diện tích đa giác bất kỳ
Tính chu vi đa giác bất kỳ
Cộng trực tiếp các cạnh, đơn giản.
Tính diện tích đa giác bất kỳ
Dùng ý nghĩa hình học của tích vector, có thể tính diện tích.
Đánh số các đỉnh đa giác ngược chiều kim đồng hồ là \(p_1,p_2,\cdots ,p_n\), chọn một điểm phụ \(O\), gọi \(\mathbf v_i=p_i-O\), diện tích \(S\) là:
Các bài toán liên quan đường tròn và đường thẳng
Tìm giao điểm đường thẳng và đường tròn
Đầu tiên kiểm tra vị trí tương đối. Nếu ngoài thì không có giao điểm, nếu tiếp xúc thì dùng tiếp tuyến và bán kính, chuyển thành bài toán giao hai đường thẳng.
Nếu có hai giao điểm, dùng định lý Pythagoras để tìm trung điểm, rồi dịch theo hướng đường thẳng một đoạn bằng nửa dây.
Tìm giao điểm hai đường tròn
Đầu tiên kiểm tra vị trí tương đối, nếu ngoài hoặc trong thì không có giao điểm, nếu tiếp xúc thì nối tâm hai đường tròn, dùng bán kính tính khoảng cách, rồi dịch tâm theo hướng đó.
Nếu hai đường tròn cắt nhau, có hai giao điểm đối xứng qua đường nối tâm. Chỉ cần tìm một giao điểm, giao điểm còn lại làm tương tự.
Nối tâm một đường tròn với giao điểm, tính góc giữa nối tâm và bán kính, quay vector nối tâm một góc đó, rồi dịch tâm theo hướng đó một đoạn bằng bán kính.
Sắp xếp theo góc cực
Các bài toán dạng này thường cần chọn một điểm gốc, tính tọa độ cực của các điểm còn lại, rồi sắp xếp theo góc cực.
「JOISC 2014 Day4」Hai chòm sao của hai người
Trong mặt phẳng có \(n\) điểm, mỗi điểm có một trong ba màu. Đếm số cặp tam giác ba màu không giao nhau. \(6\le n\le 3000\).
Hướng dẫn
Nếu hai tam giác không giao nhau, chắc chắn có thể vẽ hai tiếp tuyến chung trong, nếu giao nhau hoặc chứa nhau thì không vẽ được tiếp tuyến chung. Tiếp tuyến chung của tam giác tương tự như tiếp tuyến chung của hai đường tròn.
Chọn một điểm gốc \(O\), lấy \(O\) làm cực, qua \(O\) và song song trục \(x\) làm trục cực, xây dựng hệ tọa độ cực, sắp xếp các điểm còn lại theo góc cực tăng dần.
Đếm số điểm mỗi màu ở phía trên và dưới trục cực.
Với mỗi điểm \(P\), ban đầu tiếp tuyến là trục cực. Đếm số trường hợp. Chắc chắn có một tiếp tuyến qua \(O\) và \(P\). Vì tiếp tuyến không cắt tam giác, một bên chọn điểm phía trên, bên kia chọn điểm phía dưới. Dùng nguyên lý nhân để đếm số trường hợp.
Sau khi đếm, xoay tiếp tuyến, điểm \(P\) sẽ đổi vị trí so với tiếp tuyến, các điểm khác không đổi, chỉ cần cập nhật thông tin vị trí của \(P\). Như vậy, mỗi cặp tam giác được đếm 4 lần, nên chia kết quả cho 4.
Độ phức tạp: chọn một điểm gốc, với mỗi điểm gốc sắp xếp các điểm còn lại rồi đếm tuyến tính, tổng \(O(n^2\log n)\).
Lưu ý khi lập trình
Vì hình học tính toán thường dùng số thực double, nên dễ gặp vấn đề về sai số và tốc độ.
Một số bài toán, ví dụ tính diện tích tam giác có tọa độ nguyên, có thể dùng số nguyên để tránh sai số.
Đọc và tính toán số thực chậm hơn số nguyên, nên cần chú ý đến hằng số thời gian trong chương trình.
Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply